When 2+2 != 4

I was reminded of something I learned way back in my third year of computer science 'Numerical Method's' the other day..the fact that computers can't really do math!

No I'm not taking about the Pentium flaw from 1994, which was a big thing back on those days. I'm taking about the magic number e_min  

Many people know that computers only speak in binary (1's and 0's). So everything you see on the screen has to be somehow represented as a sequence of 1's and 0's.

In Mathematics we have irrational numbers, and repeating decimals.  1/3 for example is an infinite sequence of 0.3333333, and Pi is a long infinite sequence of numbers that does not even bother to repeat (so far as anyone has calculated so far)

So the other day, I was doing some calculations on currency. Specifically it was a sequence of additions and subtractions. The number I was adding/subtracting was 5.32. Here is the debug of the output of that program.

Now if you look carefully, you will find the problem I ran into. There is a piece of the code that summarizes a bunch of detail lines to confirm the sum of the lines is zero before allowing the user to proceed.

In this case the sum of all the lines (+5.32 and -5.32) net each other out to zero the code says something like this

If SumOfRemaining > 0 Then

 Print "The sum of all remaining amounts must be greater then zero to continue"

End If

So how surprised was I when a user reported they were seeing this error message, even though the sum of the numbers was in fact ZERO.

Yet to the machine - The sum of 5.32 + - 5.32 was in fact not zero but more like 0.000000000000757280 WTF?

And that's when I remembered my 3rd year numerical methods class!

The big secret - is that as smart as people think computers are - They can't really do math on REAL (ie: repeating decimals / irrational) numbers. Instead they approximate it using a technique known as Floating Point Arithmetic

You can experience this yourself with pretty much any calculator. Start with the number 1 and divide it by 7     over and over again... say at least 50 times.  Then re-multiply by 7 those same number of times. You should get back to 1, and many times you will get back to 1. But eventually if you keep trying, you will find not the answer back at '1' but instead at something like 0.99999999999999999999999999998. Depending on the brand of calculator, the number of divides/multiples.  

On a modern computer this can be much more difficult to reproduce because a) the computer uses more memory to store the numbers and b) a lot of calculator software 'cheats' so as to round when it thinks you are trying to 'fool' it so that you don't see the 'wrong' answer.. but none-the-less we can reproduce it.

In fact, for any machine / programming language combination we can calculate emin as follows

e(min) = smallest representable number such that adding "1" will still produce a number greater than 1

Consider the following simple algorithm:

    float e
	float sum
	float num
	float tmp
	
	e=0; sum=2; num=1;

	while (sum > 1)
		{
		tmp=1/num
		sum = 1+ tmp
		e=tmp
		num++

                }
		
	print "e(min) IS " + e

--- 

When this code runs on a computer, theoretically the loop should NEVER end, no mater how much we increase the sum by 1/num, it should get smaller and smaller to zero but never equal zero (ie: it's an asymptote)

But if we actually try to run it you will find that eventually the program does end and will output the e(min). 

ie: There is a number so small in the computer so as to be effectively 'zero' because floating point arithmetic is just an approximating of the real number system, and not the full real number system.

Even more interesting is emin number varies from machine to machine and software compiler to compiler depending upon how the floating point data type is implemented. 

On my machine - gcc - = e(min) = 5.960464e-08

                          java     e(min) is 5.960464e-08

                          python (ran for over 10 days, still did not exit!)

You can try the code out on your own machine from here: and see what e(min) looks like on your own machine.

The lesson here is to be careful when doing mathematical calculations (add, multiply, subtract, division with mixes of large numbers and small numbers together.. you just might not get the answer you expect! and 2+2 !=0

---

A final little tidbit about floating point numbers has to do with repeating decimals. Take for example the faction 1/3.  If you work this out it is a repeating set of 0.3333333 infinitely, but computers don't really use 10 digits. They only use 2 (0 and 1), and representation of a faction such as 1/3 may not be a  repeating digit, while other fractions which do not repeat in base 10 do repeat in binary (base 2).

Related:  What Every Computer Scientist Should Know About Floating-Point Arithmetic