## Re: [PrimeNumbers] Computational Number theory book

Expand Messages
• ... 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 1 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.