Services & ResourcesWolfram ForumsMathGroup Archive

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

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

• To: mathgroup at smc.vnet.net
• Subject: [mg49782] Re: contains 208,987,640 decimal digits (was: Fibonachi[5,000,000] contains 1044938 decimal digits)
• From: "Alex Vinokur" <alexvn at big-foot.com>
• Date: Sat, 31 Jul 2004 03:14:01 -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>
• Sender: owner-wri-mathgroup at wolfram.com

"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
---------------------------------------------


-- 
   Alex Vinokur
     http://mathforum.org/library/view/10978.html
     http://sourceforge.net/users/alexvn

• References:
  • Re: Fibonacci[1,000,000,000] contains 208,987,640 decimal digits (was: Fibonachi[5,000,000] contains 1044938 decimal digits)
    • From: "Alex Vinokur" <alexvn@big-foot.com>