current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 0 down vote favorite

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)
share|improve this question
1  
Is this a programming challenge? If it is could you give us the formal requirements? Also do you want a review on the speed? – Joe Wallis Apr 29 at 7:56
1  
"Refactoring" has a very specific meaning. You shouldn't use the term as a synonym for "improve". – 200_success♦ Apr 29 at 9:17
    
You can see some ways of doing what you want here: programminglogic.com/fast-exponentiation-algorithms – Marcus Vinícius Monteiro Apr 29 at 10:44
up vote 3 down vote

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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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