[Date Index]
[Thread Index]
[Author Index]
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*: [mg49668] 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 at big-foot.com>
*Date*: Tue, 27 Jul 2004 07:00:49 -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>
*Sender*: owner-wri-mathgroup at wolfram.com
"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?
--
Alex Vinokur
http://mathforum.org/library/view/10978.html
http://sourceforge.net/users/alexvn
Prev by Date:
**Re: Q: extract all k-tuple from a list of n elements**
Next by Date:
**Re: Slow LinearSolve.**
Previous by thread:
**Fibonacci[1,000,000,000] contains 208,987,640 decimal digits (was: Fibonachi[5,000,000] contains 1044938 decimal digits)**
Next by thread:
**Re: Re: Fibonacci[1,000,000,000] contains 208,987,640 decimal digits (was: Fibonachi[5,000,000] contains 1044938 decimal digits)**
| |