There are only four billion floats, so test them all (2014)

Many years ago now we built something that used a 60-bit truncated hash of URIs. So that&#x27;s far too small to be comfortable that you won&#x27;t run into collisions, but it&#x27;s big enough that for modest sizes (hundreds of millions up to billions) a collision is unlikely. So you can have a slow path for the collision case, so long as that slow path is correct. For unit testing we needed at least one collision so we could see that everything behaves as designed before some real user hits one. We had test data sets with over a billion URIs in them, but none that (as far as we could tell) had a collision.<p>So I just wrote code to mint nonsense URIs for our system based on a small integer seed (like <a href="https:&#x2F;&#x2F;foo.example&#x2F;123456789" rel="nofollow">https:&#x2F;&#x2F;foo.example&#x2F;123456789</a>), then span up a system with a bunch of RAM (maybe 8-12GB) to iterate through each seed, storing the hash and seed it was generated from, until it hit a collision after a few gigabytes of RAM, then it spat out the two URIs from the colliding seeds. Bingo, now we had data for unit testing to show that stuff works even in the unlikely case that two distinct URIs have the same hash.<p>Probably a day&#x27;s work to build that, and then I&#x27;d guess several hours every month saved debugging weird collision bugs because our unit tests would now tell us if we&#x27;d screwed up and collisions were slipping past.

Things have gotten even faster since then.<p>* Target: 64-bit space (2^64).<p>* GPUs are more flexible and faster. A Vega64 (a few years old now) has 4096 shaders (&quot;CudaThreads&quot;) at 1.6 GHz. It can search the entire 32-bit floating point (or integer) space in less than a second. 1.6 GHz x 4096 shaders == 2^42.5 bitspace per second.<p>* People exhaustively searching a space are relatively patient: and willing to wait months for the results. 60 seconds x 60 minutes x 24 hours x 30 days == 2^21.3<p>1.6 GHz x 4096 shaders x 60 seconds x 60 minutes x 24 hours x 30 days is roughly equal to 2^63.8. We&#x27;ve done it: a month of GPU effort is all you need to exhaustively search the 64-bit space<p>-------<p>We&#x27;ve entered a world (~3 years ago), where it is reasonable to brute force the 64-bit space, so long as you&#x27;re willing to wait about a month for the results.<p>If you&#x27;re not willing to wait a month, then use 2 GPUs, or 4 GPUs, or a cluster of GPUs like the DGX A100 (or multiple clusters).

I love this.<p>This is another in the &quot;Now that we have computers with gazillions of bits of RAM and many cores and gazillions of cycles, what conventional wisdom is no longer wise?&quot; series :-).<p>I suggested to a client that they use Sqlite3 for their company database rather than a disk based database. And they looked at me shocked, as if I had spoken heresy. I pointed out how many records they could store on a 64GB machine and that is a <i>small</i> data center class machine and it sort of boggled their mind. Add read-only copies, shared from a NAS device gave them perfect scalability in terms of queries per second (their sales folks had their own database that they were updating). It was fun to watch their expression go from horror to wonder to excitement when they finally implemented it.

Previous submission 2017:<p><a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=15252426" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=15252426</a><p>Can&#x27;t believe this was already 3 years ago. Interesting read!<p>Previous submission 2014: <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=7135261" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=7135261</a>

Articles like this make me wonder how everything even works if basic math functions can be so wrong and how a simple concept like floor can have different definitions&#x2F; implementations

We did this in XLA. It runs as part of CI, which I always found pretty amazing. <a href="https:&#x2F;&#x2F;github.com&#x2F;tensorflow&#x2F;tensorflow&#x2F;blob&#x2F;bd2608178bca1be95007328fb9e01408a94ba082&#x2F;tensorflow&#x2F;compiler&#x2F;xla&#x2F;tests&#x2F;exhaustive_op_test_utils.cc" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;tensorflow&#x2F;tensorflow&#x2F;blob&#x2F;bd2608178bca1b...</a><p>Found a lot of bugs this way.

It is all very nice, but if your function has two floating point parameters you have 1.6e19 tests to do...

I decided to build a scatter plot to demonstrate what I was 95% sure was a data loss bug (preproduction, thankfully) in the initializer for a CSPRNG.<p>I figured plotting a few bytes if output (256x256) would do nicely. I plotted all possible two byte inputs just to make sure it was working, and that ran instantly, so I tried 3 bytes and that was still pretty fast, so I did 4 while I was at lunch or in a meeting.<p>Sure enough, big black splotches from dropping some of the seed data on the floor. Please to be fixing.<p>Old farts know a lot of things have been tried before and how those worked out. But we also think doing a complex operation 4 billion times is going to be irretrievably slow. Always test your assumptions.

&gt; <i>For very small numbers (less than about FLT_EPSILON </i>* <i>0.25) adding 0.5 gives 0.5 exactly, and this then rounds to zero. Since about 40% of the positive floating-point numbers are smaller than FLT_EPSILON</i> * <i>0.25 this results in a lot of errors – over 850 million of them!</i><p>I thought Float Epsilon was the smallest possible number which could be represented by a float? This statement doesn’t seem to make sense...

