With preconditions p ≥ 1 and n ≥ 0 (no overflow): int x = p; int k = n; int m = 1; while (k != 0) { if (k is odd) m = m * x; x = x * x; k = floor(k / 2); } The loop invariant is m·xᵏ = pⁿ and k ≥ 0. Which must be true at the end?

1. Ax = pⁿ
2. Bm = pⁿ
3. Cp = xⁿ
4. Dp = mⁿ

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: B. m = pⁿ

Explanation

When the loop ends k = 0, so the invariant m·x⁰ = pⁿ gives m = pⁿ (fast exponentiation).