raeq

def fibonacci_recursive(i: int = None) -> int:
    """
    The simplest way to calculate a fibonacci number, using recursion.
    Simple works, but not in all cases!

    >>> fibonacci_recursive(20)
    6765
    >>> # fibonacci_recursive(100) No, don't do this, it will take forever and exhaust your computer's memory
    """
    if i == 0:

raeq

def memo(func):
    """
    An @memo decorator for functions and methods.
    It defines an internal cache. The key is value of the parameter used in the wrapped function.
    Say we call a fibonacci generator with a value of 30. The result is stored in the cache:

        cache[30] = 1346269

    When we call the fibonacci generator with 30, we can just get the value for 30 out of the cache instead
    of calculating it all again. Pretty goddamn sweet.

raeq

@memo
def fibonacci_wrapped(i: int = None) -> int:
    """
    This technique uses exactly the same recursive algorithm as in the naive solution.
    However, we are now using a technique known as "memoization". This is really useful in some
    recursive algorithms, because otherwise the same set of values is constantly being calculated.
    Here we use a nice and simple decorator to add the memoization capability.

    However, we're still using recursion, and at some point the maximum recursion depth will be reached.

raeq

def matrix_fibonacci(target: int) -> int:
    """
    This is the fastest way to compute a fibonacci number, using matrix mathematics.
    It completes quickly.
    The math is explained in detailed on the Wiki page at: https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form


    >>> matrix_fibonacci(80)
    23416728348467685

raeq

def fibonacci_goldenratio(target):
    """
    This method works by calculating the golden ratio, and then
    raising the golden ration to the power of n, whereby n is the position of the fibonacci sequence.

    As we look for higher and higher values of n, rounding errors throw us off. This method works for values of n
    less than 72 or so.

    :param target:
    :return:

raeq

def lucas_power(n: float):
    """lucas_power.

    Args:
        n (float): n
    """

    if n == 1:
        return (1, 1)
    L, F = lucas_power(n // 2)

raeq

def karatsuba_fast_multiply(multiplier: int, multiplicand: int) -> int:
    """
    Karatsuba fast multiplication, published in 1962
    https://en.wikipedia.org/wiki/Karatsuba_algorithm

    Args:
        x ():
        y ():

    Returns: int

raeq

def karatsuba_fast_multiply(multiplier: int, multiplicand: int) -> int:
    """
    Karatsuba fast multiplication, published in 1962
    https://en.wikipedia.org/wiki/Karatsuba_algorithm

    Args:
        x ():
        y ():

    Returns: int

raeq

def karatsuba_fast_multiply(multiplier: int, multiplicand: int) -> int:
    """
    Karatsuba fast multiplication, published in 1962
    https://en.wikipedia.org/wiki/Karatsuba_algorithm

    Args:
        x ():
        y ():

    Returns: int

raeq

import functools
@functools.lru_cache()
def _fd_fib(n: int) -> tuple:
    """_fd_fib.

    Args:
        n (int): n

    Returns:
        tuple: