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*: [mg49649] Fibonacci[1,000,000,000] contains 208,987,640 decimal digits (was: Fibonachi[5,000,000] contains 1044938 decimal digits)*From*: "Michael Taktikos" <michael.taktikos at hanse.net>*Date*: Mon, 26 Jul 2004 04:01:53 -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>*Sender*: owner-wri-mathgroup at wolfram.com

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. 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) ] ] ******************************************************** If you don't need all the digits, but only the number of the contained decimal digits, you can use the function of Binet with an appropriate precision: In[1]:=fiboBinet[n_]:=Module[{gr=GoldenRatio^n}, N[(gr+1/gr)/Sqrt[5],1000]] In[2]:=Timing[fiboBinet[10^9]] (gives with my old AMD 700 MHz the answer {0.6 Second, 7.9...*10^208987639} ) Now I detected an other function, which seems to be faster than Binet's one: fiboNew(n) = g^n/(2g-1) with g = GoldenRatio. Let's try it: In[3]:=fiboNew[n_]:=N[(GoldenRatio^n)/(2*GoldenRatio-1),1000]; In[4]:=Timing[fiboNew[10^9]] It gives the answer {0.1 Second, 7.9...*10^208987639} By searching with Google and looking in your "Bronstein" you will not find it published, therefore I ask the group: is this the first publication or did I only discovered the wheel again? I believe to have a proof that this function gives allways the same answer as Binet's one, now I'm looking if it contains bugs. Greetings from Hamburg, Michael Taktikos