7 ms·

There Are Only Four Billion Floats–So Test Them All (2014)

252 points by albrewer 4y ago

pfdietz 4y ago
If you have a function that fails on a substantial number of inputs, random testing is probably a better idea, as it will find a failure in short expected time. An exhaustive testing harness may waste large amounts of time on a segment of the input space it hits first, if that initial segment is free of bugs. You can use random testing for exhaustive testing. On an input space of size N, you will cover that space completely in O(NlogN) tests on average, and you will include any single input in O(NlogN) trials with high probability.
- JoeAltmaier 4y ago
  For many things (like floating-point), saving the computer time is not any kind of goal. It's not gonna complain if you ask it to try all the things. Further, writing clever shotgun tests may actually take you longer than writing the simple loop. In which case it's wasting developer time too. Be very sure you need to do anything but exhaustive testing, before expending the time money and effort on it. That's my advice.
JoeAltmaier 4y ago
I remember being surprised when Intel released a Pentium chip that couldn't do floating point right. It would have been trivial to, I don't know, try dividing by 10 and then multiplying back and checking the answer. It couldn't do that. At the time I was thinking, their test group could have tested every single mantissa over several operations exhaustively. Why didn't they? What excuse could they have had? It was a computer; they feel no pain when asked to do laborious repetitive tasks.
- dragontamer 4y ago
  You'd think so, except no. Floating point operations are innately lossy and even non-associative, and non communative. A+B+C does not equal B+C+A in floating point.
  - JoeAltmaier 4y ago
    Which should happen in entirely predictable and orderly fashion. In fact, they should be testing for that too.
randrus 4y ago
Ages ago I was testing firmware that implemented RAID data handling for a DLT tape array. I constructed a test data set containing every four byte value - and found one value that exposed a bizarre bug that would reliably trigger over-temp logic and shut down the device under test. Fun times.
odo1242 4y ago
Aren't most float operations binary? You'd need to iterate over a 64-bit space to test those.
mattbillenstein 4y ago
Not often you can employ exhaustive testing, but it's useful in some cases. I did a project in college for a VLSI minor where we implemented a 16bit multiplier - after we got the chips back we were supposed to do scan testing, but I just wrote up a little program in an fpga, wired up my chip to test, and swept all the possible inputs verifying the output. I think I could only run this at 10MHz, and you had to shift in the operands one bit at a time, but it still only took on the order of an hour or two to complete. I also verified this setup by capturing some cycles on a logic analyzer - then pulled together a little awk script to turn a dump of that into the actual numbers I could check. Fun project.
- fsckboy 4y ago
  https://semiengineering.com/knowledge_centers/test/scan-test-2/ https://semiengineering.com/knowledge_centers/test/scan-test... scan test: it involves scanning test patterns into internal circuits within the device under test (DUT). The design’s flip-flops are modified to allow them to function as stimulus and observation points, or “scan cells” during test, while performing their intended functional role during normal operation.
zX41ZdbW 4y ago
I also did this when searching for a fast string-to-float conversion function for ClickHouse: https://github.com/ClickHouse/ClickHouse/blob/master/src/IO/readFloatText.h#L38 https://github.com/ClickHouse/ClickHouse/blob/master/src/IO/... - we create a table, insert all four billion floats there, and check our functions with SQL queries. Currently, the state-of-the-art library is https://github.com/lemire/fast_double_parser https://github.com/lemire/fast_double_parser, but we use a slightly worse (but more performant) routine. It is also interesting how to format floats in string in an efficient and user-friendly way. For this problem, we switched iteratively: strtod -> Google's Double Conversion -> Ryu (patched) -> Dragonbox. Currently, we use Dragonbox.
- ignoramous 4y ago
  > ...but we use a slightly worse (but more performant) routine. If it (dragonbox?) is more performant, why is it also worse?
  - wiredfool 4y ago
    Presumably it's not as accurate?
    - nickpeterson 4y ago
      Someone needs to make a bumper sticker for developers that says “fast and wrong”. I’d imagine non-programmers would buy more of them for other reasons…
      - Dylan16807 4y ago
        It's only on edge cases that floating point isn't mathematically wrong. And sometimes you don't mind an extra couple ULPs of drift.
      - fsckboy 4y ago
        fast and wrong? that's not a great bumper sticker to have when you're getting pulled over for speeding.
