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