13 ms·

There Are Only Four Billion Floats – So Test Them All

235 points by thedufer 13y ago

jevinskie 13y ago
> A trillion tests can complete in a reasonable amount of time, and it should catch most problems. When your individual test is a handful of instructions, you can make such impressive claims. I only wish $work's test suite was so svelte!
jwmerrill 13y ago
Who's using single precision floats these days?
- plorkyeran 13y ago
  They're the standard choice for 3d graphics in games.
- lelandbatey 13y ago
  Yeah, I was going to say. The wisdom that I'm being taught in school is "Don't use single precision floats, at least not when you're on any kind of a modern system."
  - nkurz 13y ago
    That's OK wisdom unless you are aiming for high performance. I'd put it at about the same level as "Don't use C if something higher level will work." If you are hoping to gain from vectorization, or if you have enough of them to care about memory usage, single precision is twice as good, unless the extra precision of a double actually gains you something.
    - lelandbatey 13y ago
      Once again, I fell into the trap of saying "you should often do x" while leaving off the "... Except when you shouldn't". The exact comment from the CS professor I have in mind was "Using doubles when doing realtime human facing calculations (such as a calculator) is the best way to go. However, floats have their uses, such as on systems where there isn't enough memory, or where a float fulfills the requirements." but that's a bit much to type from a phone so I went for "use doubles". And now I'll never be so lazy with my comments again!
  - ajuc 13y ago
    If you don't care about precision use single floats. That's most of the time in games. Some people even used ints as fixed precision fractions. If you care about precision - doubles still aren't precise - for currency use bigdecimals, for some stuff ratios can give precise results, for irrational things your only options are doubles, but be aware that you aren't precise, even for simply looking operations. No way to compute 10% of something precisely with doubles.
    - socillion 13y ago
      You wouldn't use ints for currency?
      - hvidgaard 13y ago
        You shouldn't use fixed integers. What happens when you need to represent a fraction smaller than what your largest integer can? For financial calculation you use a dynamic integer type that expand as needed.
        vidarh 13y ago
        For many financial applications, you know precisely in advance how many decimal points you need to be able to accommodate. E.g. for UK VAT calculations, you are never required to work it out to more than four decimal points (and can then round to 3). I sort-of agree with you, in that it is easy to get bitten, and that if people have a dynamic integer type available on their platform that's probably safest. If the choice is between using integers for fixed point vs. using double's though, I'd go for the fixed point any day.
      - justincormack 13y ago
        64 bit ints in cents/pence/whatever should be OK. 32 bit ints are too small. Even in Zimbabwe which issued $100tn bills 64 bits should be enough.
      - ajuc 13y ago
        You can, but: - it's still advisable to wrap ints in some class to be able to distinguish ints that are already multipied and ints that aren't. It's also better cause then you can overload operators. I've written graphic demu using fixed point numbers (floats) without wrapping them, and it was very painful and error prone. So you still work on objects and not on primitive values. - there's a problem with how much precision you need. Different countries specify their way to round up doing money calculation differently (even with the same currencies - see Euro). When you use ints you have the assumption about precision repeated all over your codebase, which make it harder to change when tax law changes or you want to support other countries. With BigDecimals most of the code is universal.
  - dagw 13y ago
    Like all good wisdom, there are plenty of exceptions. I use single precision all the time. The most obvious advantage to me is that I can load twice as large data sets into memory, which has some definitive performance advantages.
  - forrestthewoods 13y ago
    Oh god. The future is doomed.
- nabla9 13y ago
  Anyone who wants to do fastest possible floating point arithmetic with graphics card. Also, if the memory, disk access, or IO-troughtput is the bottleneck with number crunching, single floats might give huge advantage.
- wlievens 13y ago
  We do all our image processing using floats (as memory and disk storage - not as computation accumulators obviously). It helps a lot if you keep a dozen seventy-megapixel images in memory, because it means you can run twice as many jobs on your cluster.
