Representing 0.1 (or rather, 1/10) has the same problem in binary that representing 1/3 has in decimal. Your denominator doesn't divide any power of your radix, so your representation has to be either infinite, or inaccurate. If you've ever tried to do complex decimal math by copying results like 0.6666667 into and out of a calculator, you've probably run into the same issues.
Hah! If Mike Cowlishaw was here he could give you a wonderfully eloquent treatment on why binary floating point sucks. And he's actually done something about it [1] with both a format and software to deal with decimal numbers.
Further the densely packed form gets very close to optimal in terms of bit representation. Assume that 4 bits (BCD) is 'worst' case, you can represent 0-9 but you 'waste' the information space 'a-f' (in hex, 10-15 in decimal) but 3 bits only gives you 8 states. What you want is a total of 10 states which is 3.3125 bit's worth (best case) or 3 digits in 9.9375 bits, these formats give you 3 digits in 10 bits which is pretty close.
Mike goes on to talk about how to build hardware that does floating point operations on this stuff. I built some into an FPGA and it really is pretty straight forward, especially if you do iterative multiply and divide.
Consider the interesting thing where you take 128 bits (two 64 bit words) where you use 60 bits for the whole part (18 digits) and 60 bits for the fractional part (18 digits) and you've got 8 bits left over for various non-number entities (+inf, -inf, NaN, etc). Would be great for CAD package, or a financial spreadsheet.
It is used in high end CAD systems where tolerances need to be exact, there was also a wonderful decimal package for COBOL which was doing financial computations. Unknown to many (most?) people some early IBM Mainframes [1] were decimal machines.
If you work in 3D modeling you will be familiar with the effects of binary floating point as 'gaps' between polygons where they shouldn't be. Sometimes those gaps only appear at a certain scale because that is where the rounding gets it wrong, or if you compensate by always rounding up you get overlaps or texture issues.
It depends on the underlying representation. I know it's almost never anything except IEEE 754 now, but it could be different.
When I was an undergrad doing the ACM programming contest, one year we had this triangle problem where, given the length of the three sides, you had to print whether it was an equilateral, isosceles, right, or not a triangle at all. Lots of naive programmers (including me) just checked if (aa + bb) == c*c for a right triangle. The kicker is, for the (secret) test data, that worked fine if you used single-precision floats and failed if you used double-precision floats.
That educated a whole region of ACM contest competitors on floating point representations.
Sure it does - in that any floating point scheme is a well defined partition of the real line in the range [-FLT_MAX, +FLT_MAX] into 2^n intervals (less two Infs, a load of NaNs and a spare zero), one of which absolutely contains 0.1
There are an infinite number of real values in the range [-FLT_MAX, +FLT_MAX], but only 2^n values can be represented with n bits. That means there are an infinite number of values in that range that cannot be represented with any number of bits.
People often forget that IEEE 754 supports representations where b = 2 or 10. 1*10^-2 should be easy enough to store in any of the defined decimal layouts.
A lot of people, when they're starting out, have no idea how computers store digits. I can easily store 1/3 in decimal - 0.3 with a bar over the 3. But, as the article points out, computers don't store bars.
But did you learn that on the first day that you sat down at a computer?
Just because something is obvious to one person, it doesn't mean every person has considered it long enough to make the connection between them. This article might just make a whole bunch of people "click", and understand why they are getting unexpected results.
I found it insightful. Why can't you write down 1/10 in binary? What is 1/10 in binary? OP calculates it, and then explains that any fraction in reduced form in which the denominator is a power of 2 will terminate in binary. (Powers of 5 and 2 for decimal). These are interesting bits of trivia.
I think it's a great article and it's nice to see a that it has up votes, as a lot of programmers, including those without a computer science background, have no idea about binary or how computers represent decimals.
The article opens with a good summary of the problem:
Questions [about floating point issues] are asked every day, on online forums like stackoverflow.com.
The answer is that most decimals have infinite representations in binary.
This is the type of thing I learned in my first semester of undergrad as a CompE. This information is not a revelation for 90% of people with programming experience unless I'm greatly overestimating our collective knowledge.
kmfrk: You have a point. I guess my point was that _I_ don't think HN is a venue for sharing articles aimed at beginners. But the upvotes prove me wrong :) The article is pretty well written.
In fact, it's something that should be pounded into the skulls of programmers at every opportunity. It's something we tend to forget often enough (if we learned it) that we should be reminded of it frequently.
I would be MUCH more interested to get some insight as to WHY a binary numbering system, which can't represent accurately a number so trivial as 0.1, have ever become ubiquitous for general-purpose floating-point applications. Or why it's no worse than any other system.
Any taker?
The original article in itself is pretty interesting, but of very limited appeal to the HN crowd. The visitors here being mostly technical types, anyone with a Comp. Sci. or Comp. Eng. degree has already gone through those computations many times over during their career.
> I am writing a simple financial application in a language without a decimal type (Go), and my workaround for this is to multiply by 100 when storing currency. The thought process was that at least cents will be represented exactly.
Yes, that will work -- until you need to compute taxes, discounts, or any other quantity that involves amounts less than a penny during interim computations. Then you're back to square one.
> Things like currency exchange would still benefit from a proper decimal type though.
Yes, but binary floating-point doesn't really pose a problem if handled carefully. The classic solution is to store all amounts internally in double-precision floating-point and only display the rounded values -- never truncate the values to the nearest penny as student programmers tend to do.
In the system described above, that used in all major financial packages, amounts like 0.1 simply aren't an issue, and every number base has amounts it can't represent exactly.
