The 1000th Fibonacci Number

Date: 09/25/98 at 11:27:39
From: Francois Compain
Subject: Fibonacci sequence

Hi, 

I was asked by my teacher to find the 1000th number in the Fibonacci 
sequence. I was able to make a program for my calculator, but I 
couldn't go beyond the 450th number. Could you help me find the 1000th?

Thanks.

Date: 09/25/98 at 13:42:42
From: Doctor Rob
Subject: Re: Fibonacci sequence

The number you seek has 209 decimal digits. Your calculator will have 
to be able to deal with that, or else you will have to do this on 
paper. Do you need all the digits, or will an approximation do?  For 
example:

   F(450) = 495396701187506647316252492523160404772779187134606\
            1001150551747313593851366517214899257280600

or approximately 4.953967011875 * 10^93. Will the latter do?

If an approximation will work, try this to find the nth Fibonacci 
number F(n) (where F(0) = 0, F(1) = 1, F(2) = 1, F(3) = 2, and so on).  
Compute phi = (1+sqrt[5])/2, and take its logarithm (base 10).  
Multiply that by n, and subtract half the logarithm (base 10) of 5.  
This will be the logarithm (base 10) of your answer. The integer part 
will tell you the exponent of 10 in the approximation, and raising 10 
to the fractional part power will tell you the first several digits of 
the first factor of the approximation.

Example:  n = 12
          phi = 1.6180... 
          log_10(phi) = 0.2090...
          12*log_10(phi) = 2.5079...  
          log_10(5)/2 = 0.3495...  

The difference of the last two numbers is 2.1584..., and 
10^0.1584... = 1.44001..., so the approximation is 1.44001*10^2.  
Of course F(12) = 144, so this is an excellent approximation.

This works because phi^n/sqrt(5), when rounded to the nearest integer,
gives F(n) exactly, and the approximation gets better the bigger n is.

If you need all the digits, you can proceed as follows.

Start with two sequences F(n) above, and L(n), defined by L(0) = 2,
L(1) = 1, and L(n) = L(n-1) + L(n-2) for every n >= 2. The L sequence 
is called the Lucas Sequence, and goes 2, 1, 3, 4, 7, 11, 18, 29, 47, 
76, 123, and so on.  Now there are the following identities between 
these numbers:

   1.  F(2*n) = F(n)*L(n)
   2.  L(2*n) = L(n)^2 - 2*(-1)^n
   3.  F(n+1) = [L(n)+F(n)]/2
   4.  L(n+1) = [L(n)+5*F(n)]/2

which are true for all positive values of n. These allow you to 
compute F(1000) if you know F(500) and L(500), by using 1 above with 
n = 500. These two you can find from F(250) and L(250), by using 1 and 
2 above with n = 250. These two you can find from F(125) and L(125), 
by using 1 and 2 above with n = 125. These two you can find from 
F(124) and L(124), by using 3 and 4 above with n = 124. These two you 
can find from F(62) and L(62), by using 1 and 2 above with n = 62.  
These two you can find from F(31) and L(31), by using 1 and 2 above 
with n = 31. These two you can find from F(30) and L(30), by using 3 
and 4 above with n = 30. These two you can find from F(15) and L(15), 
by using 1 and 2 above with n = 15. These two you can find from F(14) 
and L(14), by using 3 and 4 above with n = 14. These two you can find 
from F(7) and L(7), by using 1 and 2 above with n = 7. These two you 
can find from F(6) and L(6), by using 3 and 4 above with n = 6. These 
two you can find from F(3) and L(3), by using 1 and 2 above with 
n = 3.

Now you know that F(3) = 2 and L(3) = 4, so you can work back up the 
chain in the last paragraph to find F(6) = 8 and L(6) = 18, F(7) = 13 
and L(7) = 29, and so on until you find F(1000). Most of the work 
comes at the end, when you have to multiply together F(500) and 
L(500), two numbers with more than 100 decimal digits each.

In principal, 1 through 4 above will allow you to compute F(n) and 
L(n) for any positive integer n, no matter how large, with only a 
relatively few arithmetic operations.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/