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

Computational Number theory book

Expand Messages
  • Kermit Rose
    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
      #}
      #}
    • 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 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.