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.