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