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

https://randomascii.wordpress.com/2014/01/27/theres-only-four-billion-floatsso-test-them-all/

by tape_measure • 6 years ago

501 175 6 years ago

randomascii.wordpress.com

ascar• 6 years ago

Previous submission 2017:

https://news.ycombinator.com/item?id=15252426

Can't believe this was already 3 years ago. Interesting read!

Previous submission 2014: https://news.ycombinator.com/item?id=7135261

tape_measure• 6 years ago

Yes, I originally came across this on HN, likely in 2017 based on my surrounding bookmarks. It has stuck with me ever since even though I don't do much programming anymore. At the time, I was a TA in a MATLAB course, so I tried to emphasize that the code runs on a machine and is fundamentally discrete. (.1 + .2 == .3) returning false is an easy way into this concept.

32 bits (and now 64 as @dragontamer calculated) is a huge input space. You could verify 4 int_8 or 2 char[2] functions.

MeteorMarc• 6 years ago

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

fallingmeat3• 6 years ago

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.

pm215• 6 years ago

Yes, the article says "Exhaustive testing works brilliantly for functions that take a single float as input. I used this to great effect when rewriting all of the CRT math functions for a game console some years ago. On the other hand, if you have a function that takes multiple floats or a double as input then the search space is too big. In that case a mixture of test cases for suspected problem areas and random testing should work."

I think the point is that exhaustive testing is feasible in more situations than you might at first think, and than floating-point arithmetic is a particularly fertile source of edge conditions and corner cases, so it's a good place to go for exhaustive testing where you can.

fallingmeat3• 6 years ago

fertile indeed!!!! haha

I should learn to read

nullc• 6 years ago

In many cases it is practical but people wrongly assume it isn't. In cases where its not practical exhausting a subset can still be very powerful.

E.g. for a function that takes two floats (x,y) test every value of x input with y={0,-0,1,nan,inf,-1,x,-x,2x,x/2,FLT_EPSILON,FLT_MIN,FLT_MAX,random,random,random...}, and then repeat with x,y swapped.

A little knowledge of the domain can help pick better special values, but there is a trade-off in introducing the same blind-spots that permitted bugs in the first place. Still: testing just one argument on all values because that's all you can afford is still a lot better than only testing a couple special values for both arguments.

Exhaustive testing, like randomized testing catches errors you weren't even thinking about-- but unlike random testing exhaustion can reliably catch bugs which are extremely rare. "Partial exhaustion" can have some of the same benefits.

fallingmeat3• 6 years ago

mmm, disagree based on my experience. oh also I think people on this thread may be misusing the concept of float epsilon. keep in mind that is not the smallest value of a float.

kardos• 6 years ago

Testing all of the doubles may actually be possible [1]. Even if that estimate is optimistic, testing all doubles for order $10k would be feasible for some problems.

[1] https://news.ycombinator.com/item?id=18109432

brianberns• 6 years ago

Not to mention that exhaustive testing only works when you already know the correct result for each input.

sega_sai• 6 years ago

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

andi999• 6 years ago

So it only needs 4 Billion times 90s, so is this like never in a million years? (actually it should be only around 12000 year, so you could use a cluster of 48000 Computer and be done in 3 month)

Someone• 6 years ago

Distribute it over every smartphone on the planet (about 4 billion), and the computations will be done in minutes (of course, that’s dependent on the function being tested).

There will be orchestration overhead and transmission latency, but I guess one could get all results in one place in a day, if one had the ability to do the “run it on every smartphone” thing.

thechao• 6 years ago

I have worked at two companies where we brute-force checked binary floating point operators. It’s annoying, error prone, boring, and soooooo satisfying. The Holy Grail^TM is brute force F32-FMA. That one really requires a lot of thought, and can’t be reasonably brute-forced on anyone’s budget.

ChrisLomont• 6 years ago

Then you can prove your algorithm correct using proof libraries like Z3.

formerly_proven• 6 years ago

Totally doable. That's just a few hours using 100k cores.

TheRealPomax3• 6 years ago

