MathGroup Archive 2000

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

Search the Archive

Re: The most efficient Fibonacci algorithim?

  • To: mathgroup at
  • Subject: [mg23405] Re: The most efficient Fibonacci algorithim?
  • From: "Peter Tolksdorf" <Peter.Tolksdorf at>
  • Date: Sat, 6 May 2000 19:14:14 -0400 (EDT)
  • References: <8er92l$>
  • Sender: owner-wri-mathgroup at


<zeno at> schrieb in im Newsbeitrag: 8er92l$hdq at
> 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
> 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: An example of a quadratic that version 2.2.2 can not solve but version 3 does...
  • Next by Date: Re: matrices, dot products and convergents of continued fractions
  • Previous by thread: Re: The most efficient Fibonacci algorithim?
  • Next by thread: A bug in SameQ