Exponentiation by Squaring (Logarithmic runtime)

Christopher Diep
3 min readNov 25, 2018

Efficiency trick!

I grew up learning math early on. My dad would borrow videos from the library. I would watch those videos and learn math.

Coding puts me in the same state of mind as math did. Whether it was arithmetic, linear algebra, or multivariable calculus, I get into a flow where all that exists is me and this abstract logic. We are one, yet we are separate.

Recently, I ran into a problem that brought math and coding together into a simple logic problem.

More Efficient Fibonacci

Matrix to calculate Fibonacci

The Fibonacci sequence can be calculated with linear algebra. The derivation just requires remembering high school math knowledge to understand. (Or a YouTube video will suffice.)

The problem presented is to write a function that would return the last six digits of the n-th number in a Fibonacci sequence.

With this fun little factoid, I can write a function with logarithmic runtime.

Raise it to the Power of…

First, let’s write out a function for matrix multiplication in which we only care about the six least significant figures.

function multiplyMatrices(m, n) {
let a = (m[0][0] * n[0][0] + m[0][1] * n[1][0]) % 1000000;
let b = (m[0][0] * n[0][1] + m[0][1] * n[1][1]) % 1000000;
let c = (m[1][0] * n[0][0] + m[1][1] * n[1][0]) % 1000000;
let d = (m[1][0] * n[0][1] + m[1][1] * n[1][1]) % 1000000;
return [[a, b], [c, d]]
}

The next part is exponentiation by squaring. This is based off the power rule for exponents.

http://www.math.com/school/subject2/lessons/S2U2L2DP.html

In this example, it is possible to (1) square 5 and then cube its square or (2) multiply by 5 repeatedly until the it is done with six 5’s. Option 1 is logarithmic. Option 2 is linear. Here’s what my function looks like for option 2:

function matrixToPower(m, exp) {
if (exp === 1) return m;
let mSquared = multiplyMatrices(m, m); if (exp % 2 === 0) {
return matrixToPower(mSquared, exp / 2)
} else {
return multiplyMatrices(m, matrixToPower(mSquared, Math.floor(exp / 2)))
}
}

Where’s Fibonacci?

Well, don’t forget this Fibonacci factoid from earlier.

Matrix to calculate Fibonacci
function fibonacci(N) {
if (N < 2) {
return N
} else {
let fibMatrix = [[1, 1], [1, 0]];
let result = matrixToPower(fibMatrix, N - 1);
return result[0][0]
}
}

More efficient algorithms make me happy!

Sources

--

--