neilv 4y ago
I used a similar idea the other day, while implementing in Rust the CRC algorithm that a device required, but the vendor didn't document 100% clearly. Fortunately, I had some device vendor sample code in C (of varying quality and provenance), which I believed was probably correct, but I wasn't 100% certain which (if any) of numerous CRC standard variants it was actually implementing (so I couldn't just use an off-the-shelf Rust library). So, the fastest/best way to get a perfectly compatible Rust implementation seemed to be: 1. Write idiomatic Rust code to try to mimic the behavior of the C code. 2. Write some C code to generate a text file of exhaustive results from the known-good C implementation, for all possible inputs up to length N. 3. Exhaustively check the Rust implementation against that text file of inputs and outputs.
- AlotOfReading 4y ago
  For future reference there's an excellent tool for discovering the parameters of a CRC model with pairs of inputs and outputs called RevEng [0] (github copy: [1]). Once you have the parameters you can use the CRC crate [2] with a predefined CRC or a custom algorithm (highly unlikely). [0] https://reveng.sourceforge.io/ https://reveng.sourceforge.io/ [1] https://github.com/berney/reveng https://github.com/berney/reveng [2] https://crates.io/crates/crc https://crates.io/crates/crc
  - dragontamer 4y ago
    Going on this "Brute Force" discussion... the CRC Zoo is computing the minimal hamming distances of various CRCs. https://users.ece.cmu.edu/~koopman/crc/notes.html https://users.ece.cmu.edu/~koopman/crc/notes.html I don't know what algorithm they're using, but the idea that you can make a hamming distance calculation over all possible input sets these days is pretty spectacular.
  - neilv 4y ago
    Thanks! And another tool recommended to me: https://crccalc.com/ https://crccalc.com/
- dizhn 4y ago
  This sounds like things I heard in Rob Pike's presentation regarding how they wrote the go parser. I am no expert though.
bhaney 4y ago
> For very small numbers (less than about FLT_EPSILON * 0.25) adding 0.5 gives 0.5 exactly, and this then rounds to zero Is that not correct? Isn't it expected that very small numbers round to zero?
- zerocrates 4y ago
  This is in the context of the implementation of a ciel() function: a very small but still positive float should have a ciel() of 1. As said near this part, IEEE default rounding is round half to nearest even: 0.5 rounds to 0, the closest even integer, so if your addition of 0.5 to the argument to ciel() results in exactly 0.5, the result will incorrectly be 0 instead of 1.
- teraflop 4y ago
  The quote is talking about code that is supposed to find the ceiling of a number, and does so by adding 0.5 and then rounding to the nearest value (breaking ties by rounding towards even). If you have a very small but non-zero positive number, it gets rounded to 0.5 after the addition, and then the second rounding incorrectly rounds toward 0 instead of 1. The result is that you have a value x such that x > ceil(x), which shouldn't ever happen.
  - bhaney 4y ago
    > supposed to find the ceiling Oh duh. I somehow forgot that over the span of a few sentences. Thanks.
FpUser 4y ago
Silly me. As far as I can remember I've always used epsilon when comparing floats.
- eru 4y ago
  That's not a general solution. (And if you know what you are doing, you can also compare floats exactly in some circumstances.) But the article already mentions that.
  - kccqzy 4y ago
    Absolutely. I was once refactoring some badly written floating point code. To make sure I did not screw up, I want the result of the old and new code to be identical, since I know the refactoring should not change the float operations. (I also knew the code won't produce NaNs so == suffices.)
    - k0k0r0 4y ago
      Oh, yes... This. Had a project like this not long ago. NaNs almost killed me. The code used complex numbers, and you know who their userbase is. Anyway, exact floating point comparisons made all of this possible. In the process my coworker and found something we believed to be a bug with complex nans in some recent GCC versions, but where not smart enough to understand whether it is actually a bug or undefined behaviour in the standart. Anyway, we where so exhausted from the refactor, we didn't follow it up again.
  - FpUser 4y ago
    >"And if you know what you are doing" I knew what I was doing and that is why using Epsilon was the most reliable thing in my data processing algos.
    - eru 4y ago
      Hence the 'in some circumstances'.
chriswarbo 4y ago
4 billion inputs is a little on the extreme end, especially for slower interpreted languages, but it's always useful to look for functions which can be exhaustively tested; e.g. booleans and enums. I spotted a bug in a code review today, which was formatting dates with ordinal numbers, like "9th Feb". The ordinal logic only has to work for inputs 1 to 31, so I wrote an exhaustive test, which it failed by outputting "11st", "12nd" and "13rd" (due to only looking at the last digit)
- ben0x539 4y ago
  A while back for some videogame related data processing I ended up writing a "regular number to roman numeral" (or maybe the other way around) function in idk ruby or something. Not super convinced that I had gotten it right, I sat down to write a few tests, and then I realized I only needed it to work for numbers up to like 16. So I deleted the actual code, extended the table of test cases to cover 1 through 20 just in case, and just did a lookup in that.
  - giraffe_lady 4y ago
    true senior eng shit right there. https://i.imgflip.com/7alx6q.jpg https://i.imgflip.com/7alx6q.jpg
  - SnowHill9902 4y ago
    That’s actually the right solution to that specific problem.
  - travisjungroth 4y ago
    It happens. Writing the test puts you in the headspace of “assume the problem is already solved”, which is sometimes wildly more effective. There’s some story (that I hope an archivist can link) of someone writing a shell script to verify some giant program. Well, turns out the script could just _replace_ the program. Ran way faster. Sales wouldn’t have that, though.
  - JohnFen 4y ago
    Never underestimate the power of a properly placed lookup table.
archi42 4y ago
I loved this, since this resonates with my own experience. If the problem space is small enough, just test against a known good (but slower) implementation. With custom algorithms this can also be very interesting for the person writing the test: Their reference code needs to be correct beyond doubt, but can forfeit mostly every manual optimization. Also, for larger input spaces I like to do a nested for-loop over vectors of "interesting" values, plus add a large set of random values.
askvictor 4y ago
*Only 4 billion floats for 32-bit floats. When you get into double-precision floats, well, there's a lot more.
- quacker 4y ago
  Or I could be using two floats (adding or multiplying). Or three.
  - mr_toad 4y ago
    I was looking for this comment. In my experience functions that work with large multi-variate datasets cause TDD to fall flat on its face.
    - k0k0r0 4y ago
      No they don't. As far as Test Driven Development is commonly understood, at least. TDD would be extremely stupid if the idea would fall flat on its face when tests can not cover the whole input.
Taniwha 4y ago
Yup - I've just finished bringing up some FP hardware - you can't do all the 64-bit double space but you can do all the 32-bit single op instructions (converts, sqrt, etc) - but add/sub/multiple (32x32) are not doable But this is even more appropriate for 16-bit floats - you can realistically do all the adds/multiplies/etc, but maybe not the 3op multiply-accumulates
dragontamer 4y ago
A modern GPU with 5120 shaders and 2Ghz speeds can perform 2^32 ops in just 0.4 milliseconds. (AMD's Rx 6900xt. Yes, sub-millisecond times) The truth of todays computers is that the 32-bit space is a sub-second problem, possibly faster than human reaction speeds. Test the whole 32 bit space. It's cheap today. ------- Extrapolating a bit: the 2^48 space is 27 seconds per op. Maybe 100 ops are needed for your test code, so the 48-bit space (aka: 3x 16-bit input space) can be exhausted and tested in roughly 50 minutes.
- thechao 4y ago
  And a 64b sweep is ~21 days. As a HW guy who tests fp units... just saying. The real issue is that the verification code is much, much, slower.
  - dragontamer 4y ago
    > And a 64b sweep is ~21 days Per GPU. A consumer GPU at that (A100 is faster). 4x GPUs (the AMD 6900 XT) per node and maybe 10x nodes in a rack (4U per node, 42U cabinet) can do 64-bit sweep in half a day. > The real issue is that the verification code is much, much, slower. Isn't verification of 64b multipliers actually a 128-bit problem? (x * y == z, so you have 2x 64-bit numbers to work with). Also, I think they use BDDs, which although multiplication is exponential, its still small enough exponent that 128-bit BDDs fit on today's computers. So its not a brute force thing like discussed in this topic, but actually a very elegant data-structure (though with tons of complications, as is the nature of NP-complete and expspace problems).
    - thechao 4y ago
      It’s a lot easier to do formal verification… which is a fancy BDD, in many ways.
  - insanitybit 4y ago
    At that point I might just take the first 2^32 numbers, the last 2^32 numbers, and some range in between, and feel good about it.
throwawaymaths 4y ago
Until you have to test a binary operation. Or, god forbid you have to verify that fma works
supernova87a 4y ago
If I were to use a mental analogy with numerical methods that you get taught in grad school, isn't this kind of just a problem of identifying where poles are in your functions? If you're cycling through all possible numbers and seeing where the output might blow up or go pathological, you probably instead (to be efficient about it) test the far limits of the input number range, and then sample the internal space with an adaptive spacing to see where things are changing and whether it's about to go crazy somewhere. Like divide by zero, subtract 2 small numbers etc.? Or analyze the function to see where subtraction (or whatever operation is applicable here) might misbehave? Rather than spend all your compute equally sampling every possible number. I'm no expert but it seems to be the same type of problem.
- swatcoder 4y ago
  The insight is that 32-bit space is so cheap to exhaustively explore now that you don’t need to resort to possible misses through sampling or spend the effort to make and verify a smart way of sampling. Just brute force the darn thing and be done.
  - supernova87a 4y ago
    Ah, I see, for a test that you'll only run once or rarely, might as well!
    - DougBTX 4y ago
      No no no! That’s really the realisation they’re pushing at, this is fine for routine tests too! In this almost ten year old post the runtime was ~90s, which isn’t too painful. On some threads here, times on modern hardware are quoted as milliseconds or less. The takeaway might be more: spend time to optimise testing everything, rather than spending time optimising the selection of the subset to test. Massive caveat of course is that some search spaces are just big, but 32bit space shouldn’t be considered big any more.
      - supernova87a 4y ago
crazygringo 4y ago
If you're writing functions for basic mathematical operations, then sure. But how often is anyone doing that? If you design microprocessors, or programming languages (maybe), or numerical libraries. But hopefully if you do any of those, you already know to test every value against a reference algorithm. Is there anything in this post that is more generally applicable to the other 99.99% of developers? I'm trying to think of anything I've ever written where it would even be possible to test billions of input values, but there'd never be a reference to test it against.
- JohnFen 4y ago
  Or if you're coding for very small microcontrollers.
hansvm 4y ago
I recently had to implement floating point math. Can confirm that testing them all was by far the cheapest way to fix all the bugs and then verify the final solution was correct.
pvg 4y ago
Discussions from 2, 5 and 9 years ago: https://news.ycombinator.com/item?id=24745563 https://news.ycombinator.com/item?id=24745563 175 comments https://news.ycombinator.com/item?id=15252426 https://news.ycombinator.com/item?id=15252426 50 comments https://news.ycombinator.com/item?id=7135261 https://news.ycombinator.com/item?id=7135261 118 comments
exikyut 4y ago
Hmmmmm. Reading the aside In fact IEEE floating-point math is designed to, whenever practical, give the best possible answer (correctly rounded) Made me realize - there are not "just" four billion floats, there are four billion floats multiplied by however many levels of rounding you want to test against. The "ninety seconds" doesn't qualify if the test harness was multithreaded. If it wasn't, a modern >30 core box (maybe buried in CI somewhere) should be able to manage quite a few rounding levels without difficulty thankfully.

252 points by albrewer 4y ago

If you have a function that fails on a substantial number of inputs, random testing is probably a better idea, as it will find a failure in short expected time. An exhaustive testing harness may waste large amounts of time on a segment of the input space it hits first, if that initial segment is free of bugs. You can use random testing for exhaustive testing. On an input space of size N, you will cover that space completely in O(NlogN) tests on average, and you will include any single input in O(NlogN) trials with high probability.

JoeAltmaier 4y ago
For many things (like floating-point), saving the computer time is not any kind of goal. It's not gonna complain if you ask it to try all the things. Further, writing clever shotgun tests may actually take you longer than writing the simple loop. In which case it's wasting developer time too. Be very sure you need to do anything but exhaustive testing, before expending the time money and effort on it. That's my advice.

JoeAltmaier 4y ago

I remember being surprised when Intel released a Pentium chip that couldn't do floating point right. It would have been trivial to, I don't know, try dividing by 10 and then multiplying back and checking the answer. It couldn't do that. At the time I was thinking, their test group could have tested every single mantissa over several operations exhaustively. Why didn't they? What excuse could they have had? It was a computer; they feel no pain when asked to do laborious repetitive tasks.

dragontamer 4y ago
You'd think so, except no. Floating point operations are innately lossy and even non-associative, and non communative. A+B+C does not equal B+C+A in floating point.
- JoeAltmaier 4y ago
  Which should happen in entirely predictable and orderly fashion. In fact, they should be testing for that too.

randrus 4y ago

Ages ago I was testing firmware that implemented RAID data handling for a DLT tape array. I constructed a test data set containing every four byte value - and found one value that exposed a bizarre bug that would reliably trigger over-temp logic and shut down the device under test. Fun times.

odo1242 4y ago

Aren't most float operations binary? You'd need to iterate over a 64-bit space to test those.

mattbillenstein 4y ago

Not often you can employ exhaustive testing, but it's useful in some cases. I did a project in college for a VLSI minor where we implemented a 16bit multiplier - after we got the chips back we were supposed to do scan testing, but I just wrote up a little program in an fpga, wired up my chip to test, and swept all the possible inputs verifying the output. I think I could only run this at 10MHz, and you had to shift in the operands one bit at a time, but it still only took on the order of an hour or two to complete. I also verified this setup by capturing some cycles on a logic analyzer - then pulled together a little awk script to turn a dump of that into the actual numbers I could check. Fun project.

fsckboy 4y ago
https://semiengineering.com/knowledge_centers/test/scan-test-2/ https://semiengineering.com/knowledge_centers/test/scan-test... scan test: it involves scanning test patterns into internal circuits within the device under test (DUT). The design’s flip-flops are modified to allow them to function as stimulus and observation points, or “scan cells” during test, while performing their intended functional role during normal operation.

zX41ZdbW 4y ago

I also did this when searching for a fast string-to-float conversion function for ClickHouse: https://github.com/ClickHouse/ClickHouse/blob/master/src/IO/readFloatText.h#L38 https://github.com/ClickHouse/ClickHouse/blob/master/src/IO/... - we create a table, insert all four billion floats there, and check our functions with SQL queries. Currently, the state-of-the-art library is https://github.com/lemire/fast_double_parser https://github.com/lemire/fast_double_parser, but we use a slightly worse (but more performant) routine. It is also interesting how to format floats in string in an efficient and user-friendly way. For this problem, we switched iteratively: strtod -> Google's Double Conversion -> Ryu (patched) -> Dragonbox. Currently, we use Dragonbox.

ignoramous 4y ago
> ...but we use a slightly worse (but more performant) routine. If it (dragonbox?) is more performant, why is it also worse?
- wiredfool 4y ago
  Presumably it's not as accurate?
  - nickpeterson 4y ago
    Someone needs to make a bumper sticker for developers that says “fast and wrong”. I’d imagine non-programmers would buy more of them for other reasons…
    - Dylan16807 4y ago
      It's only on edge cases that floating point isn't mathematically wrong. And sometimes you don't mind an extra couple ULPs of drift.
    - fsckboy 4y ago
      fast and wrong? that's not a great bumper sticker to have when you're getting pulled over for speeding.

neilv 4y ago

I used a similar idea the other day, while implementing in Rust the CRC algorithm that a device required, but the vendor didn't document 100% clearly. Fortunately, I had some device vendor sample code in C (of varying quality and provenance), which I believed was probably correct, but I wasn't 100% certain which (if any) of numerous CRC standard variants it was actually implementing (so I couldn't just use an off-the-shelf Rust library). So, the fastest/best way to get a perfectly compatible Rust implementation seemed to be: 1. Write idiomatic Rust code to try to mimic the behavior of the C code. 2. Write some C code to generate a text file of exhaustive results from the known-good C implementation, for all possible inputs up to length N. 3. Exhaustively check the Rust implementation against that text file of inputs and outputs.

AlotOfReading 4y ago
For future reference there's an excellent tool for discovering the parameters of a CRC model with pairs of inputs and outputs called RevEng [0] (github copy: [1]). Once you have the parameters you can use the CRC crate [2] with a predefined CRC or a custom algorithm (highly unlikely). [0] https://reveng.sourceforge.io/ https://reveng.sourceforge.io/ [1] https://github.com/berney/reveng https://github.com/berney/reveng [2] https://crates.io/crates/crc https://crates.io/crates/crc
- dragontamer 4y ago
  Going on this "Brute Force" discussion... the CRC Zoo is computing the minimal hamming distances of various CRCs. https://users.ece.cmu.edu/~koopman/crc/notes.html https://users.ece.cmu.edu/~koopman/crc/notes.html I don't know what algorithm they're using, but the idea that you can make a hamming distance calculation over all possible input sets these days is pretty spectacular.
- neilv 4y ago
  Thanks! And another tool recommended to me: https://crccalc.com/ https://crccalc.com/
dizhn 4y ago
This sounds like things I heard in Rob Pike's presentation regarding how they wrote the go parser. I am no expert though.

bhaney 4y ago

> For very small numbers (less than about FLT_EPSILON * 0.25) adding 0.5 gives 0.5 exactly, and this then rounds to zero Is that not correct? Isn't it expected that very small numbers round to zero?

zerocrates 4y ago
This is in the context of the implementation of a ciel() function: a very small but still positive float should have a ciel() of 1. As said near this part, IEEE default rounding is round half to nearest even: 0.5 rounds to 0, the closest even integer, so if your addition of 0.5 to the argument to ciel() results in exactly 0.5, the result will incorrectly be 0 instead of 1.
teraflop 4y ago
The quote is talking about code that is supposed to find the ceiling of a number, and does so by adding 0.5 and then rounding to the nearest value (breaking ties by rounding towards even). If you have a very small but non-zero positive number, it gets rounded to 0.5 after the addition, and then the second rounding incorrectly rounds toward 0 instead of 1. The result is that you have a value x such that x > ceil(x), which shouldn't ever happen.
- bhaney 4y ago
  > supposed to find the ceiling Oh duh. I somehow forgot that over the span of a few sentences. Thanks.

FpUser 4y ago

Silly me. As far as I can remember I've always used epsilon when comparing floats.

eru 4y ago
That's not a general solution. (And if you know what you are doing, you can also compare floats exactly in some circumstances.) But the article already mentions that.
- kccqzy 4y ago
  Absolutely. I was once refactoring some badly written floating point code. To make sure I did not screw up, I want the result of the old and new code to be identical, since I know the refactoring should not change the float operations. (I also knew the code won't produce NaNs so == suffices.)
  - k0k0r0 4y ago
    Oh, yes... This. Had a project like this not long ago. NaNs almost killed me. The code used complex numbers, and you know who their userbase is. Anyway, exact floating point comparisons made all of this possible. In the process my coworker and found something we believed to be a bug with complex nans in some recent GCC versions, but where not smart enough to understand whether it is actually a bug or undefined behaviour in the standart. Anyway, we where so exhausted from the refactor, we didn't follow it up again.
- FpUser 4y ago
  >"And if you know what you are doing" I knew what I was doing and that is why using Epsilon was the most reliable thing in my data processing algos.
  - eru 4y ago
    Hence the 'in some circumstances'.

chriswarbo 4y ago

4 billion inputs is a little on the extreme end, especially for slower interpreted languages, but it's always useful to look for functions which can be exhaustively tested; e.g. booleans and enums. I spotted a bug in a code review today, which was formatting dates with ordinal numbers, like "9th Feb". The ordinal logic only has to work for inputs 1 to 31, so I wrote an exhaustive test, which it failed by outputting "11st", "12nd" and "13rd" (due to only looking at the last digit)

ben0x539 4y ago
A while back for some videogame related data processing I ended up writing a "regular number to roman numeral" (or maybe the other way around) function in idk ruby or something. Not super convinced that I had gotten it right, I sat down to write a few tests, and then I realized I only needed it to work for numbers up to like 16. So I deleted the actual code, extended the table of test cases to cover 1 through 20 just in case, and just did a lookup in that.
- giraffe_lady 4y ago
  true senior eng shit right there. https://i.imgflip.com/7alx6q.jpg https://i.imgflip.com/7alx6q.jpg
- SnowHill9902 4y ago
  That’s actually the right solution to that specific problem.
- travisjungroth 4y ago
  It happens. Writing the test puts you in the headspace of “assume the problem is already solved”, which is sometimes wildly more effective. There’s some story (that I hope an archivist can link) of someone writing a shell script to verify some giant program. Well, turns out the script could just _replace_ the program. Ran way faster. Sales wouldn’t have that, though.
- JohnFen 4y ago
  Never underestimate the power of a properly placed lookup table.

archi42 4y ago

I loved this, since this resonates with my own experience. If the problem space is small enough, just test against a known good (but slower) implementation. With custom algorithms this can also be very interesting for the person writing the test: Their reference code needs to be correct beyond doubt, but can forfeit mostly every manual optimization. Also, for larger input spaces I like to do a nested for-loop over vectors of "interesting" values, plus add a large set of random values.

askvictor 4y ago

*Only 4 billion floats for 32-bit floats. When you get into double-precision floats, well, there's a lot more.

quacker 4y ago
Or I could be using two floats (adding or multiplying). Or three.
- mr_toad 4y ago
  I was looking for this comment. In my experience functions that work with large multi-variate datasets cause TDD to fall flat on its face.
  - k0k0r0 4y ago
    No they don't. As far as Test Driven Development is commonly understood, at least. TDD would be extremely stupid if the idea would fall flat on its face when tests can not cover the whole input.

Taniwha 4y ago

Yup - I've just finished bringing up some FP hardware - you can't do all the 64-bit double space but you can do all the 32-bit single op instructions (converts, sqrt, etc) - but add/sub/multiple (32x32) are not doable But this is even more appropriate for 16-bit floats - you can realistically do all the adds/multiplies/etc, but maybe not the 3op multiply-accumulates

dragontamer 4y ago

A modern GPU with 5120 shaders and 2Ghz speeds can perform 2^32 ops in just 0.4 milliseconds. (AMD's Rx 6900xt. Yes, sub-millisecond times) The truth of todays computers is that the 32-bit space is a sub-second problem, possibly faster than human reaction speeds. Test the whole 32 bit space. It's cheap today. ------- Extrapolating a bit: the 2^48 space is 27 seconds per op. Maybe 100 ops are needed for your test code, so the 48-bit space (aka: 3x 16-bit input space) can be exhausted and tested in roughly 50 minutes.

thechao 4y ago
And a 64b sweep is ~21 days. As a HW guy who tests fp units... just saying. The real issue is that the verification code is much, much, slower.
- dragontamer 4y ago
  > And a 64b sweep is ~21 days Per GPU. A consumer GPU at that (A100 is faster). 4x GPUs (the AMD 6900 XT) per node and maybe 10x nodes in a rack (4U per node, 42U cabinet) can do 64-bit sweep in half a day. > The real issue is that the verification code is much, much, slower. Isn't verification of 64b multipliers actually a 128-bit problem? (x * y == z, so you have 2x 64-bit numbers to work with). Also, I think they use BDDs, which although multiplication is exponential, its still small enough exponent that 128-bit BDDs fit on today's computers. So its not a brute force thing like discussed in this topic, but actually a very elegant data-structure (though with tons of complications, as is the nature of NP-complete and expspace problems).
  - thechao 4y ago
    It’s a lot easier to do formal verification… which is a fancy BDD, in many ways.
- insanitybit 4y ago
  At that point I might just take the first 2^32 numbers, the last 2^32 numbers, and some range in between, and feel good about it.

throwawaymaths 4y ago

Until you have to test a binary operation. Or, god forbid you have to verify that fma works

supernova87a 4y ago

If I were to use a mental analogy with numerical methods that you get taught in grad school, isn't this kind of just a problem of identifying where poles are in your functions? If you're cycling through all possible numbers and seeing where the output might blow up or go pathological, you probably instead (to be efficient about it) test the far limits of the input number range, and then sample the internal space with an adaptive spacing to see where things are changing and whether it's about to go crazy somewhere. Like divide by zero, subtract 2 small numbers etc.? Or analyze the function to see where subtraction (or whatever operation is applicable here) might misbehave? Rather than spend all your compute equally sampling every possible number. I'm no expert but it seems to be the same type of problem.

swatcoder 4y ago
The insight is that 32-bit space is so cheap to exhaustively explore now that you don’t need to resort to possible misses through sampling or spend the effort to make and verify a smart way of sampling. Just brute force the darn thing and be done.
- supernova87a 4y ago
  Ah, I see, for a test that you'll only run once or rarely, might as well!
  - DougBTX 4y ago
    No no no! That’s really the realisation they’re pushing at, this is fine for routine tests too! In this almost ten year old post the runtime was ~90s, which isn’t too painful. On some threads here, times on modern hardware are quoted as milliseconds or less. The takeaway might be more: spend time to optimise testing everything, rather than spending time optimising the selection of the subset to test. Massive caveat of course is that some search spaces are just big, but 32bit space shouldn’t be considered big any more.
    - supernova87a 4y ago

crazygringo 4y ago

If you're writing functions for basic mathematical operations, then sure. But how often is anyone doing that? If you design microprocessors, or programming languages (maybe), or numerical libraries. But hopefully if you do any of those, you already know to test every value against a reference algorithm. Is there anything in this post that is more generally applicable to the other 99.99% of developers? I'm trying to think of anything I've ever written where it would even be possible to test billions of input values, but there'd never be a reference to test it against.

JohnFen 4y ago
Or if you're coding for very small microcontrollers.

hansvm 4y ago

I recently had to implement floating point math. Can confirm that testing them all was by far the cheapest way to fix all the bugs and then verify the final solution was correct.

pvg 4y ago

Discussions from 2, 5 and 9 years ago: https://news.ycombinator.com/item?id=24745563 https://news.ycombinator.com/item?id=24745563 175 comments https://news.ycombinator.com/item?id=15252426 https://news.ycombinator.com/item?id=15252426 50 comments https://news.ycombinator.com/item?id=7135261 https://news.ycombinator.com/item?id=7135261 118 comments

exikyut 4y ago

Hmmmmm. Reading the aside In fact IEEE floating-point math is designed to, whenever practical, give the best possible answer (correctly rounded) Made me realize - there are not "just" four billion floats, there are four billion floats multiplied by however many levels of rounding you want to test against. The "ninety seconds" doesn't qualify if the test harness was multithreaded. If it wasn't, a modern >30 core box (maybe buried in CI somewhere) should be able to manage quite a few rounding levels without difficulty thankfully.