- LnxPrgr3 13y ago
  Depends on the application. If I'm processing audio in a PBX, 64-bit floating point precision isn't going to do me much good when my source is a noisy 8-bit µ-law stream. All I'd gain is twice the demand for memory space and bandwidth—not a cost I'm willing to pay when I gain zero developer productivity from it. Even CD-quality audio only has 16 bits per sample. My digital camera only records 12 bits per pixel, and that's before the image is converted to a more reasonable 8-bit-per-channel format. Single precision is still overkill in a number of applications.
  - yread 13y ago
    but these are all fixed point! When doing arithmetics you can lose as much as 1 bit of precision per floating point operation. So, it pays off to do use more precision for calculations even when the storage format doesn't persist it. Besides I remember reading somewhere that 32-bit floats instructions aren't actually any faster than 64-bit (except of course the cache...). They even might be slower because the FPU has to extend them to 64-bit before performing the operation
    - LnxPrgr3 13y ago
      To be clear: are you talking FPU instructions, or more modern SSE(N) instruction sets? Modern compilers on modern CPUs pretty aggressively vectorize my number crunching. If it's something you're worried about, I'd suggest measuring the difference in your actual application, both in terms of performance and accuracy. If I can come up with a decent test case I can legally publish, I'll post results, but your mileage may still vary.
    - sharpneli 13y ago
      The time when the actual floating point instructions were a bottleneck are long gone. Nowadays when you do computations with single float/double values in your registers they are equally fast. The biggest difference comes from memory bandwith and the ability to vectorize. Your CPU can calculate either 4 floats or 2 doubles in one instruction (assuming pre AVX X64 processor). With AVX it's 8 floats or 4 doubles.
  - 13y ago
- Negitivefrags 13y ago
  Your comment makes me feel sad. It just reflects a whole mindset that makes me feel like an oppressed minority somehow. It sucks that most people don't really care about performance any more. It sucks when people causally dismiss people who do care about performance with arguments like "premature optimization" and so on. It kind of sucks that the web is taking over because it gives an excuse to use slow languages. It almost makes me feel sick to think that Javascript stores all numbers as doubles. So you know what? It makes me feel happy to use the most efficient type that will work. I like my single precision floats. I can die happy knowing that I didn't waste everyone's collective network, disks and CPUs with needless processing. Can't it be good to save just for the sake of saving? So you want a practical reason do you? I shaved over 2 gigabytes off the size off the download size of our product simply by using more efficient data types. Using half size floats is good enough for some data (16 bits). And let me tell you about a data type that we used to use called a char. 8 bits would you believe! Turns out those x86 CPUs that are sitting there a few VMs deep still support those things.
  - hvidgaard 13y ago
    It's not even about performance. It's about actively thinking about what data you'd be processing. Why use doubles when singles are okay? I'd sure not be using 64 bit ints just because "it's bigger" when a normal 32 bit would be just fine.
    - marcosdumay 13y ago
      > Why use doubles when singles are okay? Because of rounding issues, that look like a no problem for a single precision number, but will be a no problem^2 for a double precision one. Thus, if I'm wrong (or get wrong after a change in scope), the program will still work.
      - cwp 13y ago
        Well, if you need more precision than singles provide, then yeah, use doubles. The question was, "why use doubles when singles are okay?"
- zvrba 13y ago
  In engineering applications, it's perfectly sensible to use float for world modelling, which give you precision of about 1 in 10 million. Then you can use double for intermediate results and lose less precision in a long calculation, producing a more accurate result (rounded to float) in the end. Also, if the dynamic range of your data allows it [and for physical application it usually does], you can first rescale it to [0,1] in order to further increase precision. [It's the interval where floats are most dense.] Having worked for a few years now in computational geometry, i'm more and more convinced that "float by default" is the way to go. Doubles should be used for intermediate computations.
  - sampo 13y ago
    > rescale it to [0,1] in order to further increase precision. [It's the interval where floats are most dense.] Who not to scale to [0,0.5], where they are even more dense? ;-)
    - brucedawson 13y ago
      Amateur. Scale to [0,FLT_MIN*2]. There they are truly most dense, and the density is uniform across the entire range. It's almost like using 24-bit integers.
- ygra 13y ago
  Last place I had to use them was OpenGL stuff on Android. No doubles even supported, as far as I could tell.
- nly 13y ago
  Anyone who doesn't need more than 6 digits of decimal precision but can't be arsed to scale everything in to a fixed point format.
- epsylon 13y ago
  The whole games industry uses 99.999% floats.
  - dj-wonk 13y ago
    Ironically, like a float, I suspect the precision of your `99.999%` estimate is dubious.
- malkia 13y ago
  Oh wow. Just about anyone in game development :) - lol... lol since I've had the exact opposite arguments with my own folks - but it wasn't for in game use, but rather game tools. But I think I was wrong at the end. Storing all model geometry vertices in floats would be too much of a loss, also stick to 16-bit vertex indices (instead of 32-bit).
- wglb 13y ago
  In many applications, single is good enough. If you have a mass of values that needs to be stored somewhere, and the accuracy of single precision is fine, then single precision it should be. If there is a long chain of calculations that use those numbers, you might do the intermediate calculations in double, or even long double.
deleted 13y ago
[deleted]
zomgbbq 13y ago
If it takes 90s to test 2^32 floats then it should only take about 12,257 years to test 2^64 doubles.
- Someone 13y ago
  It's perfectly parallelizable. Go to AWS, fire up 2^20 four core instances for a day, and you are all set :-)
  - kordless 13y ago
    Assuming you could do it, would it be worth it to do it?
  - croddin 13y ago
    That would only cost 7.5 million dollars using c3.xlarge instances! I am actually surprised that it is that close to being feasible.
    - _delirium 13y ago
      Are there any estimates on how much on-demand capacity Amazon typically has? If I tried to spin up instances as fast as the API will let me, how long until I run out of quickly provisioned instances? Can I get thousands on short notice? Tens of thousands? Millions?
      - deleted 13y ago
        [deleted]
    - techdragon 13y ago
      You would need to ask them very nicely ahead of time for permission to spin up that many instances. The default limits are rather a lot lower than that. 20 instances per global region. Going to need a fair few more than that.
  - kazagistar 13y ago
    Isn't distributing hardware tests missing the point?
vanderZwan 13y ago
> However the ceil function gave the wrong answer for many numbers it was supposed to handle, including odd-ball numbers like ‘one’. Given all the special and unique features of the number one, I sincerely cannot tell if he's being sarcastic or not.
- ghayes 13y ago
  I believe he's (dramatically) saying that you'd expect someone to have checked that number manually, if not by other means.
  - sampo 13y ago
    Maybe they were like "of course it works for simple cases like 1, let's just test some more difficult numbers".
    - ajuc 13y ago
      That's why unit testing is so great.
      - tripzilch 13y ago
        Because one is the unit number.
maho 13y 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. Wat. I had never even heard about this, but the more I read and think about it, the more this rule makes sense to me. How did I miss this - is this commonly taught in school and I just did not pay attention? It seriously worries me that I don't even know how to round properly - I always thought of myself as a math-and-sciency guy...
- ghayes 13y ago
  I learned about this in HS chem class and it's always stuck, even if people don't use it in informal settings. Also called "unbiased rounding" or "bankers' rounding" [1] [1] http://en.wikipedia.org/wiki/Rounding#Round_half_to_even http://en.wikipedia.org/wiki/Rounding#Round_half_to_even
- hvidgaard 13y ago
  it's rarely taught in school. Most people know that you round .5 up, but that is a slightly uneven distribution and rounding to the even number however produce a perfectly even distribution. It's also the way you round in the financial sector.
  - pkolaczk 13y ago
    Financial sector of many (all?) countries in UE is required to round all .5 up. If you use banker's rounding, you might get into trouble with the tax office. So always check the local regulations for the rounding mode.
    - hvidgaard 13y ago
      I'm not sure what UE is. But as usual, always get the actual specifications for whatever you're doing.
      - skrebbel 13y ago
        Unia Europejska.
