       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
>>>>>
>>>[C++ code, snip]
>>
>
>
> Impoved version of that algorithm can be seen at
>
>
>>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
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

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

```

• Prev by Date: Follow up: Help wanted ... bounding function is pierced for n even > 10^7.
• Next by Date: Re: Launching the Mathematica interface via mathlink
• Previous by thread: Re: Fibonacci[1,000,000,000] contains 208,987,640 decimal digits (was: Fibonachi[5,000,000] contains 1044938 decimal digits)
• Next by thread: Re: contains 208,987,640 decimal digits (was: Fibonachi[5,000,000] contains 1044938 decimal digits)