This repository exists to learn catalytic computing by implementing its algorithms in Kotlin. Catalytic algorithms borrow a memory region whose initial contents are arbitrary: they may use those values during a computation, but must restore them exactly. Here, each construction is executable and tested from dirty initial registers against an independent conventional result where one is useful.
The historical
lemma_1_boolean_circuit.main.kts
was the first implementation of Lemma 1 and is the only non-AI-assisted code in
the repository. The production implementation grew from that starting point.
This is an educational companion to the papers, not a proof assistant. Deterministic and exhaustive tests validate finite algebraic and restoration invariants; they do not formally verify asymptotic complexity-class claims.
- Ian Mertz, Reusing Space: Techniques and Open Problems, with the repository's Mertz implementation notes.
- James Cook and Edward Pyne, Efficient Catalytic Graph Algorithms, with the repository's Cook–Pyne source authority and roadmap.
Given an input/NOT/AND circuit, the evaluator XORs its output into any one of three borrowed Boolean registers and restores the other two. For an AND gate, four products across toggled scratch states cancel every dirty term except the product of the two child values. Mertz Exercise 1 is represented by exhaustive tests of every destination and initial three-bit state, including the self-inverse round trip.
Minimal use:
val c = circuit {
val x0 = input(0)
val x1 = input(1)
x0 and not(x1)
}
val evaluator = LemmaOneEvaluator(c, booleanArrayOf(true, false),
booleanArrayOf(true, false, true))
evaluator.computeOutputInto(destination = 1)
check(evaluator.registers.contentEquals(booleanArrayOf(true, true, true)))Core implementation excerpt (abridged; … marks omitted code;
full source):
// …
repeat(2) {
computeInto(gate.left, leftRegister)
xorProductInto(destination, leftRegister, rightRegister)
computeInto(gate.right, rightRegister)
xorProductInto(destination, leftRegister, rightRegister)
}
// …Input/add/multiply circuits are evaluated over a generic ring. The multiplication construction adds and removes each child in two scratch registers; four signed products leave only the ordered product in the target, so the same three registers work even for noncommutative rings. The implementation provides a direct evaluator, a reversible instruction compiler, and exact finite-ring branching-program bounds without materializing the exponential graph.
Minimal use:
val ring = ModularIntegerRing(4)
val c = arithmeticCircuit {
val x0 = input(0)
val x1 = input(1)
x0 * (x0 + x1)
}
val program = c.toRegisterProgram()
val before = listOf(1, 2, 3)
val after = program.execute(ring, listOf(3, 2), before)
check(after == listOf(0, 2, 3))
check(program.inverse().execute(ring, listOf(3, 2), after) == before)Core implementation from the
direct evaluator
(abridged; … marks omitted code):
// …
computeInto(gate.left, leftRegister, UpdateSign.PLUS)
updateWithProduct(destination, leftRegister, rightRegister, sign.inverse())
computeInto(gate.right, rightRegister, UpdateSign.PLUS)
updateWithProduct(destination, leftRegister, rightRegister, sign)
computeInto(gate.left, leftRegister, UpdateSign.MINUS)
updateWithProduct(destination, leftRegister, rightRegister, sign.inverse())
computeInto(gate.right, rightRegister, UpdateSign.MINUS)
updateWithProduct(destination, leftRegister, rightRegister, sign)
// …Each input is treated as the output of another clean Boolean program. The balanced construction recursively reuses the Lemma 1 product cancellation with three registers; the subset expansion toggles every subset of one borrowed register per input so all dirty monomials cancel except the full conjunction. Both variants have direct evaluators, reversible programs, and exact resource counters.
Minimal use:
val program = compileExerciseThreeProgram(
inputCount = 3,
construction = ExerciseThreeConstruction.SUBSET_EXPANSION,
)
val before = listOf(true, false, true, false)
val after = program.execute(BooleanRing, listOf(true, true, true), before)
check(after == listOf(false, false, true, false))
check(program.inverse().execute(BooleanRing, listOf(true, true, true), after) == before)
val balanced = compileExerciseThreeProgram(
inputCount = 3,
construction = ExerciseThreeConstruction.BALANCED_TREE,
)
val balancedBefore = listOf(true, false, true)
val balancedAfter =
balanced.execute(BooleanRing, listOf(true, true, true), balancedBefore)
check(balancedAfter == listOf(false, false, true))
check(
balanced.inverse()
.execute(BooleanRing, listOf(true, true, true), balancedAfter) == balancedBefore,
)Core implementation from the
direct evaluator
(abridged; … marks omitted code):
// …
// Balanced tree
repeat(2) {
computeBalancedRange(start, middle, leftRegister)
xorProductInto(destination, leftRegister, rightRegister)
computeBalancedRange(middle, end, rightRegister)
xorProductInto(destination, leftRegister, rightRegister)
}
// …
// Subset expansion
forEachSubset(input.size) { selectedInputs ->
selectedInputs.forEach(::callInputProgram)
memory[TARGET_REGISTER] =
memory[TARGET_REGISTER] xor (1 until memory.size).all(memory::get)
selectedInputs.asReversed().forEach(::callInputProgram)
}
// …Exercise 4 adds any nonempty collection of clean-program values over a generic ring. It calls the input programs into borrowed source registers, updates the target with their sum, uncomputes the sources, and repeats the target update with the opposite sign so the sources' unknown initial values cancel.
Minimal use:
val ring = ModularIntegerRing(5)
val program = compileExerciseFourProgram(inputCount = 3)
val before = listOf(1, 3, 0, 2)
val after = program.execute(ring, listOf(2, 4, 3), before)
check(after == listOf(0, 3, 0, 2))
check(program.inverse().execute(ring, listOf(2, 4, 3), after) == before)Core implementation excerpt (abridged; … marks omitted code;
full source):
// …
fun computeSumInto(): Unit {
for (inputIndex in input.indices) {
callInputProgram(inputIndex, UpdateSign.PLUS)
}
updateTargetWithSources(UpdateSign.PLUS)
for (inputIndex in input.indices.reversed()) {
callInputProgram(inputIndex, UpdateSign.MINUS)
}
updateTargetWithSources(UpdateSign.MINUS)
}
// …
private fun updateTargetWithSources(sign: UpdateSign) {
var sum = ring.zero
for (sourceRegister in 1 until memory.size) {
sum = ring.add(sum, memory[sourceRegister])
}
updateRegister(TARGET_REGISTER, sum, sign)
}
// …For a nonnegative exponent, the evaluator uses the paper's binomial expansion
to add v^k to a target over a commutative unital ring, including v^0 = 1.
Auxiliary power registers may start dirty; paired polynomial updates cancel
their initial values and the inverse restores the whole register file.
Minimal use:
val ring = ModularIntegerRing(5)
val program = compileExerciseFiveProgram(exponent = 4)
val before = List(program.registerCount) { ring.zero }
val after = program.execute(ring, listOf(3), before)
check(after[0] == 1) // 3^4 mod 5
check(after.drop(1) == before.drop(1))
check(program.inverse().execute(ring, listOf(3), after) == before)Core implementation excerpt (abridged; … marks omitted code;
full source):
// …
fun computePowerInto(): Unit {
callValueProgram(UpdateSign.MINUS)
updateAuxiliaryPowers(UpdateSign.PLUS)
callValueProgram(UpdateSign.PLUS)
updateTargetWithBinomial(UpdateSign.PLUS)
callValueProgram(UpdateSign.MINUS)
updateAuxiliaryPowers(UpdateSign.MINUS)
callValueProgram(UpdateSign.PLUS)
updateTargetWithBinomial(UpdateSign.MINUS)
}
// …
private fun updateTargetWithBinomial(sign: UpdateSign) {
var polynomial = ring.zero
for (valuePower in 0..exponent) {
val auxiliaryPower = exponent - valuePower
val product =
ring.multiply(
ring.power(memory[VALUE_REGISTER], valuePower),
memory[AUXILIARY_REGISTER_START + auxiliaryPower],
)
val coefficientSign = if (auxiliaryPower % 2 == 0) 1 else -1
val coefficient = coefficients[valuePower].multiply(BigInteger.valueOf(coefficientSign.toLong()))
polynomial = ring.add(polynomial, scaleByInteger(product, coefficient))
}
updateRegister(TARGET_REGISTER, polynomial, sign)
}
// …For m Boolean inputs, the implementation selects the smallest prime p > m
and composes Exercises 4 and 5 to evaluate
1 - (targetWeight - sum(inputs))^(p - 1) in F_p. Fermat's little theorem
makes this one exactly at the requested Hamming weight. A typed wrapper fixes
the field, while the direct and compiled paths restore arbitrary non-target
field registers.
Minimal use:
val program = compileLemmaThreeProgram(inputCount = 3, targetWeight = 2)
val before = List(program.registerCount) { program.field.zero }
val after = program.execute(listOf(true, false, true), before)
check(program.field.characteristic == 5)
check(after[0] == program.field.one)
check(program.inverse().execute(listOf(true, false, true), after) == before)Core implementation excerpt (abridged; … marks omitted code;
full source):
// …
val field: PrimeIntegerField = PrimeIntegerField(layout.fieldCharacteristic)
// …
private val exactWeightKernel: ExactWeightKernel =
ExactWeightKernel(
field = field,
memory = memory,
inputCount = input.size,
targetWeight = targetWeight,
targetRegister = TARGET_REGISTER,
sumRegister = SUM_REGISTER,
auxiliaryRegisterStart = AUXILIARY_REGISTER_START,
inputRegisterStart = layout.inputRegisterStart,
callInputProgram = ::callInputProgram,
)
// …
fun computeIndicatorInto(): Unit = exactWeightKernel.compute(UpdateSign.PLUS)
// …
fun subtractIndicatorFrom(): Unit = exactWeightKernel.compute(UpdateSign.MINUS)
private fun callInputProgram(
inputIndex: Int,
targetRegister: Int,
sign: UpdateSign,
) {
val update = if (input[inputIndex]) field.one else field.zero
val signedUpdate = if (sign == UpdateSign.PLUS) update else field.negate(update)
memory[targetRegister] = field.add(memory[targetRegister], signedUpdate)
}
// …A Boolean Möbius transform interpolates a truth table into its unique
multilinear polynomial over F2. Four subset-product cancellation rounds then
XOR that function into the target while restoring an exponential borrowed
register file. The
direct evaluator
avoids materializing the compiled program's potentially 3^n polynomial
payload.
Minimal use:
// x0 OR x1; x0 is the least-significant truth-table bit.
val polynomial = interpolateBooleanPolynomial(
booleanArrayOf(false, true, true, true),
)
val evaluator = ExerciseSevenEvaluator(polynomial, booleanArrayOf(true, false))
evaluator.computeFunctionInto()
check(evaluator.registers[0])
check(evaluator.registers.drop(1).all { !it })Core interpolation excerpt (abridged; … marks omitted code;
full source):
// …
for (variable in 0 until inputCount) {
val variableBit = 1 shl variable
for (subsetMask in coefficients.indices) {
if (subsetMask and variableBit != 0) {
coefficients[subsetMask] =
coefficients[subsetMask] xor coefficients[subsetMask xor variableBit]
}
}
}
// …Core catalytic-cancellation excerpt (abridged; … marks omitted code;
full source):
// …
updateSubsetProducts(layout.tauSubsetRegisterStart)
updateTargetWithSubstitutedPolynomial()
callInputPrograms()
updateSubsetProducts(layout.ySubsetRegisterStart)
updateTargetWithSubstitutedPolynomial()
callInputPrograms()
updateSubsetProducts(layout.tauSubsetRegisterStart)
updateTargetWithSubstitutedPolynomial()
callInputPrograms()
updateSubsetProducts(layout.ySubsetRegisterStart)
updateTargetWithSubstitutedPolynomial()
callInputPrograms()
// …The problem is to decide whether a validated undirected tree has diameter at least a threshold. A conventional two-sweep BFS provides an exact witness. The original catalytic case study recursively reads entries of a Boolean reachability matrix and composes clean AND, OR, and exact-weight gates; it uses few field registers but recomputes shared predicates. Its explicitly named memoized mode uses ordinary host memory and is not part of the catalytic bound.
A second Cook–Pyne edge-push implementation turns each tree path into a unique nonbacktracking path, applies the layered path-count kernel, and combines all source/target answers with clean ORs. It uses more catalytic registers but gives faithful polynomial-time execution. Both catalytic programs add the threshold indicator to register zero and restore every other arbitrary field register.
Minimal comparison:
val tree = UndirectedTree.of(2, listOf(UndirectedEdge(0, 1)))
check(twoSweepTreeDiameter(tree) == TreeDiameterWitness(1, 0, 1))
val matrixProgram = compileExerciseEightProgram(vertexCount = 2, threshold = 1)
val matrixAfter = matrixProgram.execute(tree)
check(matrixAfter[0] == matrixProgram.field.one)
check(matrixProgram.inverse().execute(tree, matrixAfter).all { it == 0 })
check(matrixProgram.executeMemoized(tree) == matrixAfter)
val edgePushProgram = compileEdgePushExerciseEightProgram(2, threshold = 1)
val edgePushAfter = edgePushProgram.execute(tree)
check(edgePushAfter[0] == edgePushProgram.field.one)
check(edgePushProgram.inverse().execute(tree, edgePushAfter).all { it == 0 })Core two-sweep excerpt (abridged; … marks omitted code;
full source):
// …
val firstSweep = farthestVertex(tree, startVertex)
val secondSweep = farthestVertex(tree, firstSweep.vertex)
return TreeDiameterWitness(
firstEndpoint = firstSweep.vertex,
secondEndpoint = secondSweep.vertex,
length = secondSweep.distance,
)
// …Core Boolean-matrix excerpt (abridged; … marks omitted code;
full source):
// …
val leftBound = bound / 2
val rightBound = bound - leftBound
computeAny(
inputCount = tree.vertexCount,
destination = destination,
sign = sign,
frameStart = frameStart,
) { middle, childDestination, childSign, childFrame ->
computeProduct(
destination = childDestination,
sign = childSign,
frameStart = childFrame,
left = { leftDestination, leftSign, leftFrame ->
computeReachWithin(leftBound, from, middle, leftDestination, leftSign, leftFrame)
},
right = { rightDestination, rightSign, rightFrame ->
computeReachWithin(rightBound, middle, to, rightDestination, rightSign, rightFrame)
},
)
}
// …Core tree edge-push excerpt (abridged; … marks omitted code;
full source):
// …
kernel.push(field.zero)
updateRegister(destination, kernel.wordAt(threshold, graph.acceptVertex), sign.inverse())
kernel.reverse(field.zero)
kernel.push(field.one)
updateRegister(destination, kernel.wordAt(threshold, graph.acceptVertex), sign)
kernel.reverse(field.one)
// …Core host-memoization excerpt (abridged; … marks omitted code;
full source):
// …
val cachedValue = cache[cacheIndex]
if (cachedValue != UNKNOWN_CACHE_VALUE) {
memoization!!.recordHit()
applyCachedBoolean(destination, cachedValue, sign)
return
}
// …
val before = memory[destination]
body()
cache[cacheIndex] = observeBooleanDelta(before, memory[destination], sign)
// …A physical word is interpreted as a * q + b: the arbitrary quotient a is
borrowed data and only residue b participates in modular arithmetic. Each
update preserves the quotient, and subtracting the same residue restores the
exact word. The current edge-push evaluator requires initial words in complete
residue blocks.
Minimal use:
val layout = ModularRegisterLayout(bitWidth = 3, modulus = BigInteger.valueOf(3))
val dirtyWord = BigInteger.valueOf(5) // 1 * 3 + 2
val updated = layout.addResidue(dirtyWord, BigInteger.TWO)
check(updated == BigInteger.valueOf(4)) // 1 * 3 + 1
check(layout.quotient(updated) == layout.quotient(dirtyWord))
check(layout.addResidue(updated, BigInteger.TWO.negate()) == dirtyWord)Core implementation excerpt (abridged; … marks omitted code;
full source):
// …
val quotientPart = quotient(targetWord).multiply(modulus)
val updatedResidue = residue(targetWord).add(update).mod(modulus)
return quotientPart.add(updatedResidue)
// …For a directed graph, source, target, modulus, and exact walk length T, each
edge pushes a source residue into the corresponding register in the next time
layer. Running the sequence with source increments zero and one cancels the
unknown initial tape; their target difference is the number of length-T
paths modulo q. Reversing each sequence restores every physical register
word, including the quotient part preserved by the
modular layout.
Minimal use:
val graph = DirectedGraph.of(3,
listOf(DirectedEdge(0, 1), DirectedEdge(1, 2)))
val layout = ModularRegisterLayout(bitWidth = 2, modulus = BigInteger.valueOf(3))
val initial = List(9) { BigInteger.ZERO }
val evaluator = LayeredEdgePushEvaluator(graph, 0, 2, 2, layout, initial)
check(evaluator.computePathCountModulo() == BigInteger.ONE)
check(evaluator.registers == initial)Core implementation excerpt (abridged; … marks omitted code;
full source):
// …
val neighbor = requireInNeighbor(graph, nextVertex, nextNeighborIndex)
val sourceIndex = registerIndex(nextLayer, neighbor)
val targetIndex = registerIndex(nextLayer + 1, nextVertex)
if (phase == Phase.PUSHING) {
memory[targetIndex] =
arithmetic.addSource(memory[targetIndex], memory[sourceIndex])
// …
} else {
// …
memory[targetIndex] =
arithmetic.subtractSource(memory[targetIndex], memory[sourceIndex])
// …
}
// …Final restoration is not enough when the owner of borrowed memory needs a word during execution. At every modeled modular-update boundary, local recovery uses only the current word, the ordered incoming contributions already applied, and the traversal cursor to reconstruct that word's exact initial physical value without changing the tape or execution state.
Minimal stepwise check:
val graph = DirectedGraph.of(1, listOf(DirectedEdge(0, 0)))
val layout = ModularRegisterLayout(bitWidth = 2, modulus = BigInteger.valueOf(3))
val initial = listOf(BigInteger.TWO, BigInteger.ONE)
val evaluator = LayeredEdgePushEvaluator(graph, 0, 0, 1, layout, initial)
evaluator.beginPush(BigInteger.ONE)
while (evaluator.phase == LayeredEdgePushPhase.PUSHING) {
evaluator.advanceOneUpdate()
check(evaluator.recoverInitialWord(0, 0) == initial[0])
check(evaluator.recoverInitialWord(1, 0) == initial[1])
}
evaluator.reversePush()
check(evaluator.registers == initial)Core implementation excerpt (abridged; … marks omitted code;
full source):
// …
var recovered = kernel.wordAt(layer, vertex)
val appliedSourceCount = kernel.appliedIncomingSourceCount(layer, vertex)
if (layer > 0) {
for (neighborIndex in 0 until appliedSourceCount) {
val neighbor = requireInNeighbor(graph, vertex, neighborIndex)
recovered =
registerLayout.subtract(recovered, kernel.wordAt(layer - 1, neighbor))
}
}
if (layer == 0 && vertex == source && kernel.startIncrementPresent) {
recovered =
registerLayout.addResidue(recovered, checkNotNull(activeIncrement).negate())
}
return recovered
// …JDK 21 is the only prerequisite; use the checked-in Gradle Wrapper:
./gradlew test
./gradlew ktlintCheck
./gradlew run
./gradlew buildrun prints the complete truth table for x0 AND (x1 AND NOT x2) together
with the resulting three-register memory. The deterministic test suite is the
best guide to restoration edge cases and independent oracles.
For the optional containerized development environment, see the short entry point in the development-container guide.
Original repository code, including the historical starter script, is licensed under the Apache License 2.0. The linked papers are not repository code and remain under their authors' and publishers' terms; the Cook–Pyne source-authority notes record that paper's license. Generated Gradle Wrapper material retains its Apache-2.0 provenance, and its JAR contains the applicable license text.