Worth it if your function is acutely fundamental to the operation of your software because your software runs everyone else's software. You buy some time on a compute cluster with 1024 cores and 4TB of ram, and off you go, after making sure you understand your own code and reduce that number back down to "no it isn't, because two arguments in a given space for fundamental maths operations, taken together, almost certainly don't require combinatorial testing" =)

xchaotic• 6 years ago

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/ implementations

marketingPro2• 6 years ago

Someone correct me if I'm wrong because it's been years since my EE class.

Basic math ends at division. Heck if you learn how math works on computers, it feels like a number trick. Those are reliable.

The issue comes when you need to track never ending decimal points. Even if every transistor was dedicated to your problem, you'd still need to round. So even if you have 32 bits of decimals, there will be rounding sometimes.

The human has to decide what to do. Instead of converting the binary to decimal and calling it done, it's more important to be consistent and predictable.

The issues described in the article arent 5/2= 2 billion. The article talks about rounding giving you always even numbers, which you can imagine leads to issues if you are using both float and using logic that involves even and odd numbers.

Edit- can someone correct me or add details, I'm very interested but I'm not taking ENG 240 again... :p

esperent• 6 years ago

Exactly this. The floor function works on binary numbers but has to round them to a decimal place. It's not simple, it just appears to be.

CydeWeys4• 6 years ago

This is why the big rational data type is so useful on occasion. When you just want to get one calculation exactly right, and performance doesn't matter so much because you aren't doing huge numbers of repeated operations (as in ML), use a big rational with its arbitrary precision numerator and denominator and you don't need to worry about even epsilon error.

Frost1x• 6 years ago

It often doesn't to high degrees of precision and reliability. It works within some tolerance range and those tolerance ranges are managed or acceptable levels of error (often unnoticed).

I recently helped move/port one fairly complex numeric model from a language and environment to another language and environment and there was an assumption made by upper management that this was simple and exact deterministic results would be easily had.

I warned that this could be an involved process because of simple variations, lack of equivalent mappings between environments and languages, some of which pointed out in this article.

Management were quite surprised with the level of effort needed to dig down layers of abstraction and identify all these sort of variations in numeric libraries from consistent high level abstractions they were familiar with, and why those high level abstractions simply didn't exist in the other language and environment. They were additionally surprised inthe level of effort needed to get satisfactory error tolerance ranges between the two models when having to recreate high level abstractions identically from the source language and environment to the target language and environment that simply didn't exist prior to the work.

They didn't realize the variation until we performed a detailed analysis on results and found very small but statistically distinguishable results from the two versions. We ended up identifying a few dozen small assumptions they made about their high level abstractions from the source environment that were false and caused the variation.

pierrebai• 6 years ago

The answer is that the bugs the article claims are corners cases, most of which will not matter in most practical uses of floating point maths... and some of which will is due to not emulating a weird IEEE floating point rule about rounding numbers of the form N.5 to the even number instead of up like everyone is taught in school.

So "wrong" as used in the article simply means "not the same as the IEEE behavior", not "wrong" as in "wildly inaccurate". It matters if you want 100% exact emulation to get identical results. It doesn't if you don't and just want speed.

CydeWeys4• 6 years ago

some of which will is due to not emulating a weird IEEE floating point rule about rounding numbers of the form N.5 to the even number instead of up like everyone is taught in school.

Round-to-even (also known as banker's rounding, because it's used in finance too) isn't weird at all. It minimizes rounding error, especially on repeated calculations. The rounding rule that everyone learns in elementary school is bad and results in systematically biased computations. We can and should do better than that flawed approach. This post explains it in more depth: https://mathematica.stackexchange.com/a/2120

phkahler• 6 years ago

> The answer is that the bugs the article claims are corners cases, most of which will not matter in most practical uses of floating point maths...

Most bugs are corner cases of one sort or another. At the application level you can decide how important the corners are. When you're creating a math library that many others are going to use, and there is a standard, I think the expectations should be higher.

brucedawson5• 6 years ago

I recently saw a talk (internal only unfortunately) about how some "minor" changes in sin/cos/whatever functions in Chrome broke multiple web sites. It was things like mapping sites and the "minor" changes in the output of sin led to huge errors in the maps.

