▲ 53 points
back
40 comments
I code-review altcoins[1] as a hobby and stuff like this is why I give a ding to coins using floating point operations in, say, reward code, especially when it's something relatively complicated like multiplication or division. I'm just waiting for different processors to differ in the last decimal place to cause a fork on the coin's network.
As far as I know, all the modern processors follow the IEEE 754 standard, which is a serious and reliable standard, so if anything like that happens, it shouldn't be a processor issue.
The implementations of the languages are something else, however. I suggest the fine article by Bruce Dawson:
https://randomascii.wordpress.com/2013/07/16/floating-point-...
Clarification: The opening few slides (titled “who is NOT using floating point numbers”) contain a list of prominent software that uses floating-point. The author is not an idiot. Presumably this was more clear with the verbal portion of the talk intact, but it would appear to be rhetorical device: “who uses floating point? It would be easier to list who doesn’t; lots of prominent software uses floating-point…”
If you don’t know who Paul Zimmermann is, you may safely assume that he knows more about floating-point than you do (actually that he knows more about computer arithmetic than you do). While there may well be errors or typos in the slides, it’s far more likely that you are misinterpreting something without the context of the talk that went along with them.
Much of the problem with floating point is that we intuitively expect it to follow the math rules we're familiar with, but they seem to, but often don't.
Most programmers realize they are 'approximate' but they don't notice consequences, such as checking for exactly equal to zero, when you need to check for "close enough" depending on your context.
More subtly, but perhaps more damaging, they break properties like associative and commutative. Different orders change values, you can add tiny values repeatedly to a large value, and it won't change, breaking testing of the value...
The presentation goes over many of these, but the fundamental problem, to me, is that we're falsely presenting an interface suggesting "this acts like a number" when it doesn't in many key ways. We should perhaps call them approximate pseudo numbers or something. Don't allow operators, require functions like SortOfMaybeAdd, AcculumateList...
Perhaps such measures will communicate better. A fascinating world we program in...
I've long wanted a language that defaults to a decimal type (or perhaps forces the user to specify a precision), and provides hardware floating point only as an option where requested. Something like the way Python handles integers.
Most of what C-family languages do has the wrong semantics. Any program which is happy to accept round-to-even and arbitrary increases in precision would probably accept the rearrangement of arithmetic under the assumption that it was commutative, but in e.g. Java there's no way to change rounding mode, and also no way to just request an approximate answer. The defaults are a compromise that satisfies no-one.
The problem is that decimal types don't make things any better, at least when you have finite precision. They have the same problems with rounding error. The error analysis is exactly the same when designing your algorithms, only in a different base.
The only thing that they make easier is parsing and displaying numbers. The number of times where you deal with things that are guaranteed to be perfectly represented by powers of ten are relatively few.
> The number of times where you deal with things that are guaranteed to be perfectly represented by powers of ten are relatively few.
For a physicist, a few. For an accountant, all.
> I've long wanted a language that defaults to a decimal type (or perhaps forces the user to specify a precision), and provides hardware floating point only as an option where requested.
Scheme (via its numeric tower) and some other language default to exact types (decimal or in some cases rational if they don't have a separate exact decimal type) and only use approximate floating point types if explicitly requested (including using by using a function which inherently produces an approximate output.)
Haskell can be configured by way of the default specifier to do something analogous to this in its handling of ambiguous numeric types (which includes literals, which start out with a generic type of Num a => a) , though the default default uses double precision floating point for types that can't be constrained to arbitrary precision integers -- default (Integer, Double) -- so to do this you need something like default (Integer, Rational, Double.)
In haskell, every literal is constructed via an Integer (big int) or Rational, which is then converted into the final representation. (roughly). I'm actually slowly doing some auditing of GHC Haskell's floating point machinery as I find the time.
That makes sense as the underlying implementation approach, but I was more referring to the "final" representation (I've also edited the description as it regards Haskell with more details, since its not really about literal handling specifically, though that's subsumed within it.)
> More subtly, but perhaps more damaging, they break properties like associative and commutative.
No: commutativity of multiplication and addition still holds, but associativity indeed does not. That associativity does not hold is a much more unpleasant than if associativity would hold but commutativity wouldn't (the mathematics of common associative, but non-commutative structures is understood quite well, say (non-abelian) groups and monoids).
Actually commutativity doesn't hold either, because of dealing with NaNs (at least on x86, on a quick search I can't find a reference for whether this behavior is part of IEEE 754 or just implementation defined). Operations with two NaNs will give the first operand. You can see this with a quick test program:
#include <stdio.h>
int main() {
unsigned long long bits = 0x7FFC000000000000;
double x = *(double *)&bits;
bits += 1;
double y = *(double *)&bits;
double z = x + y, w = y + x;
printf("%llx %llx\n", *(unsigned long long *)&z, *(unsigned long long *)&w);
}
IEEE-754 says that the result “should” be one of the two input NaNs. A platform could choose to e.g. take the NaN with the smaller payload to make * and + commutative, or it could simply define away NaN payloads entirely.
Ah yep. I was mixing things up a bit.
The one that surprised me was that, in some cases:
Large + small + small + small =! small + small + small + = Large
Really underscores how complex things are.
The other typically expected property that fails is distributivity.
So for floats:
a ( b + c ) != a * b + a * c
> We should perhaps call them approximate pseudo numbers or something.
More importantly, we just shouldn't make them the default types used for decimal literals (or, a fortiori, for all numbers in your language -- yes, JavaScript, I'm looking at you.)
Premature optimization is the root of all kinds of evil -- or at least errors -- in programming, and "treat decimal literals as floating point because that's the most processor-friendly way of dealing with non-integer numbers" is the most pervasive premature optimization in computing.
What alternative are you suggesting? Any finite precision numbers will have most of the same problems as IEEE floats. Decimal numbers are a specific case -- assuming them by default would be worse in some ways.
"Much of the problem with floating point is that we intuitively expect it to follow the math rules we're familiar with, but they seem to, but often don't."
Well... maybe. I don't think most people have the foggiest idea what floating point numbers are, or what the Real numbers they approximate are, so the idea that people (a) have a solid understanding of Math (let's just say Real Analysis) and that (b) this solid understanding is violated by the behavior of floating point numbers is a bit of a stretch.
E.g. I doubt many programmers realize that 1/10 doesn't have a finite binary expansion.
Is there any separate write-up of this? Trying to read the slides to a presentation is just frustrating.
(And if you can actually read the slides by themselves the presentation is probably not very good).
Interesting, though Excel most certainly does use floating point numbers for storage and calculations (both at the time of its writing and now), and has some infamous calculation errors as a result. Maybe I misunderstood the slide.
EDIT: I don't normally care much about a "downvote", but when it must be backed by ignorance I have to comment. Excel has always, and to this day, uses doubles. There is not a whit of decimal math to be found in the product. I kind of know this given that my industry is finance, and the calculation quirks of Excel (which is simply a quirk of floating point math) are something that the industry is aware of and works around.
Now it by default rounds the number for presentation, but surely no one on HN would be so confused that they fail to understand the difference.
You are right, Excel uses doubles internally, taking care to format them as good as it can. BLAS also uses floating point numbers: singles, doubles, complex (note the S, D, Z prefixes):
My understanding is that Excel mostly uses double, but with a bunch of hacks bolted on to make some results “seem” right. If anything this makes the situation worse. IIRC, for example, it’s possible to construct numbers such that any desired subset of the following three properties do or do not hold:
1. a and b have the same default displayed representation
2. a and b compare equal
3. (a - b) is zero
Don't worry about downvoters, they know not what they do. Also, it's easy to accidentally press the wrong arrow and it cannot be undone.
On topic: do you happen to know why Excel doesn't use decimal math? I'd imagine for most spreadsheets the performance difference shouldn't be noticeable.
Speculation: The performance impact would have been significant in the mid-1980s. They can’t change the arithmetic now because users would complain if their spreadsheets started producing different results (how many billions of dollars of contracts were negotiated based on the results of an Excel spreadsheet?)
BLAS doesn't use floating-point numbers? So what does it use? My impression was that BLAS was a library of fast linear algebra. Decimals are not fast, as far as I'm aware.
It does use floating point. I think the slide was misleading.
BLAS uses it, and Excel of course also uses floating point.
On the first look, it appears a dubious presentation anyway. The examples don't have much sense too: you can't actually calculate properly sin( 10e22 ) in binary floating point format because both exponent and mantissa are binary: the exponent is 2^76 and in 4-bytes floats you have 23 bits, in 8-byte doubles 53 bits, so you can't even represent the starting number with the enough bits to calculate meaningful sin. You'd need a two parameter function to be even able to pass what you actually want to pass. So calling sin( 10e22 ) in the languages with 4 or 8-bytes binary FP of course can't be expected to produce any meaningful result.
But maybe all this was spoken, not written, and it's just misleading to read it without knowing the comments.
"Who is NOT using: Excel, BLAS" could maybe then mean that author wanted to say "Excel, BLAS, they use them too"? (If we want to believe that he had any idea what he wrote about). Definitely not good to give this presentation to somebody who doesn't already know more. Confusion guaranteed.
Paul Zimmermann certainly knows that BLAS and Excel use floating-point. I assume that the spoken content of the presentation made the meaning of those slides much clearer; it’s too bad that the slides are being discussed in a vacuum.
Also 1e22 (note: not 10e22) is exactly representable in double (though not in float). Specifically, it is exactly equal to:
1.000011110000110011110000011001001101110101011001001 * 2^73
You are absolutely right, 1e22 fits in the double, exactly with the bit pattern you showed. And it doesn't fit in the float. Thanks. One more proof that PDF alone is too little of the presentation and that it's easy for the reader to remain confused. I consider your reply "a missing slide" between p 15 and p 16.
So the author is: http://en.wikipedia.org/wiki/Paul_Zimmermann
I think it does use them? What does "real" here mean?
http://www.netlib.org/lapack/explore-html/d8/daf/saxpy_8f.ht...
Seems to mean floating point according to this...: http://www-classes.usc.edu/engr/ce/108/text/fbk01.htm
Please correct me if I'm wrong, I'm not that familiar with Fortran.
It does use floats.
Floats are not that much of a problem as people might think. They come as a surprise for those that don't know how they work. Small course in numerical analysis would do people good.
Switching to fixed point would not cure anything, just change the ways they can break. Floats actually have way superior error propagation properties compared to fixed point if your range varies widely, as it often does in physics. In a massively simplified way one can say that multiplication is error free in floats whereas in fixed point multiplication is horrible.
Switching to arbitrary position decimal/rational would cure most easily curable problems (which are the ones that deal with simple arithmetic not working as expected.)
Dealing with the bigger problems (like combining arithmetic with transcendental functions and then getting bitten by approximation issues) require using a symbolic math engine and only reducing to numeric approximations when needed (e.g., for presentation) rather than for intermediate values.
"Throw floats at the problem and hope that it works okay" is a great approach for performance, but not really the best approach for correctness. Which is fine, if its a conscious decision, but its so pervasive and encouraged by most programming environments that its easy for people to forget the tradeoff that they are making.
It's a little bit of a misrepresentation on the part of the presenter. BLAS is a specification for linear algebra software, of which implementers are free to use the most appropriate representation of numbers as they wish - the fastest being floating point because of native hardware support.
Although the naming schemes for BLAS routines do explicitly reference "single precision" and "double precision" so now I'm confused too.
Why we need floating point at all now? IEEE-754 64-bit decimal appears to cover everything that's needed.
> Why we need floating point at all now? IEEE-754 64-bit decimal appears to cover everything that's needed.
IEEE-754 64-bit decimal is also a floating point representation:
They have the same kind of rounding problems - except in base 10 instead of 2.
> They have the same kind of rounding problems - except in base 10 instead of 2
Sure, but if you aren't dealing with transcendental functions but just typical input from people and arithmetic, you don't usually introduce as many errors by rounding to a base-10 representation, so decimal floating point solves a lot of the problems (at the cost of performance if you have a system that implements it over hardware that doesn't.)
You still have the big + small problem, though.
It is proven that the binary FP accumulates errors slower than any other bigger base when the longer scientific calculations are involved.
But when you want to represent something like money, there's by definition an error as soon as you want to store 0.01 as the binary FP, and the same error doesn't happen in decimal FP.
On the other hand: If your smallest unit of money is cents (or perhaps tenth of cents), you better use large integers to store the amount of money instead of base 10 floating point numbers.