17
$\begingroup$

For IEEE, the single representation is 1-bit sign, 8-bit exponent and 23-bit mantissa. This means that at each exponent value, you can test all 2^23-1 (roughly 9mil cases) possible combination of binary representation (give or take). Then you do it for all exponent value (255 values), and you can basically cover all floating points represented by IEEE.

However, for double precision, such approach is not really viable. With 52-bit mantissa, at each value of exponent you would need to test 2^52-1 binary combinations (which is roughly 4 million bilion, ~E15).

This seems to suggest that you need some randomizing scheme to test that your arithmetic implementation is bounded with high probability. But do we know which scheme to use? Would it also be beneficial to consider how floating point numbers are distributed (i.e. more collocated around certain value/zero)?

$\endgroup$
8
  • 1
    $\begingroup$ For special functions I like ULP plots: blogs.mathworks.com/cleve/2017/01/23/… $\endgroup$
    – user14717
    Nov 29, 2021 at 18:18
  • 1
    $\begingroup$ boost.org/doc/libs/master/libs/math/doc/html/math_toolkit/… $\endgroup$
    – user14717
    Nov 29, 2021 at 18:19
  • 1
    $\begingroup$ Obligatory xkcd. $\endgroup$
    – wizzwizz4
    Nov 29, 2021 at 21:01
  • 1
    $\begingroup$ Intel's famous floating point division bug on the Pentium shows the difficulty of comprehensively testing floating point. en.wikipedia.org/wiki/Pentium_FDIV_bug $\endgroup$ Nov 30, 2021 at 0:59
  • 3
    $\begingroup$ @wizzwizz4 Intel docs stated the ulp error for the trig instructions under the provision that π = machine PI, and under that provision, error bounds were stated correctly. That was not spelled out explicitly, and can rightfully be considered a misleading documentation bug. Intel's testing for the error bounds would have used a 66-bit PI as well. I worked on and with x87 FPUs for three Intel competitors and used the same 66-bit PI in my work, and also made test programs based on it. The only x87 design that deviated from this was (to my knowledge) the AMD K5, which used a 256-bit PI instead. $\endgroup$
    – njuffa
    Dec 2, 2021 at 0:27

4 Answers 4

20
$\begingroup$

You should test transition points.

Floating-point numbers have several distinct "ranges":

  • Standard/Normal arithmetic
  • Subnormal arithmetic
  • Infinite arithmetic
  • NaN arithmetic
  • Zero arithmetic

For instance, if I add any normal number to an infinite number, I need to get an infinite number back. If I add two large enough subnormals, I should get a normal number. Any math done on a NaN makes a NaN. Adding two large normals might get me an Inf.

So my testing strategy would be:

  • Randomly check a few instances of math where the answer stays within a class (note that operations which affect the exponent can be distinguished from changes that affect only the mantissa). If 1+2=3, then probably I've gotten 2+3=5 correct as well.
  • Spend much more time/effort checking math at the boundaries of classes, since these represent special cases.

I'd probably write a few unit tests to explore specific cases I understand well, but then use property-based testing to be more thorough. This works especially well with things like zero, inf, and NaN.

Finally, I'd measure code coverage to ensure that the test suite is hitting the entirety of the library.

Pre-existing test suites include:

  • Kahan's paranoia
  • Schryer's "A Test of a Computer’s Floating-Point Arithmetic Unit" (I haven't found source code for this)
