Re: Fibonacci [5,000,000] contains 1044938 decimal digits
- To: mathgroup at smc.vnet.net
- Subject: [mg17180] Re: Fibonacci [5,000,000] contains 1044938 decimal digits
- From: Mark Sofroniou <marks>
- Date: Tue, 20 Apr 1999 01:20:56 -0400
- Organization: NETTuno
- References: <7f9ibr$55t@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Alex Vinokur wrote:
> Hi,
>
> Several large Fibonacci numbers were calculated using only
> the well-known explicit formula:
> Fib (0) = 0, Fib (1) = 1,
> Fib (n) = Fib (n-1) + Fib (n-2), n >= 2
> All the (decimal) digits of these numbers were obtained.
>
> It was using the EXPLICIT Fibonacci formula and
> computing ALL the large Fibonacci numbers digits
> that were set as an object.
> Using just EXPLICIT Fibonacci formula is not an imperative requirement.
> But to get ALL digits of the large Fibonacci number is very advisable one.
>
> ... snipped ...
>
> Here are the experiment results
>
> Comparative table.
> ================================================================
> | | About Fib [n] |
> | |----------------------------------------------------|
> | Index n | Decimal | Calculation time (hh:mm:ss) |
> | | Digits |-----------------------------------------|
> | | | DesirableLongInt | bc utility |
> | | |----------------------------| |
> | | | vector | basic_string | |
> |--------------------------------------------------------------|
> | 100000 | 20899 | 1:08.30 | 1:33.94 | 1:39.40 |
> | 500000 | 104494 | 26:38.46 | 38:41.73 | 40:21.01 |
> | 1000000 | 208988 | 1:42:43.78 | 2:35:08.71 | 2:39:51.56 |
> | 5000000 | 1044938 | 43:00:17.66 | 63:34:31.07 | None |
> ================================================================
>
> Conclusion. Although Fib[5,000,000] was calculated,
> these methods are unacceptable to calculate Fib [1,000,000+]
> because it takes too long time.
>
> The question is, if is there any EXPLICIT method
> that calculates ALL digits Fib [5,000,000+] and
> takes acceptable time?
>
> ... snipped ...
Generally it is not efficient to compute Fibonacci numbers using the exact
formula involving Sqrt[5] because at high precision better methods exist.
The basic recurrence is fine for small values, but if you want to compute the
5000000th value then the best approach that I am aware of is to use a
different set of recurrence relations (there are many to choose from).
The basic idea is to decompose the input into a binary number. This can be
done as:
IntegerDigits[5000000,2]
Then use recurrence relations that define fib(2n) or fib(2n-1) in terms of
fib(n) and fib(n-1). The idea is explained in Chapter 7, Fibonacci on the
Fast Track in Roman Maeder's book The Mathematica Programmer.
By doing the computation this way the problem reduces to multiplication and
addition. Therefore you can make use of asymptotically faster multiplication
methods. Mathematica Version 3.0 has Karatsuba multiplication for arbitrary
length integers for example, which reduces the cost of multiplication from
O(n^2) to approximately O(n^1.58).
Here is the result from Version 3.0:
In[1]:= f = Fibonacci[5000000];//Timing
Out[1]= {23.42 Second, Null}
In[2]:= N[f]
1044937
Out[2]= 7.10828597205853 10
Mark