MathGroup Archive 2000

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

Search the Archive

The most efficient Fibonacci algorithim?

  • To: mathgroup at smc.vnet.net
  • Subject: [mg23357] The most efficient Fibonacci algorithim?
  • From: zeno at magicnet.net
  • Date: Thu, 4 May 2000 02:59:24 -0400 (EDT)
  • Organization: Verio
  • Sender: owner-wri-mathgroup at wolfram.com

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.


  • Prev by Date: RE: Could we build matrix with codition instruction?
  • Next by Date: A bug in SameQ
  • Previous by thread: Re: Random Geometric (long)
  • Next by thread: Re: The most efficient Fibonacci algorithim?