Gcd / lcm — Euclid's algorithm and its consequences gcd() is a builtin (Euclid on absolute values)
lcm(a,b) = a*b / gcd(a,b). gcd_list folds the builtin across a whole list with reduce. Coprimality is just gcd == 1.
A Soma program from the math part of the verified corpus: 54 lines, cells GcdLcm, GcdTests. It passes soma check with soma 3.2.4.
How it is built
The cell GcdLcm declares 4 signals in its face: lcm(a: Int, b: Int) -> Int, gcd_list(xs: List) -> Int, coprime(a: Int, b: Int) -> Bool and run() -> Map. Handlers: lcm (line 20), gcd_list (line 24), coprime (line 28) and run (line 32).
The file also holds 1 test cell (GcdTests) with 7 assertions, run by soma test.
The source
gcd_lcm.cell
// ============================================================================
// GCD / LCM — Euclid's algorithm and its consequences
// ============================================================================
//
// gcd() is a builtin (Euclid on absolute values). lcm(a,b) = a*b / gcd(a,b).
// gcd_list folds the builtin across a whole list with reduce. Coprimality is
// just gcd == 1.
//
// soma run gcd_lcm.cell run
// ============================================================================
cell GcdLcm {
face {
signal lcm(a: Int, b: Int) -> Int
signal gcd_list(xs: List) -> Int
signal coprime(a: Int, b: Int) -> Bool
signal run() -> Map
}
on lcm(a: Int, b: Int) {
return idiv(a * b, gcd(a, b))
}
on gcd_list(xs: List) {
return xs |> reduce(0, p => gcd(p.acc, p.val))
}
on coprime(a: Int, b: Int) {
return gcd(a, b) == 1
}
on run() {
return map(
"gcd_48_36", gcd(48, 36),
"lcm_4_6", lcm(4, 6),
"gcd_list", gcd_list([24, 36, 60]),
"coprime_8_15", coprime(8, 15)
)
}
}
cell test GcdTests {
rules {
assert gcd(48, 36) == 12
assert gcd(17, 5) == 1
// reduce with seed 0: gcd(0, x) = x, so folding works
assert gcd_list([24, 36, 60]) == 12
assert lcm(4, 6) == 12
assert lcm(21, 6) == 42
assert coprime(8, 15)
assert coprime(8, 12) == false
}
}What the toolchain says
$ soma check gcd_lcm.cell
✓ All checks passed.$ soma test gcd_lcm.cell
test GcdTests ...
✓ assert gcd(48, 36) == 12
✓ assert gcd(17, 5) == 1
✓ assert gcd_list([24, 36, 60]) == 12
✓ assert lcm(4, 6) == 12
✓ assert lcm(21, 6) == 42
✓ assert coprime(8, 15)
✓ assert coprime(8, 12) == false
7 tests: 7 passed, 0 failed$ soma verify gcd_lcm.cell
Verifying gcd_lcm.cell...
No state machine in this program: nothing to prove beyond `soma check` (invariants and lifecycles are what verify proves).
VERIFY OK (vacuous — no state machine)$ soma run gcd_lcm.cell run
{"gcd_48_36": 12, "lcm_4_6": 12, "gcd_list": 12, "coprime_8_15": true}