CODEWITHSUNDEEP
pythonmathexponential
MTG
MTG

Reputation: 163

Exponentiate (Multiply) Without ** (Python)

How can I perform this:

if p1 == 0:
    return 1
if p1 == 1:
    return temp_obj
if p1 == 2:
    return temp_obj*temp_obj
if p1 == 3:
    return temp_obj*temp_obj*temp_obj
if p1 == 4:
    return temp_obj*temp_obj*temp_obj*temp_obj

Without using **

I am actually writing this in a class that overloads pow and the * is already overloaded.

I tried 

for x in range(p1):
  temp_obj = temp_obj * temp_obj

But that didn't work. The values were very high.

Thanks

Upvotes: 2

Views: 426

Answers (3)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477533

The reason this does not work is because you square the number for every value of the power. So that means that for p1 = 3, we get:

temp_obj = 5
temp_obj = temp_obj * temp_obj = 25
temp_obj = temp_obj * temp_obj = 625
temp_obj = temp_obj * temp_obj = 390625

So you actually calculated 523. So 58 = 390'625.

We can solve this by each time multiplying with the value, so:

def power(x, p):
    if not p:
        return 1
    y = x
    for x in range(p-1):
        y *= x
    return y

But this works in linear time, we can also construct an algorithm in logarithmic time:

def power(x, p):
    if p == 0:
        return 1
    elif p & 1:
        return x * power(x*x, p//2)
    else:
        return power(x*x, p//2)

Or if we want to reduce the overhead of the recursive calls, an imperative version:

def power(x, p):
    r = 1
    while p:
        if p & 1:
            r *= x
        x *= x
        p >>= 1
    return r

For example:

>>> power(5, 6)
15625
>>> power(5, 1)
5
>>> power(5, 0)
1
>>> power(3, 2)
9
>>> power(3, 7)
2187

Upvotes: 6

A.J. Uppal
A.J. Uppal

Reputation: 19264

Your attempt does not work because as you modify temp_obj, you cease to multiply it by its original value. You could also try the following:

initial_value = temp_obj
for x in range(p1):
  temp_obj = temp_obj * initial_value

Upvotes: 0

internet_user
internet_user

Reputation: 3279

Assuming multiplication is associative, you can use exponentiation by squaring (O(log n)):

def pow(obj, num):
  res = 1  # assuming 1 is the identity
  while num:
    num, mul = divmod(num, 2)
    if mul:
      res *= obj
    obj *= obj
  return res

Upvotes: 2

Related Questions