Skip to content

Instantly share code, notes, and snippets.

@impredicative
Created December 26, 2016 02:30
Show Gist options
  • Save impredicative/df702264a8158af38ab5d1d785219d84 to your computer and use it in GitHub Desktop.
Save impredicative/df702264a8158af38ab5d1d785219d84 to your computer and use it in GitHub Desktop.
Integer exponentiation
import math
# Python ≥ 3.5
def recursive_linear(b, n):
if n < 0:
return (1/b) * recursive_linear(b, n+1)
if n == 0:
return 1
else:
return b * recursive_linear(b, n-1)
def recursive_log(b, n):
if n == 0:
return 1
else:
p = recursive_log(b, int(n/2))
b = 1/b if n<0 else b
return p*p * (b if n % 2 else 1)
def iterative_linear(b, n):
p = 1
b = 1/b if n < 0 else b
for _ in range(abs(n)):
p *= b
return p
def iterative_log_left2right(b, n):
p = 1
b = 1/b if n<0 else b
n = abs(n) # If n<0
for i in range(n.bit_length() - 1, -1, -1):
bit = (n >> i) & 1
p *= p * (b if bit else 1)
return p
def iterative_log_right2left(b, n):
p = 1
b = 1/b if n<0 else b
n = abs(n) # If n<0
for i in range(n.bit_length()):
bit = (n >> i) & 1
p *= b if bit else 1
b *= b
return p
def iterative_log_right2left_whileloop(b, n):
p = 1
b = 1/b if n<0 else b
n = abs(n) # If n<0
while n:
bit = n % 2
p *= b if bit else 1
b *= b
n //= 2
return p
# Test
def test():
functions = (recursive_linear,
recursive_log,
iterative_linear,
iterative_log_left2right,
iterative_log_right2left,
iterative_log_right2left_whileloop,
)
for f in functions:
for b in range(-100, 100):
for n in range(-100, 100):
try:
expected = b**n
except ZeroDivisionError:
continue
actual = f(b, n)
isclose = math.isclose(expected, actual)
try:
assert(isclose)
except AssertionError:
print(f.__name__, b, n, expected, actual)
return
test()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment