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

*To*: mathgroup at smc.vnet.net*Subject*: [mg49703] Re: [mg49668] Re: Fibonacci[1,000,000,000] contains 208,987,640 decimal digits (was: Fibonachi[5,000,000] contains 1044938 decimal digits)*From*: Daniel Lichtblau <danl at wolfram.com>*Date*: Thu, 29 Jul 2004 07:43:15 -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>*Sender*: owner-wri-mathgroup at wolfram.com

Alex Vinokur wrote: > "Michael Taktikos" <michael.taktikos at hanse.net> wrote in message news:ce2ftd$8rh$1 at smc.vnet.net... > >>Alex Vinokur <alexvn at bigfoot.com> wrote: >> >> >>>>>>Several large Fibonacci numbers were calculated using only >>>>>>the well-known explicit formula: >>>>>> Fib (0) = 0, Fib (1) = 1, >>>>>> Fib (n) = Fib (n-1) + Fib (n-2), n >= 2 >>>>>>All the (decimal) digits of these numbers were obtained. >>>>> >>[...] >> >>>>>>But to get ALL digits of the large Fibonacci number is very >>>>> >>>advisable one. >>>[C++ code, snip] >> >>Thanks for your code. > > > Impoved version of that algorithm can be seen at > http://groups.google.com/groups?selm=2mk62rFo1mv0U1%40uni-berlin.de > > >>Until now, the fastest way to get with "Mathematica-alone" all digits of >>large Fibonacci numbers seems to be that of Roman Maeder: >> >>******************************************************** >>fibmaeder[n_] := >> Module[{r11 = 1, r12 = 0, r22 = 1, digits = IntegerDigits[n-1, 2], i, t}, >> Do[ If[ digits[[i]] == 1, >> {r11, r22} = {r11(r11 + 2r12), r12(r11 + r22)}; >> r12 = r11 - r22 >> , t = r12(r11 + r22); >> {r11, r12} = {r11(r11 + 2r12) - t, t}; >> r22 = r11 - r12 >> ], >> {i, Length[digits]-1} >> ]; >> If[ digits[[-1]] == 1, >> r11(r11 + 2r12), >> r11(r11 + r22) - (-1)^((n-1)/2) >> ] >> ] >> > > [snip] > > I would like to measure the comparative performance of my C++ algorithm and "Mathematica-alone" code above. > 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 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

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