Ad
Zantyrvs.Johnicholas

Find the nth Fibonacci number

Not sure whether it fits the theme - not using the phi constant.

The algorithm is an implementation of some 3kyu kata and is described there: https://mitpress.mit.edu/sicp/chapter1/node15.html The transform must be found by you yourself, as the p' and q' are not given. I did this by observing how individual transforms behave and concluding.

Code
Diff
  • def fib(n):
    if n<0:
        if n%2: return fib(-n)
        else: return -fib(-n)
    def transform(a,b,p,q,n):
        if n==0: return a
        if n%2==0:
            return transform(a,b,p*p+q*q,q*q+2*p*q,n/2)
        else:
            return transform(a*q+a*p+b*q,b*p+a*q,p,q,n-1)
    return transform(1,0,0,1,n)
    • from math import sqrt
    • def fib(x):
    • if x < 70:
    • a = 0.7236067977499789 # (sqrt(5) + 1) / (2 * sqrt(5))
    • b = 1.618033988749895 # (1 + sqrt(5)) / 2
    • return round(a * b**x)
    • elif x % 2 == 0:
    • a = fib(x / 2)
    • b = fib(x / 2 + 1)
    • return a * (2 * fib(b) - a)
    • else:
    • # x % 2 == 1, by elimination
    • a = fib((x - 1) / 2)
    • b = fib((x + 1) / 2)
    • return a * a + b * b
    • def fib(n):
    • if n<0:
    • if n%2: return fib(-n)
    • else: return -fib(-n)
    • def transform(a,b,p,q,n):
    • if n==0: return a
    • if n%2==0:
    • return transform(a,b,p*p+q*q,q*q+2*p*q,n/2)
    • else:
    • return transform(a*q+a*p+b*q,b*p+a*q,p,q,n-1)
    • return transform(1,0,0,1,n)