Lisp, Floating Points and Muller's Recurrence
Floating point number representations are annoying to work with. Lisp and by extension Clojure deal with them by using fractions instead.
I came across this article about why the IRS has had trouble to break away from Cobol. The article argues that a big reason is due to Cobol’s native support of fixed point as opposed to floating point. Below is a quick recap of the article and the problem with floating points.
The problem with floating point representation
The nature of floating point representations results in some unexpected values. For instance, in python if you try to add 0.1 and 0.2 you get the result below.
>>> 0.1 + 0.20.30000000000000004
The dangerous thing about this is that it crops up in unexpected places and during recursion can build up to drastically deviate from the expected result. Muller’s Recurrence is a prime example.
If you were to compare the results as i goes from 0 to 19 using floating vs fixed points, you would get the results below.
i | floating pt | fixed pt-- | -------------- | ---------------------------0 | 4 | 41 | 4.25 | 4.252 | 4.47058823529 | 4.47058823529411764705882353 | 4.64473684211 | 4.64473684210526315789473624 | 4.77053824363 | 4.77053824362606232294616185 | 4.85570071257 | 4.85570071258907363420398576 | 4.91084749866 | 4.91084749908279320043429387 | 4.94553739553 | 4.94553740412391672465195298 | 4.96696240804 | 4.96696258176270059625712889 | 4.98004220429 | 4.980045701355631111852658210 | 4.9879092328 | 4.987979448478391267943941511 | 4.99136264131 | 4.992770288062048206746825312 | 4.96745509555 | 4.995655891506235647818498513 | 4.42969049831 | 4.997391268373369754025308814 | -7.81723657846 | 4.998433943785248237678160115 | 168.939167671 | 4.999060068778541393842418816 | 102.039963152 | 4.999435873288037699050118417 | 100.099947516 | 4.999660246786657582170063418 | 100.004992041 | 4.999771352671616781797971419 | 100.000249579 | 4.9993671517118171375788238
For more discussion, visit the original article. It goes more in depth and I recommend reading it.
Muller’s Recurrence in Clojure
I’ve been dabbling in lisp and Clojure over the last few weeks (Clojure is a dialect of lisp). One of the cool things about lisp is that it handles fractions natively. For example, when doing integer division the results are represented as fractions. 1 divided by 10 is the fraction 1/10. And operations on fractions work as expected.
(/ 1 10) => 1/10(+ 1/10 2/10) => 3/10
Of course you can still do floating point calculations.
(/ 1 10.0) => 0.1(+ 0.1 0.2) => 0.30000000000000004
As a quick side-note, lisp has a syntax different from most modern programming languages.
Most languages:function(arg1, arg2, ..., argn)e.g. sum(1, 2)
Lisp(function-name arg1 arg2 ... argn)e.g. (sum 1 2)
In general, lisp handles numbers very well and can do some impressive calculations. Below is an example of 53 ^ 53 in Common Lisp (example stolen from the great book Land of Lisp).
> (expt 53 53)24356848165022712132477606520104725518533453128685640844505130879576720609150223301256150373
Muller’s Recurrence in Clojure
How would the previous example of Muller’s Recurrence look in Clojure?
(defn rec [y,z] (- 108 (/ (- 815 (/ 1500 z)) y)))
The above defines a function rec, which takes two parameters, y and z. Again, here is the formula we used as an example of Muller’s Recurrence.
To calculate xi recursively, we can use the formula below, which will print out our results as they get processed.
(defn recn [n y z] (do (println n y z)) (if (<= n 0) z (recn (- n 1) (rec y z) y)))
Since Clojure works with fractions, using fractions as inputs just treats everything as a fraction, avoiding the problem with floating points.
=> (recn 20 17/4 4)20 17/4 419 76/17 17/418 353/76 76/1717 1684/353 353/7616 8177/1684 1684/35315 40156/8177 8177/168414 198593/40156 40156/817713 986404/198593 198593/4015612 4912337/986404 986404/19859311 24502636/4912337 4912337/98640410 122336033/24502636 24502636/49123379 611148724/122336033 122336033/245026368 3054149297/611148724 611148724/1223360337 15265963516/3054149297 3054149297/6111487246 76315468673/15265963516 15265963516/30541492975 381534296644/76315468673 76315468673/152659635164 1907542343057/381534296644 381534296644/763154686733 9537324294796/1907542343057 1907542343057/3815342966442 47685459212513/9537324294796 9537324294796/19075423430571 238423809278164/47685459212513 47685459212513/95373242947960 1192108586037617/238423809278164 238423809278164/47685459212513238423809278164/47685459212513
Note this example counts down from 20 while the original example counts up to 20.
If we want to convert that final value to a float, we can do so:
(float 238423809278164/47685459212513)4.9999268795046
But of course, if you start out with floats, you’ll have the same problem:
=> (recn 20 4.25 4)20 4.25 419 4.470588235294116 4.2518 4.6447368421052175 4.47058823529411617 4.770538243625083 4.644736842105217516 4.855700712568563 4.77053824362508315 4.91084749866063 4.85570071256856314 4.945537395530508 4.9108474986606313 4.966962408040999 4.94553739553050812 4.980042204293014 4.96696240804099911 4.987909232795786 4.98004220429301410 4.991362641314552 4.9879092327957869 4.967455095552268 4.9913626413145528 4.42969049830883 4.9674550955522687 -7.817236578459315 4.429690498308836 168.93916767106458 -7.8172365784593155 102.03996315205927 168.939167671064584 100.0999475162497 102.039963152059273 100.00499204097244 100.09994751624972 100.0002495792373 100.004992040972441 100.00001247862016 100.00024957923730 100.00000062392161 100.00001247862016100.00001247862016
Lisp’s native handling of fractions is a nice feature that can help you avoid some problems associated with floating point numbers.