Computing x raised to the power n (written xn) naively requires n multiplications. Binary exponentiation (also called fast power or exponentiation by squaring) reduces this to O(log n) multiplications by halving the exponent at each step: if n is even, compute xn/2 and square it; if n is odd, multiply x by xn-1. The original …