[Haskell-cafe] Problems with truncate big float values in Haskell

[Albert Y. C. Lai]

On 2017-01-05 02:30 PM, Albert Y. C. Lai wrote:
> On 2017-01-05 01:16 PM, Henson wrote:
>> I have one Rational number (3 + sqrt 5)
>
> Irrational Number.
>
>> let x = (truncate ((3 + sqrt 5) ^ 2000000)) `mod` 1000 and result is 216.
>
> You need to firstly read http://floating-point-gui.de/formats/fp/ , and
> secondly google for "goldberg floating point" and read "what every
> computer scientist should know about floating-point arithmetic".

And the conclusion at that point should be: A direct Double approach 
will not work. ("direct" means you don't do your own math first.) You 
will need to be either indirect (do your own math first) or forget Double.

In fact I would do both indirect and forget Double.

Let r = 3 + sqrt 5, s = 3 - sqrt 5. s is the evil twin of r.

Define (as in math, not code) h n = r^n + s^n for natural n.

(a) Prove: r and s are the roots of x^2 - 6x + 4 = 0.
   And so r^2 = 6r - 4, s^2 = 6s - 4.

   (How did I think up that equation? From (x - r)*(x - s).)

(b) Prove: h satisfies the following recurrence

   h 0 = 2
   h 1 = 6
   h n = 6 * h (n-1) - 4 * h (n-2)  for n>=2

   (Sketch: Part (a) will be useful.)

(c) Prove: floor(r^n) = h n - 1. (Sketch: 0 < s^n < 1, and the 
recurrence tells you that h n is a natural number.)

(d) Give and/or code up an algorithm to compute the last three decimal 
digits of floor(r^n); it should use only O(n) time, O(lg n) space, and 
integer/natural arithmetic. In fact, the lg n space is only for counting 
from 0 to n, the algorithm is constant-space otherwise (for mod-1000 
arithmetic).

   (Actually you could get it down to O(lg n) time too, but that's for 
another day.)

(e) Do a similar thing to floor((the gold ratio)^n).


How I came up with this idea: I recalled that the fibonacci numbers are 
related to (the golden ratio)^n (for example CLRS has a few lines on 
this). So I just had to adapt it to 3 + sqrt 5.

* * *

For a decade, I haven't had a good excuse to use my smug saying. So this 
is a good chance to say:

The language of computing is not C, Node.js, or Haskell. The language of 
computing is mathematics.