Bill Dubuque
Guest
|
 Posted: Sat Jul 19, 2008 12:53 am Post subject: Re: Maple fibonacci bug ? |
 |
|
Michael Press <rubrum@pacbell.net> wrote:
[quote]
The following identity for the Fibonacci numbers is well known.
F_{n-1}F_{m} + F_{n}F_{m+1} = F_{m+n}
Set n = m+1 (F_{m})^2 + (F_{m+1})^2 = F_{2m+1}
Suppose we know F_{k-1}, F_{k},F_{k+1}. Then
F_{2k-1} = (F_{k-1})^2 + (F_{k})^2
F_{2k} = (F_{k+1})^2 - (F_{k-1})^2
F_{2k+1} = (F_{k})^2 + (F_{k+1})^2
If we want to know F_{n} for large n, we can find it
without iterating up from F_1.
(20)_10 = (10100)_2
F_4 = 3, F_5 = 5, F_6 = 8
F_9 = 3^2 + 5^2 = 34
F_10 = 8^2 - 3^2 = 55
F_11 = 5^2 + 8^2 = 89
F_19 = 34^2 + 55^2 = 4181
F_20 = 89^2 - 34^2 = 6765
F_21 = 55^2 + 89^2 = 10946
There are formulae that accomplish each step with
only 2 multiplications, rather than 3 squares.
[/quote]
In fact any linear recursive sequence can be computed quickly
in a similar manner. One need only recast a k-term recursion
in system form as
[f(n+1),f(n+2),..,f(n+k)] = A [f(n),f(n+1),..,f(n+k-1)]
so that A is the shift operator. Computing the n>th term amounts
to computing A^n, doable by repeated squaring quickly O(log_2 n).
When applied to the fibonacci sequence this yields
n
[ f ] [ 0 1 ] [ f ] [ 0 1 ] [ f ]
| n | | | | n-1 | | | | 0 |
| | = | | | | = ... = | | | |
| f | | | | f | | | | f |
[ n+1 ] [ 1 1 ] [ n ] [ 1 1 ] [ 1 ]
Sometimes linearity isn>t needed, e.g. [1] when proving cyclical.
The inverse process, going from a system of first order equations
to a linear homogeneous equation is also very important - see my
prior post [2] on the cyclic-vector method for references.
Note that the method of repeated-squaring is nothing but rewriting
the expt in Horner poly form (radix 2), as I explained before [3].
--Bill Dubuque
[1] http://google.com/groups?selm=y8zoe5857bx.fsf%40nestle.csail.mit.edu
[2] http://google.com/groups?selm=y8z1x4fnind.fsf%40nestle.csail.mit.edu
[3] http://google.com/groups?selm=y8zznx39vsz.fsf%40nestle.ai.mit.edu |
|
