Code
Diff
  • def fib(x):
        fib = [1,1]
        for x in range(x-1):
            fib.append(fib[-2]+fib[-1])
        return fib[-1]
  • 1
    def _fib(n):
    
    2
        k = n.bit_length()-1
    
    3
        x0, x1 = 1, 0
    
    4
        y0, y1 = 0, 1
    
    5
        for i in range(k, -1, -1):
    
    6
            y2 = y0*y0
    
    7
            y0, y1 = 2*y0*y1+y2, y2+y1*y1
    
    8
            if (n>>i)&1:
    
    9
                xy = x0*y0
    
    10
                y0, y1 = x0*y1+x1*y0+xy, xy+x1*y1
    
    11
        return y0
    
    12
        
    
    13
    def fib(n):
    
    14
        return _fib(n+1)
    
    1+
    def fib(x):
    
    2+
        fib = [1,1]
    
    3+
        for x in range(x-1):
    
    4+
            fib.append(fib[-2]+fib[-1])
    
    5+
        return fib[-1]