Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2000
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

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: [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.
> 



  • Prev by Date: Re: A bug in SameQ
  • Next by Date: Re: fitting data to a sampled waveform?
  • Previous by thread: Re: The most efficient Fibonacci algorithim?
  • Next by thread: Re: The most efficient Fibonacci algorithim?