# Exponentiation by Squaring (Logarithmic runtime)

*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**

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.

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.

`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!