I was reading about an implementation of Barrett reduction recently:<p><a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Barrett_reduction" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Barrett_reduction</a><p>Specifically one that uses 80-bit long double for calculating `(__int128_t)a * b % M` from this github:<p><a href="https:&#x2F;&#x2F;github.com&#x2F;kth-competitive-programming&#x2F;kactl&#x2F;blob&#x2F;master&#x2F;content&#x2F;number-theory&#x2F;ModMulLL.h" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;kth-competitive-programming&#x2F;kactl&#x2F;blob&#x2F;ma...</a><p>But how do you test the correctness of such code? You can&#x27;t just stress test all possible product of 64 bit numbers!<p>In the end you still gotta go back to good old fashion proofs: <a href="https:&#x2F;&#x2F;github.com&#x2F;kth-competitive-programming&#x2F;kactl&#x2F;blob&#x2F;master&#x2F;doc&#x2F;modmul-proof.pdf" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;kth-competitive-programming&#x2F;kactl&#x2F;blob&#x2F;ma...</a>

We&#x27;ve certainly tested all Float32 inputs to some functions in Julia&#x27;s math packages. I&#x27;m unable to find the relevant issues this very moment, otherwise would certainly post them.

maybe I dont understand, but is this article only trying to suggest exhaustive testing for single precision, single input functions? obviously this approach is not practical as soon as there are multiple inputs or wider precision.

In addition to many correctness issues, that code is relatively slow.<p>SSE4.1 introduced roundps instruction that&#x27;s both fast and correct. Unlike AVX2 or FMA3, SSE4.1 support is almost universal by now. In most of my current projects, I check support on startup and refuse to run if SSE4.1 ain&#x27;t supported. Just don&#x27;t forget to set the corresponding macros for DirectXMath, Eigen, etc.

&quot;When in doubt, use brute force&quot; -- Ken Thompson

My god this issue has been around for too long. In the &#x27;80s testing folk learned to shotgun the argument space to test functions, and they&#x27;ve not gone an inch forward since! Or so it seems.<p>A version of the Pentium was released that couldn&#x27;t divide by 10. And even back then, testing all the mantissas on a simulator would have taken only hours. Instead, they masked, marketed and released a tragically flawed processor.<p>Just test the input space exhaustively, folks! It&#x27;s a computer; it feels no pain. Work it hard until it fails or works perfectly.

In the early 1980s, truncated floating point calculations caused the Vancouver Stock Exchange index value to drift down for about 23 months, until it was shown as less than half the correct value: <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Vancouver_Stock_Exchange#Rounding_errors_on_its_Index_price" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Vancouver_Stock_Exchange#Round...</a>

I was once in the position to test 3M possible inputs - that took only a few minutes. It&#x27;s a good strategy to keep in mind.

Does anyone have code to reduce the search space by a few orders of magnitude to test functions with a float64 argument or two or three float32 arguments in a few seconds? Perhaps by skipping &quot;boring&quot; floats that aren&#x27;t near endpoints that are unlikely to produce errors that more interesting floats do?

Javascript guy here, can you help me set up that Beowulf cluster so I can start testing my 2^64 cases?

I recall hackers building standard password hashes of all eight character ascii combinations. Then create a reverse lookup table. But thats 400 trillion entries for stand 68 character ascii password subset.<p>400 trillion hashes is not a big computation in the blockchain era.

&quot;Round to nearest even is the default IEEE rounding mode. This means that 5.5 rounds to 6, and 6.5 also rounds to 6&quot;<p>Does anyone know the reason behind this? why the nearest even and not a hard cut like &quot;always round up with &gt;= 0.5&quot;?

Makes sense when you&#x27;re refactoring an existing function with one numeric argument, and which evaluates rapidly.

Crap now I have 67 million failures to fix.

&gt; I’ve written in great detail about how to compare floating-point values using an epsilon, but there are times when it is just not appropriate. Sometimes there really is an answer that is correct, and in those cases anything less than perfection is just sloppy.<p>Certain applications will choose fixed point to avoid what appears to be the imprecisions of floating point.

For python you cannot user the stdlib for this, but it would work for numpy float32.

1. Given the thoroughness of the write-up, I&#x27;m going to assume that the author did not find that any of the discrepancies in the implementations were actually bugs in the reference implementation. He goes as far as to say that he reimplemented the reference implantation so this seems like a safe assumption. Still, it would be nice to confirm. Given that other implementations seem so shoddy, it wouldn&#x27;t be surprising to find a bug in the reference.<p>2. &quot;Conventional wisdom Nazis&quot; Maybe the author was just bored of writing at this point, but some justification for why bitwise comparing floats was a correct decision would have been nice. Is it because there&#x27;s no math involving unrepresentable intermediates? Because there&#x27;s no integration happening, so no way for errors to accumulate?

Test them all and waste a huge amount of energy and computational resources!<p>I hope people test like that for really critical stuff, but not for your everyday library for your personal startup or e-business. Not even the big players need this.

&quot;Seymour Cray didn&#x27;t care that 81.0&#x2F;3.0 did not give exactly 27.0 on the CDC 6000 class machines; and he was universally respected for making the fastest machines around.&quot; ──Linus Torvalds

&quot;Several of the ceil functions were implemented by adding 0.5 to the input value and rounding to nearest.&quot;<p>What sort of clown would make that mistake and yet think they are capable of writing a floating point library?

Very difficult due to rounding errors;

How do you do this for a function with more than one or two inputs? If the domain is 4B to the power five, you are out of luck. Very few of us need to implement &quot;floor&quot; or any other function that takes 1 float input.