Efficiency of algorithms which compute Fibonacci numbers using the primary formula (was: contains 1044938 decimal digits)
- To: mathgroup at smc.vnet.net
- Subject: [mg49802] Efficiency of algorithms which compute Fibonacci numbers using the primary formula (was: contains 1044938 decimal digits)
- From: "Alex Vinokur" <alexvn at big-foot.com>
- Date: Sun, 1 Aug 2004 18:48:32 -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> <cei901$2jt$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
"Daniel Lichtblau" <danl at wolfram.com> wrote in message news:cei901$2jt$1 at smc.vnet.net... > Alex Vinokur wrote: [snip] > > But I would like to know what is time complexity of computing Fibonacci numbers using the _exact_ > > formula. I want to refine myself. I would like to compare efficiency of algorithms which compute Fibonacci numbers using the _primary_ formula. [snip] > > 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 > -- Alex Vinokur http://mathforum.org/library/view/10978.html http://sourceforge.net/users/alexvn