4 ms·

I'm curious to see how languages with support for rational types would handle this problem. (E.g. Scheme, Clojure, Haskell) Seems to me that they would eliminat

I'm curious to see how languages with support for rational types would handle this problem. (E.g. Scheme, Clojure, Haskell) Seems to me that they would eliminate the round-off problem entirely for a great number of commonly-faced applications in the finance world. (So easy to use `x/100`.)

divs1210 8y ago
I got curious too, so ported the code to Clojure: https://gist.github.com/divs1210/b2076eeaf533d5e49262bd9684381b9a https://gist.github.com/divs1210/b2076eeaf533d5e49262bd96843...
slaymaker1907 8y ago
I think part of the problem with rationals is that they have much more chaotic memory usage, even more so than normal big integers. This is because while integers are straight forward to estimate memory usage based off of size which is easy to reason about, rationals grow rapidly from both multiplications as well as divisions. Furthermore, they get even more complicated since they can shrink unexpectedly from either operation if you are continuously optimizing using GCD.
lispm 8y ago
In Common Lisp: (defun r1 (y z) (- 108 (/ (- 815 (/ 1500 z)) y))) (defun r (n &aux (l '(4 425/100))) (loop for i from 2 upto (1+ n) do (setf l (append l (list (r1 (elt l (- i 1)) (elt l (- i 2))))))) l) CL-USER 68 > (loop for e in (r 20) and i below 20 do (format t "~%~3a~20,15f" i (float e 1.0d0))) 0 4.000000000000000 1 4.250000000000000 2 4.470588235294118 3 4.644736842105263 4 4.770538243626063 5 4.855700712589074 6 4.910847499082793 7 4.945537404123916 8 4.966962581762701 9 4.980045701355631 10 4.987979448478392 11 4.992770288062068 12 4.995655891506634 13 4.997391268381344 14 4.998433943944817 15 4.999060071970894 16 4.999435937146839 17 4.999661524103767 18 4.999796900713418 19 4.999878135477931
draegtun 8y ago
Here's a naive conversion to Smalltalk (tested in Pharo) going up to N=30.... | rec results | rec := [ :y :z | 108 - (815 - (1500 / z) / y) ]. results := { 4. 425/100. } asOrderedCollection. 3 to: 30 do: [ :i | results add: (rec value: (results at: i - 1) value: (results at: i - 2)). ]. results doWithIndex: [ :each :i | Transcript show: i; tab; tab; show: each asFloat; cr. ]. Output: 1 4.0 2 4.25 3 4.470588235294118 4 4.644736842105263 5 4.770538243626063 6 4.855700712589074 7 4.910847499082793 8 4.945537404123916 9 4.966962581762701 10 4.980045701355631 11 4.987979448478392 12 4.992770288062068 13 4.995655891506634 14 4.997391268381344 15 4.998433943944817 16 4.999060071970894 17 4.999435937146839 18 4.999661524103767 19 4.9997969007134175 20 4.999878135477931 21 4.9999268795046 22 4.999956127061158 23 4.9999736760057125 24 4.999984205520272 25 4.999990523282228 26 4.99999431395856 27 4.999996588371256 28 4.9999979530213565 29 4.999998771812312 30 4.999999263087206

divs1210 8y ago

I got curious too, so ported the code to Clojure: https://gist.github.com/divs1210/b2076eeaf533d5e49262bd9684381b9a https://gist.github.com/divs1210/b2076eeaf533d5e49262bd96843...

slaymaker1907 8y ago

I think part of the problem with rationals is that they have much more chaotic memory usage, even more so than normal big integers. This is because while integers are straight forward to estimate memory usage based off of size which is easy to reason about, rationals grow rapidly from both multiplications as well as divisions. Furthermore, they get even more complicated since they can shrink unexpectedly from either operation if you are continuously optimizing using GCD.

lispm 8y ago

In Common Lisp: (defun r1 (y z) (- 108 (/ (- 815 (/ 1500 z)) y))) (defun r (n &aux (l '(4 425/100))) (loop for i from 2 upto (1+ n) do (setf l (append l (list (r1 (elt l (- i 1)) (elt l (- i 2))))))) l) CL-USER 68 > (loop for e in (r 20) and i below 20 do (format t "~%~3a~20,15f" i (float e 1.0d0))) 0 4.000000000000000 1 4.250000000000000 2 4.470588235294118 3 4.644736842105263 4 4.770538243626063 5 4.855700712589074 6 4.910847499082793 7 4.945537404123916 8 4.966962581762701 9 4.980045701355631 10 4.987979448478392 11 4.992770288062068 12 4.995655891506634 13 4.997391268381344 14 4.998433943944817 15 4.999060071970894 16 4.999435937146839 17 4.999661524103767 18 4.999796900713418 19 4.999878135477931

draegtun 8y ago

Here's a naive conversion to Smalltalk (tested in Pharo) going up to N=30.... | rec results | rec := [ :y :z | 108 - (815 - (1500 / z) / y) ]. results := { 4. 425/100. } asOrderedCollection. 3 to: 30 do: [ :i | results add: (rec value: (results at: i - 1) value: (results at: i - 2)). ]. results doWithIndex: [ :each :i | Transcript show: i; tab; tab; show: each asFloat; cr. ]. Output: 1 4.0 2 4.25 3 4.470588235294118 4 4.644736842105263 5 4.770538243626063 6 4.855700712589074 7 4.910847499082793 8 4.945537404123916 9 4.966962581762701 10 4.980045701355631 11 4.987979448478392 12 4.992770288062068 13 4.995655891506634 14 4.997391268381344 15 4.998433943944817 16 4.999060071970894 17 4.999435937146839 18 4.999661524103767 19 4.9997969007134175 20 4.999878135477931 21 4.9999268795046 22 4.999956127061158 23 4.9999736760057125 24 4.999984205520272 25 4.999990523282228 26 4.99999431395856 27 4.999996588371256 28 4.9999979530213565 29 4.999998771812312 30 4.999999263087206