This implementation of fibonacci follows https://www.nayuki.io/page/fast-fibonacci-algorithms, with a base case that uses math.pow.
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# Fibonacci #- from math import sqrt
c1 = (sqrt(5) - 1) / (2 * sqrt(5))c2 = (sqrt(5) + 1) / (2 * sqrt(5))def f(x):fibo = c1 * ((1 - sqrt(5)) / 2)**x + c2 * ((1 + sqrt(5)) / 2)**xreturn int(round(fibo))- 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
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 + btest.assert_equals(5, f(4), "")print f(1)print f(2)print f(3)print f(4)print f(5)- 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