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>
- Re: Re: Re: contains 208,987,640 decimal digits (was: Fibonachi[5,000,000] contains 1044938 decimal digits)