cperciva 13y ago
I did something quite similar when I was finding worst-case inputs for complex multiplication rounding errors. Here I had to search over tuples of four floating-point values; but I could ignore factors of two (since they don't affect relative rounding errors) and I had some simple bounds on the inputs such that I had only a hundred billion tuples left to consider -- a small enough number that it took a few hours for my laptop to perform the search. Replicating this for double-precision inputs would have been impossible, of course; but fortunately knowing that the worst-case single precision rounding error occurred in computing (3/4 + 12582909 / 16777216 i) * (5592409 / 8388608 + 5592407 / 8388608 i) made it easy to anticipate what the worst cases would be in general -- and as usual, knowing the answer made constructing a proof dramatically easier.
kordless 13y ago
It seems like a perfect fit for a genetic algorithm. Even for the speed stuff.
- dj-wonk 13y ago
  A perfect fit? Care to expand on your idea? I'd like to see what you had in mind.
zamalek 13y ago
The problem with this is that there are a select few cases where a machine can (or should) determine the expected value for a test assertion. - My function does something complicated: chances are you will be replicating your function in your test code. Hand-code assertions. - My function can be tested using a function that is provided by the runtime/framework: great! Remove your function and use the one in the framework/runtime instead. - My function can be tested using a function that is provided by the runtime/framework, but is written for another platform or has some performance trick: test as described in the article. - My function should never return NaNs or infinities: test as described in the article. > And, you can test every float bit-pattern (all four billion!) in about ninety seconds. [...] A trillion tests can complete in a reasonable amount of time, and it should catch most problems. Your developers will never run said tests. Unit tests are supposed to be fast. However, these exhaustive tests could be run on the CI server.
- chriswarbo 13y ago
  The code in the article is about optimisation, in which case there should always be a slow reference implementation. Never try to write highly optimised code on the first go: make it work, make it correct, then make it fast. Also, these aren't unit tests; they're property tests.
  - zamalek 13y ago
    > The code in the article is about optimization [...] Very true but that really should have been stated up-front by the author. Next thing you know "some guy at Valve said all unit tests with floats should test all 4 billion cases." You would be surprised at how much people take away from a skim over something - e.g. a poor understanding of Apps Hungarian created the monster that is Systems Hungarian. > in which case there should always be a slow reference implementation. Good point - however, keep in mind that bug fixes would need to be made in two places. Not only does it mean the maintainer needs to grok two pieces of code, but they may have to determine if the original code is providing bad truths. Hopefully there wouldn't be many places where this type of testing would be required as the low hanging fruit is often enough: however keep in mind certain industries do optimize to ridiculous degrees - and in some of those industries optimization can happen first depending on the developers [well-seasoned] intuition, and can be a frequent habit. The author's industry is a brilliant example of where the typical order of optimization (make it work, make it correct, make it fast) takes a back seat - life is incredibly different at 60/120Hz.
nraynaud 13y ago
I like his notion that IEEE errors result from sloppiness. So here are 2 "non-sloppy" version of the computation of the sign of a determinant: https://github.com/bjornharrtell/jsts/blob/master/src/jsts/algorithm/RobustDeterminant.js https://github.com/bjornharrtell/jsts/blob/master/src/jsts/a... http://www.cs.cmu.edu/afs/cs/project/quake/public/code/predicates.c http://www.cs.cmu.edu/afs/cs/project/quake/public/code/predi... Remember, the determinant value is not the rounded value of the exact computation with those things unless it is is zero, it's still "sloppy" if it's far from zero. You get only 1 bit of guaranteed accuracy in a 64bits FP number if the result is not zero. I think there is a little bit to "sloppiness" in the fact that we carry very inexact results in FP. Even "good enough" FP computation is PhD level.
ElliotH 13y ago
I did some work for my third year dissertation on performing exhaustive testing on floats. Worked well enough, but I was never convinced that it was an especially effective way of testing. If your test oracle is code itself, then it's not unlikely you'll make the same bug twice. I can't find the paper I'm after, but NASA did some work here. If your test oracle isn't code, you have the problem of working out the correct outputs for the entire function space (at which point maybe you'd be better off with some kind of look-up table anyway) The next problem is your input combinations grow much faster than you are able to test. Most functions don't just work on one float (which is very feasible) but they might work on three or four streams of input, and keep internal state. The moment you have these combinations you run into massive problems of test execution time, even if you can parallelise really well. Butler and Finelli did some work http://www.cs.stonybrook.edu/~tashbook/fall2009/cse308/butler-finelli-infeasibilit.pdf http://www.cs.stonybrook.edu/~tashbook/fall2009/cse308/butle... also at NASA investigating if doing a sample of the input space was worthwhile, but their conclusion was that it isn't helpful, and that any statistical verification is infeasible. In my report I ended up concluding that it isn't a particularly useful approach. It seems that following good engineering practice has better returns on your investment.
wglb 13y ago
This should be one of the required units of study in Floating Point School. Quick--why would you sort an array of floating point numbers before adding them up? And in which order?
- alanh 13y ago
  Ooh, nice question. Floats are a quantity and a magnitude. Adding two floats requires (at least) the larger of the two magnitudes because larger values are more important than smaller ones. So the smaller float essentially gets converted to a small quantity and a large magnitude. In an extreme case, this small quantity becomes zero. So when adding a very large number and a very small number, the result will be the same as adding zero to the very large number. If you add numbers largest to smallest, then thanks to this, at a certain point you are simply doing $SUM = $SUM + 0 over and over. But if you start with the smallest numbers, they have a chance to add up to a value with a magnitude high enough to survive being added to the largest numbers.
  - wglb 13y ago
    Exactly.
donpdonp 13y ago
This post feels particularly applicable since I just came across a huge bug in ruby's BigDecimal package. If you use ruby 2.1, be sure to upgrade to BigDecimal 1.2.4. https://www.ruby-forum.com/topic/4419577#1133001 https://www.ruby-forum.com/topic/4419577#1133001 The bug is basically: if the divisor is less than 1, the result will be 0.0. https://gist.github.com/donpdonp/c36b33b861cea49c0a86 https://gist.github.com/donpdonp/c36b33b861cea49c0a86

