MathGroup Archive 2004

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

Search the Archive

Re: Fibonacci[1,000,000,000] contains 208,987,640 decimal digits

  • To: mathgroup at smc.vnet.net
  • Subject: [mg49735] Re: Fibonacci[1,000,000,000] contains 208,987,640 decimal digits
  • From: "Michael Taktikos" <michael.taktikos at hanse.net>
  • Date: Thu, 29 Jul 2004 07:45:45 -0400 (EDT)
  • Sender: owner-wri-mathgroup at wolfram.com

Doubtless, for Mathematica friends, the best books about the fastest
Fibonacci algorithms and the ways how they can be compared are the books of
Roman Maeder:

The Mathematica Programmer, Academic Press, Jan 1994
Mathematica and Computer Programming, Cambridge University Press, Feb 2000

Attention, this algorithms give all the numbers of Fibonacci[n], but are too
slow to compute Fibonacci[1,000,000,000].
The result that this number contains 208,987,640 decimal digits, I found
with my own function

fiboNew[n_] := GoldenRatio^n/(2*GoldenRatio-1)

which is faster than the function of Binet.

Greetings from Hamburg,

Michael Taktikos

____________________________________________________________________________
_________
"Alex Vinokur" <alexvn at big-foot.com> wrote about:
Re: Fibonacci[1,000,000,000] contains 208,987,640 decimal digits (was:
Fibonachi[5,000,000] contains 1044938 decimal digits)

> 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: Using "Sum" (i = 1 ... N) in a function definition
  • Next by Date: PutAppend Command and Data Output
  • Previous by thread: Re: Marking a (rectangular) zone in a standard 2D plot using "Rectangle"
  • Next by thread: PutAppend Command and Data Output