Re: The most efficient Fibonacci algorithim?

*To*: mathgroup at smc.vnet.net*Subject*: [mg23390] Re: The most efficient Fibonacci algorithim?*From*: Enrico Righes <righes at stud.uni-hannover.de>*Date*: Fri, 5 May 2000 02:07:27 -0400 (EDT)*References*: <8er92l$hdq@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

Hello! You can compute the numbers with f[n_] := f[n] = f[n-1] + f[n-2]; f[0] = 0; f[1] = 1; This seems to be recursive (so it could be too slow), but the function reminds the values of itself (because of the defintion f[n_]:=f[n]=...) Another way is to compute the numbers directly: f[n_] := ((1+Sqrt[5])^n - (1-Sqrt[5])^n) / (2^n * Sqrt[5]) or f[n_] := Round[((1+Sqrt[5])/2)^n / Sqrt[5]] Hope that helps Enrico zeno at magicnet.net schrieb: > > On page 128 of the book "The Mathematica Programmer" by Roman Maeder (the > Mathematic 2.2 edition) is this Mathematica program to compute Fibonacci > numbers... > > fibj[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)]] > > The book says this is the most efficient one of a few mentioned in the book. > Does anyone know of any other programs that are faster? This one really > screams...I am curious if anyone has done anything even better.