Ad
Code
Diff
  • def fib(x):
        fib = [1,1]
        for x in range(x-1):
            fib.append(fib[-2]+fib[-1])
        return fib[-1]
    • def _fib(n):
    • k = n.bit_length()-1
    • x0, x1 = 1, 0
    • y0, y1 = 0, 1
    • for i in range(k, -1, -1):
    • y2 = y0*y0
    • y0, y1 = 2*y0*y1+y2, y2+y1*y1
    • if (n>>i)&1:
    • xy = x0*y0
    • y0, y1 = x0*y1+x1*y0+xy, xy+x1*y1
    • return y0
    • def fib(n):
    • return _fib(n+1)
    • def fib(x):
    • fib = [1,1]
    • for x in range(x-1):
    • fib.append(fib[-2]+fib[-1])
    • return fib[-1]