Skip to content

Instantly share code, notes, and snippets.

@victor-iyi
Created August 29, 2020 13:32
Show Gist options
  • Select an option

  • Save victor-iyi/d8148fc570c9ab764fcbabde6c1351bd to your computer and use it in GitHub Desktop.

Select an option

Save victor-iyi/d8148fc570c9ab764fcbabde6c1351bd to your computer and use it in GitHub Desktop.
Implement the Python's `pow(...)` function as efficient as possible
import time
def power(base, exp):
"""Implement the `pow(...)` function recursively."""
# Base case.
if exp == 0:
return 1
elif exp == 1:
return base
# Compute: a^b = a^(c+d) = (a^c) * (a^d)
if exp % 2 == 0: # when even, c==d
half = exp / 2
return power(base, half) * power(base, half)
else:
c = int(exp / 2)
d = c + 1
return power(base, c) * power(base, d)
def pow_eff(base, exp):
"""Compute the `pow(...)` function more efficiently."""
number = 1
while exp:
if exp & 1:
number *= base
exp >>= 1
base *= base
return number
def test(base, exp):
"""Test to compare Python's `pow(...)` with the above implementations."""
# Test the recursive `power(...)` function.
start = time.time()
re_result = power(base, exp)
re_time = time.time() - start
# Test the efficient `pow_eff(...)` function.
start = time.time()
ef_result = pow_eff(base, exp)
ef_time = time.time() - start
# Test the Python's `pow(...)` function.
start = time.time()
py_result = pow(base, exp)
py_time = time.time() - start
# Print the 3 results & benchmarks.
print(f'Rec: pow({base}, {exp}) = {re_result:,}\tTime: {re_time:.6f}')
print(f'Eff: pow({base}, {exp}) = {re_result:,}\tTime: {ef_time:.6f}')
print(f'Py : pow({base}, {exp}) = {re_result:,}\tTime: {py_time:.6f}')
print('==============================================\n')
if __name__ == '__main__':
# Test 1
test(base=-2, exp=3)
# Test 2
test(base=-3, exp=2)
# Test 3
test(base=3, exp=12)
# Test 4
test(base=2, exp=16)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment