Attributes¶

Functions¶

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_memoization(-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_recursive(0) [0] >>> fib_recursive(1) [0, 1] >>> fib_recursive(5) [0, 1, 1, 2, 3, 5] >>> fib_recursive(10) [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] >>> fib_recursive(-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_recursive_cached(0) [0] >>> fib_recursive_cached(1) [0, 1] >>> fib_recursive_cached(5) [0, 1, 1, 2, 3, 5] >>> fib_recursive_cached(10) [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] >>> fib_recursive_cached(-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¶