Discussion on: Let's Get Clever #1: Fibonacci Sequence

[edA‑qa mort‑ora‑y]

I'm going for the bonus points, no explicit loops nor recursion, and O(1) time*.

import math

sq5 = math.sqrt(5.0)
def fib( n ):
    a = ((1.0 + sq5)/2) ** n
    b = ((1.0 - sq5)/2 ) ** n
    return  int( (a - b) / sq5 )

for i in range(20):
    print(fib(i))

This is a closed form evaluation of the n-th fibonnaci number.

The int cast is because the double isn't precise enough, thus a bit of error value accumulates. Remove it to see how much.

** Time complexity, you might get picky here and we can debate what the time complexity of **n is. In worst case it shouldn't be more than log(n) given that the generic pow is log(n).

[Jarod Smith]

Interesting in javascript this will have precision errors after fib(75).
Probably because of the limitations on floating point math precision.

[Jason C. McDonald]

HA! I was getting worried that the efficiency bonus goal was actually impossible, but I just had that nagging feeling there was some algorithmic way of solving this without generating each preceding element.

[edA‑qa mort‑ora‑y]

Everything is more fun with unicode:

import math

sq5 = math.sqrt(5.0)
φ = (1.0 + sq5)/2.0
ψ = -1/φ

def fib_x( n ):
    return  int( (φ ** n - ψ ** n) / sq5 )

for i in range(20):
    print(fib_x(i))