Which is to say, that minor errors often don't matter, but if you are offering up a general purpose solution then those minor errors probably matter to _somebody_.

jlebar2• 6 years ago

Six Stages of Debugging

1. That can’t happen.

2. That doesn’t happen on my machine.

3. That shouldn’t happen.

4. Why does that happen?

5. Oh, I see.

6. How did that ever work?

http://plasmasturm.org/log/6debug/

dredmorbius• 6 years ago

The DNS haiku;

    It's not DNS.
    There's no way it's DNS.
    It was DNS.

https://www.cyberciti.biz/humour/a-haiku-about-dns/

SoSoRoCoCo• 6 years ago

You should see how confusing modulo becomes of the method isn't explicitly specified:

https://en.wikipedia.org/wiki/Modulo_operation

throwaway7281• 6 years ago

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

zaroth• 6 years 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. Since about 40% of the positive floating-point numbers are smaller than FLT_EPSILON * 0.25 this results in a lot of errors – over 850 million of them!

I thought Float Epsilon was the smallest possible number which could be represented by a float? This statement doesn’t seem to make sense...

Sebb767• 6 years ago

I thought that too, but it's actually the difference between 1.0f and the next larger number; so it only represents the smallest difference for the non-dotzero range.

See here: http://www.cplusplus.com/reference/cfloat/

MatmaRex• 6 years ago