235 points by thedufer 13y ago

> A trillion tests can complete in a reasonable amount of time, and it should catch most problems. When your individual test is a handful of instructions, you can make such impressive claims. I only wish $work's test suite was so svelte!

jwmerrill 13y ago

Who's using single precision floats these days?

plorkyeran 13y ago
They're the standard choice for 3d graphics in games.
lelandbatey 13y ago
Yeah, I was going to say. The wisdom that I'm being taught in school is "Don't use single precision floats, at least not when you're on any kind of a modern system."
- nkurz 13y ago
  That's OK wisdom unless you are aiming for high performance. I'd put it at about the same level as "Don't use C if something higher level will work." If you are hoping to gain from vectorization, or if you have enough of them to care about memory usage, single precision is twice as good, unless the extra precision of a double actually gains you something.
  - lelandbatey 13y ago
    Once again, I fell into the trap of saying "you should often do x" while leaving off the "... Except when you shouldn't". The exact comment from the CS professor I have in mind was "Using doubles when doing realtime human facing calculations (such as a calculator) is the best way to go. However, floats have their uses, such as on systems where there isn't enough memory, or where a float fulfills the requirements." but that's a bit much to type from a phone so I went for "use doubles". And now I'll never be so lazy with my comments again!
- ajuc 13y ago
  If you don't care about precision use single floats. That's most of the time in games. Some people even used ints as fixed precision fractions. If you care about precision - doubles still aren't precise - for currency use bigdecimals, for some stuff ratios can give precise results, for irrational things your only options are doubles, but be aware that you aren't precise, even for simply looking operations. No way to compute 10% of something precisely with doubles.
  - socillion 13y ago
    You wouldn't use ints for currency?
    - hvidgaard 13y ago
      You shouldn't use fixed integers. What happens when you need to represent a fraction smaller than what your largest integer can? For financial calculation you use a dynamic integer type that expand as needed.
      - vidarh 13y ago
        For many financial applications, you know precisely in advance how many decimal points you need to be able to accommodate. E.g. for UK VAT calculations, you are never required to work it out to more than four decimal points (and can then round to 3). I sort-of agree with you, in that it is easy to get bitten, and that if people have a dynamic integer type available on their platform that's probably safest. If the choice is between using integers for fixed point vs. using double's though, I'd go for the fixed point any day.
    - justincormack 13y ago
      64 bit ints in cents/pence/whatever should be OK. 32 bit ints are too small. Even in Zimbabwe which issued $100tn bills 64 bits should be enough.
    - ajuc 13y ago
      You can, but: - it's still advisable to wrap ints in some class to be able to distinguish ints that are already multipied and ints that aren't. It's also better cause then you can overload operators. I've written graphic demu using fixed point numbers (floats) without wrapping them, and it was very painful and error prone. So you still work on objects and not on primitive values. - there's a problem with how much precision you need. Different countries specify their way to round up doing money calculation differently (even with the same currencies - see Euro). When you use ints you have the assumption about precision repeated all over your codebase, which make it harder to change when tax law changes or you want to support other countries. With BigDecimals most of the code is universal.
- dagw 13y ago
  Like all good wisdom, there are plenty of exceptions. I use single precision all the time. The most obvious advantage to me is that I can load twice as large data sets into memory, which has some definitive performance advantages.
- forrestthewoods 13y ago
  Oh god. The future is doomed.
nabla9 13y ago
Anyone who wants to do fastest possible floating point arithmetic with graphics card. Also, if the memory, disk access, or IO-troughtput is the bottleneck with number crunching, single floats might give huge advantage.
wlievens 13y ago
We do all our image processing using floats (as memory and disk storage - not as computation accumulators obviously). It helps a lot if you keep a dozen seventy-megapixel images in memory, because it means you can run twice as many jobs on your cluster.
LnxPrgr3 13y ago
Depends on the application. If I'm processing audio in a PBX, 64-bit floating point precision isn't going to do me much good when my source is a noisy 8-bit µ-law stream. All I'd gain is twice the demand for memory space and bandwidth—not a cost I'm willing to pay when I gain zero developer productivity from it. Even CD-quality audio only has 16 bits per sample. My digital camera only records 12 bits per pixel, and that's before the image is converted to a more reasonable 8-bit-per-channel format. Single precision is still overkill in a number of applications.
- yread 13y ago
  but these are all fixed point! When doing arithmetics you can lose as much as 1 bit of precision per floating point operation. So, it pays off to do use more precision for calculations even when the storage format doesn't persist it. Besides I remember reading somewhere that 32-bit floats instructions aren't actually any faster than 64-bit (except of course the cache...). They even might be slower because the FPU has to extend them to 64-bit before performing the operation
  - LnxPrgr3 13y ago
    To be clear: are you talking FPU instructions, or more modern SSE(N) instruction sets? Modern compilers on modern CPUs pretty aggressively vectorize my number crunching. If it's something you're worried about, I'd suggest measuring the difference in your actual application, both in terms of performance and accuracy. If I can come up with a decent test case I can legally publish, I'll post results, but your mileage may still vary.
  - sharpneli 13y ago
    The time when the actual floating point instructions were a bottleneck are long gone. Nowadays when you do computations with single float/double values in your registers they are equally fast. The biggest difference comes from memory bandwith and the ability to vectorize. Your CPU can calculate either 4 floats or 2 doubles in one instruction (assuming pre AVX X64 processor). With AVX it's 8 floats or 4 doubles.
