fib.py

#!/usr/bin/env python3
"""
Author: Craig Cabrey
"""

identity = [[1, 1], [1, 0]]


def multiply(first, second):
    """
    multiply two 2x2 matrices together and store the result in the first matrix

    matrix reading and writing is O(1), as is the addition and multiplication
    """

    a = first[0][0] * second[0][0] + first[0][1] * second[1][0]
    b = first[0][0] * second[0][1] + first[0][1] * second[1][1]
    c = first[1][0] * second[0][0] + first[1][1] * second[1][0]
    d = first[1][0] * second[0][1] + first[1][1] * second[1][1]

    first[0][0] = a
    first[0][1] = b
    first[1][0] = c
    first[1][1] = d


def power(L, n):
    """
    raise L to the nth power

    first, we recurse to the base case of n == 0 or n == 1. next we square L
    as we bubble back up the stack. squaring L each time saves us additional
    calls as opposed to naively raising L to the nth power.

    if n is not a power of 2, we multiply L by the identity matrix to adjust.

    this function is O(log(n))
    """

    if n == 0 or n == 1:
        return

    power(L, n // 2)
    multiply(L, L)

    if n % 2 != 0:
        multiply(L, identity)


def fibPow(n, a, b):
    """
    set the initial representation of L using sequence initializers a and b,
    then use the power algorithm to raise L to the nth power to yield the nth
    fibonacci number.

    L is represented as follows:

    ┌─────────────────┐   ┌───────────────┐
    | f(n+1) | f(n)   | ⇒ | a + b | b     |
    | f(n)   | f(n-1) |   | b     | a     |
    └─────────────────┘   └───────────────┘

    thus, we return either L[0][1] or L[1][0] to fulfill the function
    L^n(a, b)_1.

    this function is O(log(n))
    """

    L = [[a + b, b], [b, a]]
    power(L, n)

    return L[0][1]

print(fibPow(1000000, 0, 1))