Hacker News Reader

Comment by shiven | Hacker News Reader

Sorry, couldn't help myself!! That approach is just so damn elegant.

int((1/math.sqrt(5))*(math.pow(((1+math.sqrt(5))/2),fibonacci)-math.pow(((1-math.sqrt(5))/2),fibonacci)))

Reference here: http://mathproofs.blogspot.com/2005/04/nth-term-of-fibonacci...

Elegant, but inefficient if you want to get exact values for large n. You're much better off using doubling operations. If you forget those, you can remember them from the matrix version. If fib(0) = 0. fib(1) = 1. etc. Then

       n
  [0 1]  = [fib(n)   fib(n+1)]
  [1 1]    [fib(n+1) fib(n+2)]

With repeated squarings, you can efficiently generate any Fibonacci number you want.

Here (where you have to search through Fibonacci numbers) I suspect memoization is rather the way to go:

  # memoized fibonacci function
  fibtable = {1:1, 0:1}

  def fib (n):
      global fibtable
      if n in fibtable.keys():
          return fibtable [n]
      val = fib (n-1) + fib (n-2)
      fibtable [n] = val
      return val

There is no need to keep track of all previous values.

  last_fib = 0
  fib = 1
  while fib < 225000 or not is_prime(fib):
    last_fib, fib = fib, last_fib + fib

Reply on news.ycombinator.com