- 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)

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

#}

#} - --- On Tue, 3/25/08, Kermit Rose <kermit@...> wrote:
> I just started to read David Bressoud's and Stan

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

> 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)

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

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.

> return value

> #}

> else:

> #{

> mhalf = (n - 1) / 2

> v1 = FibonacciMod(mhalf,z)

> v2 = FibonacciMod(mhalf + 1,z)

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

> return value

> #}

> #}

Phil

____________________________________________________________________________________

Be a better friend, newshound, and

know-it-all with Yahoo! Mobile. Try it now. http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