$\endgroup$
4
  • 5
    $\begingroup$ Good advice. In addition, N. L. Schryer, "A Test of a Computer’s Floating-Point Arithmetic Unit." Computing Science Technical Report No. 89, AT&T Bell Laboratories, February 4, 1981 describes pattern-based testing that is still relevant today. For an operation like square root, one would want to perform an exhaustive test across two adjacent binades, which is possible with a small cluster of machines (rule of thumb using today's hardware: up to 2**48 test vectors per machine). For random test vectors it is essential to use a high-quality PRNG, e.g. Mersenne Twister. $\endgroup$
    – njuffa
    Nov 29, 2021 at 1:46
  • 1
    $\begingroup$ Regarding existing test suites: Test vectors for the following paper used to be available online, but I cannot locate a copy right now: Brigitte Verdonk, Annie Cuyt, and Dennis Verschaeren, "A precision-and range-independent tool for testing floating-point arithmetic I: basic operations, square root, and remainder." ACM Transactions on Mathematical Software, Vol. 27, No. 1 (2001): pp. 92-118. The same applies to the test vectors accompanying Jerome T. Coonen, "Contributions to a Proposed Standard for Binary Floating-Point Arithmetic." PhD dissertation, Univ. of California, Berkeley, 1984. $\endgroup$
    – njuffa
    Nov 29, 2021 at 4:41
  • 2
    $\begingroup$ "Any math done on a NaN makes a NaN". Except for pow, maxNum and minNum $\endgroup$ Nov 29, 2021 at 12:17
  • 2
    $\begingroup$ @Richard : Ooooooh. Thanks for the tip, the hypothesis package looks awesome. It's a bit depressing how fast it found edge-cases on a legacy project I'm working on, but it will help us a lot. $\endgroup$ Nov 30, 2021 at 9:00
8
$\begingroup$

An online search shows various floating point test suites supporting double precision (64-bit IEEE 754) that are more comprehensive than randomized testing. I have not tested any of these myself. Examples:

$\endgroup$
1
  • 1
    $\begingroup$ An older testsuite is UCBtest, which is available from Netlib. I have not used it and the code is likely quite "dusty" now, as it dates to the mid 1990s. $\endgroup$
    – njuffa
    Nov 30, 2021 at 5:57
6
$\begingroup$

A pretty classic method is to test identities. For example, pick an $x$, calculate $\sin^2x+\cos^2 x$ using Taylor series for the trig functions, and check that the result equals 1 to within rounding errors. This has the advantage that you don't have to compare against someone else's floating point implementation that you hope is correct. Similar examples would be $\tan(\tan^{-1} x)$, or to calculate $y=1/(1-x)$ using the geometric series, then do $1-1/y$ using division and subtraction.

$\endgroup$
1
  • 2
    $\begingroup$ At this point, testing against 2048 bit MPFR is pretty safe. $\endgroup$ Nov 29, 2021 at 19:38
3
$\begingroup$

One under-rated strategy is to just test with a lot of random numbers. Specifically, I've found that reinterpreting a random 64 bit integer as floating point gives a very good distribution since it generates a lot of numbers with large and small exponents. Targeted tests for things like signed zeros, NaNs, Infs and subnormals are definitely necessary, but just testing 2^32 random values shouldn't be underestimated.

$\endgroup$
3
  • 5
    $\begingroup$ From long-time personal experience with design, implementation, and test of floating-point units and math libraries I can state that testing with lots of random test vectors is inadequate, and it usefulness is therefore, one might say, overestimated. It has utility as a quick "smoke" test on account of its simplicity. $\endgroup$
    – njuffa
    Nov 29, 2021 at 18:59
  • 1
    $\begingroup$ oh yeah, it definitely can miss things, but I've found lots of cases where a randomized test found an edge-case that I hadn't thought of as being an edge case. for example, a number that is not quite subnormal can often be an edge case that more targeted testing will often miss. $\endgroup$ Nov 29, 2021 at 19:42
  • 4
    $\begingroup$ Testing with random test vectors, even when using a lot of them and generating them with a high-quality PRNG, misses lots of edge cases. It is good for a quick test "is the implementation generally functional". I have run experiments for bugs found by code inspection/review, and they would escape testing with tons of random test vectors, but were quite easily found with pattern-based tests and/or transition-point testing, for example. $\endgroup$
    – njuffa
    Nov 29, 2021 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.