Fast Exponentiation: Halve the Exponent and Reuse the Result — Read

Opening the reading…

An exponent can be halved without losing any factors

To compute 3^13, split the exponent into two halves and account for the remainder. Since 13 is odd, integer division gives 13 / 2 = 6 and leaves a remainder of 1. That gives 3^13 = 3^6 * 3^6 * 3, or (3^6)^2 * 3. The two copies of 3^6 make the squared half-power, and the extra factor of 3 accounts for the one exponent value discarded by integer division.

TEXTThe half exponent and the extra factor for an odd exponent.

3^13 = (3^6)^2 * 3

13 / 2 = 6
13 % 2 = 1

The same split works for an even exponent without an extra factor. If the exponent is even, n / 2 and n / 2 add to n exactly, so 3^n = (3^(n / 2))^2. If the exponent is odd, the two halves add to n - 1, so one more factor of 3 is needed. The algorithm therefore needs only one rule for the half-power and a parity decision for the extra factor.

CHECKPOINT 1Not answered

Which expression correctly decomposes 3^13 using a halved exponent?

Checkpoints are not graded. They are here so you catch yourself before the quiz does — stuck, ask the tutor on the right.

Fast exponentiation makes only one recursive call at each level

The recursive function first reaches the half-power once and stores its return value in half. It then squares half. For an odd exponent, it multiplies that square by 3; for an even exponent, it returns the square unchanged. The base case power(3, 0) returns 1, because every nonzero number raised to the zero exponent is 1.

CPPThe half-power is computed once and reused for both factors.

long long power(long long base, int exponent) {
    if (exponent == 0) {
        return 1;
    }

    long long half = power(base, exponent / 2);
    long long result = half * half;

    if (exponent % 2 == 1) {
        result *= base;
    }

    return result;
}

For the running computation, power(3, 13) calls power(3, 6) once and waits for its return value. It does not call power(3, 6) again to obtain the second factor. The stored value is enough because multiplying a number by itself is exactly what squaring means.

The answer is assembled while the calls return

The calls descend by integer-dividing the exponent by 2 each time. The chain is power(3, 13), power(3, 6), power(3, 3), power(3, 1), and power(3, 0). At exponent 0, the base case returns 1. No parity multiplication is needed there because the function stops before making another recursive call.

TEXTOne recursive descent, with the exponent halved at every call.

power(3, 13)
  -> power(3, 6)
       -> power(3, 3)
            -> power(3, 1)
                 -> power(3, 0) = 1

The values are assembled in the reverse order. Exponent 1 is odd, so its half value 1 gives 1 * 1 * 3 = 3. Exponent 3 is odd, so it gives 3 * 3 * 3 = 27. Exponent 6 is even, so it gives 27 * 27 = 729 without an extra factor. Exponent 13 is odd, so it gives 729 * 729 * 3 = 1594323.

CHECKPOINT 2Not answered

Replace the two repeated recursive calls with one stored value and reuse it in the even and odd results.

long long evenResult = power(3, n / 2) * power(3, n / 2);
long long oddResult = power(3, n / 2) * power(3, n / 2) * 3;

Checkpoints are not graded. They are here so you catch yourself before the quiz does — stuck, ask the tutor on the right.

DIAGRAM — NOT DRAWN YET

A vertical call chain descends from power(3, 13) to power(3, 6), power(3, 3), power(3, 1), and power(3, 0), with exactly one recursive arrow at each level. The base case returns 1. On the way up, exponent 1 returns 1 * 1 * 3 = 3, exponent 3 returns 3 * 3 * 3 = 27, exponent 6 returns 27 * 27 = 729, and exponent 13 returns 729 * 729 * 3 = 1594323.

One call goes down each level, and the squared results come back up.

One halved subproblem gives logarithmic time and stack depth

At exponent n, the function makes one recursive call on floor(n / 2). After that call returns, it performs a fixed number of operations: one multiplication to square the half value and possibly one multiplication by 3. This gives the recurrence T(n) = T(floor(n / 2)) + O(1). The floor appears because integer division is used for the exponent.

The exponents in the running trace are 13, 6, 3, 1, and 0, so only five calls are active along the call stack. In general, halving n repeatedly reaches 0 after O(log n) levels. Therefore fast exponentiation takes O(log n) time and O(log n) recursion space, with the space coming from the active call stack.