- 13y ago
Negitivefrags 13y ago
Your comment makes me feel sad. It just reflects a whole mindset that makes me feel like an oppressed minority somehow. It sucks that most people don't really care about performance any more. It sucks when people causally dismiss people who do care about performance with arguments like "premature optimization" and so on. It kind of sucks that the web is taking over because it gives an excuse to use slow languages. It almost makes me feel sick to think that Javascript stores all numbers as doubles. So you know what? It makes me feel happy to use the most efficient type that will work. I like my single precision floats. I can die happy knowing that I didn't waste everyone's collective network, disks and CPUs with needless processing. Can't it be good to save just for the sake of saving? So you want a practical reason do you? I shaved over 2 gigabytes off the size off the download size of our product simply by using more efficient data types. Using half size floats is good enough for some data (16 bits). And let me tell you about a data type that we used to use called a char. 8 bits would you believe! Turns out those x86 CPUs that are sitting there a few VMs deep still support those things.
- hvidgaard 13y ago
  It's not even about performance. It's about actively thinking about what data you'd be processing. Why use doubles when singles are okay? I'd sure not be using 64 bit ints just because "it's bigger" when a normal 32 bit would be just fine.
  - marcosdumay 13y ago
    > Why use doubles when singles are okay? Because of rounding issues, that look like a no problem for a single precision number, but will be a no problem^2 for a double precision one. Thus, if I'm wrong (or get wrong after a change in scope), the program will still work.
    - cwp 13y ago
      Well, if you need more precision than singles provide, then yeah, use doubles. The question was, "why use doubles when singles are okay?"
zvrba 13y ago
In engineering applications, it's perfectly sensible to use float for world modelling, which give you precision of about 1 in 10 million. Then you can use double for intermediate results and lose less precision in a long calculation, producing a more accurate result (rounded to float) in the end. Also, if the dynamic range of your data allows it [and for physical application it usually does], you can first rescale it to [0,1] in order to further increase precision. [It's the interval where floats are most dense.] Having worked for a few years now in computational geometry, i'm more and more convinced that "float by default" is the way to go. Doubles should be used for intermediate computations.
- sampo 13y ago
  > rescale it to [0,1] in order to further increase precision. [It's the interval where floats are most dense.] Who not to scale to [0,0.5], where they are even more dense? ;-)
  - brucedawson 13y ago
    Amateur. Scale to [0,FLT_MIN*2]. There they are truly most dense, and the density is uniform across the entire range. It's almost like using 24-bit integers.
ygra 13y ago
Last place I had to use them was OpenGL stuff on Android. No doubles even supported, as far as I could tell.
nly 13y ago
Anyone who doesn't need more than 6 digits of decimal precision but can't be arsed to scale everything in to a fixed point format.
epsylon 13y ago
The whole games industry uses 99.999% floats.
- dj-wonk 13y ago
  Ironically, like a float, I suspect the precision of your `99.999%` estimate is dubious.
malkia 13y ago
Oh wow. Just about anyone in game development :) - lol... lol since I've had the exact opposite arguments with my own folks - but it wasn't for in game use, but rather game tools. But I think I was wrong at the end. Storing all model geometry vertices in floats would be too much of a loss, also stick to 16-bit vertex indices (instead of 32-bit).
wglb 13y ago
In many applications, single is good enough. If you have a mass of values that needs to be stored somewhere, and the accuracy of single precision is fine, then single precision it should be. If there is a long chain of calculations that use those numbers, you might do the intermediate calculations in double, or even long double.

