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

Improved Fibonacci routine

Expand Messages
  • Kermit Rose
    Thanks to Phil s hint, I have improved my FibonacciMod routine. My previous routine, using recursion, was inefficient. I see now that the recursion routine
    Message 1 of 1 , Mar 25 8:09 PM
    • 0 Attachment
      Thanks to Phil's hint, I have improved my FibonacciMod routine.

      My previous routine, using recursion, was inefficient.

      I see now that the recursion routine calculates the same Fibonacci
      values many times.

      This improved routine calculates each Fibonacci value on the binary
      ladder exactly once.





      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
      #}


      ##### Get binary sequence

      listbin = []
      mm = n + 0
      while mm > 1:
      #{
      listbin.append(mm)
      mm = mm//2
      #}


      lenmm = len(listbin)
      p0 = 0
      p1 = 1
      Fib0 = 0
      Fib1 = 1
      while lenmm > 0:
      #{
      lenmm = lenmm - 1
      target = listbin[lenmm]

      if target == p0 + p1 + 1:
      #{
      Fibnext0 = (Fib0 * Fib0 + Fib1 * Fib1)%z
      Fib2 = (Fib0 + Fib1)%z
      Fibnext1 = (Fib0 * Fib1 + Fib1 * Fib2)%z
      p0 = target - 1
      p1 = target + 0
      Fib0 = Fibnext0 + 0
      Fib1 = Fibnext1 + 0


      continue
      #}





      if target == 2 * p1 + 1:
      #{
      Fib2 = (Fib0 + Fib1)%z
      Fibnext0 = (Fib0 * Fib1 + Fib1 * Fib2)%z
      Fibnext1 = (Fib1 * Fib1 + Fib2 * Fib2)%z
      p0 = target - 1
      p1 = target + 0
      Fib0 = Fibnext0 + 0
      Fib1 = Fibnext1 + 0
      continue
      #}



      #}
      return Fib1
      #}
    Your message has been successfully submitted and would be delivered to recipients shortly.