--- On Tue, 3/25/08, Kermit Rose <

kermit@...> wrote:

> I just started to read David Bressoud's and Stan

> Wagon's excellent book,

>

> "Computational Number Theory".

>

> In the first chapter, section 1, they discuss Fibonacci

> numbers.

>

> Based on what I learned in that section, I wrote a function

> that will

> efficiently calculate

> Fibonacci numbers mod z.

>

>

>

> def FibonacciMod(n,z=0):

>

> ### Function is based on the identity f_(n + m + 1) =

> f_n * f_m +

> f_(n+1) * f_(m+1)

>

>

> #{

> if z == 0:

> #{

> v = Fibonacci(n)

> return v

> #}

> if n < 1:

> #{

> return 0

> #}

> if n < 3:

> #{

> return 1

> #}

> if n%2 == 0:

> #{

> mhalf = n/2

> v1 = FibonacciMod(mhalf - 1,z)

> v2 = FibonacciMod(mhalf,z)

> v3 = FibonacciMod(mhalf + 1,z)

Now grab a copy of Knuth, and work out the Big-Oh of that.

> value = (v2 * (v1 + v3) )%z

> return value

> #}

> else:

> #{

> mhalf = (n - 1) / 2

> v1 = FibonacciMod(mhalf,z)

> v2 = FibonacciMod(mhalf + 1,z)

> value = (v1**2 + v2**2)%z

> return value

> #}

> #}

There's an explanation of efficient implementation in Crandall & Pomerance. One method that's easy is to maintain 2 consecutive terms of the fibonacci function, F_n and F_{n+1}, as from that you can easily calculate either F_{2n} and F_{2n+1} or F_{2n+1} and F_{2n+2}, which are also consecutive terms.

Phil

____________________________________________________________________________________

Be a better friend, newshound, and

know-it-all with Yahoo! Mobile. Try it now.

http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