Pow(x, n)

def my_pow(x, n):
    if n < 0:
        x, n = 1 / x, -n
    result = 1
    while n:
        if n & 1:          # odd
            result *= x    # into the pouch
        x *= x             # square the base
        n >>= 1            # halve the exponent
    return result

Pow x n. Given a number x and a whole number n, compute x to the power n. And n can be negative.

Take two to the tenth: ten twos multiplied, one thousand twenty-four. A negative power flips it: two to the minus two is one over four, a quarter.

The simple way multiplies x in, n times. But n can be about two billion, so that's far too slow.

Here's the trick: squaring doubles the power. Square two for two to the second, again for the fourth, then the eighth. So each step, square the base and halve the exponent. When the exponent is odd, one copy is left over: multiply it into the result first. For a negative n, use one over x.

In code: flip x if n is negative, start the result at one. While n is not zero: if n is odd, multiply the result by x. Then square x, and halve n.

Let's forge two to the tenth. Ten is even, so square: x is four, n is five. Five is odd, so the pouch takes four. Square: x is sixteen, n is two. Two is even: x is two fifty-six, n is one. One is odd, so the pouch takes two fifty-six. Four times two fifty-six is one thousand twenty-four. In binary, ten is one zero one zero: its ones mark the steps that filled the pouch.

The exponent halves every step, so the time is log n. Only a few variables, so the space is constant.

Square the base, halve the power, pocket the odd ones. That's Pow x n.