0
\$\begingroup\$

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)
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.