Why 0.1 Does Not Exist In Floating-Point

http://www.exploringbinary.com/why-0-point-1-does-not-exist-in-floating-point/

by wglb • 14 years ago

60 32 14 years ago

sbanach3• 14 years ago

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

adaml_6233• 14 years ago

Perhaps you could prove your point by supplying 0.1 in a binary floating point format. You can choose the standard.

Lexarius• 14 years ago

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.

dbaupp2• 14 years ago

The parent is referring to an interval, since floating point is essentially a disguised interval arithmetic.

For IEEE754 64-bit doubles, the interval containing 0.1 is: [0.099999999999999991673327315311, 0.100000000000000005551115123126]

sbanach3• 14 years ago

Sure adaml_623,

0x3dcccccd in IEEE 754-2008 (binary32) corresponds to the interval (0.09999999776482582, 0.10000000521540642) - which contains 0.1.

Disclaimers: I worked this out with double precision, and if you care about if the endpoints are inclusive/exclusive, the wikipedia article will help.

sp3322• 14 years ago

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.

adaml_6233• 14 years ago

You know how you can't store 1/3 in decimal. (I think I learnt that in primary school)

Same case with 1/10 to binary.

Discussion Over. How does this story have any up votes?

erichocean• 14 years ago

I asked the same thing, and got so many downvotes I had to quickly delete it! The ways of HN are strange, sometimes.

pavel_lishin• 14 years ago

The key word in your first sentence is "store".

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?

mfonda• 14 years ago

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.

dbaupp2• 14 years ago

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.

(There's no need to be aggressive about it!)

nollidge• 14 years ago

Not everyone around here is a programmer, or has really thought about how fractions are represented in binary.

greyfade• 14 years ago

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.

juan_juarez• 14 years ago

The standard answer to programming noobs is "What Every Computer Scientist Should Know About Floating-point Arithmetic".

http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.ht...

rockmeamedee• 14 years ago

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.

kmfrk• 14 years ago

Your comment is exactly why getting into programming for the first time is a shit experience for many people.

I even had Ph.D. TAs in college with the same attitude.

Unbelievable.

kevhsu• 14 years ago

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.

lmkg• 14 years ago

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.

SilasX• 14 years ago

Yeah, I was surprised why it didn't mention that as being the same problem in a different, more familiar form.

ja272• 14 years ago

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.

sp3322• 14 years ago

As Lexarius mentioned, IEEE 754 includes decimal representations. https://en.wikipedia.org/wiki/IEEE_floating_point#Basic_form...

Evbn2• 14 years ago

How did the spec specify input format?

davidcuddeback• 14 years ago

In the ACM programming contests, input formats are usually ASCII text, read from STDIN or from a file.

ja272• 14 years ago

Yes, ASCII text of three decimal values per line (if I'm remembering correctly): 3.0 4.0 5.0 4.0 4.0 8.0

One of my favorite sort of problem was one that could easily be solved if you could handle arithmetic with integers larger than 32/64 bit types.

ChuckMcM2• 14 years ago

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.

[1] http://speleotrove.com/decimal/DPDecimal.html

matthiasl• 14 years ago

That was an interesting link, thanks. I liked other parts of the site too, for instance

http://speleotrove.com/decimal/

Any idea what decimal floating point is used for?

(I have little to no idea about CAD or financial software.

I can see that fixed-point decimal with two decimal places is useful for things where you want to be able to reason about rounding of cents.

I can also see that you'd want more than two decimal places for a lot of calculations, for instance computing interest.

But decimal floating point...what's specified in such a way that you need to use decimal floating point?

I checked the wikipedia decimal floating point page. Didn't see any concrete examples there either.)

ChuckMcM2• 14 years ago

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.

[1] http://en.wikipedia.org/wiki/IBM_700/7000_series#Decimal_arc...

millerc• 14 years ago

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.

kristianp• 14 years ago

The exact way of representing of numbers like 1/10 and 1/3 is to use a Rational type.

I'm not clear as to why this is a problem though, and where it can be magnified even despite using rounding in your application.

Why 0.1 Does Not Exist In Floating-Point

Related Stories