maths.fibonacci

Calculates the Fibonacci sequence using iteration, recursion, memoization, and a simplified form of Binet’s formula

NOTE 1: the iterative, recursive, memoization functions are more accurate than the Binet’s formula function because the Binet formula function uses floats

NOTE 2: the Binet’s formula function is much more limited in the size of inputs that it can handle due to the size limitations of Python floats NOTE 3: the matrix function is the fastest and most memory efficient for large n

See benchmark numbers in __main__ for performance comparisons/ https://en.wikipedia.org/wiki/Fibonacci_number for more information

Attributes

num

Functions

fib_binet(→ list[int])

Calculates the first n (0-indexed) Fibonacci numbers using a simplified form

fib_iterative(→ list[int])

Calculates the first n (0-indexed) Fibonacci numbers using iteration

fib_iterative_yield(→ collections.abc.Iterator[int])

Calculates the first n (1-indexed) Fibonacci numbers using iteration with yield

fib_matrix_np(→ int)

Calculates the n-th Fibonacci number using matrix exponentiation.

fib_memoization(→ list[int])

Calculates the first n (0-indexed) Fibonacci numbers using memoization

fib_recursive(→ list[int])

Calculates the first n (0-indexed) Fibonacci numbers using recursion

fib_recursive_cached(→ list[int])

Calculates the first n (0-indexed) Fibonacci numbers using recursion

matrix_pow_np(→ numpy.ndarray)

Raises a matrix to the power of 'power' using binary exponentiation.

time_func(func, *args, **kwargs)

Times the execution of a function with parameters

Module Contents

maths.fibonacci.fib_binet(n: int) → list[int]

Calculates the first n (0-indexed) Fibonacci numbers using a simplified form of Binet’s formula: https://en.m.wikipedia.org/wiki/Fibonacci_number#Computation_by_rounding

NOTE 1: this function diverges from fib_iterative at around n = 71, likely due to compounding floating-point arithmetic errors

NOTE 2: this function doesn’t accept n >= 1475 because it overflows thereafter due to the size limitations of Python floats >>> fib_binet(0) [0] >>> fib_binet(1) [0, 1] >>> fib_binet(5) [0, 1, 1, 2, 3, 5] >>> fib_binet(10) [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] >>> fib_binet(-1) Traceback (most recent call last):

…

ValueError: n is negative >>> fib_binet(1475) Traceback (most recent call last):

…

ValueError: n is too large

maths.fibonacci.fib_iterative(n: int) → list[int]

Calculates the first n (0-indexed) Fibonacci numbers using iteration >>> fib_iterative(0) [0] >>> fib_iterative(1) [0, 1] >>> fib_iterative(5) [0, 1, 1, 2, 3, 5] >>> fib_iterative(10) [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] >>> fib_iterative(-1) Traceback (most recent call last):

…

ValueError: n is negative

maths.fibonacci.fib_iterative_yield(n: int) → collections.abc.Iterator[int]

Calculates the first n (1-indexed) Fibonacci numbers using iteration with yield >>> list(fib_iterative_yield(0)) [0] >>> tuple(fib_iterative_yield(1)) (0, 1) >>> tuple(fib_iterative_yield(5)) (0, 1, 1, 2, 3, 5) >>> tuple(fib_iterative_yield(10)) (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55) >>> tuple(fib_iterative_yield(-1)) Traceback (most recent call last):

…

ValueError: n is negative

maths.fibonacci.fib_matrix_np(n: int) → int

Calculates the n-th Fibonacci number using matrix exponentiation. https://www.nayuki.io/page/fast-fibonacci-algorithms#:~:text= Summary:%20The%20two%20fast%20Fibonacci%20algorithms%20are%20matrix

Args:

n: Fibonacci sequence index

Returns:

The n-th Fibonacci number.

Raises:

ValueError: If n is negative.

>>> fib_matrix_np(0)
0
>>> fib_matrix_np(1)
1
>>> fib_matrix_np(5)
5
>>> fib_matrix_np(10)
55
>>> fib_matrix_np(-1)
Traceback (most recent call last):
    ...
ValueError: n is negative
maths.fibonacci.fib_memoization(n: int) → list[int]

Calculates the first n (0-indexed) Fibonacci numbers using memoization >>> fib_memoization(0) [0] >>> fib_memoization(1) [0, 1] >>> fib_memoization(5) [0, 1, 1, 2, 3, 5] >>> fib_memoization(10) [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] >>> fib_iterative(-1) Traceback (most recent call last):

…

ValueError: n is negative

maths.fibonacci.fib_recursive(n: int) → list[int]

Calculates the first n (0-indexed) Fibonacci numbers using recursion >>> fib_iterative(0) [0] >>> fib_iterative(1) [0, 1] >>> fib_iterative(5) [0, 1, 1, 2, 3, 5] >>> fib_iterative(10) [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] >>> fib_iterative(-1) Traceback (most recent call last):

…

ValueError: n is negative

maths.fibonacci.fib_recursive_cached(n: int) → list[int]

Calculates the first n (0-indexed) Fibonacci numbers using recursion >>> fib_iterative(0) [0] >>> fib_iterative(1) [0, 1] >>> fib_iterative(5) [0, 1, 1, 2, 3, 5] >>> fib_iterative(10) [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] >>> fib_iterative(-1) Traceback (most recent call last):

…

ValueError: n is negative

maths.fibonacci.matrix_pow_np(m: numpy.ndarray, power: int) → numpy.ndarray

Raises a matrix to the power of ‘power’ using binary exponentiation.

Args:

m: Matrix as a numpy array. power: The power to which the matrix is to be raised.

Returns:

The matrix raised to the power.

Raises:

ValueError: If power is negative.

>>> m = np.array([[1, 1], [1, 0]], dtype=int)
>>> matrix_pow_np(m, 0)  # Identity matrix when raised to the power of 0
array([[1, 0],
       [0, 1]])

>>> matrix_pow_np(m, 1)  # Same matrix when raised to the power of 1
array([[1, 1],
       [1, 0]])

>>> matrix_pow_np(m, 5)
array([[8, 5],
       [5, 3]])

>>> matrix_pow_np(m, -1)
Traceback (most recent call last):
    ...
ValueError: power is negative
maths.fibonacci.time_func(func, *args, **kwargs)

Times the execution of a function with parameters

maths.fibonacci.num = 30