Reputation: 163
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
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
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
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