Exponentiation using while loop in Python

Question

I could not think of any better way to raise to power, except this, but how do I refactor it? I should only use while loop, not for loop, not x**y.

I shall not use pow(x,y)

result = 1
base = 3
counter = 1
degree = 4
while counter <= degree:
        result = base * result
        counter += 1
        print("counter %d and the result %d" %(counter, result))
print("result is ", result)

Answer 1

Your algorithm is \$O(n)\$ where \$n = \text{degree}\$. This means the performance of your code is quite poor. You can make an \$O(\log(n))\$ algorithm by using binary operators on the exponent.

For an explanation of this algorithm, you:

• Have the exponent in a form where you can manipulate it's binary.

• Whilst the exponent isn't empty:

  • If the last (smallest) index of the exponent is 1, times result by the base.
  • Remove the last index of the exponent.
  • Multiply the base by it's self.

Which results in:

def pow(base, exp):
    result = 1
    while exp:
        if exp & 1:
            result *= base
        exp >>= 1
        base *= base
    return result