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()-1x0, x1 = 1, 0y0, y1 = 0, 1for i in range(k, -1, -1):y2 = y0*y0y0, y1 = 2*y0*y1+y2, y2+y1*y1if (n>>i)&1:xy = x0*y0y0, y1 = x0*y1+x1*y0+xy, xy+x1*y1return y0def 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]
test.assert_equals(1, fib(0)) test.assert_equals(1, fib(1)) test.assert_equals(2, fib(2)) test.assert_equals(3, fib(3)) test.assert_equals(5, fib(4)) test.assert_equals(8, fib(5)) a = 0 b = 1 for i in range(1000): test.assert_equals(b, fib(i)) tmp = a a = b b = tmp + b- test.assert_equals(1, fib(0))
- test.assert_equals(1, fib(1))
- test.assert_equals(2, fib(2))
- test.assert_equals(3, fib(3))
- test.assert_equals(5, fib(4))
- test.assert_equals(8, fib(5))
- a = 0
- b = 1
- for i in range(1000):
- test.assert_equals(b, fib(i))
- tmp = a
- a = b