[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
Prev by Date:
**infinity expression from matrix inverse**
Next by Date:
**Re: Marking a (rectangular) zone in a standard 2D plot using "Rectangle"**
Previous by thread:
**Re: infinity expression from matrix inverse**
Next by thread:
**Re: Re: Re: contains 208,987,640 decimal digits (was: Fibonachi[5,000,000] contains 1044938 decimal digits)**
| |