There are different "epsilon" constants in different languages that mean different things. In C and C++, FLT_EPSILON is "Difference between 1 and the least value greater than 1 that is representable." (http://www.cplusplus.com/reference/cfloat/). You might be thinking of the C# constant.

neeeeees• 6 years ago

FLT_ESPILON is the bound on rounding error for certain operations. Plenty of numbers smaller than it can be represented in most floating point implementations

jcranmer• 6 years ago

When I took numerical analysis, the concept was described as "machine epsilon", which is the smallest number that can be added to 1.0 that is not 1.0.

The utility of this metric is that it tells you the best possible relative error, as you can never guarantee a result will be more correct to the true result (in the domain of mathematical real numbers as opposed to machine floating-point numbers) than half of machine epsilon.

This concept is often extended into discussions of "units in the last place" (ULPs), which is the magnitude of the value of last bit of the mantissa. So ulp(1.0) = ulp(1.5) = machine epsilon, ulp(2.0) = ulp(3.9) = 2 * machine epsilon, etc. A good floating-point library will document its accuracy in terms of ulps, so that we might say that the maximum error of the exp function is 1 ULP and that of pow might be 6 ULPs.

brucedawson5• 6 years ago

FLT_EPSILON is the difference between 1.0f and the next float. With that we can work out the math:

- If you add 1.0f to FLT_EPSILON then you get an exact result - If you add 1.0f to FLT_EPSILON * 0.5 then you get a number that cannot be represented and it will either round to 1.0 or 1.0+FLT_EPSILON - Similarly, if you add 0.5f to FLT_EPSILON * 0.25 then you get a number that cannot be represented and it will either round to 0.5 or to 0.5 + FLT_EPSILON * 0.5

With the default rounding mode that last calculation rounds to 0.5. There are a _lot_ of floats below FLT_EPSILON.

tialaramex6• 6 years ago

Many years ago now we built something that used a 60-bit truncated hash of URIs. So that's far too small to be comfortable that you won't run into collisions, but it'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.

So I just wrote code to mint nonsense URIs for our system based on a small integer seed (like https://foo.example/123456789), 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.

Probably a day's work to build that, and then I'd guess several hours every month saved debugging weird collision bugs because our unit tests would now tell us if we'd screwed up and collisions were slipping past.

seanmcdirmid3• 6 years ago

Couldn’t you also test the recovery logic with a hasher that yielded collision more often? It’s like take your system, make it worse (use very dumb hashing), and see how it degrades and/or breaks?

xxxtentachyon• 6 years ago

Or, even simpler, just stub out your hash function and to something that always generates the same value and test with that.

rocqua• 6 years ago

Seems like that would make it less of an integration test

tialaramex6• 6 years ago

My preference is always to actually test parts in as close as possible to the real state, avoiding mocks unless they're necessary. The more "fake" the system is, the less it tells you about how your software actually works.

So since I could generate collisions for the real hash, that's what I did. If it had been infeasible, I would of course have found a different way to test.

This particular software was written mostly in C (today I would not write it in C) which makes it even more likely that introducing never-used-in-production behaviour unexpectedly perturbs the system. This same system for example ran into an obscure (and since fixed) libc allocator bug, and a defect in the Linux kernel, because we were really kicking the shit out of the memory mapped file I/O with what we were doing.

harpiaharpyja• 6 years ago

I was wondering why GP couldn't have swapped out the hash function for one that just returns a fixed value, making everything a collision. Then it would just be a matter of verifying the system still works under that condition (ignoring the performance hit).

You could even measure the performance hit from that degraded condition and create a heuristic to warn you if something is wrong with the fast path.

AtlasBarfed• 6 years ago

Did you truncate the hash for dataset size considerations? If you associate data with the hash, I would guess the test data would dwarf the hash size, so why not do 128 or 256 hashes?

tialaramex6• 6 years ago

The hash is for content-based addressing. We're going to fasten those 60 truncated bits to a 4 bit tag that says this is a URI in the content-based storage. And then we can use this 8 byte value to refer to that URI twice, or fifty thousand times in our system even if the URI is a hundred bytes long - the only problem is collisions, so we need to be sure we notice if there is a collision and handle that correctly everywhere.

nulptr3• 6 years ago

I have a question about how you generated collisions.

If each seed is a 32-bit int, and each hash is 60 bits, then you'll have to store 92 bits for each (seed, hash) pair.

With 2^32 (~4.3 billion) (seed, hash) pairs, you'd need 2^32 * 92 bits ~= 50 gigabytes.

But you mention only needing 8-12GB. Is my calculation wrong, or have I missed something?

manulp• 6 years ago

You’re looking for a collision, any of them will do, so your computation doesn’t actually need to go through all the elements. https://en.m.wikipedia.org/wiki/Birthday_attack

Thorrez2• 6 years ago

Since the hash is 60 bits, a collision is expected after 2^30 tries due to the birthday paradox. So by your math this would be 12.3GB. Although this is ignoring hash table overhead, which I expect to be at least 2x. Maybe they just got lucky.

bluesign• 6 years ago

You can also truncate hash at 30 bits and use it to address bucket, 12gb then would give you like 3x32 bits, which you can store your candidates. Then compare full hash with candidates.

jcims2• 6 years ago

I embarrassed myself as a Noogler trying to explain what in my head seemed like a good tradeoff between hash size (also of URIs) and collision handling. The process had fixed storage for a table of known hashes, and every collision was tested for validity before taking action. If you could use a truncated hash, you’d obviously increase your collisions, but if you’re going to validate all collisions anyway, it seemed like you could increase your coverage substantially (in the 60-bit case it would have been 4x) while only marginally increasing your overhead of collision handling.

There's some kind of sparsity/entropy function involved with optimizing these two but I'm too clueless to sort it out. Without the vocabulary to make my case I just got weirded out by a bunch of smart people staring at me quizzically. Sooo..

Arcuru• 6 years ago

That kind of thing happens to me all the time. I'm very often unable to think of or explain things in the moment.

Sometimes it helps to write a doc afterwards to get my thoughts in order and decide if it's worth sharing.

btrask• 6 years ago

It's known as the birthday paradox. There is a probability table here: https://en.wikipedia.org/wiki/Birthday_paradox#Probability_t...

stouset• 6 years ago

Why not just run the test-cases using a 16-bit hash function?

kortilla7• 6 years ago

Likely a C programmer with little experience doing testing with fakes. Most C projects I’ve worked on are horrible at structuring the code in a way that makes it sane to do dependency injection or mocking.

kortilla7• 6 years ago

This is one of those cases where it would have been easier to fake the hashing function in the unit tests with something that collides when you want. What happens if you want a test case where 3+ URLs hash to the same bucket?

wbsun• 6 years ago

Any reason the hash function and the collision handling can’t be separated and mocked for unit tests? What if you decide to increase the bits of hash values or change the hash algorithm?

csense• 6 years ago

Figure you need at least 12 bytes per entry to store the ID and hash. Then you can only handle 1/12 of your memory size in bytes (so 1 billion entries if you have 12 billion bytes of RAM).

Much more memory efficient to use a Bloom filter. Build n different ways of hashing the hash (this can be as simple as having some standard hash function H() making the ith different way H(h, i)). Then when you add an entry you write a bit at each of these locations.

Instead of writing right away, you check to see if all the bits were already set. If they were, the entry being added is a candidate for a possible collision with some earlier entry, so stream it out to a file or something.

Once you have the (much smaller) list of a few million collision candidates, you do another iteration over the whole data set, checking each one against only the collision candidates.

The most memory-intensive part is the Bloom filter. You could probably get away with a Bloom filter size of 10 bits per entry or less. (If you want specific numbers, there are lots of online calculators to help you calibrate the size of a Bloom filter.)

But given this is a one-off search, and you had a machine with enough RAM to find a collision, an ordinary hash-based set implementation is good enough and saves the most precious resource of all, developer time :)

tialaramex6• 6 years ago

This is clever. At the time we needed this machine anyway (this is way before "Cloud computing" was really a thing) but a few years earlier it would have been a good choice.

We actually had most of the bloom filter code you'd need because we used a lot of Bloom Filters in that project. One of the very common queries that system had was "Hey do we know about random thing X?" for which the answer would often (but not always) be "No". So Bloom Filters enabled the system to be able to say definitively "Nope, I know nothing about X" a good fraction of the time without any further work. This actually hurt us in some third party benchmarks we ran for boasting, but helped in our real use case.

Const-me• 6 years ago

In addition to many correctness issues, that code is relatively slow.

SSE4.1 introduced roundps instruction that'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't supported. Just don't forget to set the corresponding macros for DirectXMath, Eigen, etc.

elvis70• 6 years ago

"When in doubt, use brute force" -- Ken Thompson

IncRnd• 6 years ago

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.

Certain applications will choose fixed point to avoid what appears to be the imprecisions of floating point.

dragontamer7• 6 years ago

Things have gotten even faster since then.

* Target: 64-bit space (2^64).

* GPUs are more flexible and faster. A Vega64 (a few years old now) has 4096 shaders ("CudaThreads") 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.

* 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

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've done it: a month of GPU effort is all you need to exhaustively search the 64-bit space

-------

We've entered a world (~3 years ago), where it is reasonable to brute force the 64-bit space, so long as you're willing to wait about a month for the results.

If you'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).

Keyframe• 6 years ago

Sounds like a small and relatively cheap farm could do it in hours or minutes even.

dragontamer7• 6 years ago

Hmmm... assuming 4-GPUs per node, and 1200W per node, you'll need 216kW to generate the result in a day.

But that also assumes that the operation you're testing is 1-clock tick, which is only true for the most trivial of calculations. Still, 216kWs per day per "test-case clock ticks" shows us that the 2^64 exhaustive bitspace is within a reasonable organization's grasp.

antoinealb• 6 years ago

Note that the article is specifically talking about testing accelerated code. This is usually using machine-specific features, meaning it won't run on a graphic card.

I am also not sure about how fast you are if you need to transfer data out of the GPU, or to add conditional branching to the shader code (it used to be that branches were super slow in GPUs, not sure where they are now).

I could see it working for some other problems though.

dragontamer7• 6 years ago

meaning it won't run on a graphic card.

GPUs implement the ceil and round functions.

Heck, GPUs implement popcount, bit-reverse, and a whole slew of instructions that CPUs don't. (Mainly bitreverse and bpermute. Intel x86 only has permute (aka pshufb), but not the backwards version. BSwap can't emulate bitreverse)

