## Computational Number theory book

Expand Messages
• 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
Message 1 of 2 , Mar 24, 2008
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
#}
#}
• ... Now grab a copy of Knuth, and work out the Big-Oh of that. ... There s an explanation of efficient implementation in Crandall & Pomerance. One method
Message 2 of 2 , Mar 25, 2008
--- 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
Your message has been successfully submitted and would be delivered to recipients shortly.