maths.fibonacci
===============

.. py:module:: maths.fibonacci

.. autoapi-nested-parse::

   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
----------

.. autoapisummary::

   maths.fibonacci.num


Functions
---------

.. autoapisummary::

   maths.fibonacci.fib_binet
   maths.fibonacci.fib_iterative
   maths.fibonacci.fib_iterative_yield
   maths.fibonacci.fib_matrix_np
   maths.fibonacci.fib_memoization
   maths.fibonacci.fib_recursive
   maths.fibonacci.fib_recursive_cached
   maths.fibonacci.matrix_pow_np
   maths.fibonacci.time_func


Module Contents
---------------

.. py:function:: 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


.. py:function:: 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


.. py:function:: 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


.. py:function:: 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


.. py:function:: 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


.. py:function:: 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


.. py:function:: 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


.. py:function:: 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


.. py:function:: time_func(func, *args, **kwargs)

   Times the execution of a function with parameters


.. py:data:: num
   :value: 30