Created
April 25, 2016 19:12
-
-
Save craigcabrey/9a9825ad2295551b8e868d327793c77c to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment