A checksum helper needs 3^20 modulo a prime. The intern writes a loop of twenty multiplies. Fine. Then the spec becomes 3^1_000_000_007. A million multiplies is the wrong primitive. The exponent is already a binary number. Each bit is a square-or-multiply.

Binary exponentiation squares the base and multiplies into the answer when the current bit of the exponent is 1 — O(log exp) multiplies. Same recurrence as “power = square of power of half.” Iterative bit peeling is the form you ship.

This post is that loop. GCD / inverse is Euclid. Shuffle is Fisher-Yates. Catalog: Algorithms Roadmap. It is not Math.pow (floating), not BigInteger.modPow internals as a lecture, and not crypto.

The loop of exp products

static long powNaive(long base, int exp) {
    long acc = 1;
    for (int i = 0; i < exp; i++) {
        acc *= base;
    }
    return acc;
}

exp multiplies. Overflow is Java’s wrap if you stay in long. Modular pow needs % m on every multiply or you wrap the wrong ring.

Square, then maybe multiply

3^13 = 3^(8+4+1) = 3^8 · 3^4 · 3^1
13 = 1101₂
start acc=1, base=3
bit0 1 → acc *= 3;  base *= base   (base=9)
bit1 0 →            base *= base   (base=81)
bit2 1 → acc *= 81; base *= base
bit3 1 → acc *= base
static long modPow(long base, long exp, long m) {
    if (m == 1) {
        return 0;
    }
    long acc = 1;
    base %= m;
    while (exp > 0) {
        if ((exp & 1) == 1) {
            acc = (acc * base) % m;
        }
        base = (base * base) % m;
        exp >>= 1;
    }
    return acc;
}

Each step halves exp. Multiplies are O(log exp). For non-modular long power, drop % m and document overflow. Negative exponents are rationals — not this loop unless you invert (egcd) first in a field.

Math.pow returns double. BigInteger.modPow is the JDK call for big modular exponentiation. BigInteger.pow is the non-modular bigint form. Write the bit loop when you are in long modulo a prime you already trust, or when the interview is the binary method.

Note: (acc * base) % m can overflow long before % if m is larger than 2^31. Use Math.multiplyExact in a BigInteger path, or a safe multiply, when m does not fit that assumption. Interview m is usually a 32-bit prime.

When not to use this loop

  • Floating a^x. Math.pow.
  • Huge m. BigInteger.modPow.
  • You needed n multiplies of a matrix / doubling formula. Same bit peeling, different monoid. Say so.
  • Constant exp in a hot shader. Unroll; do not pretend log2(8) is a win.

Cheat sheet

Job:       base^exp, or base^exp mod m
Recurrence: even exp → (base^2)^(exp/2); odd → base * base^(exp-1)
Loop:      while exp>0: if odd acc*=base; base*=base; exp>>=1
Time:      O(log exp) multiplies
JDK:       Math.pow (double); BigInteger.pow / modPow
Not this:  naive exp multiplies; floats; crypto libraries

Do:

  • Reduce base %= m first for modular pow.
  • Use BigInteger.modPow when width is not long.
  • Pair with Euclid when you need an inverse for negative exponents mod p.

Don’t:

  • Multiply exp times and call it fine at a billion.
  • Mix Math.pow into an integer ring and round.
  • Skip overflow on (acc * base) when m is near 2^63.

Wrap-up

Binary exponentiation reads the exponent as bits: square every step, multiply into the accumulator on a 1-bit. Logarithmic multiplies are the contract. The JDK already has this for BigInteger; the loop is what you write in long.

The next procedure is a shuffle that is fair: Fisher-Yates, which is what Collections.shuffle already is.

Next optional step in the series Unbiased in-place shuffle — the algorithm behind Collections.shuffle. Fisher-Yates: Shuffle in Place Without Bias