Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2004
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2004

[Date Index] [Thread Index] [Author Index]

Search the Archive

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



  • Prev by Date: Slow LinearSolve.
  • Next by Date: Re: Fibonacci [5,000,000] contains 1044938 decimal digits
  • Previous by thread: Re: Slow LinearSolve.
  • Next by thread: Re: Fibonacci[1,000,000,000] contains 208,987,640 decimal digits (was: Fibonachi[5,000,000] contains 1044938 decimal digits)