Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2004
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2004

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

Search the Archive

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




  • Prev by Date: Re: newbie problem with NIntegrate
  • Next by Date: Re: envelope of an oscillatory InterpolatingFunction
  • Previous by thread: Re: NthPermutation: how to change output format?
  • Next by thread: Re: envelope of an oscillatory InterpolatingFunction