omnibias.boolean
Boolean truth tables, multilinear extensions, algebraic spectra, and finite-temperature gate systems.
import omnibias.booleanUse the exact core utilities for finite truth tables and their algebraic representations, and the tensor backends for differentiable relaxations of Boolean operations. Bit coordinates and spin coordinates use different conventions; convert explicitly rather than mixing zero/one values with minus-one/plus-one values.
Truth-table order, variable order, algebraic-normal-form coefficients, and Walsh coefficients must remain consistent across transforms. Enumerating a truth table or brute-force solution space grows exponentially in the number of variables. A differentiable relaxation does not remove that complexity or guarantee a satisfying discrete assignment.
When using soft gates, record inverse temperature and validate the decoded hard result independently. Threshold behavior at the boundary is a convention that matters for tests. Use the solver's status and residual information rather than interpreting any returned relaxed vector as a proof of satisfiability.
Module contract & mathematical conventions
omnibias-boolean: differentiable Boolean algebra.
The pure-Python omnibias.boolean._core provides exact truth-table, ANF /
Reed-Muller, Walsh / Fourier, Boolean-differential-calculus, equation-solving and
multilinear-extension primitives. The differentiable backends live under
omnibias.boolean.torch and omnibias.boolean.jax (soft gates, the
jet-based spectrum engine, the beta-annealed soft-gate system solver, and design
losses); import them explicitly so the core stays dependency-free.
The exact core is ground truth; the backends are differentiable *relaxations* (heuristics, no completeness guarantee). See the package README for the discrete <-> continuous derivative bridge and the honesty guardrails.
important:
**Bit-parity with the PyTorch twin requires 64-bit JAX** -- jax.config.update("jax_enable_x64", True) before the first JAX array is created (or JAX_ENABLE_X64=1). JAX otherwise truncates to float32 while PyTorch uses float64, so the twins stay internally consistent but agree only to float32 tolerance. Where a value feeds a threshold, a rounding step or an argmax, that is enough to change the decision rather than just the last digits. See omnibias.jax.precision.
Shared formulas do not imply universal floating-point identity. Verify dtype, shape, derivative-order support, and the stated numerical assumptions for the path you use.
Imports & aliases
These names share a definition with another public module. Follow a name for its full contract, parameters, and examples.
| Import from this module | Canonical reference |
|---|---|
BooleanInequalityBackend | omnibias.boolean.BooleanInequalityBackend |
algebraic_degree
omnibias.boolean.algebraic_degreeSource ↗algebraic_degree(anf: ANF) -> intAlgebraic degree = largest monomial size with a non-zero ANF coefficient.
The all-zero function (f == 0) has degree -1 by convention; a non-zero
constant has degree 0.
Parameters
| Name | Type & default | Contract |
|---|---|---|
anfpositional-or-keyword | ANFRequired | See the operation contract and implementation below. |
intExecuted regression · inconsistent linear system
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_inconsistent_linear_system() -> None:
sys = BooleanSystem.from_predicates(
[lambda a: a == 0, lambda a: a == 1], n=1
)
res = solve(sys)
assert res.method == "gf2"
assert not res.verified
assert res.assignment is Nonepython -m pytest "packages/omnibias-boolean/tests/test_solver.py::test_inconsistent_linear_system" -qRegression example · algebraic degree
This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_algebraic_degree() -> None:
assert algebraic_degree(anf_from_truth_table(AND)) == 2
assert algebraic_degree(anf_from_truth_table(XOR)) == 1
assert algebraic_degree((1, 0, 0, 0)) == 0 # constant 1
assert algebraic_degree((0, 0, 0, 0)) == -1 # zero functionpython -m pytest packages/omnibias-boolean/tests/test_anf.py -k test_algebraic_degree -qRead the implementation
def algebraic_degree(anf: ANF) -> int:
"""Algebraic degree = largest monomial size with a non-zero ANF coefficient.
The all-zero function (``f == 0``) has degree ``-1`` by convention; a non-zero
constant has degree ``0``.
"""
deg = -1
for mask, coeff in enumerate(anf):
if coeff:
deg = max(deg, bin(mask).count("1"))
return deganf_from_truth_table
omnibias.boolean.anf_from_truth_tableSource ↗anf_from_truth_table(table: TruthTable) -> ANFANF/Reed-Muller coefficients of table via the GF(2) Mobius transform.
Parameters
| Name | Type & default | Contract |
|---|---|---|
tablepositional-or-keyword | TruthTableRequired | See the operation contract and implementation below. |
ANFExecuted regression · anf or
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_anf_or() -> None:
assert anf_from_truth_table(OR) == (0, 1, 1, 1)
assert anf_to_string(anf_from_truth_table(OR)) == "x0 + x1 + x0*x1"python -m pytest "packages/omnibias-boolean/tests/test_anf.py::test_anf_or" -qRegression example · anf xor is sum
This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_anf_xor_is_sum() -> None:
assert anf_from_truth_table(XOR) == (0, 1, 1, 0)
assert anf_to_string(anf_from_truth_table(XOR)) == "x0 + x1"python -m pytest packages/omnibias-boolean/tests/test_anf.py -k test_anf_xor_is_sum -qRead the implementation
def anf_from_truth_table(table: TruthTable) -> ANF:
"""ANF/Reed-Muller coefficients of ``table`` via the GF(2) Mobius transform."""
check_truth_table(table)
a = list(table)
size = len(a)
step = 1
while step < size:
for i in range(0, size, step << 1):
for j in range(i, i + step):
a[j + step] ^= a[j]
step <<= 1
return tuple(a)anf_monomials
omnibias.boolean.anf_monomialsSource ↗anf_monomials(anf: ANF) -> list[frozenset[int]]Variable-index sets of the monomials present in the ANF (a_S == 1).
Parameters
| Name | Type & default | Contract |
|---|---|---|
anfpositional-or-keyword | ANFRequired | See the operation contract and implementation below. |
list[frozenset[int]]Executed regression · monomials
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_monomials() -> None:
mons = anf_monomials(anf_from_truth_table(OR))
assert frozenset({0}) in mons
assert frozenset({1}) in mons
assert frozenset({0, 1}) in monspython -m pytest "packages/omnibias-boolean/tests/test_anf.py::test_monomials" -qRead the implementation
def anf_monomials(anf: ANF) -> list[frozenset[int]]:
"""Variable-index sets of the monomials present in the ANF (``a_S == 1``)."""
n = num_vars(anf)
return [
frozenset(j for j in range(n) if (mask >> j) & 1)
for mask, coeff in enumerate(anf)
if coeff
]anf_to_string
omnibias.boolean.anf_to_stringSource ↗anf_to_string(anf: ANF) -> strHuman-readable ANF, e.g. "x0*x1 + x2 + 1" ("0" for the zero function).
Parameters
| Name | Type & default | Contract |
|---|---|---|
anfpositional-or-keyword | ANFRequired | See the operation contract and implementation below. |
strExecuted regression · anf or
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_anf_or() -> None:
assert anf_from_truth_table(OR) == (0, 1, 1, 1)
assert anf_to_string(anf_from_truth_table(OR)) == "x0 + x1 + x0*x1"python -m pytest "packages/omnibias-boolean/tests/test_anf.py::test_anf_or" -qRegression example · anf xor is sum
This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_anf_xor_is_sum() -> None:
assert anf_from_truth_table(XOR) == (0, 1, 1, 0)
assert anf_to_string(anf_from_truth_table(XOR)) == "x0 + x1"python -m pytest packages/omnibias-boolean/tests/test_anf.py -k test_anf_xor_is_sum -qRead the implementation
def anf_to_string(anf: ANF) -> str:
"""Human-readable ANF, e.g. ``"x0*x1 + x2 + 1"`` (``"0"`` for the zero function)."""
n = num_vars(anf)
terms: list[str] = []
for mask, coeff in enumerate(anf):
if not coeff:
continue
if mask == 0:
terms.append("1")
else:
terms.append("*".join(f"x{j}" for j in range(n) if (mask >> j) & 1))
return " + ".join(terms) if terms else "0"truth_table_from_anf
omnibias.boolean.truth_table_from_anfSource ↗truth_table_from_anf(anf: ANF) -> TruthTableInverse transform: rebuild the truth table from ANF coefficients.
The binary Mobius transform is an involution, so this is the same butterfly.
Parameters
| Name | Type & default | Contract |
|---|---|---|
anfpositional-or-keyword | ANFRequired | See the operation contract and implementation below. |
TruthTableExecuted regression · anf is involution
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_anf_is_involution() -> None:
rng = random.Random(0)
for n in (1, 2, 3, 4):
for _ in range(20):
tt = tuple(rng.randint(0, 1) for _ in range(1 << n))
anf = anf_from_truth_table(tt)
assert truth_table_from_anf(anf) == tt
# Transform is its own inverse.
assert anf_from_truth_table(anf) == ttpython -m pytest "packages/omnibias-boolean/tests/test_anf.py::test_anf_is_involution" -qRead the implementation
def truth_table_from_anf(anf: ANF) -> TruthTable:
"""Inverse transform: rebuild the truth table from ANF coefficients.
The binary Mobius transform is an involution, so this is the same butterfly.
"""
check_truth_table(anf)
return anf_from_truth_table(anf)BooleanAntiderivative
omnibias.boolean.BooleanAntiderivativeSource ↗class BooleanAntiderivativeDataclass constructor fields; inherited fields, if any, are declared by the base class. A field(...) expression describes a default factory or field options, not a literal argument default.
General antiderivative of g w.r.t. x_i with a free constant c.
general(c) builds f(x) = c(x_{!=i}) ^ (x_i & g(x)) for an
(n-1)-variable constant c; particular is the c = 0 choice.
Parameters
| Name | Type & default | Contract |
|---|---|---|
vardataclass field | intRequired | See the operation contract and implementation below. |
ndataclass field | intRequired | See the operation contract and implementation below. |
derivativedataclass field | TruthTableRequired | See the operation contract and implementation below. |
particulardataclass field | TruthTableRequired | See the operation contract and implementation below. |
Executed regression · integral recovers derivative for every constant
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_integral_recovers_derivative_for_every_constant() -> None:
rng = random.Random(4)
for n in (1, 2, 3):
for _ in range(20):
tt = tuple(rng.randint(0, 1) for _ in range(1 << n))
i = rng.randrange(n)
g = boolean_derivative(tt, i)
anti = boolean_integral(g, i)
# Every choice of the free constant yields an antiderivative of g.
length = 1 << (n - 1)
for c_int in range(1 << length):
c = tuple((c_int >> k) & 1 for k in range(length))
f = anti.general(c)
assert boolean_derivative(f, i) == g
# The original function is the antiderivative for c = f|_{x_i=0}.
assert anti.general(restrict(tt, i, 0)) == ttpython -m pytest "packages/omnibias-boolean/tests/test_derivative.py::test_integral_recovers_derivative_for_every_constant" -qFields & methods
varfield
var: intDeclared int field on BooleanAntiderivative. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.
View source ↗nfield
n: intDeclared int field on BooleanAntiderivative. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.
View source ↗derivativefield
derivative: TruthTableDeclared TruthTable field on BooleanAntiderivative. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.
View source ↗particularfield
particular: TruthTableDeclared TruthTable field on BooleanAntiderivative. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.
View source ↗generalmethod
general(self, constant: TruthTable) -> TruthTableAntiderivative for a given (n-1)-variable constant of integration.
Parameters
| Name | Type & default | Contract |
|---|---|---|
constantpositional-or-keyword | TruthTableRequired | See the operation contract and implementation below. |
Returns: TruthTable
Validation & failure cases
- When
len(constant) != expected, raisesValueError(f'constant must have length {expected} (n-1={self.n - 1} vars), got {len(constant)}').
Executed regression · integral recovers derivative for every constant
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_integral_recovers_derivative_for_every_constant() -> None:
rng = random.Random(4)
for n in (1, 2, 3):
for _ in range(20):
tt = tuple(rng.randint(0, 1) for _ in range(1 << n))
i = rng.randrange(n)
g = boolean_derivative(tt, i)
anti = boolean_integral(g, i)
# Every choice of the free constant yields an antiderivative of g.
length = 1 << (n - 1)
for c_int in range(1 << length):
c = tuple((c_int >> k) & 1 for k in range(length))
f = anti.general(c)
assert boolean_derivative(f, i) == g
# The original function is the antiderivative for c = f|_{x_i=0}.
assert anti.general(restrict(tt, i, 0)) == ttpython -m pytest "packages/omnibias-boolean/tests/test_derivative.py::test_integral_recovers_derivative_for_every_constant" -qMethod implementation
def general(self, constant: TruthTable) -> TruthTable:
"""Antiderivative for a given ``(n-1)``-variable constant of integration."""
expected = 1 << (self.n - 1)
if len(constant) != expected:
raise ValueError(
f"constant must have length {expected} (n-1={self.n - 1} vars), "
f"got {len(constant)}"
)
size = 1 << self.n
out = [0] * size
for x in range(size):
xi = (x >> self.var) & 1
c = constant[reduced_index(x, self.var, self.n)]
out[x] = c ^ (xi & self.derivative[x])
return tuple(out)Read the implementation
class BooleanAntiderivative:
"""General antiderivative of ``g`` w.r.t. ``x_i`` with a free constant ``c``.
``general(c)`` builds ``f(x) = c(x_{!=i}) ^ (x_i & g(x))`` for an
``(n-1)``-variable constant ``c``; :attr:`particular` is the ``c = 0`` choice.
"""
var: int
n: int
derivative: TruthTable
particular: TruthTable
def general(self, constant: TruthTable) -> TruthTable:
"""Antiderivative for a given ``(n-1)``-variable constant of integration."""
expected = 1 << (self.n - 1)
if len(constant) != expected:
raise ValueError(
f"constant must have length {expected} (n-1={self.n - 1} vars), "
f"got {len(constant)}"
)
size = 1 << self.n
out = [0] * size
for x in range(size):
xi = (x >> self.var) & 1
c = constant[reduced_index(x, self.var, self.n)]
out[x] = c ^ (xi & self.derivative[x])
return tuple(out)boolean_derivative
omnibias.boolean.boolean_derivativeSource ↗boolean_derivative(table: TruthTable, i: int) -> TruthTabledf/dx_i as a full n-variable truth table (constant in x_i).
Parameters
| Name | Type & default | Contract |
|---|---|---|
tablepositional-or-keyword | TruthTableRequired | See the operation contract and implementation below. |
ipositional-or-keyword | intRequired | See the operation contract and implementation below. |
TruthTableExplicit validation & failure cases
- When
not 0 <= i < n, raisesValueError(f'variable index {i} out of range for n={n}').
These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.
Executed regression · derivative is constant in its variable
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_derivative_is_constant_in_its_variable() -> None:
d = boolean_derivative(AND, 0)
assert is_independent_of(d, 0)python -m pytest "packages/omnibias-boolean/tests/test_derivative.py::test_derivative_is_constant_in_its_variable" -qRegression example · set derivative order independent
This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_set_derivative_order_independent() -> None:
rng = random.Random(3)
for _ in range(20):
tt = tuple(rng.randint(0, 1) for _ in range(1 << 3))
d01 = boolean_derivative(boolean_derivative(tt, 0), 1)
assert boolean_derivative_set(tt, [0, 1]) == d01
assert boolean_derivative_set(tt, [1, 0]) == d01python -m pytest packages/omnibias-boolean/tests/test_derivative.py -k test_set_derivative_order_independent -qRead the implementation
def boolean_derivative(table: TruthTable, i: int) -> TruthTable:
"""``df/dx_i`` as a full ``n``-variable truth table (constant in ``x_i``)."""
check_truth_table(table)
n = num_vars(table)
if not 0 <= i < n:
raise ValueError(f"variable index {i} out of range for n={n}")
bit = 1 << i
size = 1 << n
out = [0] * size
for x in range(size):
out[x] = table[x & ~bit] ^ table[x | bit]
return tuple(out)boolean_derivative_reduced
omnibias.boolean.boolean_derivative_reducedSource ↗boolean_derivative_reduced(table: TruthTable, i: int) -> TruthTabledf/dx_i as an (n-1)-variable truth table over the remaining vars.
Parameters
| Name | Type & default | Contract |
|---|---|---|
tablepositional-or-keyword | TruthTableRequired | See the operation contract and implementation below. |
ipositional-or-keyword | intRequired | See the operation contract and implementation below. |
TruthTableExecuted regression · derivative of and is other input
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_derivative_of_and_is_other_input() -> None:
# d(x0 & x1)/dx0 = x1.
assert boolean_derivative_reduced(AND, 0) == (0, 1)
assert boolean_derivative_reduced(AND, 1) == (0, 1)python -m pytest "packages/omnibias-boolean/tests/test_derivative.py::test_derivative_of_and_is_other_input" -qRegression example · derivative of xor is constant one
This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_derivative_of_xor_is_constant_one() -> None:
# d(x0 ^ x1)/dx0 = 1 (flipping x0 always flips the output).
assert boolean_derivative_reduced(XOR, 0) == (1, 1)
assert not is_independent_of(XOR, 0)python -m pytest packages/omnibias-boolean/tests/test_derivative.py -k test_derivative_of_xor_is_constant_one -qRead the implementation
def boolean_derivative_reduced(table: TruthTable, i: int) -> TruthTable:
"""``df/dx_i`` as an ``(n-1)``-variable truth table over the remaining vars."""
return restrict(boolean_derivative(table, i), i, 0)boolean_derivative_set
omnibias.boolean.boolean_derivative_setSource ↗boolean_derivative_set(table: TruthTable, indices: Iterable[int]) -> TruthTableIterated mixed Boolean derivative over a set of variables (order-independent).
Parameters
| Name | Type & default | Contract |
|---|---|---|
tablepositional-or-keyword | TruthTableRequired | See the operation contract and implementation below. |
indicespositional-or-keyword | Iterable[int]Required | See the operation contract and implementation below. |
TruthTableExecuted regression · set derivative order independent
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_set_derivative_order_independent() -> None:
rng = random.Random(3)
for _ in range(20):
tt = tuple(rng.randint(0, 1) for _ in range(1 << 3))
d01 = boolean_derivative(boolean_derivative(tt, 0), 1)
assert boolean_derivative_set(tt, [0, 1]) == d01
assert boolean_derivative_set(tt, [1, 0]) == d01python -m pytest "packages/omnibias-boolean/tests/test_derivative.py::test_set_derivative_order_independent" -qRead the implementation
def boolean_derivative_set(table: TruthTable, indices: Iterable[int]) -> TruthTable:
"""Iterated mixed Boolean derivative over a set of variables (order-independent)."""
result = table
for i in sorted(set(indices)):
result = boolean_derivative(result, i)
return resultboolean_integral
omnibias.boolean.boolean_integralSource ↗boolean_integral(g: TruthTable, i: int) -> BooleanAntiderivativeAntiderivative of g w.r.t. x_i (requires g independent of x_i).
Raises ValueError if g depends on x_i (no antiderivative exists --
the discrete analogue of a non-exact differential).
Parameters
| Name | Type & default | Contract |
|---|---|---|
gpositional-or-keyword | TruthTableRequired | See the operation contract and implementation below. |
ipositional-or-keyword | intRequired | See the operation contract and implementation below. |
BooleanAntiderivativeExplicit validation & failure cases
- When
not 0 <= i < n, raisesValueError(f'variable index {i} out of range for n={n}'). - When
not is_independent_of(g, i), raisesValueError(f'g depends on x_{i}; no antiderivative exists (integrability/exactness condition violated)').
These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.
Executed regression · integral requires exactness
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_integral_requires_exactness() -> None:
# A function that depends on x0 has no antiderivative w.r.t. x0.
with pytest.raises(ValueError):
boolean_integral(AND, 0)python -m pytest "packages/omnibias-boolean/tests/test_derivative.py::test_integral_requires_exactness" -qRegression example · integral recovers derivative for every constant
This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_integral_recovers_derivative_for_every_constant() -> None:
rng = random.Random(4)
for n in (1, 2, 3):
for _ in range(20):
tt = tuple(rng.randint(0, 1) for _ in range(1 << n))
i = rng.randrange(n)
g = boolean_derivative(tt, i)
anti = boolean_integral(g, i)
# Every choice of the free constant yields an antiderivative of g.
length = 1 << (n - 1)
for c_int in range(1 << length):
c = tuple((c_int >> k) & 1 for k in range(length))
f = anti.general(c)
assert boolean_derivative(f, i) == g
# The original function is the antiderivative for c = f|_{x_i=0}.
assert anti.general(restrict(tt, i, 0)) == ttpython -m pytest packages/omnibias-boolean/tests/test_derivative.py -k test_integral_recovers_derivative_for_every_constant -qRead the implementation
def boolean_integral(g: TruthTable, i: int) -> BooleanAntiderivative:
"""Antiderivative of ``g`` w.r.t. ``x_i`` (requires ``g`` independent of ``x_i``).
Raises ``ValueError`` if ``g`` depends on ``x_i`` (no antiderivative exists --
the discrete analogue of a non-exact differential).
"""
check_truth_table(g)
n = num_vars(g)
if not 0 <= i < n:
raise ValueError(f"variable index {i} out of range for n={n}")
if not is_independent_of(g, i):
raise ValueError(
f"g depends on x_{i}; no antiderivative exists "
"(integrability/exactness condition violated)"
)
zero_constant = tuple([0] * (1 << (n - 1)))
anti = BooleanAntiderivative(var=i, n=n, derivative=g, particular=())
particular = anti.general(zero_constant)
return BooleanAntiderivative(var=i, n=n, derivative=g, particular=particular)is_independent_of
omnibias.boolean.is_independent_ofSource ↗is_independent_of(table: TruthTable, i: int) -> boolTrue iff f does not depend on x_i (its Boolean derivative is 0).
Parameters
| Name | Type & default | Contract |
|---|---|---|
tablepositional-or-keyword | TruthTableRequired | See the operation contract and implementation below. |
ipositional-or-keyword | intRequired | See the operation contract and implementation below. |
boolExecuted regression · derivative is constant in its variable
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_derivative_is_constant_in_its_variable() -> None:
d = boolean_derivative(AND, 0)
assert is_independent_of(d, 0)python -m pytest "packages/omnibias-boolean/tests/test_derivative.py::test_derivative_is_constant_in_its_variable" -qRegression example · derivative of xor is constant one
This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_derivative_of_xor_is_constant_one() -> None:
# d(x0 ^ x1)/dx0 = 1 (flipping x0 always flips the output).
assert boolean_derivative_reduced(XOR, 0) == (1, 1)
assert not is_independent_of(XOR, 0)python -m pytest packages/omnibias-boolean/tests/test_derivative.py -k test_derivative_of_xor_is_constant_one -qRead the implementation
def is_independent_of(table: TruthTable, i: int) -> bool:
"""``True`` iff ``f`` does not depend on ``x_i`` (its Boolean derivative is 0)."""
return all(v == 0 for v in boolean_derivative(table, i))reduced_index
omnibias.boolean.reduced_indexSource ↗reduced_index(x: int, i: int, n: int) -> intIndex of assignment x with bit i deleted (over the n-1 rest).
Parameters
| Name | Type & default | Contract |
|---|---|---|
xpositional-or-keyword | intRequired | See the operation contract and implementation below. |
ipositional-or-keyword | intRequired | See the operation contract and implementation below. |
npositional-or-keyword | intRequired | See the operation contract and implementation below. |
intExecuted regression · derivative of and is other input
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_derivative_of_and_is_other_input() -> None:
# d(x0 & x1)/dx0 = x1.
assert boolean_derivative_reduced(AND, 0) == (0, 1)
assert boolean_derivative_reduced(AND, 1) == (0, 1)python -m pytest "packages/omnibias-boolean/tests/test_derivative.py::test_derivative_of_and_is_other_input" -qRead the implementation
def reduced_index(x: int, i: int, n: int) -> int:
"""Index of assignment ``x`` with bit ``i`` deleted (over the ``n-1`` rest)."""
low = x & ((1 << i) - 1)
high = (x >> (i + 1)) << i
return low | highrestrict
omnibias.boolean.restrictSource ↗restrict(table: TruthTable, i: int, value: int) -> TruthTableCofactor f|_{x_i = value} as a function of the remaining n-1 variables.
Parameters
| Name | Type & default | Contract |
|---|---|---|
tablepositional-or-keyword | TruthTableRequired | See the operation contract and implementation below. |
ipositional-or-keyword | intRequired | See the operation contract and implementation below. |
valuepositional-or-keyword | intRequired | See the operation contract and implementation below. |
TruthTableExplicit validation & failure cases
- When
not 0 <= i < n, raisesValueError(f'variable index {i} out of range for n={n}'). - When
value not in (0, 1), raisesValueError(f'value must be 0 or 1, got {value}').
These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.
Executed regression · derivative of and is other input
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_derivative_of_and_is_other_input() -> None:
# d(x0 & x1)/dx0 = x1.
assert boolean_derivative_reduced(AND, 0) == (0, 1)
assert boolean_derivative_reduced(AND, 1) == (0, 1)python -m pytest "packages/omnibias-boolean/tests/test_derivative.py::test_derivative_of_and_is_other_input" -qRegression example · integral recovers derivative for every constant
This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_integral_recovers_derivative_for_every_constant() -> None:
rng = random.Random(4)
for n in (1, 2, 3):
for _ in range(20):
tt = tuple(rng.randint(0, 1) for _ in range(1 << n))
i = rng.randrange(n)
g = boolean_derivative(tt, i)
anti = boolean_integral(g, i)
# Every choice of the free constant yields an antiderivative of g.
length = 1 << (n - 1)
for c_int in range(1 << length):
c = tuple((c_int >> k) & 1 for k in range(length))
f = anti.general(c)
assert boolean_derivative(f, i) == g
# The original function is the antiderivative for c = f|_{x_i=0}.
assert anti.general(restrict(tt, i, 0)) == ttpython -m pytest packages/omnibias-boolean/tests/test_derivative.py -k test_integral_recovers_derivative_for_every_constant -qRead the implementation
def restrict(table: TruthTable, i: int, value: int) -> TruthTable:
"""Cofactor ``f|_{x_i = value}`` as a function of the remaining ``n-1`` variables."""
check_truth_table(table)
n = num_vars(table)
if not 0 <= i < n:
raise ValueError(f"variable index {i} out of range for n={n}")
if value not in (0, 1):
raise ValueError(f"value must be 0 or 1, got {value}")
size = 1 << n
out = [0] * (size >> 1)
for x in range(size):
if ((x >> i) & 1) == value:
out[reduced_index(x, i, n)] = table[x]
return tuple(out)BooleanSolution
omnibias.boolean.BooleanSolutionSource ↗class BooleanSolutionDataclass constructor fields; inherited fields, if any, are declared by the base class. A field(...) expression describes a default factory or field options, not a literal argument default.
Reproductive general solution of constraint = 0 for one variable.
solution is a truth table over (rest..., c) -- the n-1 remaining
variables (in original order) followed by the free parameter c in the
most-significant slot -- whose value is the chosen x_var.
consistency is 1 where a solution exists.
Parameters
| Name | Type & default | Contract |
|---|---|---|
vardataclass field | intRequired | See the operation contract and implementation below. |
ndataclass field | intRequired | See the operation contract and implementation below. |
rest_varsdataclass field | tuple[int, ...]Required | See the operation contract and implementation below. |
consistencydataclass field | TruthTableRequired | See the operation contract and implementation below. |
solutiondataclass field | TruthTableRequired | See the operation contract and implementation below. |
Executed regression · solve for is a valid reproductive solution
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_solve_for_is_a_valid_reproductive_solution() -> None:
sol = solve_for(AND_EQ, 1)
# Plugging the solution back satisfies the original equation everywhere consistent.
assert sol.satisfies(AND_EQ)python -m pytest "packages/omnibias-boolean/tests/test_equations.py::test_solve_for_is_a_valid_reproductive_solution" -qFields & methods
varfield
var: intDeclared int field on BooleanSolution. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.
View source ↗nfield
n: intDeclared int field on BooleanSolution. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.
View source ↗rest_varsfield
rest_vars: tuple[int, ...]Declared tuple[int, ...] field on BooleanSolution. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.
View source ↗consistencyfield
consistency: TruthTableDeclared TruthTable field on BooleanSolution. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.
View source ↗solutionfield
solution: TruthTableDeclared TruthTable field on BooleanSolution. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.
View source ↗valuemethod
value(self, rest_bits: int, c: int) -> intChosen x_var for a given setting of the rest and the parameter c.
Parameters
| Name | Type & default | Contract |
|---|---|---|
rest_bitspositional-or-keyword | intRequired | See the operation contract and implementation below. |
cpositional-or-keyword | intRequired | See the operation contract and implementation below. |
Returns: int
Executed regression · solve for is a valid reproductive solution
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_solve_for_is_a_valid_reproductive_solution() -> None:
sol = solve_for(AND_EQ, 1)
# Plugging the solution back satisfies the original equation everywhere consistent.
assert sol.satisfies(AND_EQ)python -m pytest "packages/omnibias-boolean/tests/test_equations.py::test_solve_for_is_a_valid_reproductive_solution" -qMethod implementation
def value(self, rest_bits: int, c: int) -> int:
"""Chosen ``x_var`` for a given setting of the rest and the parameter ``c``."""
return self.solution[rest_bits | ((c & 1) << (self.n - 1))]satisfiesmethod
satisfies(self, constraint: TruthTable) -> boolCheck the defining property: every consistent (rest, c) solves phi=0.
Parameters
| Name | Type & default | Contract |
|---|---|---|
constraintpositional-or-keyword | TruthTableRequired | See the operation contract and implementation below. |
Returns: bool
Executed regression · solve for is a valid reproductive solution
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_solve_for_is_a_valid_reproductive_solution() -> None:
sol = solve_for(AND_EQ, 1)
# Plugging the solution back satisfies the original equation everywhere consistent.
assert sol.satisfies(AND_EQ)python -m pytest "packages/omnibias-boolean/tests/test_equations.py::test_solve_for_is_a_valid_reproductive_solution" -qMethod implementation
def satisfies(self, constraint: TruthTable) -> bool:
"""Check the defining property: every consistent ``(rest, c)`` solves ``phi=0``."""
for r in range(1 << (self.n - 1)):
if not self.consistency[r]:
continue
for c in (0, 1):
xi = self.value(r, c)
x = _full_index(self.rest_vars, self.var, r, xi, self.n)
if constraint[x] != 0:
return False
return TrueRead the implementation
class BooleanSolution:
"""Reproductive general solution of ``constraint = 0`` for one variable.
:attr:`solution` is a truth table over ``(rest..., c)`` -- the ``n-1`` remaining
variables (in original order) followed by the free parameter ``c`` in the
most-significant slot -- whose value is the chosen ``x_var``.
:attr:`consistency` is ``1`` where a solution exists.
"""
var: int
n: int
rest_vars: tuple[int, ...]
consistency: TruthTable
solution: TruthTable
def value(self, rest_bits: int, c: int) -> int:
"""Chosen ``x_var`` for a given setting of the rest and the parameter ``c``."""
return self.solution[rest_bits | ((c & 1) << (self.n - 1))]
def satisfies(self, constraint: TruthTable) -> bool:
"""Check the defining property: every consistent ``(rest, c)`` solves ``phi=0``."""
for r in range(1 << (self.n - 1)):
if not self.consistency[r]:
continue
for c in (0, 1):
xi = self.value(r, c)
x = _full_index(self.rest_vars, self.var, r, xi, self.n)
if constraint[x] != 0:
return False
return TrueGeneralSolution
omnibias.boolean.GeneralSolutionSource ↗class GeneralSolutionDataclass constructor fields; inherited fields, if any, are declared by the base class. A field(...) expression describes a default factory or field options, not a literal argument default.
Parametric general solution of a system via Boole's successive elimination.
For each variable x_k (eliminated in increasing order) we keep the cofactor
pair (A_k, B_k) over the later variables; back-substitution turns any
parameter vector c in {0,1}^n into a solution, and sweeping c over the
cube enumerates the whole solution set (reproductively).
Parameters
| Name | Type & default | Contract |
|---|---|---|
ndataclass field | intRequired | See the operation contract and implementation below. |
cofactorsdataclass field | tuple[tuple[TruthTable, TruthTable], ...]Required | See the operation contract and implementation below. |
consistentdataclass field | boolRequired | See the operation contract and implementation below. |
Executed regression · inconsistent system is empty
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_inconsistent_system_is_empty() -> None:
# x0 = 0 and x0 = 1 simultaneously.
c1 = (0, 1) # phi = x0 (violated when x0=1) -> forces x0=0
c2 = (1, 0) # phi = ~x0 (violated when x0=0) -> forces x0=1
gen = solve_system([c1, c2])
assert not gen.consistent
assert gen.enumerate_solutions() == []python -m pytest "packages/omnibias-boolean/tests/test_equations.py::test_inconsistent_system_is_empty" -qFields & methods
nfield
n: intDeclared int field on GeneralSolution. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.
View source ↗cofactorsfield
cofactors: tuple[tuple[TruthTable, TruthTable], ...]Declared tuple[tuple[TruthTable, TruthTable], ...] field on GeneralSolution. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.
View source ↗consistentfield
consistent: boolDeclared bool field on GeneralSolution. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.
View source ↗reconstructmethod
reconstruct(self, params: Sequence[int]) -> tuple[int, ...]Back-substitute a parameter vector c into a concrete assignment.
Parameters
| Name | Type & default | Contract |
|---|---|---|
paramspositional-or-keyword | Sequence[int]Required | See the operation contract and implementation below. |
Returns: tuple[int, ...]
Validation & failure cases
- When
len(params) != self.n, raisesValueError(f'need {self.n} parameters, got {len(params)}').
Executed regression · solve system enumerates solution set
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_solve_system_enumerates_solution_set() -> None:
rng = random.Random(5)
for n in (1, 2, 3, 4):
for _ in range(25):
# A random system of 1-3 constraints.
k = rng.randint(1, 3)
constraints = [
tuple(rng.randint(0, 1) for _ in range(1 << n)) for _ in range(k)
]
from omnibias.boolean._core.equations import system_constraint
phi = system_constraint(constraints)
gen = solve_system(constraints)
assert gen.enumerate_solutions() == solution_set(phi)python -m pytest "packages/omnibias-boolean/tests/test_equations.py::test_solve_system_enumerates_solution_set" -qMethod implementation
def reconstruct(self, params: Sequence[int]) -> tuple[int, ...]:
"""Back-substitute a parameter vector ``c`` into a concrete assignment."""
if len(params) != self.n:
raise ValueError(f"need {self.n} parameters, got {len(params)}")
xs = [0] * self.n
for k in range(self.n - 1, -1, -1):
a_tab, b_tab = self.cofactors[k]
rest_index = 0
for pos in range(self.n - 1 - k):
if xs[k + 1 + pos]:
rest_index |= 1 << pos
a = a_tab[rest_index]
b = b_tab[rest_index]
c = params[k] & 1
xs[k] = 1 if ((not b) and (a or c)) else 0
return tuple(xs)enumerate_solutionsmethod
enumerate_solutions(self) -> list[int]All solution indices obtained by sweeping the free parameters.
Returns: list[int]
Executed regression · inconsistent system is empty
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_inconsistent_system_is_empty() -> None:
# x0 = 0 and x0 = 1 simultaneously.
c1 = (0, 1) # phi = x0 (violated when x0=1) -> forces x0=0
c2 = (1, 0) # phi = ~x0 (violated when x0=0) -> forces x0=1
gen = solve_system([c1, c2])
assert not gen.consistent
assert gen.enumerate_solutions() == []python -m pytest "packages/omnibias-boolean/tests/test_equations.py::test_inconsistent_system_is_empty" -qMethod implementation
def enumerate_solutions(self) -> list[int]:
"""All solution indices obtained by sweeping the free parameters."""
if not self.consistent:
return []
sols = set()
for p in range(1 << self.n):
params = tuple((p >> k) & 1 for k in range(self.n))
sols.add(index_of(self.reconstruct(params)))
return sorted(sols)Read the implementation
class GeneralSolution:
"""Parametric general solution of a system via Boole's successive elimination.
For each variable ``x_k`` (eliminated in increasing order) we keep the cofactor
pair ``(A_k, B_k)`` over the later variables; back-substitution turns any
parameter vector ``c in {0,1}^n`` into a solution, and sweeping ``c`` over the
cube enumerates the whole solution set (reproductively).
"""
n: int
cofactors: tuple[tuple[TruthTable, TruthTable], ...]
consistent: bool
def reconstruct(self, params: Sequence[int]) -> tuple[int, ...]:
"""Back-substitute a parameter vector ``c`` into a concrete assignment."""
if len(params) != self.n:
raise ValueError(f"need {self.n} parameters, got {len(params)}")
xs = [0] * self.n
for k in range(self.n - 1, -1, -1):
a_tab, b_tab = self.cofactors[k]
rest_index = 0
for pos in range(self.n - 1 - k):
if xs[k + 1 + pos]:
rest_index |= 1 << pos
a = a_tab[rest_index]
b = b_tab[rest_index]
c = params[k] & 1
xs[k] = 1 if ((not b) and (a or c)) else 0
return tuple(xs)
def enumerate_solutions(self) -> list[int]:
"""All solution indices obtained by sweeping the free parameters."""
if not self.consistent:
return []
sols = set()
for p in range(1 << self.n):
params = tuple((p >> k) & 1 for k in range(self.n))
sols.add(index_of(self.reconstruct(params)))
return sorted(sols)constraint_from_predicate
omnibias.boolean.constraint_from_predicateSource ↗constraint_from_predicate(pred: Callable[..., bool], n: int) -> TruthTableConstraint that is 0 exactly where pred(x) is satisfied.
Parameters
| Name | Type & default | Contract |
|---|---|---|
predpositional-or-keyword | Callable[..., bool]Required | See the operation contract and implementation below. |
npositional-or-keyword | intRequired | See the operation contract and implementation below. |
TruthTableRead the implementation
def constraint_from_predicate(pred: Callable[..., bool], n: int) -> TruthTable:
"""Constraint that is ``0`` exactly where ``pred(x)`` is satisfied."""
from omnibias.boolean._core.truth_table import all_assignments
return tuple(0 if pred(*bits) else 1 for bits in all_assignments(n))eliminant
omnibias.boolean.eliminantSource ↗eliminant(constraint: TruthTable, i: int) -> TruthTableEliminant of x_i: (phi|_{x_i=0} AND phi|_{x_i=1}) over the rest.
The equation constraint = 0 has a solution in x_i for a given setting
of the other variables iff this (n-1)-variable function is 0 there.
Parameters
| Name | Type & default | Contract |
|---|---|---|
constraintpositional-or-keyword | TruthTableRequired | See the operation contract and implementation below. |
ipositional-or-keyword | intRequired | See the operation contract and implementation below. |
TruthTableExecuted regression · eliminant and equation
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_eliminant_and_equation() -> None:
# Solve x0 & x1 = y for x1; eliminant over (x0, y) is "no x1 works".
elim = eliminant(AND_EQ, 1)
# rest vars are (x0, y) with x0 = bit0, y = bit1 (reduced order).
# No x1 works exactly when y=1 and x0=0 -> rest index = 0b10 = 2.
assert elim[2] == 1
assert sum(elim) == 1python -m pytest "packages/omnibias-boolean/tests/test_equations.py::test_eliminant_and_equation" -qRead the implementation
def eliminant(constraint: TruthTable, i: int) -> TruthTable:
"""Eliminant of ``x_i``: ``(phi|_{x_i=0} AND phi|_{x_i=1})`` over the rest.
The equation ``constraint = 0`` has a solution in ``x_i`` for a given setting
of the other variables iff this ``(n-1)``-variable function is ``0`` there.
"""
e0 = restrict(constraint, i, 0)
e1 = restrict(constraint, i, 1)
return tuple(a & b for a, b in zip(e0, e1, strict=False))equation_from_callables
omnibias.boolean.equation_from_callablesSource ↗equation_from_callables(lhs: Callable[..., int], rhs: Callable[..., int], n: int) -> TruthTableConstraint phi = lhs XOR rhs (0 where lhs == rhs).
Parameters
| Name | Type & default | Contract |
|---|---|---|
lhspositional-or-keyword | Callable[..., int]Required | See the operation contract and implementation below. |
rhspositional-or-keyword | Callable[..., int]Required | See the operation contract and implementation below. |
npositional-or-keyword | intRequired | See the operation contract and implementation below. |
TruthTableRegression example · solve for is a valid reproductive solution
This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_solve_for_is_a_valid_reproductive_solution() -> None:
sol = solve_for(AND_EQ, 1)
# Plugging the solution back satisfies the original equation everywhere consistent.
assert sol.satisfies(AND_EQ)python -m pytest packages/omnibias-boolean/tests/test_equations.py -k test_solve_for_is_a_valid_reproductive_solution -qRegression example · eliminant and equation
This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_eliminant_and_equation() -> None:
# Solve x0 & x1 = y for x1; eliminant over (x0, y) is "no x1 works".
elim = eliminant(AND_EQ, 1)
# rest vars are (x0, y) with x0 = bit0, y = bit1 (reduced order).
# No x1 works exactly when y=1 and x0=0 -> rest index = 0b10 = 2.
assert elim[2] == 1
assert sum(elim) == 1python -m pytest packages/omnibias-boolean/tests/test_equations.py -k test_eliminant_and_equation -qRead the implementation
def equation_from_callables(
lhs: Callable[..., int], rhs: Callable[..., int], n: int
) -> TruthTable:
"""Constraint ``phi = lhs XOR rhs`` (``0`` where ``lhs == rhs``)."""
from omnibias.boolean._core.truth_table import all_assignments
rows = []
for bits in all_assignments(n):
rows.append(1 if bool(lhs(*bits)) != bool(rhs(*bits)) else 0)
return tuple(rows)is_satisfiable
omnibias.boolean.is_satisfiableSource ↗is_satisfiable(constraint: TruthTable) -> boolTrue iff the equation constraint = 0 has at least one solution.
Parameters
| Name | Type & default | Contract |
|---|---|---|
constraintpositional-or-keyword | TruthTableRequired | See the operation contract and implementation below. |
boolRead the implementation
def is_satisfiable(constraint: TruthTable) -> bool:
"""``True`` iff the equation ``constraint = 0`` has at least one solution."""
return any(v == 0 for v in constraint)solution_set
omnibias.boolean.solution_setSource ↗solution_set(constraint: TruthTable) -> list[int]All assignment indices x with constraint[x] == 0 (brute force).
Parameters
| Name | Type & default | Contract |
|---|---|---|
constraintpositional-or-keyword | TruthTableRequired | See the operation contract and implementation below. |
list[int]Executed regression · solve system enumerates solution set
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_solve_system_enumerates_solution_set() -> None:
rng = random.Random(5)
for n in (1, 2, 3, 4):
for _ in range(25):
# A random system of 1-3 constraints.
k = rng.randint(1, 3)
constraints = [
tuple(rng.randint(0, 1) for _ in range(1 << n)) for _ in range(k)
]
from omnibias.boolean._core.equations import system_constraint
phi = system_constraint(constraints)
gen = solve_system(constraints)
assert gen.enumerate_solutions() == solution_set(phi)python -m pytest "packages/omnibias-boolean/tests/test_equations.py::test_solve_system_enumerates_solution_set" -qRead the implementation
def solution_set(constraint: TruthTable) -> list[int]:
"""All assignment indices ``x`` with ``constraint[x] == 0`` (brute force)."""
check_truth_table(constraint)
return [x for x, v in enumerate(constraint) if v == 0]solve_for
omnibias.boolean.solve_forSource ↗solve_for(constraint: TruthTable, i: int) -> BooleanSolutionReproductive general solution of constraint = 0 for variable x_i.
Parameters
| Name | Type & default | Contract |
|---|---|---|
constraintpositional-or-keyword | TruthTableRequired | See the operation contract and implementation below. |
ipositional-or-keyword | intRequired | See the operation contract and implementation below. |
BooleanSolutionExplicit validation & failure cases
- When
not 0 <= i < n, raisesValueError(f'variable index {i} out of range for n={n}').
These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.
Executed regression · solve for is a valid reproductive solution
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_solve_for_is_a_valid_reproductive_solution() -> None:
sol = solve_for(AND_EQ, 1)
# Plugging the solution back satisfies the original equation everywhere consistent.
assert sol.satisfies(AND_EQ)python -m pytest "packages/omnibias-boolean/tests/test_equations.py::test_solve_for_is_a_valid_reproductive_solution" -qRegression example · solve for matches known branches
This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_solve_for_matches_known_branches() -> None:
sol = solve_for(AND_EQ, 1)
# rest = (x0, y): index = x0 | (y<<1). When x0=1 the AND forces x1 = y.
# x0=1, y=0 -> x1 must be 0 (any c).
r = index_of((1, 0)) # x0=1, y=0 over rest (x0,y)
assert sol.value(r, 0) == 0 and sol.value(r, 1) == 0
# x0=1, y=1 -> x1 must be 1.
r = index_of((1, 1))
assert sol.value(r, 0) == 1 and sol.value(r, 1) == 1
# x0=0, y=0 -> x1 is free (equals the parameter c).
r = index_of((0, 0))
assert sol.value(r, 0) == 0 and sol.value(r, 1) == 1python -m pytest packages/omnibias-boolean/tests/test_equations.py -k test_solve_for_matches_known_branches -qRead the implementation
def solve_for(constraint: TruthTable, i: int) -> BooleanSolution:
"""Reproductive general solution of ``constraint = 0`` for variable ``x_i``."""
check_truth_table(constraint)
n = num_vars(constraint)
if not 0 <= i < n:
raise ValueError(f"variable index {i} out of range for n={n}")
e0 = restrict(constraint, i, 0)
e1 = restrict(constraint, i, 1)
rest_vars = tuple(j for j in range(n) if j != i)
m = 1 << (n - 1)
consistency = tuple(0 if (e0[r] and e1[r]) else 1 for r in range(m))
sol = [0] * (1 << n)
for r in range(m):
for c in (0, 1):
chosen = 1 if ((not e1[r]) and (e0[r] or c)) else 0
sol[r | (c << (n - 1))] = chosen
return BooleanSolution(
var=i, n=n, rest_vars=rest_vars, consistency=consistency, solution=tuple(sol)
)solve_system
omnibias.boolean.solve_systemSource ↗solve_system(constraints: Sequence[TruthTable]) -> GeneralSolutionReproductive general solution of a Boolean system by successive elimination.
Parameters
| Name | Type & default | Contract |
|---|---|---|
constraintspositional-or-keyword | Sequence[TruthTable]Required | See the operation contract and implementation below. |
GeneralSolutionExplicit validation & failure cases
- When
n < 1, raisesValueError('system must have at least one variable').
These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.
Executed regression · inconsistent system is empty
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_inconsistent_system_is_empty() -> None:
# x0 = 0 and x0 = 1 simultaneously.
c1 = (0, 1) # phi = x0 (violated when x0=1) -> forces x0=0
c2 = (1, 0) # phi = ~x0 (violated when x0=0) -> forces x0=1
gen = solve_system([c1, c2])
assert not gen.consistent
assert gen.enumerate_solutions() == []python -m pytest "packages/omnibias-boolean/tests/test_equations.py::test_inconsistent_system_is_empty" -qRegression example · solve system enumerates solution set
This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_solve_system_enumerates_solution_set() -> None:
rng = random.Random(5)
for n in (1, 2, 3, 4):
for _ in range(25):
# A random system of 1-3 constraints.
k = rng.randint(1, 3)
constraints = [
tuple(rng.randint(0, 1) for _ in range(1 << n)) for _ in range(k)
]
from omnibias.boolean._core.equations import system_constraint
phi = system_constraint(constraints)
gen = solve_system(constraints)
assert gen.enumerate_solutions() == solution_set(phi)python -m pytest packages/omnibias-boolean/tests/test_equations.py -k test_solve_system_enumerates_solution_set -qRead the implementation
def solve_system(constraints: Sequence[TruthTable]) -> GeneralSolution:
"""Reproductive general solution of a Boolean system by successive elimination."""
phi = system_constraint(constraints)
n = num_vars(phi)
if n < 1:
raise ValueError("system must have at least one variable")
cofactors: list[tuple[TruthTable, TruthTable]] = []
cur = phi
for _ in range(n):
a_tab = restrict(cur, 0, 0)
b_tab = restrict(cur, 0, 1)
cofactors.append((a_tab, b_tab))
cur = tuple(a & b for a, b in zip(a_tab, b_tab, strict=False))
final_const = cur[0]
return GeneralSolution(n=n, cofactors=tuple(cofactors), consistent=(final_const == 0))system_constraint
omnibias.boolean.system_constraintSource ↗system_constraint(constraints: Sequence[TruthTable]) -> TruthTableCombine equations phi_k = 0 into one constraint (their logical OR).
Parameters
| Name | Type & default | Contract |
|---|---|---|
constraintspositional-or-keyword | Sequence[TruthTable]Required | See the operation contract and implementation below. |
TruthTableExplicit validation & failure cases
- When
not constraints, raisesValueError('need at least one constraint'). - When
num_vars(c) != n, raisesValueError('all constraints must have the same number of variables').
These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.
Executed regression · inconsistent system is empty
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_inconsistent_system_is_empty() -> None:
# x0 = 0 and x0 = 1 simultaneously.
c1 = (0, 1) # phi = x0 (violated when x0=1) -> forces x0=0
c2 = (1, 0) # phi = ~x0 (violated when x0=0) -> forces x0=1
gen = solve_system([c1, c2])
assert not gen.consistent
assert gen.enumerate_solutions() == []python -m pytest "packages/omnibias-boolean/tests/test_equations.py::test_inconsistent_system_is_empty" -qRegression example · solve system enumerates solution set
This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_solve_system_enumerates_solution_set() -> None:
rng = random.Random(5)
for n in (1, 2, 3, 4):
for _ in range(25):
# A random system of 1-3 constraints.
k = rng.randint(1, 3)
constraints = [
tuple(rng.randint(0, 1) for _ in range(1 << n)) for _ in range(k)
]
from omnibias.boolean._core.equations import system_constraint
phi = system_constraint(constraints)
gen = solve_system(constraints)
assert gen.enumerate_solutions() == solution_set(phi)python -m pytest packages/omnibias-boolean/tests/test_equations.py -k test_solve_system_enumerates_solution_set -qRead the implementation
def system_constraint(constraints: Sequence[TruthTable]) -> TruthTable:
"""Combine equations ``phi_k = 0`` into one constraint (their logical OR)."""
if not constraints:
raise ValueError("need at least one constraint")
n = num_vars(constraints[0])
for c in constraints:
if num_vars(c) != n:
raise ValueError("all constraints must have the same number of variables")
size = 1 << n
out = [0] * size
for c in constraints:
for x in range(size):
out[x] |= c[x]
return tuple(out)anf_from_multilinear_coeffs
omnibias.boolean.anf_from_multilinear_coeffsSource ↗anf_from_multilinear_coeffs(coeffs: Sequence[Number]) -> tuple[int, ...]GF(2) ANF coefficients = integer Mobius coefficients reduced mod 2.
Valid for a {0,1}-valued function; the integer Mobius transform coincides
with the binary one modulo 2.
Parameters
| Name | Type & default | Contract |
|---|---|---|
coeffspositional-or-keyword | Sequence[Number]Required | See the operation contract and implementation below. |
tuple[int, ...]Executed regression · anf is multilinear mod two
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_anf_is_multilinear_mod_two() -> None:
rng = random.Random(9)
for n in (1, 2, 3, 4):
for _ in range(20):
tt = tuple(rng.randint(0, 1) for _ in range(1 << n))
coeffs = multilinear_coeffs(tt)
assert anf_from_multilinear_coeffs(coeffs) == anf_from_truth_table(tt)python -m pytest "packages/omnibias-boolean/tests/test_multilinear.py::test_anf_is_multilinear_mod_two" -qRead the implementation
def anf_from_multilinear_coeffs(coeffs: Sequence[Number]) -> tuple[int, ...]:
"""GF(2) ANF coefficients = integer Mobius coefficients reduced mod 2.
Valid for a ``{0,1}``-valued function; the integer Mobius transform coincides
with the binary one modulo 2.
"""
return tuple(int(round(float(c))) & 1 for c in coeffs)mixed_partial
omnibias.boolean.mixed_partialSource ↗mixed_partial(values: Sequence[Number], subset: int, x: Sequence[float]) -> floatMixed partial d^{|subset|} F / prod_{i in subset} d x_i at x.
subset is a variable bitmask. At x = 0 this returns m_subset
(the Mobius coefficient), demonstrating the partial-derivative bridge.
Parameters
| Name | Type & default | Contract |
|---|---|---|
valuespositional-or-keyword | Sequence[Number]Required | See the operation contract and implementation below. |
subsetpositional-or-keyword | intRequired | See the operation contract and implementation below. |
xpositional-or-keyword | Sequence[float]Required | See the operation contract and implementation below. |
floatExplicit validation & failure cases
- When
len(x) != n, raisesValueError(f'x must have length {n}, got {len(x)}').
These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.
Executed regression · mobius coeff is mixed partial at zero
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_mobius_coeff_is_mixed_partial_at_zero() -> None:
rng = random.Random(8)
for n in (1, 2, 3):
for _ in range(10):
tt = tuple(rng.randint(0, 1) for _ in range(1 << n))
coeffs = multilinear_coeffs(tt)
zero = [0.0] * n
for subset in range(1 << n):
assert math.isclose(
mixed_partial(tt, subset, zero), float(coeffs[subset]), abs_tol=1e-9
)python -m pytest "packages/omnibias-boolean/tests/test_multilinear.py::test_mobius_coeff_is_mixed_partial_at_zero" -qRead the implementation
def mixed_partial(values: Sequence[Number], subset: int, x: Sequence[float]) -> float:
"""Mixed partial ``d^{|subset|} F / prod_{i in subset} d x_i`` at ``x``.
``subset`` is a variable bitmask. At ``x = 0`` this returns ``m_subset``
(the Mobius coefficient), demonstrating the partial-derivative bridge.
"""
coeffs = multilinear_coeffs(values)
size = len(coeffs)
n = _num_vars(size)
if len(x) != n:
raise ValueError(f"x must have length {n}, got {len(x)}")
total = 0.0
for t in range(size):
if (t & subset) != subset:
continue
coeff = coeffs[t]
if coeff == 0:
continue
remaining = t & ~subset
prod = 1.0
for i in range(n):
if (remaining >> i) & 1:
prod *= x[i]
total += float(coeff) * prod
return totalmultilinear_coeffs
omnibias.boolean.multilinear_coeffsSource ↗multilinear_coeffs(values: Sequence[Number]) -> tuple[Number, ...]Monomial coefficients m_S of the multilinear extension (real Mobius).
Parameters
| Name | Type & default | Contract |
|---|---|---|
valuespositional-or-keyword | Sequence[Number]Required | See the operation contract and implementation below. |
tuple[Number, ...]Executed regression · known multilinear coeffs
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_known_multilinear_coeffs() -> None:
assert multilinear_coeffs(AND) == (0, 0, 0, 1) # x0*x1
assert multilinear_coeffs(OR) == (0, 1, 1, -1) # x0 + x1 - x0*x1
assert multilinear_coeffs(XOR) == (0, 1, 1, -2) # x0 + x1 - 2*x0*x1python -m pytest "packages/omnibias-boolean/tests/test_multilinear.py::test_known_multilinear_coeffs" -qRegression example · coeffs round trip
This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_coeffs_round_trip() -> None:
rng = random.Random(7)
for n in (1, 2, 3, 4):
for _ in range(10):
tt = tuple(rng.randint(0, 1) for _ in range(1 << n))
coeffs = multilinear_coeffs(tt)
assert values_from_multilinear_coeffs(coeffs) == ttpython -m pytest packages/omnibias-boolean/tests/test_multilinear.py -k test_coeffs_round_trip -qRead the implementation
def multilinear_coeffs(values: Sequence[Number]) -> tuple[Number, ...]:
"""Monomial coefficients ``m_S`` of the multilinear extension (real Mobius)."""
a = list(values)
size = len(a)
_num_vars(size)
step = 1
while step < size:
for i in range(0, size, step << 1):
for j in range(i, i + step):
a[j + step] = a[j + step] - a[j]
step <<= 1
return tuple(a)multilinear_eval
omnibias.boolean.multilinear_evalSource ↗multilinear_eval(values: Sequence[Number], x: Sequence[float]) -> floatEvaluate the multilinear extension F(x) from cube values via products.
Parameters
| Name | Type & default | Contract |
|---|---|---|
valuespositional-or-keyword | Sequence[Number]Required | See the operation contract and implementation below. |
xpositional-or-keyword | Sequence[float]Required | See the operation contract and implementation below. |
floatExplicit validation & failure cases
- When
len(x) != n, raisesValueError(f'x must have length {n}, got {len(x)}').
These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.
Executed regression · extension agrees on cube corners
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_extension_agrees_on_cube_corners() -> None:
rng = random.Random(6)
for n in (1, 2, 3, 4):
for _ in range(10):
tt = tuple(rng.randint(0, 1) for _ in range(1 << n))
for idx, val in enumerate(tt):
x = [float(b) for b in assignment(idx, n)]
assert math.isclose(multilinear_eval(tt, x), val, abs_tol=1e-12)python -m pytest "packages/omnibias-boolean/tests/test_multilinear.py::test_extension_agrees_on_cube_corners" -qRead the implementation
def multilinear_eval(values: Sequence[Number], x: Sequence[float]) -> float:
"""Evaluate the multilinear extension ``F(x)`` from cube values via products."""
size = len(values)
n = _num_vars(size)
if len(x) != n:
raise ValueError(f"x must have length {n}, got {len(x)}")
total = 0.0
for a in range(size):
prod = 1.0
for i in range(n):
prod *= x[i] if (a >> i) & 1 else (1.0 - x[i])
total += float(values[a]) * prod
return totalmultilinear_eval_from_coeffs
omnibias.boolean.multilinear_eval_from_coeffsSource ↗multilinear_eval_from_coeffs(coeffs: Sequence[Number], x: Sequence[float]) -> floatEvaluate F(x) = sum_S m_S prod_{i in S} x_i from monomial coefficients.
Parameters
| Name | Type & default | Contract |
|---|---|---|
coeffspositional-or-keyword | Sequence[Number]Required | See the operation contract and implementation below. |
xpositional-or-keyword | Sequence[float]Required | See the operation contract and implementation below. |
floatExplicit validation & failure cases
- When
len(x) != n, raisesValueError(f'x must have length {n}, got {len(x)}').
These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.
Read the implementation
def multilinear_eval_from_coeffs(coeffs: Sequence[Number], x: Sequence[float]) -> float:
"""Evaluate ``F(x) = sum_S m_S prod_{i in S} x_i`` from monomial coefficients."""
size = len(coeffs)
n = _num_vars(size)
if len(x) != n:
raise ValueError(f"x must have length {n}, got {len(x)}")
total = 0.0
for s in range(size):
coeff = coeffs[s]
if coeff == 0:
continue
prod = 1.0
for i in range(n):
if (s >> i) & 1:
prod *= x[i]
total += float(coeff) * prod
return totalvalues_from_multilinear_coeffs
omnibias.boolean.values_from_multilinear_coeffsSource ↗values_from_multilinear_coeffs(coeffs: Sequence[Number]) -> tuple[Number, ...]Inverse transform (zeta / addition butterfly): cube values from m_S.
Parameters
| Name | Type & default | Contract |
|---|---|---|
coeffspositional-or-keyword | Sequence[Number]Required | See the operation contract and implementation below. |
tuple[Number, ...]Executed regression · coeffs round trip
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_coeffs_round_trip() -> None:
rng = random.Random(7)
for n in (1, 2, 3, 4):
for _ in range(10):
tt = tuple(rng.randint(0, 1) for _ in range(1 << n))
coeffs = multilinear_coeffs(tt)
assert values_from_multilinear_coeffs(coeffs) == ttpython -m pytest "packages/omnibias-boolean/tests/test_multilinear.py::test_coeffs_round_trip" -qRead the implementation
def values_from_multilinear_coeffs(coeffs: Sequence[Number]) -> tuple[Number, ...]:
"""Inverse transform (zeta / addition butterfly): cube values from ``m_S``."""
a = list(coeffs)
size = len(a)
_num_vars(size)
step = 1
while step < size:
for i in range(0, size, step << 1):
for j in range(i, i + step):
a[j + step] = a[j + step] + a[j]
step <<= 1
return tuple(a)GF2Solution
omnibias.boolean.GF2SolutionSource ↗class GF2SolutionDataclass constructor fields; inherited fields, if any, are declared by the base class. A field(...) expression describes a default factory or field options, not a literal argument default.
Solution space of an affine GF(2) system: particular + span(basis).
Parameters
| Name | Type & default | Contract |
|---|---|---|
consistentdataclass field | boolRequired | See the operation contract and implementation below. |
ndataclass field | intRequired | See the operation contract and implementation below. |
particulardataclass field | tuple[int, ...]Required | See the operation contract and implementation below. |
free_varsdataclass field | tuple[int, ...]Required | See the operation contract and implementation below. |
basisdataclass field | tuple[tuple[int, ...], ...]Required | See the operation contract and implementation below. |
Executed regression · gf2 enumerates full solution space
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_gf2_enumerates_full_solution_space() -> None:
# Parity x0 ^ x1 ^ x2 = 0 has a 2-dimensional null space (4 even-parity points).
sys = BooleanSystem.from_predicates([lambda a, b, c: (a ^ b ^ c) == 0], n=3)
gsol = gf2_solve(sys.constraints)
assert gsol is not None and gsol.consistent
from omnibias.boolean._core.truth_table import index_of
bf = sorted(index_of(b) for b in brute_force_solutions(sys))
assert gsol.enumerate_solutions() == bf
assert len(bf) == 4python -m pytest "packages/omnibias-boolean/tests/test_solver.py::test_gf2_enumerates_full_solution_space" -qFields & methods
consistentfield
consistent: boolDeclared bool field on GF2Solution. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.
View source ↗nfield
n: intDeclared int field on GF2Solution. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.
View source ↗particularfield
particular: tuple[int, ...]Declared tuple[int, ...] field on GF2Solution. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.
View source ↗free_varsfield
free_vars: tuple[int, ...]Declared tuple[int, ...] field on GF2Solution. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.
View source ↗basisfield
basis: tuple[tuple[int, ...], ...]Declared tuple[tuple[int, ...], ...] field on GF2Solution. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.
View source ↗enumerate_solutionsmethod
enumerate_solutions(self, limit: int=1 << 20) -> list[int]All solution indices (capped at limit when the null space is large).
Parameters
| Name | Type & default | Contract |
|---|---|---|
limitpositional-or-keyword | intDefault: 1 << 20 | See the operation contract and implementation below. |
Returns: list[int]
Validation & failure cases
- When
1 << k > limit, raisesValueError(f'null space has 2**{k} solutions; raise limit to enumerate').
Executed regression · gf2 enumerates full solution space
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_gf2_enumerates_full_solution_space() -> None:
# Parity x0 ^ x1 ^ x2 = 0 has a 2-dimensional null space (4 even-parity points).
sys = BooleanSystem.from_predicates([lambda a, b, c: (a ^ b ^ c) == 0], n=3)
gsol = gf2_solve(sys.constraints)
assert gsol is not None and gsol.consistent
from omnibias.boolean._core.truth_table import index_of
bf = sorted(index_of(b) for b in brute_force_solutions(sys))
assert gsol.enumerate_solutions() == bf
assert len(bf) == 4python -m pytest "packages/omnibias-boolean/tests/test_solver.py::test_gf2_enumerates_full_solution_space" -qMethod implementation
def enumerate_solutions(self, limit: int = 1 << 20) -> list[int]:
"""All solution indices (capped at ``limit`` when the null space is large)."""
if not self.consistent:
return []
sols = set()
k = len(self.free_vars)
if (1 << k) > limit:
raise ValueError(
f"null space has 2**{k} solutions; raise limit to enumerate"
)
for combo in range(1 << k):
bits = list(self.particular)
for j in range(k):
if (combo >> j) & 1:
for i in range(self.n):
bits[i] ^= self.basis[j][i]
sols.add(index_of(tuple(bits)))
return sorted(sols)Read the implementation
class GF2Solution:
"""Solution space of an affine GF(2) system: ``particular + span(basis)``."""
consistent: bool
n: int
particular: tuple[int, ...]
free_vars: tuple[int, ...]
basis: tuple[tuple[int, ...], ...]
def enumerate_solutions(self, limit: int = 1 << 20) -> list[int]:
"""All solution indices (capped at ``limit`` when the null space is large)."""
if not self.consistent:
return []
sols = set()
k = len(self.free_vars)
if (1 << k) > limit:
raise ValueError(
f"null space has 2**{k} solutions; raise limit to enumerate"
)
for combo in range(1 << k):
bits = list(self.particular)
for j in range(k):
if (combo >> j) & 1:
for i in range(self.n):
bits[i] ^= self.basis[j][i]
sols.add(index_of(tuple(bits)))
return sorted(sols)constraints_are_linear
omnibias.boolean.constraints_are_linearSource ↗constraints_are_linear(constraints: Sequence[TruthTable]) -> boolTrue iff every constraint is XOR-linear (ANF algebraic degree <= 1).
Parameters
| Name | Type & default | Contract |
|---|---|---|
constraintspositional-or-keyword | Sequence[TruthTable]Required | See the operation contract and implementation below. |
boolExecuted regression · inconsistent linear system
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_inconsistent_linear_system() -> None:
sys = BooleanSystem.from_predicates(
[lambda a: a == 0, lambda a: a == 1], n=1
)
res = solve(sys)
assert res.method == "gf2"
assert not res.verified
assert res.assignment is Nonepython -m pytest "packages/omnibias-boolean/tests/test_solver.py::test_inconsistent_linear_system" -qRead the implementation
def constraints_are_linear(constraints: Sequence[TruthTable]) -> bool:
"""``True`` iff every constraint is XOR-linear (ANF algebraic degree <= 1)."""
return all(algebraic_degree(anf_from_truth_table(c)) <= 1 for c in constraints)gf2_solve
omnibias.boolean.gf2_solveSource ↗gf2_solve(constraints: Sequence[TruthTable]) -> GF2Solution | NoneSolve an all-linear Boolean system over GF(2); None if it is non-linear.
Parameters
| Name | Type & default | Contract |
|---|---|---|
constraintspositional-or-keyword | Sequence[TruthTable]Required | See the operation contract and implementation below. |
GF2Solution | NoneExplicit validation & failure cases
- When
not constraints, raisesValueError('need at least one constraint').
These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.
Executed regression · inconsistent linear system
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_inconsistent_linear_system() -> None:
sys = BooleanSystem.from_predicates(
[lambda a: a == 0, lambda a: a == 1], n=1
)
res = solve(sys)
assert res.method == "gf2"
assert not res.verified
assert res.assignment is Nonepython -m pytest "packages/omnibias-boolean/tests/test_solver.py::test_inconsistent_linear_system" -qRegression example · gf2 enumerates full solution space
This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_gf2_enumerates_full_solution_space() -> None:
# Parity x0 ^ x1 ^ x2 = 0 has a 2-dimensional null space (4 even-parity points).
sys = BooleanSystem.from_predicates([lambda a, b, c: (a ^ b ^ c) == 0], n=3)
gsol = gf2_solve(sys.constraints)
assert gsol is not None and gsol.consistent
from omnibias.boolean._core.truth_table import index_of
bf = sorted(index_of(b) for b in brute_force_solutions(sys))
assert gsol.enumerate_solutions() == bf
assert len(bf) == 4python -m pytest packages/omnibias-boolean/tests/test_solver.py -k test_gf2_enumerates_full_solution_space -qRead the implementation
def gf2_solve(constraints: Sequence[TruthTable]) -> GF2Solution | None:
"""Solve an all-linear Boolean system over GF(2); ``None`` if it is non-linear."""
if not constraints:
raise ValueError("need at least one constraint")
n = num_vars(constraints[0])
rows = linear_system_rows(constraints, n)
if rows is None:
return None
aug = [list(coeffs) + [rhs] for coeffs, rhs in rows]
pivot_row_of_col: dict[int, int] = {}
r = 0
for col in range(n):
piv = next((rr for rr in range(r, len(aug)) if aug[rr][col] == 1), None)
if piv is None:
continue
aug[r], aug[piv] = aug[piv], aug[r]
for rr in range(len(aug)):
if rr != r and aug[rr][col] == 1:
aug[rr] = [a ^ b for a, b in zip(aug[rr], aug[r], strict=False)]
pivot_row_of_col[col] = r
r += 1
for row in aug:
if all(v == 0 for v in row[:n]) and row[n] == 1:
return GF2Solution(
consistent=False, n=n, particular=(), free_vars=(), basis=()
)
particular = [0] * n
for col, row in pivot_row_of_col.items():
particular[col] = aug[row][n]
free_vars = tuple(col for col in range(n) if col not in pivot_row_of_col)
basis: list[tuple[int, ...]] = []
for f in free_vars:
vec = [0] * n
vec[f] = 1
for col, row in pivot_row_of_col.items():
vec[col] = aug[row][f]
basis.append(tuple(vec))
return GF2Solution(
consistent=True,
n=n,
particular=tuple(particular),
free_vars=free_vars,
basis=tuple(basis),
)linear_system_rows
omnibias.boolean.linear_system_rowsSource ↗linear_system_rows(constraints: Sequence[TruthTable], n: int) -> list[tuple[tuple[int, ...], int]] | NoneAffine GF(2) rows (coeffs, rhs) for XOR_i coeffs_i x_i = rhs.
Returns None if any constraint is non-linear (ANF degree > 1).
Parameters
| Name | Type & default | Contract |
|---|---|---|
constraintspositional-or-keyword | Sequence[TruthTable]Required | See the operation contract and implementation below. |
npositional-or-keyword | intRequired | See the operation contract and implementation below. |
list[tuple[tuple[int, ...], int]] | NoneExecuted regression · inconsistent linear system
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_inconsistent_linear_system() -> None:
sys = BooleanSystem.from_predicates(
[lambda a: a == 0, lambda a: a == 1], n=1
)
res = solve(sys)
assert res.method == "gf2"
assert not res.verified
assert res.assignment is Nonepython -m pytest "packages/omnibias-boolean/tests/test_solver.py::test_inconsistent_linear_system" -qRead the implementation
def linear_system_rows(
constraints: Sequence[TruthTable], n: int
) -> list[tuple[tuple[int, ...], int]] | None:
"""Affine GF(2) rows ``(coeffs, rhs)`` for ``XOR_i coeffs_i x_i = rhs``.
Returns ``None`` if any constraint is non-linear (ANF degree > 1).
"""
rows: list[tuple[tuple[int, ...], int]] = []
for c in constraints:
anf = anf_from_truth_table(c)
if algebraic_degree(anf) > 1:
return None
coeffs = tuple(anf[1 << i] for i in range(n))
rows.append((coeffs, anf[0]))
return rowsverify_assignment
omnibias.boolean.verify_assignmentSource ↗verify_assignment(constraints: Sequence[TruthTable], bits: Sequence[int]) -> boolTrue iff every constraint phi_k is 0 at the assignment bits.
Parameters
| Name | Type & default | Contract |
|---|---|---|
constraintspositional-or-keyword | Sequence[TruthTable]Required | See the operation contract and implementation below. |
bitspositional-or-keyword | Sequence[int]Required | See the operation contract and implementation below. |
boolExecuted regression · gf2 fast path linear unique
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_gf2_fast_path_linear_unique() -> None:
# x0 ^ x1 = 1 and x1 = 1 -> x1 = 1, x0 = 0 (unique).
sys = BooleanSystem.from_predicates(
[lambda a, b: (a ^ b) == 1, lambda a, b: b == 1], n=2
)
assert sys.is_linear()
res = solve(sys)
assert res.method == "gf2"
assert res.verified
assert res.assignment == (0, 1)python -m pytest "packages/omnibias-boolean/tests/test_solver.py::test_gf2_fast_path_linear_unique" -qRead the implementation
def verify_assignment(constraints: Sequence[TruthTable], bits: Sequence[int]) -> bool:
"""``True`` iff every constraint ``phi_k`` is ``0`` at the assignment ``bits``."""
idx = index_of(tuple(bits))
return all(c[idx] == 0 for c in constraints)TruthTable
omnibias.boolean.TruthTableSource ↗TruthTable = tuple[int, ...]This exported constant is defined by the expression above. Its exact value and annotation come from the pinned source; use it with the module contract.
Read the implementation
TruthTable = tuple[int, ...]all_assignments
omnibias.boolean.all_assignmentsSource ↗all_assignments(n: int) -> Iterator[tuple[int, ...]]Iterate over every assignment (x_0, ..., x_{n-1}) in row order.
Parameters
| Name | Type & default | Contract |
|---|---|---|
npositional-or-keyword | intRequired | See the operation contract and implementation below. |
Iterator[tuple[int, ...]]Executed regression · inconsistent linear system
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_inconsistent_linear_system() -> None:
sys = BooleanSystem.from_predicates(
[lambda a: a == 0, lambda a: a == 1], n=1
)
res = solve(sys)
assert res.method == "gf2"
assert not res.verified
assert res.assignment is Nonepython -m pytest "packages/omnibias-boolean/tests/test_solver.py::test_inconsistent_linear_system" -qRead the implementation
def all_assignments(n: int) -> Iterator[tuple[int, ...]]:
"""Iterate over every assignment ``(x_0, ..., x_{n-1})`` in row order."""
for i in range(1 << n):
yield assignment(i, n)assignment
omnibias.boolean.assignmentSource ↗assignment(index: int, n: int) -> tuple[int, ...]Decode row index into the bit tuple (x_0, ..., x_{n-1}) (LSB-first).
Parameters
| Name | Type & default | Contract |
|---|---|---|
indexpositional-or-keyword | intRequired | See the operation contract and implementation below. |
npositional-or-keyword | intRequired | See the operation contract and implementation below. |
tuple[int, ...]Explicit validation & failure cases
- When
not 0 <= index < 1 << n, raisesValueError(f'index {index} out of range for n={n}').
These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.
Executed regression · inconsistent linear system
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_inconsistent_linear_system() -> None:
sys = BooleanSystem.from_predicates(
[lambda a: a == 0, lambda a: a == 1], n=1
)
res = solve(sys)
assert res.method == "gf2"
assert not res.verified
assert res.assignment is Nonepython -m pytest "packages/omnibias-boolean/tests/test_solver.py::test_inconsistent_linear_system" -qRegression example · extension agrees on cube corners
This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_extension_agrees_on_cube_corners() -> None:
rng = random.Random(6)
for n in (1, 2, 3, 4):
for _ in range(10):
tt = tuple(rng.randint(0, 1) for _ in range(1 << n))
for idx, val in enumerate(tt):
x = [float(b) for b in assignment(idx, n)]
assert math.isclose(multilinear_eval(tt, x), val, abs_tol=1e-12)python -m pytest packages/omnibias-boolean/tests/test_multilinear.py -k test_extension_agrees_on_cube_corners -qRead the implementation
def assignment(index: int, n: int) -> tuple[int, ...]:
"""Decode row ``index`` into the bit tuple ``(x_0, ..., x_{n-1})`` (LSB-first)."""
if not 0 <= index < (1 << n):
raise ValueError(f"index {index} out of range for n={n}")
return tuple((index >> j) & 1 for j in range(n))bit_to_spin
omnibias.boolean.bit_to_spinSource ↗bit_to_spin(b: int) -> intMap a bit {0, 1} to a spin {+1, -1} via s = 1 - 2b.
Parameters
| Name | Type & default | Contract |
|---|---|---|
bpositional-or-keyword | intRequired | See the operation contract and implementation below. |
intExplicit validation & failure cases
- When
b not in (0, 1), raisesValueError(f'bit must be 0 or 1, got {b}').
These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.
Executed regression · degree soft of parity
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_degree_soft_of_parity() -> None:
# 2-bit XOR is pure order-2 in the Walsh basis -> soft degree == 2.
xor = (0, 1, 1, 0)
vals = torch.tensor(pm1_values(xor), dtype=torch.float64)
assert float(spectrum.algebraic_degree_soft(vals)) == pytest.approx(2.0, abs=1e-9)python -m pytest "packages/omnibias-boolean/tests/test_spectrum.py::test_degree_soft_of_parity" -qRead the implementation
def bit_to_spin(b: int) -> int:
"""Map a bit ``{0, 1}`` to a spin ``{+1, -1}`` via ``s = 1 - 2b``."""
if b not in (0, 1):
raise ValueError(f"bit must be 0 or 1, got {b}")
return 1 - 2 * bcheck_truth_table
omnibias.boolean.check_truth_tableSource ↗check_truth_table(table: TruthTable) -> NoneValidate that table has power-of-two length and {0, 1} entries.
Parameters
| Name | Type & default | Contract |
|---|---|---|
tablepositional-or-keyword | TruthTableRequired | See the operation contract and implementation below. |
NoneExplicit validation & failure cases
- When
v not in (0, 1), raisesValueError(f'truth-table entries must be 0 or 1, got {v}').
These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.
Executed regression · derivative is constant in its variable
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_derivative_is_constant_in_its_variable() -> None:
d = boolean_derivative(AND, 0)
assert is_independent_of(d, 0)python -m pytest "packages/omnibias-boolean/tests/test_derivative.py::test_derivative_is_constant_in_its_variable" -qRead the implementation
def check_truth_table(table: TruthTable) -> None:
"""Validate that ``table`` has power-of-two length and ``{0, 1}`` entries."""
num_vars(table)
for v in table:
if v not in (0, 1):
raise ValueError(f"truth-table entries must be 0 or 1, got {v}")index_of
omnibias.boolean.index_ofSource ↗index_of(bits: tuple[int, ...]) -> intEncode a bit tuple (x_0, ..., x_{n-1}) (LSB-first) into its row index.
Parameters
| Name | Type & default | Contract |
|---|---|---|
bitspositional-or-keyword | tuple[int, ...]Required | See the operation contract and implementation below. |
intExplicit validation & failure cases
- When
b not in (0, 1), raisesValueError(f'bits must be 0 or 1, got {b}').
These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.
Executed regression · gf2 fast path linear unique
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_gf2_fast_path_linear_unique() -> None:
# x0 ^ x1 = 1 and x1 = 1 -> x1 = 1, x0 = 0 (unique).
sys = BooleanSystem.from_predicates(
[lambda a, b: (a ^ b) == 1, lambda a, b: b == 1], n=2
)
assert sys.is_linear()
res = solve(sys)
assert res.method == "gf2"
assert res.verified
assert res.assignment == (0, 1)python -m pytest "packages/omnibias-boolean/tests/test_solver.py::test_gf2_fast_path_linear_unique" -qRegression example · gf2 enumerates full solution space
This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_gf2_enumerates_full_solution_space() -> None:
# Parity x0 ^ x1 ^ x2 = 0 has a 2-dimensional null space (4 even-parity points).
sys = BooleanSystem.from_predicates([lambda a, b, c: (a ^ b ^ c) == 0], n=3)
gsol = gf2_solve(sys.constraints)
assert gsol is not None and gsol.consistent
from omnibias.boolean._core.truth_table import index_of
bf = sorted(index_of(b) for b in brute_force_solutions(sys))
assert gsol.enumerate_solutions() == bf
assert len(bf) == 4python -m pytest packages/omnibias-boolean/tests/test_solver.py -k test_gf2_enumerates_full_solution_space -qRead the implementation
def index_of(bits: tuple[int, ...]) -> int:
"""Encode a bit tuple ``(x_0, ..., x_{n-1})`` (LSB-first) into its row index."""
idx = 0
for j, b in enumerate(bits):
if b not in (0, 1):
raise ValueError(f"bits must be 0 or 1, got {b}")
idx |= (b & 1) << j
return idxnum_vars
omnibias.boolean.num_varsSource ↗num_vars(table: TruthTable) -> intNumber of variables n such that len(table) == 2**n.
Parameters
| Name | Type & default | Contract |
|---|---|---|
tablepositional-or-keyword | TruthTableRequired | See the operation contract and implementation below. |
intExplicit validation & failure cases
- When
not is_power_of_two(size), raisesValueError(f'truth-table length must be a power of two, got {size}').
These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.
Executed regression · derivative is constant in its variable
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_derivative_is_constant_in_its_variable() -> None:
d = boolean_derivative(AND, 0)
assert is_independent_of(d, 0)python -m pytest "packages/omnibias-boolean/tests/test_derivative.py::test_derivative_is_constant_in_its_variable" -qRead the implementation
def num_vars(table: TruthTable) -> int:
"""Number of variables ``n`` such that ``len(table) == 2**n``."""
size = len(table)
if not is_power_of_two(size):
raise ValueError(f"truth-table length must be a power of two, got {size}")
return size.bit_length() - 1pm1_values
omnibias.boolean.pm1_valuesSource ↗pm1_values(table: TruthTable) -> tuple[int, ...]Map a {0, 1} truth table to its {+1, -1} output encoding.
Parameters
| Name | Type & default | Contract |
|---|---|---|
tablepositional-or-keyword | TruthTableRequired | See the operation contract and implementation below. |
tuple[int, ...]Executed regression · degree soft of parity
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_degree_soft_of_parity() -> None:
# 2-bit XOR is pure order-2 in the Walsh basis -> soft degree == 2.
xor = (0, 1, 1, 0)
vals = torch.tensor(pm1_values(xor), dtype=torch.float64)
assert float(spectrum.algebraic_degree_soft(vals)) == pytest.approx(2.0, abs=1e-9)python -m pytest "packages/omnibias-boolean/tests/test_spectrum.py::test_degree_soft_of_parity" -qRegression example · design loss parity
This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_design_loss_parity() -> None:
vals = [0.1, 0.7, 0.3, 0.9]
t = float(tb.degree_penalty(torch.tensor(vals, dtype=torch.float64)))
j = float(jb.degree_penalty(jnp.asarray(vals, dtype=jnp.float64)))
assert t == pytest.approx(j, rel=1e-9, abs=1e-11)python -m pytest packages/omnibias-boolean/tests/test_cross_backend.py -k test_design_loss_parity -qRead the implementation
def pm1_values(table: TruthTable) -> tuple[int, ...]:
"""Map a ``{0, 1}`` truth table to its ``{+1, -1}`` output encoding."""
return tuple(bit_to_spin(v) for v in table)spin_to_bit
omnibias.boolean.spin_to_bitSource ↗spin_to_bit(s: int) -> intMap a spin {+1, -1} back to a bit {0, 1} via b = (1 - s) / 2.
Parameters
| Name | Type & default | Contract |
|---|---|---|
spositional-or-keyword | intRequired | See the operation contract and implementation below. |
intExplicit validation & failure cases
- When
s not in (1, -1), raisesValueError(f'spin must be +1 or -1, got {s}').
These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.
Read the implementation
def spin_to_bit(s: int) -> int:
"""Map a spin ``{+1, -1}`` back to a bit ``{0, 1}`` via ``b = (1 - s) / 2``."""
if s not in (1, -1):
raise ValueError(f"spin must be +1 or -1, got {s}")
return (1 - s) // 2truth_table_from_callable
omnibias.boolean.truth_table_from_callableSource ↗truth_table_from_callable(func: Callable[..., int], n: int) -> TruthTableTabulate func(x_0, ..., x_{n-1}) over all 2**n assignments.
func receives the bits as positional arguments and returns 0/1
(any truthy value is coerced to 1).
Parameters
| Name | Type & default | Contract |
|---|---|---|
funcpositional-or-keyword | Callable[..., int]Required | See the operation contract and implementation below. |
npositional-or-keyword | intRequired | See the operation contract and implementation below. |
TruthTableExplicit validation & failure cases
- When
n < 0, raisesValueError(f'n must be >= 0, got {n}').
These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.
Regression example · derivative is constant in its variable
This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_derivative_is_constant_in_its_variable() -> None:
d = boolean_derivative(AND, 0)
assert is_independent_of(d, 0)python -m pytest packages/omnibias-boolean/tests/test_derivative.py -k test_derivative_is_constant_in_its_variable -qRegression example · anf or
This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_anf_or() -> None:
assert anf_from_truth_table(OR) == (0, 1, 1, 1)
assert anf_to_string(anf_from_truth_table(OR)) == "x0 + x1 + x0*x1"python -m pytest packages/omnibias-boolean/tests/test_anf.py -k test_anf_or -qRead the implementation
def truth_table_from_callable(func: Callable[..., int], n: int) -> TruthTable:
"""Tabulate ``func(x_0, ..., x_{n-1})`` over all ``2**n`` assignments.
``func`` receives the bits as positional arguments and returns ``0``/``1``
(any truthy value is coerced to ``1``).
"""
if n < 0:
raise ValueError(f"n must be >= 0, got {n}")
rows = []
for bits in all_assignments(n):
rows.append(1 if func(*bits) else 0)
return tuple(rows)truth_table_to_callable
omnibias.boolean.truth_table_to_callableSource ↗truth_table_to_callable(table: TruthTable) -> Callable[..., int]Return func(x_0, ..., x_{n-1}) -> {0, 1} reading from table.
Parameters
| Name | Type & default | Contract |
|---|---|---|
tablepositional-or-keyword | TruthTableRequired | See the operation contract and implementation below. |
Callable[..., int]Read the implementation
def truth_table_to_callable(table: TruthTable) -> Callable[..., int]:
"""Return ``func(x_0, ..., x_{n-1}) -> {0, 1}`` reading from ``table``."""
n = num_vars(table)
def func(*bits: int) -> int:
if len(bits) != n:
raise ValueError(f"expected {n} bits, got {len(bits)}")
return table[index_of(bits)]
return funcabsolute_indicator_iv
omnibias.boolean.absolute_indicator_ivSource ↗absolute_indicator_iv(table: TruthTable) -> IntervalEnclosure of the absolute indicator max_{a != 0} |C_f(a)|.
A small absolute indicator certifies good resistance to differential-style attacks (the function is far from having any high-bias derivative).
Parameters
| Name | Type & default | Contract |
|---|---|---|
tablepositional-or-keyword | TruthTableRequired | See the operation contract and implementation below. |
IntervalExecuted regression · bent function certificates
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_bent_function_certificates() -> None:
# Bent on n=4: linearity 4, nonlinearity 6, perfect (zero) autocorrelation.
assert linearity_iv(BENT4).contains(4.0)
assert nonlinearity_iv(BENT4).contains(6.0)
ai = absolute_indicator_iv(BENT4)
assert ai.contains(0.0)
assert ai.hi < 1e-9 # near-zero up to defensive outward rounding
# every nonzero linear bias has magnitude exactly 1/8 = 4 / 2^(4+1).
assert max_linear_bias_iv(BENT4).contains(0.125)python -m pytest "packages/omnibias-boolean/tests/test_verified_spectra.py::test_bent_function_certificates" -qRead the implementation
def absolute_indicator_iv(table: TruthTable) -> Interval:
"""Enclosure of the absolute indicator ``max_{a != 0} |C_f(a)|``.
A small absolute indicator certifies good resistance to differential-style
attacks (the function is far from having any high-bias derivative).
"""
n = num_vars(table)
size = 1 << n
return _max_iv([_abs_iv(autocorrelation_iv(table, a)) for a in range(1, size)])autocorrelation_iv
omnibias.boolean.autocorrelation_ivSource ↗autocorrelation_iv(table: TruthTable | None=None, shift: int=0, *, values: Sequence[IntervalLike] | None=None) -> IntervalEnclosure of the autocorrelation C_f(a) = sum_x s(x) s(x xor a) (spin).
For a Boolean f this is 2^n (1 - 2 Pr_x[D_a f(x) = 1]) where
D_a f = f(x) xor f(x xor a) is the (first-order) Boolean derivative.
Parameters
| Name | Type & default | Contract |
|---|---|---|
tablepositional-or-keyword | TruthTable | NoneDefault: None | See the operation contract and implementation below. |
shiftpositional-or-keyword | intDefault: 0 | See the operation contract and implementation below. |
valueskeyword-only | Sequence[IntervalLike] | NoneDefault: None | See the operation contract and implementation below. |
IntervalExplicit validation & failure cases
- When
not 0 <= shift < size, raisesValueError(f'shift {shift} out of range for length {size}').
These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.
Executed regression · autocorrelation and differential bias oracle
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_autocorrelation_and_differential_bias_oracle() -> None:
rng = random.Random(5)
for n in (2, 3, 4):
for _ in range(20):
tt = _rand_table(rng, n)
spin = [1 - 2 * v for v in tt]
for a in range(1 << n):
c = sum(spin[x] * spin[x ^ a] for x in range(1 << n))
assert autocorrelation_iv(tt, a).contains(float(c))
assert differential_bias_iv(tt, a).contains(c / (1 << (n + 1)))python -m pytest "packages/omnibias-boolean/tests/test_verified_spectra.py::test_autocorrelation_and_differential_bias_oracle" -qRead the implementation
def autocorrelation_iv(
table: TruthTable | None = None,
shift: int = 0,
*,
values: Sequence[IntervalLike] | None = None,
) -> Interval:
r"""Enclosure of the autocorrelation ``C_f(a) = sum_x s(x) s(x xor a)`` (spin).
For a Boolean ``f`` this is ``2^n (1 - 2 Pr_x[D_a f(x) = 1])`` where
``D_a f = f(x) xor f(x xor a)`` is the (first-order) Boolean derivative.
"""
vals, _ = _pm1_values_iv(table, values, "pm1")
size = len(vals)
if not 0 <= shift < size:
raise ValueError(f"shift {shift} out of range for length {size}")
acc = Interval.point(0.0)
for x in range(size):
acc = acc + vals[x] * vals[x ^ shift]
return accdifferential_bias_iv
omnibias.boolean.differential_bias_ivSource ↗differential_bias_iv(table: TruthTable, shift: int) -> IntervalCertified differential bias Pr_x[D_a f(x) = 0] - 1/2 = C_f(a) / 2^{n+1}.
Parameters
| Name | Type & default | Contract |
|---|---|---|
tablepositional-or-keyword | TruthTableRequired | See the operation contract and implementation below. |
shiftpositional-or-keyword | intRequired | See the operation contract and implementation below. |
IntervalExecuted regression · autocorrelation and differential bias oracle
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_autocorrelation_and_differential_bias_oracle() -> None:
rng = random.Random(5)
for n in (2, 3, 4):
for _ in range(20):
tt = _rand_table(rng, n)
spin = [1 - 2 * v for v in tt]
for a in range(1 << n):
c = sum(spin[x] * spin[x ^ a] for x in range(1 << n))
assert autocorrelation_iv(tt, a).contains(float(c))
assert differential_bias_iv(tt, a).contains(c / (1 << (n + 1)))python -m pytest "packages/omnibias-boolean/tests/test_verified_spectra.py::test_autocorrelation_and_differential_bias_oracle" -qRead the implementation
def differential_bias_iv(table: TruthTable, shift: int) -> Interval:
r"""Certified differential bias ``Pr_x[D_a f(x) = 0] - 1/2 = C_f(a) / 2^{n+1}``."""
n = num_vars(table)
c = autocorrelation_iv(table, shift)
return c * Interval.from_rational(Fraction(1, 1 << (n + 1)))fourier_coeffs_iv
omnibias.boolean.fourier_coeffs_ivSource ↗fourier_coeffs_iv(table: TruthTable | None=None, *, values: Sequence[IntervalLike] | None=None, encoding: str='pm1') -> tuple[Interval, ...]Rigorous Fourier coefficients hat f(S) = 2^{-n} (WHT f)(S).
Pass an exact {0,1} table (with encoding "pm1" / "01") for
the certified twin of omnibias.boolean._core.walsh.fourier_coeffs, or
pass real / interval values for the spectrum of a differentiable surrogate.
Parameters
| Name | Type & default | Contract |
|---|---|---|
tablepositional-or-keyword | TruthTable | NoneDefault: None | See the operation contract and implementation below. |
valueskeyword-only | Sequence[IntervalLike] | NoneDefault: None | See the operation contract and implementation below. |
encodingkeyword-only | strDefault: 'pm1' | See the operation contract and implementation below. |
tuple[Interval, ...]Executed regression · parseval defect contains zero
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_parseval_defect_contains_zero() -> None:
rng = random.Random(6)
for n in (1, 2, 3, 4):
for _ in range(20):
tt = _rand_table(rng, n)
assert parseval_defect_iv(tt).contains(0.0)python -m pytest "packages/omnibias-boolean/tests/test_verified_spectra.py::test_parseval_defect_contains_zero" -qRegression example · mobius iv contains float core
This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_mobius_iv_contains_float_core() -> None:
rng = random.Random(1)
for n in (1, 2, 3, 4):
for _ in range(20):
vals = [rng.uniform(-2.0, 2.0) for _ in range(1 << n)]
iv = mobius_iv(vals)
fl = multilinear_coeffs(vals)
for a, b in zip(iv, fl, strict=True):
assert a.contains(float(b))python -m pytest packages/omnibias-boolean/tests/test_verified_spectra.py -k test_mobius_iv_contains_float_core -qRead the implementation
def fourier_coeffs_iv(
table: TruthTable | None = None,
*,
values: Sequence[IntervalLike] | None = None,
encoding: str = "pm1",
) -> tuple[Interval, ...]:
r"""Rigorous Fourier coefficients ``hat f(S) = 2^{-n} (WHT f)(S)``.
Pass an exact ``{0,1}`` ``table`` (with ``encoding`` ``"pm1"`` / ``"01"``) for
the certified twin of :func:`omnibias.boolean._core.walsh.fourier_coeffs`, or
pass real / interval ``values`` for the spectrum of a differentiable surrogate.
"""
vals, n = _pm1_values_iv(table, values, encoding)
wht = walsh_hadamard_iv(vals)
scale = Interval.from_rational(Fraction(1, 1 << n))
return tuple(c * scale for c in wht)linear_bias_iv
omnibias.boolean.linear_bias_ivSource ↗linear_bias_iv(table: TruthTable, mask: int) -> IntervalCertified linear-approximation bias Pr_x[f(x) = <mask,x>] - 1/2.
Equals hat f(mask) / 2 in the {+1,-1} encoding; |bias| <= 1/2.
Parameters
| Name | Type & default | Contract |
|---|---|---|
tablepositional-or-keyword | TruthTableRequired | See the operation contract and implementation below. |
maskpositional-or-keyword | intRequired | See the operation contract and implementation below. |
IntervalExecuted regression · xor linear bias is extremal
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_xor_linear_bias_is_extremal() -> None:
# XOR equals chi_{0,1}, so the linear approximation by mask {0,1} = 0b11 is
# exact: f(x) == <mask, x> for every x, giving the extremal bias +1/2.
b = linear_bias_iv(XOR, 0b11)
assert b.contains(0.5)
# and the best linear bias over all nonzero masks is 1/2.
assert max_linear_bias_iv(XOR).contains(0.5)python -m pytest "packages/omnibias-boolean/tests/test_verified_spectra.py::test_xor_linear_bias_is_extremal" -qRegression example · mobius iv contains float core
This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_mobius_iv_contains_float_core() -> None:
rng = random.Random(1)
for n in (1, 2, 3, 4):
for _ in range(20):
vals = [rng.uniform(-2.0, 2.0) for _ in range(1 << n)]
iv = mobius_iv(vals)
fl = multilinear_coeffs(vals)
for a, b in zip(iv, fl, strict=True):
assert a.contains(float(b))python -m pytest packages/omnibias-boolean/tests/test_verified_spectra.py -k test_mobius_iv_contains_float_core -qRead the implementation
def linear_bias_iv(table: TruthTable, mask: int) -> Interval:
r"""Certified linear-approximation bias ``Pr_x[f(x) = <mask,x>] - 1/2``.
Equals ``hat f(mask) / 2`` in the ``{+1,-1}`` encoding; ``|bias| <= 1/2``.
"""
n = num_vars(table)
w = walsh_at_iv(table, mask)
scale = Interval.from_rational(Fraction(1, 1 << (n + 1)))
return w * scalelinearity_iv
omnibias.boolean.linearity_ivSource ↗linearity_iv(table: TruthTable | None=None, *, values: Sequence[IntervalLike] | None=None) -> IntervalEnclosure of the linearity L(f) = max_S |(WHT s)(S)| (spin, unnormalised).
Parameters
| Name | Type & default | Contract |
|---|---|---|
tablepositional-or-keyword | TruthTable | NoneDefault: None | See the operation contract and implementation below. |
valueskeyword-only | Sequence[IntervalLike] | NoneDefault: None | See the operation contract and implementation below. |
IntervalExecuted regression · linearity nonlinearity oracle
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_linearity_nonlinearity_oracle() -> None:
rng = random.Random(3)
for n in (2, 3, 4):
for _ in range(30):
tt = _rand_table(rng, n)
spin = [1 - 2 * v for v in tt]
wht = _exact_wht(spin)
lin = max(abs(c) for c in wht)
nl = (1 << (n - 1)) - lin // 2
assert linearity_iv(tt).contains(float(lin))
assert nonlinearity_iv(tt).contains(float(nl))python -m pytest "packages/omnibias-boolean/tests/test_verified_spectra.py::test_linearity_nonlinearity_oracle" -qRegression example · bent function certificates
This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_bent_function_certificates() -> None:
# Bent on n=4: linearity 4, nonlinearity 6, perfect (zero) autocorrelation.
assert linearity_iv(BENT4).contains(4.0)
assert nonlinearity_iv(BENT4).contains(6.0)
ai = absolute_indicator_iv(BENT4)
assert ai.contains(0.0)
assert ai.hi < 1e-9 # near-zero up to defensive outward rounding
# every nonzero linear bias has magnitude exactly 1/8 = 4 / 2^(4+1).
assert max_linear_bias_iv(BENT4).contains(0.125)python -m pytest packages/omnibias-boolean/tests/test_verified_spectra.py -k test_bent_function_certificates -qRead the implementation
def linearity_iv(
table: TruthTable | None = None, *, values: Sequence[IntervalLike] | None = None
) -> Interval:
"""Enclosure of the linearity ``L(f) = max_S |(WHT s)(S)|`` (spin, unnormalised)."""
vals, _ = _pm1_values_iv(table, values, "pm1")
wht = walsh_hadamard_iv(vals)
return _max_iv([_abs_iv(c) for c in wht])max_linear_bias_iv
omnibias.boolean.max_linear_bias_ivSource ↗max_linear_bias_iv(table: TruthTable) -> IntervalEnclosure of max_{a != 0} |Pr_x[f(x) = <a,x>] - 1/2| (best linear approx).
Parameters
| Name | Type & default | Contract |
|---|---|---|
tablepositional-or-keyword | TruthTableRequired | See the operation contract and implementation below. |
IntervalExecuted regression · xor linear bias is extremal
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_xor_linear_bias_is_extremal() -> None:
# XOR equals chi_{0,1}, so the linear approximation by mask {0,1} = 0b11 is
# exact: f(x) == <mask, x> for every x, giving the extremal bias +1/2.
b = linear_bias_iv(XOR, 0b11)
assert b.contains(0.5)
# and the best linear bias over all nonzero masks is 1/2.
assert max_linear_bias_iv(XOR).contains(0.5)python -m pytest "packages/omnibias-boolean/tests/test_verified_spectra.py::test_xor_linear_bias_is_extremal" -qRegression example · bent function certificates
This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_bent_function_certificates() -> None:
# Bent on n=4: linearity 4, nonlinearity 6, perfect (zero) autocorrelation.
assert linearity_iv(BENT4).contains(4.0)
assert nonlinearity_iv(BENT4).contains(6.0)
ai = absolute_indicator_iv(BENT4)
assert ai.contains(0.0)
assert ai.hi < 1e-9 # near-zero up to defensive outward rounding
# every nonzero linear bias has magnitude exactly 1/8 = 4 / 2^(4+1).
assert max_linear_bias_iv(BENT4).contains(0.125)python -m pytest packages/omnibias-boolean/tests/test_verified_spectra.py -k test_bent_function_certificates -qRead the implementation
def max_linear_bias_iv(table: TruthTable) -> Interval:
"""Enclosure of ``max_{a != 0} |Pr_x[f(x) = <a,x>] - 1/2|`` (best linear approx)."""
n = num_vars(table)
wht = walsh_hadamard_iv([Interval.point(float(1 - 2 * v)) for v in table])
scale = Interval.from_rational(Fraction(1, 1 << (n + 1)))
return _max_iv([_abs_iv(wht[mask] * scale) for mask in range(1, len(wht))])mobius_iv
omnibias.boolean.mobius_ivSource ↗mobius_iv(values: Sequence[IntervalLike]) -> list[Interval]Outward-rounded real Mobius transform = interval multilinear coefficients.
Twin of omnibias.boolean._core.multilinear.multilinear_coeffs (the
real-valued Reed-Muller / ANF extension); result[S] encloses the monomial
coefficient m_S of the multilinear extension of values.
Parameters
| Name | Type & default | Contract |
|---|---|---|
valuespositional-or-keyword | Sequence[IntervalLike]Required | See the operation contract and implementation below. |
list[Interval]Executed regression · mobius iv contains float core
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_mobius_iv_contains_float_core() -> None:
rng = random.Random(1)
for n in (1, 2, 3, 4):
for _ in range(20):
vals = [rng.uniform(-2.0, 2.0) for _ in range(1 << n)]
iv = mobius_iv(vals)
fl = multilinear_coeffs(vals)
for a, b in zip(iv, fl, strict=True):
assert a.contains(float(b))python -m pytest "packages/omnibias-boolean/tests/test_verified_spectra.py::test_mobius_iv_contains_float_core" -qRead the implementation
def mobius_iv(values: Sequence[IntervalLike]) -> list[Interval]:
r"""Outward-rounded real Mobius transform = interval multilinear coefficients.
Twin of :func:`omnibias.boolean._core.multilinear.multilinear_coeffs` (the
real-valued Reed-Muller / ANF extension); ``result[S]`` encloses the monomial
coefficient ``m_S`` of the multilinear extension of ``values``.
"""
a = [Interval.from_value(v) for v in values]
size = len(a)
_check_pow2(size)
step = 1
while step < size:
for i in range(0, size, step << 1):
for j in range(i, i + step):
a[j + step] = a[j + step] - a[j]
step <<= 1
return anonlinearity_iv
omnibias.boolean.nonlinearity_ivSource ↗nonlinearity_iv(table: TruthTable | None=None, *, values: Sequence[IntervalLike] | None=None) -> IntervalEnclosure of the nonlinearity NL(f) = 2^{n-1} - L(f)/2.
Parameters
| Name | Type & default | Contract |
|---|---|---|
tablepositional-or-keyword | TruthTable | NoneDefault: None | See the operation contract and implementation below. |
valueskeyword-only | Sequence[IntervalLike] | NoneDefault: None | See the operation contract and implementation below. |
IntervalExecuted regression · linearity nonlinearity oracle
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_linearity_nonlinearity_oracle() -> None:
rng = random.Random(3)
for n in (2, 3, 4):
for _ in range(30):
tt = _rand_table(rng, n)
spin = [1 - 2 * v for v in tt]
wht = _exact_wht(spin)
lin = max(abs(c) for c in wht)
nl = (1 << (n - 1)) - lin // 2
assert linearity_iv(tt).contains(float(lin))
assert nonlinearity_iv(tt).contains(float(nl))python -m pytest "packages/omnibias-boolean/tests/test_verified_spectra.py::test_linearity_nonlinearity_oracle" -qRegression example · bent function certificates
This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_bent_function_certificates() -> None:
# Bent on n=4: linearity 4, nonlinearity 6, perfect (zero) autocorrelation.
assert linearity_iv(BENT4).contains(4.0)
assert nonlinearity_iv(BENT4).contains(6.0)
ai = absolute_indicator_iv(BENT4)
assert ai.contains(0.0)
assert ai.hi < 1e-9 # near-zero up to defensive outward rounding
# every nonzero linear bias has magnitude exactly 1/8 = 4 / 2^(4+1).
assert max_linear_bias_iv(BENT4).contains(0.125)python -m pytest packages/omnibias-boolean/tests/test_verified_spectra.py -k test_bent_function_certificates -qRead the implementation
def nonlinearity_iv(
table: TruthTable | None = None, *, values: Sequence[IntervalLike] | None = None
) -> Interval:
"""Enclosure of the nonlinearity ``NL(f) = 2^{n-1} - L(f)/2``."""
vals, n = _pm1_values_iv(table, values, "pm1")
lin = linearity_iv(values=vals)
half = Interval.point(0.5)
return Interval.point(float(1 << (n - 1))) - lin * halfparseval_defect_iv
omnibias.boolean.parseval_defect_ivSource ↗parseval_defect_iv(table: TruthTable) -> IntervalEnclosure of sum_S hat f(S)^2 - 1 (contains 0 for any Boolean f).
Parameters
| Name | Type & default | Contract |
|---|---|---|
tablepositional-or-keyword | TruthTableRequired | See the operation contract and implementation below. |
IntervalExecuted regression · parseval defect contains zero
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_parseval_defect_contains_zero() -> None:
rng = random.Random(6)
for n in (1, 2, 3, 4):
for _ in range(20):
tt = _rand_table(rng, n)
assert parseval_defect_iv(tt).contains(0.0)python -m pytest "packages/omnibias-boolean/tests/test_verified_spectra.py::test_parseval_defect_contains_zero" -qRead the implementation
def parseval_defect_iv(table: TruthTable) -> Interval:
"""Enclosure of ``sum_S hat f(S)^2 - 1`` (contains ``0`` for any Boolean ``f``)."""
coeffs = fourier_coeffs_iv(table, encoding="pm1")
acc = Interval.point(0.0)
for c in coeffs:
acc = acc + c * c
return acc - Interval.point(1.0)walsh_at_iv
omnibias.boolean.walsh_at_ivSource ↗walsh_at_iv(table: TruthTable | None=None, mask: int=0, *, values: Sequence[IntervalLike] | None=None) -> IntervalEnclosure of the unnormalised Walsh coefficient (WHT s)(mask) (spin).
Parameters
| Name | Type & default | Contract |
|---|---|---|
tablepositional-or-keyword | TruthTable | NoneDefault: None | See the operation contract and implementation below. |
maskpositional-or-keyword | intDefault: 0 | See the operation contract and implementation below. |
valueskeyword-only | Sequence[IntervalLike] | NoneDefault: None | See the operation contract and implementation below. |
IntervalExplicit validation & failure cases
- When
not 0 <= mask < len(vals), raisesValueError(f'mask {mask} out of range for length {len(vals)}').
These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.
Executed regression · xor linear bias is extremal
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_xor_linear_bias_is_extremal() -> None:
# XOR equals chi_{0,1}, so the linear approximation by mask {0,1} = 0b11 is
# exact: f(x) == <mask, x> for every x, giving the extremal bias +1/2.
b = linear_bias_iv(XOR, 0b11)
assert b.contains(0.5)
# and the best linear bias over all nonzero masks is 1/2.
assert max_linear_bias_iv(XOR).contains(0.5)python -m pytest "packages/omnibias-boolean/tests/test_verified_spectra.py::test_xor_linear_bias_is_extremal" -qRead the implementation
def walsh_at_iv(
table: TruthTable | None = None,
mask: int = 0,
*,
values: Sequence[IntervalLike] | None = None,
) -> Interval:
"""Enclosure of the unnormalised Walsh coefficient ``(WHT s)(mask)`` (spin)."""
vals, _ = _pm1_values_iv(table, values, "pm1")
if not 0 <= mask < len(vals):
raise ValueError(f"mask {mask} out of range for length {len(vals)}")
return walsh_hadamard_iv(vals)[mask]walsh_hadamard_iv
omnibias.boolean.walsh_hadamard_ivSource ↗walsh_hadamard_iv(values: Sequence[IntervalLike]) -> list[Interval]Outward-rounded fast Walsh-Hadamard transform (unnormalised).
Twin of omnibias.boolean._core.walsh.walsh_hadamard; every
sum/difference is an interval operation, so result[k] encloses
sum_x (-1)^{<k,x>} values[x] for every realisation inside the inputs.
Parameters
| Name | Type & default | Contract |
|---|---|---|
valuespositional-or-keyword | Sequence[IntervalLike]Required | See the operation contract and implementation below. |
list[Interval]Executed regression · parseval defect contains zero
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_parseval_defect_contains_zero() -> None:
rng = random.Random(6)
for n in (1, 2, 3, 4):
for _ in range(20):
tt = _rand_table(rng, n)
assert parseval_defect_iv(tt).contains(0.0)python -m pytest "packages/omnibias-boolean/tests/test_verified_spectra.py::test_parseval_defect_contains_zero" -qRegression example · wht iv contains float core
This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_wht_iv_contains_float_core() -> None:
rng = random.Random(0)
for n in (1, 2, 3, 4):
for _ in range(20):
tt = _rand_table(rng, n)
spin = [float(1 - 2 * v) for v in tt]
iv = walsh_hadamard_iv(spin)
fl = walsh_hadamard(spin)
for a, b in zip(iv, fl, strict=True):
assert a.contains(b)python -m pytest packages/omnibias-boolean/tests/test_verified_spectra.py -k test_wht_iv_contains_float_core -qRead the implementation
def walsh_hadamard_iv(values: Sequence[IntervalLike]) -> list[Interval]:
"""Outward-rounded fast Walsh-Hadamard transform (unnormalised).
Twin of :func:`omnibias.boolean._core.walsh.walsh_hadamard`; every
sum/difference is an interval operation, so ``result[k]`` encloses
``sum_x (-1)^{<k,x>} values[x]`` for every realisation inside the inputs.
"""
a = [Interval.from_value(v) for v in values]
size = len(a)
_check_pow2(size)
step = 1
while step < size:
for i in range(0, size, step << 1):
for j in range(i, i + step):
u = a[j]
v = a[j + step]
a[j] = u + v
a[j + step] = u - v
step <<= 1
return awalsh_spectrum_iv
omnibias.boolean.walsh_spectrum_ivSource ↗walsh_spectrum_iv(table: TruthTable, encoding: str='pm1') -> dict[frozenset[int], Interval]Interval Fourier coefficients as a {variable-set: enclosure} mapping.
Parameters
| Name | Type & default | Contract |
|---|---|---|
tablepositional-or-keyword | TruthTableRequired | See the operation contract and implementation below. |
encodingpositional-or-keyword | strDefault: 'pm1' | See the operation contract and implementation below. |
dict[frozenset[int], Interval]Executed regression · walsh spectrum iv keys match float
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_walsh_spectrum_iv_keys_match_float() -> None:
spec_iv = walsh_spectrum_iv(AND, encoding="pm1")
spec_fl = fourier_coeffs(AND, encoding="pm1")
# mapping is keyed by variable subset; spot-check the empty set = mean.
assert spec_iv[frozenset()].contains(spec_fl[0])python -m pytest "packages/omnibias-boolean/tests/test_verified_spectra.py::test_walsh_spectrum_iv_keys_match_float" -qRead the implementation
def walsh_spectrum_iv(
table: TruthTable, encoding: str = "pm1"
) -> dict[frozenset[int], Interval]:
"""Interval Fourier coefficients as a ``{variable-set: enclosure}`` mapping."""
n = num_vars(table)
coeffs = fourier_coeffs_iv(table, encoding=encoding)
return {
frozenset(j for j in range(n) if (mask >> j) & 1): c
for mask, c in enumerate(coeffs)
}fourier_coeffs
omnibias.boolean.fourier_coeffsSource ↗fourier_coeffs(table: TruthTable, encoding: str='pm1') -> tuple[float, ...]Fourier coefficients hat f(S) indexed by subset bitmask.
encoding="pm1" maps the output to {+1, -1} (f = 1 - 2b, the usual
convention for which Parseval gives sum_S hat f(S)^2 = 1); encoding="01"
keeps the {0, 1} output.
Parameters
| Name | Type & default | Contract |
|---|---|---|
tablepositional-or-keyword | TruthTableRequired | See the operation contract and implementation below. |
encodingpositional-or-keyword | strDefault: 'pm1' | See the operation contract and implementation below. |
tuple[float, ...]Executed regression · parseval
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_parseval() -> None:
rng = random.Random(1)
for n in (1, 2, 3, 4):
for _ in range(15):
tt = tuple(rng.randint(0, 1) for _ in range(1 << n))
assert parseval_defect(tt) < 1e-9python -m pytest "packages/omnibias-boolean/tests/test_walsh.py::test_parseval" -qRegression example · fourier coeffs indexing
This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_fourier_coeffs_indexing() -> None:
coeffs = fourier_coeffs(AND, encoding="pm1")
assert len(coeffs) == 4
# E[f] for +/-1 AND = mean of (1,1,1,-1) = 0.5.
assert math.isclose(coeffs[0], 0.5, abs_tol=1e-12)python -m pytest packages/omnibias-boolean/tests/test_walsh.py -k test_fourier_coeffs_indexing -qRead the implementation
def fourier_coeffs(table: TruthTable, encoding: str = "pm1") -> tuple[float, ...]:
"""Fourier coefficients ``hat f(S)`` indexed by subset bitmask.
``encoding="pm1"`` maps the output to ``{+1, -1}`` (``f = 1 - 2b``, the usual
convention for which Parseval gives ``sum_S hat f(S)^2 = 1``); ``encoding="01"``
keeps the ``{0, 1}`` output.
"""
check_truth_table(table)
n = num_vars(table)
if encoding == "pm1":
vals = [float(1 - 2 * v) for v in table]
elif encoding == "01":
vals = [float(v) for v in table]
else:
raise ValueError(f"encoding must be 'pm1' or '01', got {encoding!r}")
wht = walsh_hadamard(vals)
scale = 1.0 / (1 << n)
return tuple(c * scale for c in wht)fourier_influences
omnibias.boolean.fourier_influencesSource ↗fourier_influences(table: TruthTable) -> list[float]Influence via the Fourier weight Inf_i = sum_{S in i} hat f(S)^2.
Equal to influences for a {+1,-1}-valued function (cross-checked in
the tests).
Parameters
| Name | Type & default | Contract |
|---|---|---|
tablepositional-or-keyword | TruthTableRequired | See the operation contract and implementation below. |
list[float]Executed regression · influence definitions agree
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_influence_definitions_agree() -> None:
rng = random.Random(2)
for n in (1, 2, 3, 4):
for _ in range(15):
tt = tuple(rng.randint(0, 1) for _ in range(1 << n))
comb = influences(tt)
four = fourier_influences(tt)
assert all(math.isclose(a, b, abs_tol=1e-9) for a, b in zip(comb, four, strict=False))python -m pytest "packages/omnibias-boolean/tests/test_walsh.py::test_influence_definitions_agree" -qRead the implementation
def fourier_influences(table: TruthTable) -> list[float]:
"""Influence via the Fourier weight ``Inf_i = sum_{S in i} hat f(S)^2``.
Equal to :func:`influences` for a ``{+1,-1}``-valued function (cross-checked in
the tests).
"""
n = num_vars(table)
coeffs = fourier_coeffs(table, encoding="pm1")
out = [0.0] * n
for mask, c in enumerate(coeffs):
for i in range(n):
if (mask >> i) & 1:
out[i] += c * c
return outinfluences
omnibias.boolean.influencesSource ↗influences(table: TruthTable) -> list[float]Combinatorial influence Inf_i = Pr_x[f(x) != f(x ^ e_i)] per coordinate.
Parameters
| Name | Type & default | Contract |
|---|---|---|
tablepositional-or-keyword | TruthTableRequired | See the operation contract and implementation below. |
list[float]Executed regression · and total influence
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_and_total_influence() -> None:
# AND on 2 bits: each input flips the output on 1 of 2 settings of the other.
assert math.isclose(total_influence(AND), 1.0, abs_tol=1e-12)python -m pytest "packages/omnibias-boolean/tests/test_walsh.py::test_and_total_influence" -qRegression example · dictator influences
This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_dictator_influences() -> None:
inf = influences(DICTATOR)
assert math.isclose(inf[0], 1.0, abs_tol=1e-12)
assert math.isclose(inf[1], 0.0, abs_tol=1e-12)
assert math.isclose(inf[2], 0.0, abs_tol=1e-12)python -m pytest packages/omnibias-boolean/tests/test_walsh.py -k test_dictator_influences -qRead the implementation
def influences(table: TruthTable) -> list[float]:
"""Combinatorial influence ``Inf_i = Pr_x[f(x) != f(x ^ e_i)]`` per coordinate."""
check_truth_table(table)
n = num_vars(table)
size = 1 << n
out: list[float] = []
for i in range(n):
bit = 1 << i
diff_pairs = 0
for x in range(size):
if (x & bit) == 0 and table[x] != table[x | bit]:
diff_pairs += 1
out.append(diff_pairs / (size >> 1))
return outparseval_defect
omnibias.boolean.parseval_defectSource ↗parseval_defect(table: TruthTable) -> float|sum_S hat f(S)^2 - 1| for the {+1,-1} encoding (zero up to rounding).
Parameters
| Name | Type & default | Contract |
|---|---|---|
tablepositional-or-keyword | TruthTableRequired | See the operation contract and implementation below. |
floatExecuted regression · parseval
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_parseval() -> None:
rng = random.Random(1)
for n in (1, 2, 3, 4):
for _ in range(15):
tt = tuple(rng.randint(0, 1) for _ in range(1 << n))
assert parseval_defect(tt) < 1e-9python -m pytest "packages/omnibias-boolean/tests/test_walsh.py::test_parseval" -qRead the implementation
def parseval_defect(table: TruthTable) -> float:
"""``|sum_S hat f(S)^2 - 1|`` for the ``{+1,-1}`` encoding (zero up to rounding)."""
coeffs = fourier_coeffs(table, encoding="pm1")
return abs(sum(c * c for c in coeffs) - 1.0)total_influence
omnibias.boolean.total_influenceSource ↗total_influence(table: TruthTable) -> floatTotal influence I(f) = sum_i Inf_i (average sensitivity).
Parameters
| Name | Type & default | Contract |
|---|---|---|
tablepositional-or-keyword | TruthTableRequired | See the operation contract and implementation below. |
floatExecuted regression · and total influence
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_and_total_influence() -> None:
# AND on 2 bits: each input flips the output on 1 of 2 settings of the other.
assert math.isclose(total_influence(AND), 1.0, abs_tol=1e-12)python -m pytest "packages/omnibias-boolean/tests/test_walsh.py::test_and_total_influence" -qRead the implementation
def total_influence(table: TruthTable) -> float:
"""Total influence ``I(f) = sum_i Inf_i`` (average sensitivity)."""
return sum(influences(table))walsh_hadamard
omnibias.boolean.walsh_hadamardSource ↗walsh_hadamard(values: Sequence[float]) -> list[float]Unnormalized fast Walsh-Hadamard transform of a power-of-two-length array.
Returns W with W[k] = sum_x (-1)^{<k, x>} values[x] where <k, x> is
the bitwise dot product (parity of k & x).
Parameters
| Name | Type & default | Contract |
|---|---|---|
valuespositional-or-keyword | Sequence[float]Required | See the operation contract and implementation below. |
list[float]Explicit validation & failure cases
- When
not is_power_of_two(size), raisesValueError(f'values length must be a power of two, got {size}').
These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.
Executed regression · parseval
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_parseval() -> None:
rng = random.Random(1)
for n in (1, 2, 3, 4):
for _ in range(15):
tt = tuple(rng.randint(0, 1) for _ in range(1 << n))
assert parseval_defect(tt) < 1e-9python -m pytest "packages/omnibias-boolean/tests/test_walsh.py::test_parseval" -qRegression example · wht iv contains float core
This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_wht_iv_contains_float_core() -> None:
rng = random.Random(0)
for n in (1, 2, 3, 4):
for _ in range(20):
tt = _rand_table(rng, n)
spin = [float(1 - 2 * v) for v in tt]
iv = walsh_hadamard_iv(spin)
fl = walsh_hadamard(spin)
for a, b in zip(iv, fl, strict=True):
assert a.contains(b)python -m pytest packages/omnibias-boolean/tests/test_verified_spectra.py -k test_wht_iv_contains_float_core -qRead the implementation
def walsh_hadamard(values: Sequence[float]) -> list[float]:
"""Unnormalized fast Walsh-Hadamard transform of a power-of-two-length array.
Returns ``W`` with ``W[k] = sum_x (-1)^{<k, x>} values[x]`` where ``<k, x>`` is
the bitwise dot product (parity of ``k & x``).
"""
a = [float(v) for v in values]
size = len(a)
if not is_power_of_two(size):
raise ValueError(f"values length must be a power of two, got {size}")
step = 1
while step < size:
for i in range(0, size, step << 1):
for j in range(i, i + step):
u = a[j]
v = a[j + step]
a[j] = u + v
a[j + step] = u - v
step <<= 1
return awalsh_spectrum
omnibias.boolean.walsh_spectrumSource ↗walsh_spectrum(table: TruthTable, encoding: str='pm1') -> dict[frozenset[int], float]Fourier coefficients as a {variable-set: hat f(S)} mapping.
Parameters
| Name | Type & default | Contract |
|---|---|---|
tablepositional-or-keyword | TruthTableRequired | See the operation contract and implementation below. |
encodingpositional-or-keyword | strDefault: 'pm1' | See the operation contract and implementation below. |
dict[frozenset[int], float]Executed regression · xor is pure high frequency
Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.
def test_xor_is_pure_high_frequency() -> None:
# x0 ^ x1 in +/-1 output == chi_{0,1} exactly, so hat f({0,1}) = +1.
spec = walsh_spectrum(XOR)
assert math.isclose(spec[frozenset({0, 1})], 1.0, abs_tol=1e-12)
for s, c in spec.items():
if s != frozenset({0, 1}):
assert abs(c) < 1e-12python -m pytest "packages/omnibias-boolean/tests/test_walsh.py::test_xor_is_pure_high_frequency" -qRead the implementation
def walsh_spectrum(table: TruthTable, encoding: str = "pm1") -> dict[frozenset[int], float]:
"""Fourier coefficients as a ``{variable-set: hat f(S)}`` mapping."""
n = num_vars(table)
coeffs = fourier_coeffs(table, encoding=encoding)
return {
frozenset(j for j in range(n) if (mask >> j) & 1): c
for mask, c in enumerate(coeffs)
}