Companion source · Python 3.11+

Every pair, every bucket, every wrap

This complete program contains the two compact implementations used in Chapter 2 plus executable checks for the worked examples. Run it with python src/simdoc/textbook/examples/math_foundations.py, or open the adjacent marimo lab for a reactive construction.

"""Runnable reference implementations for Chapter 2."""


def convolve(left: list[int], right: list[int]) -> list[int]:
    """Multiply every pair and accumulate it into bucket i + k."""
    output = [0] * (len(left) + len(right) - 1)

    for i, left_value in enumerate(left):
        for k, right_value in enumerate(right):
            destination = i + k
            product = left_value * right_value
            output[destination] += product

    return output


def negacyclic_multiply(left: list[int], right: list[int]) -> list[int]:
    """Multiply two equal-length lists using the boundary x**N = -1."""
    if len(left) != len(right):
        raise ValueError("inputs must have the same length")

    size = len(left)
    output = [0] * size

    for i, left_value in enumerate(left):
        for k, right_value in enumerate(right):
            destination = i + k
            product = left_value * right_value

            if destination < size:
                output[destination] += product
            else:
                output[destination - size] -= product

    return output


def _self_test() -> None:
    assert convolve([1, 2, 1], [3, -1]) == [3, 5, 1, -1]
    assert convolve([2, -1, 3], [4, 5, -2]) == [8, 6, 3, 17, -6]
    assert negacyclic_multiply([1, 2, 0, 0], [3, 0, 0, 4]) == [-5, 6, 0, 4]
    print("All mathematical foundation examples passed.")


if __name__ == "__main__":
    _self_test()