Albert Y. C. Lai trebla at vex.net
Fri Jan 6 01:35:02 UTC 2017

```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
> 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.

```