[Date Index] [Thread Index] [Author Index]

Re: Re: contains 208,987,640 decimal digits (was: Fibonachi[5,000,000] contains 1044938 decimal digits)

• To: mathgroup at smc.vnet.net
• Subject: [mg49795] Re: [mg49782] Re: contains 208,987,640 decimal digits (was: Fibonachi[5,000,000] contains 1044938 decimal digits)
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Sun, 1 Aug 2004 04:09:58 -0400 (EDT)
• References: <7f4ffu$6dj$1@nnrp1.dejanews.com>, <Mo2OZGACWlF3Ewez@raos.demon.co.uk>, <7g0qsd$dr9@smc.vnet.net> <cdvm0e$7hv$1@smc.vnet.net> <ce2ftd$8rh$1@smc.vnet.net> <200407271100.HAA11140@smc.vnet.net> <ceap6b$aej$1@smc.vnet.net> <200407310714.DAA12036@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

Alex Vinokur wrote:
> "Daniel Lichtblau" <danl at wolfram.com> wrote in message news:ceap6b$aej$1 at smc.vnet.net...
> 
>>Alex Vinokur wrote:
> 
> [snip]
> 
>>>I would like to measure the comparative performance of my C++ algorithm and "Mathematica-alone" code above.
>>
> (I mean codes for computing Fibonaccii).
> 
>>>However I have never worked with "Mathematica-alone".
>>>How can I compare those algorithms?
>>
>>You could run them both on identical machines/inputs and check the
>>timings. You might also want to read what Mark Sofroniou said about this
>>five years ago (in response to your similar post back then).
>>
>>http://forums.wolfram.com/mathgroup/archive/1999/Apr/msg00349.html
> 
> 
> <QUOTE from that message>
> Generally it is not efficient to compute Fibonacci numbers using the exact
> formula involving Sqrt[5] because at high precision better methods exist.
> 
> </QUOTE>
> 
> Of course.
> But I would like to know what is time complexity of computing Fibonacci numbers using the _exact_
> formula.
> 
> 
>>His point remains unchanged. Not knowing then about Mark's posts, I also
>>wrote a bit about this in 2001:
>>
>>http://forums.wolfram.com/mathgroup/archive/2001/Jan/msg00234.html
>>
>>But what Mark said is most relevant here. In essence, the method in
>>Maeder's code is a good divide-and-conquer, based on doubling
>>recurrences in Fibonacci numbers. This is much faster than anything
>>based on the linear recurrences, as it takes advantage of asymptotically
>>fast multiplication.
>>
>>
>>Daniel Lichtblau
>>Wolfram Research
>>
> 
> 
> There are very fast algorithms for computing Fibonacci numbers not using the exact
> formula.
> For instance, GMP (GNU Multiple Precision Arithmetic Library) http://www.swox.com/gmp/.
> 
> http://swox.com/cgi-bin/gmp_calc.pl?expr=fib+%285000000%29
> ---------------------------------------------
> The result of executing fib (5000000) is:
> computation took 466 ms
> result is about 1044938 digits, not printing it
> ---------------------------------------------

I'm not sure what you want to do. There are many exact formulas. The one 
in question (Mathematica code from Roman Maeder) uses a doubling 
recurrence, that is, f[2*n] in terms of f[n] and f[n+1] (or something 
like that. It is exact. But I do not know if you are interested in the 
complexity of the best exact formulas, or the complexity of a particular 
exact formula e.g. the closed form involving Sqrt[5].

Below is computed exactly, then numericized. It is not done using any 
formula involving Sqrt[5].

In[2]:= Timing[ff = Fibonacci[5000000];]
Out[2]= {0.59 Second, Null}

In[3]:= InputForm[N[ff]]
Out[3]//InputForm=
7.108285972058527236971171956172`15.954589770191005*^1044937

Likewise the GMP result you site is computed using an exact method 
(probably about the same as what we do).


Daniel Lichtblau
Wolfram Research

• Follow-Ups:
  • Re: Re: Re: contains 208,987,640 decimal digits (was: Fibonachi[5,000,000] contains 1044938 decimal digits)
    • From: Ed Pegg Jr <edpegg@gmail.com>