title: Fast Fibonacci slows to a crawl over 1,000,000
body: <p>I've written a pretty standard fibonacci function through fast doubling using an algorithm derived from the matrix exponentiation algorithm which should run in O(log(n)) time and calls, but stalls out at around over 1,000,000 - even when that should be just around 25 calls.</p>
  
  <p>Code: </p>
  
  <pre><code>"""
  O(log(n)) time fibonacci algorithm using fast doubling derived from the matrix
  squaring algorithm for the same thing.
  """
  
  def fibonacci(num):
      "O(log(n)) implementation of fibonacci using fast doubling."
      if num &gt;= 0:
          return fib_helper(num)[0]
  
  def fib_helper(num):
      "Helper function for fibonacci()."
      if num == 0:
          return (0, 1)
      elif num == 1:
          return (1, 1)
      else:
          f_k, f_k_1 = fib_helper(num // 2)
          f_k_even = f_k * (2 * f_k_1 - f_k)
          f_k_odd = f_k_1 * f_k_1 + f_k * f_k
          return (f_k_even, f_k_odd) if num % 2 == 0 else (f_k_odd, f_k_even +
                  f_k_odd)
  </code></pre>
  
  <p>This code <em>should</em> only generate log(n) calls to fib_helper and one call to fibonacci. For numbers greater than 1,000,000 it just stalls out and doesn't return.</p>
  
  <p>I've tried implementing a basic decorator to to count function calls which tells me that it is only running 32 calls for 2^32, but it still stalls out at the end.</p>
  
  <p>Why is this slowing to a halt on large integers?</p>