Djisktra uses Lucas Powers to calculate Fibonacci

fibonacci.py

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

    Args:
        n (float): n
    """

    if n == 1:
        return (1, 1)
    L, F = lucas_power(n // 2)
    L, F = (L**2 + 5 * F**2) >> 1, L * F
    if int(n) & 1:
        return ((L + 5 * F) >> 1, (L + F) >> 1)
    else:
        return (L, F)


def _fib_djikstra(n: float):
    """fib.

    Args:
        n (float): n
    """

    if int(n) & 1:
        return lucas_power(n)[1]
    else:
        L, F = lucas_power(n // 2)
    return L * F


fibs = {0: 0, 1: 1}


def fibonacci_djikstra(n: int):
    """
    See: https://www.cs.utexas.edu/users/EWD/ewd06xx/EWD654.PDF

    >>> fibonacci_djikstra(80)
    23416728348467685
    """
    if n in fibs:
        return fibs[n]
    if n % 2 == 0:
        fibs[n] = ((2 * _fib_djikstra((n / 2) - 1)) + _fib_djikstra(n / 2)) * _fib_djikstra(n / 2)
        return fibs[n]
    else:
        fibs[n] = (_fib_djikstra((n - 1) / 2)**2) + (_fib_djikstra((n + 1) / 2)**2)

    return fibs[n]