Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] Computational Number theory book

Expand Messages
  • Phil Carmody
    ... 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
    • 0 Attachment
      --- 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.