4 ms·

Code to generate fibs is literally one line. Remember eigenvalues :)?

• shiven 16y ago
  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-sequence.html http://mathproofs.blogspot.com/2005/04/nth-term-of-fibonacci...
  • btilly 16y ago
    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.
    • kasterma 16y ago
      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
      • btilly 16y ago
        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