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: <firstname.lastname@example.org>, <Mo2OZGACWlF3Ewez@raos.demon.co.uk>, <email@example.com> <firstname.lastname@example.org> <email@example.com> <200407271100.HAA11140@smc.vnet.net> <firstname.lastname@example.org>
- 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:
> > 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).
<QUOTE from that message>
Generally it is not efficient to compute Fibonacci numbers using the exact
formula involving Sqrt because at high precision better methods exist.
But I would like to know what is time complexity of computing Fibonacci numbers using the _exact_
> His point remains unchanged. Not knowing then about Mark's posts, I also
> wrote a bit about this in 2001:
> 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
For instance, GMP (GNU Multiple Precision Arithmetic Library) http://www.swox.com/gmp/.
The result of executing fib (5000000) is:
computation took 466 ms
result is about 1044938 digits, not printing it
Prev by Date:
Re: Question about composing a complex function.
Next by Date:
Re: ListDensityPlot (solution, and critical comment))
Previous by thread:
Re: Re: Fibonacci[1,000,000,000] contains 208,987,640 decimal digits (was: Fibonachi[5,000,000] contains 1044938 decimal digits)
Next by thread:
Any ways to recover a broken file?