Floating point Arithmetic Disasters

“Floating point numbers are like piles of sand; every time you move them around, you lose a little sand and pick up a little dirt. ” — Brian Kernighan and P. J. Plauger.

If you are using Windows machine, open your calculator, try following calculation,

\sqrt[2]{4} - 2 and 2 - \sqrt[2]{4}.

Are both the results same? Are they equal to 0?

After saying WTF 3-4 times, try contemplating the consequences of it.

The accumulation of floating point errors caused many accidents, 3 among these were pretty deadly.

  • Ariane 5 rocket. [June 4, 1996] 10 year, $7 billion ESA project exploded after launch. They converted 64-bit float to 16 bit signed int. Unanticipated (that what they call it in their official report, it’s simply insane) overflow.

See this interesting report here http://www.around.com/ariane.html

  • Vancouver stock exchange. [November, 1983]. Index undervalued by 44%. Recalculated index after each trade by adding change in price. 22 months of accumulated truncation error.
  • Patriot missile accident. [February 25, 1991] Failed to track scud; hit Army barracks, killed 28. Inaccuracy in measuring time in 1/20 of a second since using 24 bit binary floating point.

Report is available here http://www.fas.org/spp/starwars/gao/im92026.htm

If you have seen that Movie ‘The Matrix 3’ in which Neo meets the Architect, read this conversation between them.

Neo: Why am I here?

Architect: Your life is the sum of a remainder of an unbalanced equation inherent to the programming of the matrix. you are the eventuality of an anomaly which despite my sincerest efforts I have been unable to eliminate from what is otherwise a harmony of mathematical precision. While it remains a burden assiduously avoided it is not unexpected, and thus not beyond a measure of control. Which has led you inexorably….here

Make sense why the Architect is helpless?

\sqrt[2](4) - 2 is not zero because of the algorithm implemented inside the ALU to calculate the square root of a number. They use Taylor series based algorithms (remember Newton Raphson method). See details here. This ‘floating point arithmetic’ is a tricky business.

Second hurdle is calculating the roots of ‘polynomial’. It is well proven results [Group Theory – Évariste Galois, 1938] that there exists no algorithm which can produce the exact root of a polynomial of degree higher than 3. One has to do the numerical computations. Avoid calculating roots of polynomials whenever you see them. That is one reason why there is no state-space based circuit simulator even though they are conceptually tempting.

There are languages which are capable of calculating these expression precisely. They emulate ‘Turing machines’ (equivalent to Lambda calculus). Languages such as LISP (which is popular among AI people) and the new cult Haskell are capable of computing to the arbitrary number precision, only bounded by the memory. The drawback is, that since every bit is treated as a ‘symbol’, these languages are computationally very slow. Supporter of these languages say, and I agree, that if you learn these ‘functional programming languages, you will laugh at jokes which no one will understand.
END NOTES:

In a masterpiece ‘Alice in Wonderland’ which was written by a Mathematician and Logician, there are many instances of mathematical reasoning between Alice and Humpty-Dumpty, Alice and Mad Hatter. The conversation between Tweedledum and Tweedledee have the reeks of reducible logic everywhere.

The creator of ‘Simplex Method’ in Linear programming, Dantiz starts his book by a conversation between Alice and Hatter at his tea party which you can read in ‘Through the looking glass’. In which Hatter was insisting Alice to take some more tea. Alice got irritated and argued that how can she take more tea when she has none. On it, Hatter replied that probably she doesn’t know how to take less tea. This novel is one of the defining work which points out the limitation of natural language in describing ‘truth’. No wonder Jacquas Derrida came up with his school of thought ‘Deconstruction.’ See here

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s