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.