Fast Exponentiation and Matrix Power: The Trick Behind "Compute the Nth Fibonacci Number in O(log n)

Some interview questions look like simple loops until the interviewer adds one condition: "n can be up to 10^18." Suddenly O(n) is too slow, and the expected answer is exponentiation by squaring, sometimes applied to matrices. It is a compact idea that shows up in math-flavored problems, modular arithmetic questions, and linear recurrences. Exponentiation by squaring To compute x^n, notice that x^n = (x^(n/2))^2 when n is even, and x * x^(n-1) when n is odd. Each step halves n, so the work is O(log n) multiplications. def power(x, n, mod): result = 1 x %= mod while n > 0: if n & 1: result = result * x % mod x = x * x % mod n >>= 1 return result The loop reads the bits of n from least significant to most significant. Every bit that is 1 contributes the current power of x to the result. Python has pow(x, n, mod) built in, but interviewers usually want to see you write it. Handling negative exponents For "implement pow(x, n)" with floating point x, handle n < 0 by computing power(1/x, -n). Watch the edge case where n is the minimum 32-bit integer in languages like Java, because negating it overflows. From numbers to matrices The Fibonacci recurrence F(n) = F(n-1) + F(n-2) can be written as a matrix multiplication: [F(n+1)] [1 1] [F(n) ] [F(n) ] = [1 0] [F(n-1)] So the vector after n steps is M^n applied to the starting vector, where M = [[1, 1], [1, 0]]. Raise M to the nth power with the same squaring trick, using matrix multiplication instead of number multiplication, and you get F(n) in O(log n) time. def mat_mult(a, b, mod): return [[(a[0][0]*b[0][0] + a[0][1]*b[1][0]) % mod, (a[0][0]*b[0][1] + a[0][1]*b[1][1]) % mod], [(a[1][0]*b[0][0] + a[1][1]*b[1][0]) % mod, (a[1][0]*b[0][1] + a[1][1]*b[1][1]) % mod]] def fib(n, mod=10**9 + 7): result = [[1, 0], [0, 1]] m = [[1, 1], [1, 0]] while n > 0: if n & 1: result = mat_mult(result, m, mod) m = mat_mult(m, m, mod) n >>= 1 return result[0][1] Where else it applies - Any linear recurrence with fixed coefficients, such as tribonacci or "number of ways to tile a 2 x n board", becomes a k x k matrix power. - Counting paths of exactly length L in a graph: raise the adjacency matrix to the Lth power. - Modular inverse with a prime modulus: by Fermat's little theorem, the inverse of a is a^(p-2) mod p, computed with fast exponentiation. Complexity Number exponentiation is O(log n). Matrix exponentiation with a k x k matrix is O(k^3 log n), which is excellent when k is small and n is huge. How to present it in an interview Start with the naive loop and its O(n) cost, then explain the halving observation, then generalize to matrices if the problem is a recurrence. Mention modular arithmetic early if numbers can get large; interviewers notice when you protect against overflow. Explaining the bit-by-bit loop while coding is easy to fumble when you are nervous. Linkjob AI (https://linkjob.ai) provides real-time help during job interviews and technical interviews, helping you keep your explanation organized step by step. It is most useful on top of real practice. Takeaway: when n is enormous and the operation is associative, think "square and halve".