# Exponentiation using while loop in Python

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)


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