How to Test for Numeric Errors in Floating- and Fixed-Point Algorithms

Have you ever been burned by flawed numerics? A more efficient version of an algorithm looked great, but flaws were discovered very late, causing lots of wasted time. Imagine the advantages if counterexamples proving the flaws could have been found in the first few minutes.

This video will show you how to quickly identify numeric flaws in your algorithms. As a first example, let's consider the goal of dropping the four fractional bits from a fixed point number and rounding to the nearest integer. For ties, the goal is to round up. So 9.5 would round up to 10.

Inspired by a well-known trick for rounding floating point values, an efficient looking algorithm is to add 8 and then shift right by four bits. To see if this algorithm is correct, let's experimentally stress test it using rich numeric input values. The first step in the experiment is to provide input attributes using data specification. The second step is to create numerically rich test inputs using data generator.

The last two steps are standard testing practice, get the output of the golden baseline and of the new algorithm, then compare them. When we run this script, it instantly produces counter examples that prove the algorithm is flawed. The flaw in the algorithm is that adding 8 can cause overflow for the 8 biggest input values. Because the overflow bit is lost, the subsequent shift right will produce just zero, but it should produce 2 to the power 28.

Overflows are an extremely common source of flaws. The data generator tool ensures that test inputs cover all extreme input combinations. Now let's consider two equations that are equivalent in the Ideal world of symbolic math. But we want to know if they are also equivalent in the world of double precision floating point math.

Let's run an experiment. This script is just like the first, except that floating point double is used and there are two inputs instead of one. Running the script produces counter examples proving many categories of flaws. The data generator exposes these flaws because it had the smarts to test messy combinations like NAND mixed with infinity, and combinations of extreme finite values that might overflow to infinity.

When applying an algorithm to an engineering application, the inputs often have limited ranges. In those cases, counterexamples involving non-finites or huge values are irrelevant noise. Data specification and data generator make it easy to apply limits and focus your testing. Let's repeat the last experiment, but with single precision inputs in the interval from minus 10 to plus 10.

With two very simple changes, we can run the script. It again produces many counter examples. The data generator has the smarts to include values that push the input data types to their precision extremes, thus exposing flaws as shown here. Let's run one last flaw detection experiment but with a twist.

We'll step up our game by combining the power of data generator with the excellent unit testing framework provided with MATLAB. The goal of the algorithm is to losslessly compute the sum of all elements in an integer matrix. To support matrix inputs is a simple matter of providing dimensions information to data specification.

Now let's go to the command line and run the unit test. The output shows that the test has failed. And that there are lots of points with numeric flaws. Now let's try to see where the bug is. In the algorithm under test, we see a lot of indexing code and every developer knows that it's all too easy to mess up indexing. And sure enough, line 8 has an indexing flaw. Let's correct that and rerun.

We see that the regression test is now passing. One of data generator's strengths is providing rich combinations across inputs and dimensions. These rich combinations are great at exposing indexing flaws. Data generator is designed to be fully flexible and supports just about any input combination.

But combinatoric explosion can easily get out of hand, so the dimensions and number of inputs must be kept modest in practice. Data generator is available with fixed point designer as a release R 2019 B. At the MathWorks, we've used an internal version of data generator for over a decade. That long experience has proven data generator to be highly effective at finding flaws. I hope data generator will prove beneficial to your work, too. Thanks for watching.