Branchless Paradigm#
Auxiliary Functions#
def equal_to(x: int, y: int) -> bool:
return x == y
assert equal_to(1, 1)
assert not equal_to(1, 2)
Predecessor and Successor#
def predecessor(x: int) -> int:
equal = equal_to(x, 1)
return (equal and 0) or ((not equal) and (1 + predecessor(x - 1)))
assert predecessor(1) == 0
assert predecessor(10) == 9
def successor(x: int) -> int:
equal = equal_to(x, 0)
return (equal and 1) or ((not equal) and (1 + successor(predecessor(x))))
assert successor(0) == 1
assert successor(10) == 11
Addition#
def addition(x: int, y: int) -> int:
equal = equal_to(y, 0)
return (equal and x) or ((not equal) and (addition(successor(x), predecessor(y))))
assert addition(0, 0) == 0
assert addition(1, 0) == 1
assert addition(0, 1) == 1
assert addition(10, 10) == 20, addition(10, 10)
Multiplication#
def multiplication(x: int, y: int) -> int:
equal_0 = equal_to(y, 0)
return (equal_0 and 0) or (
not equal_0 and (addition(x, multiplication(x, predecessor(y))))
)
assert multiplication(0, 0) == 0
assert multiplication(2, 0) == 0
assert multiplication(0, 2) == 0
assert multiplication(10, 10) == 100
Exponentiation#
def exponentiation(x: int, y: int) -> int:
x_equal_0 = equal_to(x, 0)
y_equal_0 = equal_to(y, 0)
return (
(x_equal_0 and 0)
or (not x_equal_0 and y_equal_0 and 1)
or (
not x_equal_0
and not y_equal_0
and multiplication(x, exponentiation(x, predecessor(y)))
)
)
assert exponentiation(1, 0) == 1
assert exponentiation(0, 1) == 0
assert exponentiation(3, 3) == 27