MathGroup Archive 2000

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

Search the Archive

Re: The most efficient Fibonacci algorithim?

  • To: mathgroup at smc.vnet.net
  • Subject: [mg23393] Re: The most efficient Fibonacci algorithim?
  • From: Enrico Righes <righes at stud.uni-hannover.de>
  • Date: Fri, 5 May 2000 02:07:32 -0400 (EDT)
  • Organization: RRZN - Newsserver Test
  • 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.


  • Prev by Date: Re: Gif file?
  • Next by Date: Re: The most efficient Fibonacci algorithim?
  • Previous by thread: The most efficient Fibonacci algorithim?
  • Next by thread: Re: The most efficient Fibonacci algorithim?