deleted 13y ago

[deleted]

zomgbbq 13y ago

If it takes 90s to test 2^32 floats then it should only take about 12,257 years to test 2^64 doubles.

Someone 13y ago
It's perfectly parallelizable. Go to AWS, fire up 2^20 four core instances for a day, and you are all set :-)
- kordless 13y ago
  Assuming you could do it, would it be worth it to do it?
- croddin 13y ago
  That would only cost 7.5 million dollars using c3.xlarge instances! I am actually surprised that it is that close to being feasible.
  - _delirium 13y ago
    Are there any estimates on how much on-demand capacity Amazon typically has? If I tried to spin up instances as fast as the API will let me, how long until I run out of quickly provisioned instances? Can I get thousands on short notice? Tens of thousands? Millions?
    - deleted 13y ago
      [deleted]
  - techdragon 13y ago
    You would need to ask them very nicely ahead of time for permission to spin up that many instances. The default limits are rather a lot lower than that. 20 instances per global region. Going to need a fair few more than that.
- kazagistar 13y ago
  Isn't distributing hardware tests missing the point?

vanderZwan 13y ago

> However the ceil function gave the wrong answer for many numbers it was supposed to handle, including odd-ball numbers like ‘one’. Given all the special and unique features of the number one, I sincerely cannot tell if he's being sarcastic or not.

ghayes 13y ago
I believe he's (dramatically) saying that you'd expect someone to have checked that number manually, if not by other means.
- sampo 13y ago
  Maybe they were like "of course it works for simple cases like 1, let's just test some more difficult numbers".
  - ajuc 13y ago
    That's why unit testing is so great.
    - tripzilch 13y ago
      Because one is the unit number.

maho 13y 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. Wat. I had never even heard about this, but the more I read and think about it, the more this rule makes sense to me. How did I miss this - is this commonly taught in school and I just did not pay attention? It seriously worries me that I don't even know how to round properly - I always thought of myself as a math-and-sciency guy...

ghayes 13y ago
I learned about this in HS chem class and it's always stuck, even if people don't use it in informal settings. Also called "unbiased rounding" or "bankers' rounding" [1] [1] http://en.wikipedia.org/wiki/Rounding#Round_half_to_even http://en.wikipedia.org/wiki/Rounding#Round_half_to_even
hvidgaard 13y ago
it's rarely taught in school. Most people know that you round .5 up, but that is a slightly uneven distribution and rounding to the even number however produce a perfectly even distribution. It's also the way you round in the financial sector.
- pkolaczk 13y ago
  Financial sector of many (all?) countries in UE is required to round all .5 up. If you use banker's rounding, you might get into trouble with the tax office. So always check the local regulations for the rounding mode.
  - hvidgaard 13y ago
    I'm not sure what UE is. But as usual, always get the actual specifications for whatever you're doing.
    - skrebbel 13y ago
      Unia Europejska.

cperciva 13y ago

