Re: iterative-version for computing a Fibonacci number

arnuld wrote:
Paul F. Dietz wrote:
( 0 1 )
A = ( )
( 1 1 )

times the vector ( F_0 F_1 ) is the vector ( F_n F_{n+1} ).

So, compute 1 + A^2 + A^4 + ... + A^n. This is equal
to (A^2 - I)^-1 (A^{n+2) - I), which can be computed in O(log n)
operations.

i did not even get the "a,b,c" of this method. keep in mind that i am
pretty weak at maths.

Take A to be the following 2x2 matrix (2 rows and 2 columns):

|1 1|
|1 0|

if you keep multiplying A by itself you get the following sequence:

A^2 =
|2 1|
|1 1|

A^3=
|3 2|
|2 1|

A^4=
|5 3|
|3 2|

A^5=
|8 5|
|5 3|

A^6=
|13 8|
|8 5|

A^7=
|21 13|
|13 8|

A^8=
|34 21|
|21 13|

and so on.

You will notice that the sequence of first numbers from each matrix is
the Fibonacci sequence.

Also note that the 'nth' power of A gives the 'n+1th' Fibonacci.

This technique is used in the Python code here:


http://en.wikipedia.org/wiki/Fibonacci_number_program#Matrix_equation

with reference to:


http://en.wikipedia.org/wiki/Exponentiating_by_squaring#Squaring_algorithm

(It in fact uses 3-tuples beginning with (1,1,0) because the symmetry
of the matrices in the sequence means that only three multiplications
are necessary).

Lisp and Scheme code (not using the matrix method) from the same page:

http://en.wikipedia.org/wiki/Fibonacci_number_program#Common_Lisp

http://en.wikipedia.org/wiki/Fibonacci_number_program#Scheme

hth

Gerard

(I am not a lisper, just lurking after reading this:
http://www.defmacro.org/ramblings/lisp.html )

.

Relevant Pages

  • Re: The last ancestor of all life
    ... that a specific sequence will exist in a given genome. ... terminology of probability theory. ... multiplying probabilities is the way to go here. ... However, at higher and higher levels, the size ...
    (talk.origins)
  • Re: The last ancestor of all life
    ... that a specific sequence will exist in a given genome. ... terminology of probability theory. ... multiplying probabilities is the way to go here. ... the proteins' P, P, P, etc. ...
    (talk.origins)
  • Re: and [True,True] --> [True, True]?????
    ... that the argument is a sequence. ... Maybe I was just too annoyed by lots of Python code I read that looked ... def foo: ... x could be a set, a dict, an unsorted list, a sorted list, a tuple, a ...
    (comp.lang.python)
  • Re: "do" as a keyword
    ... many thousands of lines of Python code, ... solutions in terms of iteration over sequence rather than as traditional ... If I need a "1 or more" loop I formulate the ... problem as a sequence of 1 or more elements. ...
    (comp.lang.python)
  • Re: Hilbert transform using FFT approach
    ... Multiplying any sequence that has zeros with another equal length ... sequence will have zeros in the same locations and may introduce more. ... Are you talking about a combined mix by Fs/4 and decimate by 4 filter? ...
    (comp.dsp)
Loading