(it used to be that branches were super slow in GPUs, not sure where they are now).

Branches are fine. Its divergent branches (in both CPUs and GPUs) that are slow. A uniform branch will be branch-predicted on a CPU, while a uniform branch on a GPU will have all 64-threads (AMD GCN) or 32-threads (NVidia or RDNA) follow the instruction pointer.

There's no slowdown with uniform branches, either on CPUs or GPUs. Both CPUs and GPUs do poorly on divergent branches, but GPUs do MUCH worse than CPUs.

xigency• 6 years ago

Note that the article is specifically talking about testing accelerated code. This is usually using machine-specific features, meaning it won't run on a graphic card.

I think there are a lot of computing algorithms you might run on a GPU where you might want to verify the correctness over the range of 32-bit or 64-bit numbers (integers or floating point).

OscarCunningham• 6 years ago

You could also use this to verify 32-bit functions with two arguments.

known• 6 years ago

Very difficult due to rounding errors;

vortico2• 6 years ago

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 "boring" floats that aren't near endpoints that are unlikely to produce errors that more interesting floats do?

TheRealPomax3• 6 years ago

all floats are equally boring.

vortico2• 6 years ago

No, -0.f is more interesting than 4.1045857301e23f. It's more interesting because it's more likely to fail a test where others don't.

