Fast Exponentiation by Squaring
Implement a function power(base, exponent) that computes base^exponent efficiently, where exponent is a non-negative integer.
Your solution must run in $O(\log n)$ time where $n$ is the exponent, rather than the naive $O(n)$ approach of repeated multiplication.
Provide both recursive and iterative implementations, and explain the key idea.
Constraints: - $0 \le \text{exponent} \le 10^9$ - base can be any real number (including negative and zero)
Examples: - Input: base = 2, exponent = 10 -- Output: 1024 - Input: base = 3, exponent = 0 -- Output: 1 - Input: base = 2, exponent = 31 -- Output: 2147483648
Hints
- Think about what happens when you square $x^{n/2}$ -- how many multiplications does that save compared to computing $x^n$ directly?
- Use the recurrence $x^n = (x^{n/2})^2$ when $n$ is even, and $x^n = x \cdot x^{n-1}$ when $n$ is odd.
- For the iterative version, process the binary representation of $n$ from the least significant bit upward, squaring the base at each step.
Worked Solution
How to Think About It: The naive approach multiplies base by itself n times -- $O(n)$ operations. When $n$ can be a billion, that is way too slow. The key observation is that you can express any power in terms of half-powers. If $n$ is even, $x^n = (x^{n/2})^2$ -- one recursive call plus one multiplication. If $n$ is odd, peel off one factor: $x^n = x \cdot x^{n-1}$. Since you halve the exponent at each step, you do at most $O(\log n)$ multiplications total. This is the same idea behind binary search -- exploit the binary representation of the input.
Algorithm: Write the exponent in binary. Scan the bits from least significant to most significant. Maintain a running result and a running power of the base. For each bit that is set, multiply the result by the current power. Square the power at every step.
Code:
Recursive: ```python def power(x, n): if n == 0: return 1 if n % 2 == 0: half = power(x, n // 2) return half * half else: return x * power(x, n - 1) ```
Iterative (preferred -- $O(1)$ space): ```python def power(x, n): result = 1 while n > 0: if n % 2 == 1: result *= x x *= x n //= 2 return result ```
Walkthrough with $2^{10}$: - $n = 10 = 1010_2$ - Step 1: $n$ is even, skip multiply. Square base: $x = 4$. $n = 5$. - Step 2: $n$ is odd, $\text{result} = 4$. Square base: $x = 16$. $n = 2$. - Step 3: $n$ is even, skip. Square base: $x = 256$. $n = 1$. - Step 4: $n$ is odd, $\text{result} = 4 \times 256 = 1024$. Done. - Total: 4 multiplications instead of 9.
Complexity: $O(\log n)$ time, $O(1)$ space (iterative) or $O(\log n)$ stack space (recursive).
Answer: Exponentiation by squaring computes $x^n$ in $O(\log n)$ multiplications by repeatedly halving the exponent and squaring the base. The iterative version processes the binary representation of $n$ bit by bit.
Intuition
Exponentiation by squaring is one of the most fundamental algorithmic tricks. The core idea -- reducing a problem of size $n$ to size $n/2$ in constant work -- is the same pattern behind binary search, merge sort, and many divide-and-conquer algorithms. In practice, this shows up in modular exponentiation for cryptography (RSA), matrix exponentiation for solving linear recurrences (Fibonacci in $O(\log n)$), and computing large powers in competitive programming. The iterative version is essentially reading the binary digits of the exponent and deciding at each bit whether to fold the current base power into the result.