Re: The most efficient Fibonacci algorithim?

*To*: mathgroup at smc.vnet.net*Subject*: [mg23383] Re: [mg23357] The most efficient Fibonacci algorithim?*From*: Jack Goldberg <jackgold at math.lsa.umich.edu>*Date*: Fri, 5 May 2000 02:07:16 -0400 (EDT)*Sender*: owner-wri-mathgroup at wolfram.com

FYI, Roman Maeder's new book on Mathematica and Computer Programming discusses this problam in a bit more detail than the book you quoted. It appears that Maeder's method is faster than the built-in one. I too was started by this... Unfortunately, the method as it stands takes advantage of special features or the companion matrix to the difference equation f[n+1] = f[n]+f[n-1] {{1,1},{1,0}] namely, its symmetry. Generally companion matrices are not symmetric so the technique does not generalize in any obvious way. On Thu, 4 May 2000 zeno at magicnet.net wrote: > 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. >