I did something quite similar when I was finding worst-case inputs for complex multiplication rounding errors. Here I had to search over tuples of four floating-point values; but I could ignore factors of two (since they don't affect relative rounding errors) and I had some simple bounds on the inputs such that I had only a hundred billion tuples left to consider -- a small enough number that it took a few hours for my laptop to perform the search. Replicating this for double-precision inputs would have been impossible, of course; but fortunately knowing that the worst-case single precision rounding error occurred in computing (3/4 + 12582909 / 16777216 i) * (5592409 / 8388608 + 5592407 / 8388608 i) made it easy to anticipate what the worst cases would be in general -- and as usual, knowing the answer made constructing a proof dramatically easier.

kordless 13y ago

It seems like a perfect fit for a genetic algorithm. Even for the speed stuff.

dj-wonk 13y ago
A perfect fit? Care to expand on your idea? I'd like to see what you had in mind.

zamalek 13y ago

The problem with this is that there are a select few cases where a machine can (or should) determine the expected value for a test assertion. - My function does something complicated: chances are you will be replicating your function in your test code. Hand-code assertions. - My function can be tested using a function that is provided by the runtime/framework: great! Remove your function and use the one in the framework/runtime instead. - My function can be tested using a function that is provided by the runtime/framework, but is written for another platform or has some performance trick: test as described in the article. - My function should never return NaNs or infinities: test as described in the article. > And, you can test every float bit-pattern (all four billion!) in about ninety seconds. [...] A trillion tests can complete in a reasonable amount of time, and it should catch most problems. Your developers will never run said tests. Unit tests are supposed to be fast. However, these exhaustive tests could be run on the CI server.

chriswarbo 13y ago
The code in the article is about optimisation, in which case there should always be a slow reference implementation. Never try to write highly optimised code on the first go: make it work, make it correct, then make it fast. Also, these aren't unit tests; they're property tests.
- zamalek 13y ago
  > The code in the article is about optimization [...] Very true but that really should have been stated up-front by the author. Next thing you know "some guy at Valve said all unit tests with floats should test all 4 billion cases." You would be surprised at how much people take away from a skim over something - e.g. a poor understanding of Apps Hungarian created the monster that is Systems Hungarian. > in which case there should always be a slow reference implementation. Good point - however, keep in mind that bug fixes would need to be made in two places. Not only does it mean the maintainer needs to grok two pieces of code, but they may have to determine if the original code is providing bad truths. Hopefully there wouldn't be many places where this type of testing would be required as the low hanging fruit is often enough: however keep in mind certain industries do optimize to ridiculous degrees - and in some of those industries optimization can happen first depending on the developers [well-seasoned] intuition, and can be a frequent habit. The author's industry is a brilliant example of where the typical order of optimization (make it work, make it correct, make it fast) takes a back seat - life is incredibly different at 60/120Hz.

nraynaud 13y ago

I like his notion that IEEE errors result from sloppiness. So here are 2 "non-sloppy" version of the computation of the sign of a determinant: https://github.com/bjornharrtell/jsts/blob/master/src/jsts/algorithm/RobustDeterminant.js https://github.com/bjornharrtell/jsts/blob/master/src/jsts/a... http://www.cs.cmu.edu/afs/cs/project/quake/public/code/predicates.c http://www.cs.cmu.edu/afs/cs/project/quake/public/code/predi... Remember, the determinant value is not the rounded value of the exact computation with those things unless it is is zero, it's still "sloppy" if it's far from zero. You get only 1 bit of guaranteed accuracy in a 64bits FP number if the result is not zero. I think there is a little bit to "sloppiness" in the fact that we carry very inexact results in FP. Even "good enough" FP computation is PhD level.

ElliotH 13y ago

I did some work for my third year dissertation on performing exhaustive testing on floats. Worked well enough, but I was never convinced that it was an especially effective way of testing. If your test oracle is code itself, then it's not unlikely you'll make the same bug twice. I can't find the paper I'm after, but NASA did some work here. If your test oracle isn't code, you have the problem of working out the correct outputs for the entire function space (at which point maybe you'd be better off with some kind of look-up table anyway) The next problem is your input combinations grow much faster than you are able to test. Most functions don't just work on one float (which is very feasible) but they might work on three or four streams of input, and keep internal state. The moment you have these combinations you run into massive problems of test execution time, even if you can parallelise really well. Butler and Finelli did some work http://www.cs.stonybrook.edu/~tashbook/fall2009/cse308/butler-finelli-infeasibilit.pdf http://www.cs.stonybrook.edu/~tashbook/fall2009/cse308/butle... also at NASA investigating if doing a sample of the input space was worthwhile, but their conclusion was that it isn't helpful, and that any statistical verification is infeasible. In my report I ended up concluding that it isn't a particularly useful approach. It seems that following good engineering practice has better returns on your investment.

wglb 13y ago

This should be one of the required units of study in Floating Point School. Quick--why would you sort an array of floating point numbers before adding them up? And in which order?

alanh 13y ago
Ooh, nice question. Floats are a quantity and a magnitude. Adding two floats requires (at least) the larger of the two magnitudes because larger values are more important than smaller ones. So the smaller float essentially gets converted to a small quantity and a large magnitude. In an extreme case, this small quantity becomes zero. So when adding a very large number and a very small number, the result will be the same as adding zero to the very large number. If you add numbers largest to smallest, then thanks to this, at a certain point you are simply doing $SUM = $SUM + 0 over and over. But if you start with the smallest numbers, they have a chance to add up to a value with a magnitude high enough to survive being added to the largest numbers.
- wglb 13y ago
  Exactly.

donpdonp 13y ago

This post feels particularly applicable since I just came across a huge bug in ruby's BigDecimal package. If you use ruby 2.1, be sure to upgrade to BigDecimal 1.2.4. https://www.ruby-forum.com/topic/4419577#1133001 https://www.ruby-forum.com/topic/4419577#1133001 The bug is basically: if the divisor is less than 1, the result will be 0.0. https://gist.github.com/donpdonp/c36b33b861cea49c0a86 https://gist.github.com/donpdonp/c36b33b861cea49c0a86