dynamic_programming.fast_fibonacci

This program calculates the nth Fibonacci number in O(log(n)). It’s possible to calculate F(1_000_000) in less than a second.

Attributes

n

Functions

_fib(→ tuple[int, int])
fibonacci(→ int)	return F(n)

Module Contents

dynamic_programming.fast_fibonacci._fib(n: int) → tuple[int, int]

dynamic_programming.fast_fibonacci.fibonacci(n: int) → int

return F(n) >>> [fibonacci(i) for i in range(13)] [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]

dynamic_programming.fast_fibonacci.n