daveFNbuck3• 6 years ago

That's essentially what fuzzy testing libraries do. You tell the library what types of arguments you want, write your test, and it puts in some known corner cases and a few random values that change each time you run the test (but are saved as new corner cases when the test fails in the better libraries).

rigtorp• 6 years ago

Yes, I've done this using libFuzzer. Supply custom mutation and crossover functions that generates interesting floating point numbers. Then let the coverage guided fuzzer exercise your code. https://rigtorp.se/fuzzing-floating-point-code/

ramshorns• 6 years ago

Well, if the ceil function failed on 1.0f, maybe even the ordinary numbers are worth testing.

But... would randomness help? Take a representative sample of like 1/64th of the double space and you might run into most of the common problems.

recursivecaveat• 6 years ago

You can't naively do it with the bits of a float, but for most purposes N-wise testing will get you a lot of coverage relative to random or manual cases for little expense. I've had success with it using a library to generate cases testing math kernels with many parameters.

https://en.m.wikipedia.org/wiki/All-pairs_testing

jlebar2• 6 years ago

We did this in XLA. It runs as part of CI, which I always found pretty amazing. https://github.com/tensorflow/tensorflow/blob/bd2608178bca1b...

Found a lot of bugs this way.

NelsonMinar2• 6 years ago

"Several of the ceil functions were implemented by adding 0.5 to the input value and rounding to nearest."

What sort of clown would make that mistake and yet think they are capable of writing a floating point library?

Exuma• 6 years ago

Can you give an example of when this wouldn't work? I'm definitely not qualified to write a float library (lol) but I also can't think of any cases where that wouldn't work?

brianush1• 6 years ago

ceil(5) = round(5.5) = 6

ceil(5) should be 5

zelphirkalt2• 6 years ago

This is probably about number precision and loosing digits, when you add something with digits only in the beginning like 0.5 to something small like 0.1000000000000000000000000000013124142579275927597245205 or whatever a barely representable floating point number is. Then the result becomes inprecise and rounding to nearest will result in the wrong value.

Such effects and similar should be well known to anyone taking on the responsibility to develop a floating point library.

NelsonMinar2• 6 years ago

Every odd integer? The original article discusses it in great detail.

zelphirkalt2• 6 years ago

Test them all and waste a huge amount of energy and computational resources!

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.

zzzeek• 6 years ago

Crap now I have 67 million failures to fix.

ViralBShah• 6 years ago

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

raphlinus• 6 years ago

I suspect https://github.com/JuliaLang/julia/pull/29700 might be one of them. As the original post states, rounding is (a) amenable to hardware acceleration, (b) easy to get wrong or slow, and (c) possible to test exhaustively.

ChuckMcM• 6 years ago

I love this.

This is another in the "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?" series :-).

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 small 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.

michaelmcmillan• 6 years ago

Yup! I'm currently running a b2c solution for a client that's grossing ~$3 million/year using Python + sqlite3 behind nginx.

I work for another shop that scolds me for even suggesting using something else than k8s. How can a persistent file system possibly scale? Lol. Ironically they're grossing -$3 million/year.

tonetheman• 6 years ago

I am curious about your case is the traffic mostly read heavy? Ha wish you could share more. Interesting stuff.

dragontamer7• 6 years ago

https://yourdatafitsinram.net/

The IBM 53-bit quantum compute result from a ton of hard drives + compute power was also intriguing (https://www.ibm.com/blogs/research/2019/10/on-quantum-suprem...).

128PiB of disk space needed for a 54-qubit computation on their system (hard drives). Fun to see where the supercomputers are still needed, but smaller qubits can be emulated on normal computers. 40 qubit calculations probably can be emulated on a 16TB team of hard drives in RAID0.

kortilla7• 6 years ago

The trade-off isn’t really size in a lot of cases though. When stuff is stored in RAM you lose the persistence story.

greggyb• 6 years ago

Disk storage for the WAL and periodic checkpoints can get you sub-second recovery targets easily.

Ninja edit: or a UPS and a shutdown procedure triggered by it that writes the database to disk. You can write 100GB in a couple minutes over a 10Gbps network. Faster to a local SSD.

svnpenn• 6 years ago

I suggested to a client that they use Sqlite3 for their company database rather than a disk based database.

Sqlite is a disk based database...

capableweb• 6 years ago

Well, maybe not "disk based" per se. It can be stored on disk, yeah. But it can also run in memory. I think in this case it's clear that ChuckMcM meant a machine with 64GB of RAM (not disk space), therefore they are talking about having SQLite running in memory, not on disk.

jansan• 6 years ago

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

JoeAltmaier• 6 years ago

My god this issue has been around for too long. In the '80s testing folk learned to shotgun the argument space to test functions, and they've not gone an inch forward since! Or so it seems.

A version of the Pentium was released that couldn'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.

Just test the input space exhaustively, folks! It's a computer; it feels no pain. Work it hard until it fails or works perfectly.

drivebycomment• 6 years ago

On most CPUs, there's plenty of 2 64-bit operands, and with SIMD instructions, plenty of CPUs have more than 1K bits total as input to the instruction. Good luck exhaustively testing those.

wtn• 6 years ago

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: https://en.wikipedia.org/wiki/Vancouver_Stock_Exchange#Round...

peter303• 6 years ago

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.

400 trillion hashes is not a big computation in the blockchain era.

SirYandi• 6 years ago

More info: https://en.m.wikipedia.org/wiki/Rainbow_table

hinkley• 6 years ago

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.

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.

Sure enough, big black splotches from dropping some of the seed data on the floor. Please to be fixing.

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.

uyt• 6 years ago

I was reading about an implementation of Barrett reduction recently:

https://en.wikipedia.org/wiki/Barrett_reduction

Specifically one that uses 80-bit long double for calculating `(__int128_t)a * b % M` from this github:

https://github.com/kth-competitive-programming/kactl/blob/ma...

But how do you test the correctness of such code? You can't just stress test all possible product of 64 bit numbers!

In the end you still gotta go back to good old fashion proofs: https://github.com/kth-competitive-programming/kactl/blob/ma...

tagh• 6 years ago

Makes sense when you're refactoring an existing function with one numeric argument, and which evaluates rapidly.

CGamesPlay• 6 years ago

1. Given the thoroughness of the write-up, I'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't be surprising to find a bug in the reference.

2. "Conventional wisdom Nazis" 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's no math involving unrepresentable intermediates? Because there's no integration happening, so no way for errors to accumulate?

brucedawson5• 6 years ago

"Sometimes there really is an answer that is correct, and in those cases anything less than perfection is just sloppy."

Anytime there is a correct answer, and it can be determined exactly (+, -, *, /, sqrt) you should expect nothing less than perfection. ceil, round, and floor fall into this category fairly self-evidently, I think.

alkonaut• 6 years ago

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 "floor" or any other function that takes 1 float input.

jart• 6 years ago

"Seymour Cray didn't care that 81.0/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." ──Linus Torvalds

lentil_soup• 6 years ago

"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"

Does anyone know the reason behind this? why the nearest even and not a hard cut like "always round up with >= 0.5"?

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

Related Stories