Fibonacci — iterative, and the closed-form Binet approximation
The iterative version carries the last two terms in two variables. Binet's formula F(n) = (phi^n − psi^n)/√5 gives a closed form; we round it back to the exact integer for small n. Both agree, which the tests cross-check.
A Soma program from the math part of the verified corpus: 66 lines, cells Fibonacci, FibTests. It passes soma check with soma 3.2.4.
How it is built
The cell Fibonacci declares 4 signals in its face: fib(n: Int) -> Int, binet(n: Int) -> Int, fib_list(n: Int) -> List and run() -> Map. Handlers: fib (line 20), binet (line 32), fib_list (line 38) and run (line 44).
The file also holds 1 test cell (FibTests) with 7 assertions, run by soma test.
The source
fibonacci.cell
// ============================================================================
// Fibonacci — iterative, and the closed-form Binet approximation
// ============================================================================
//
// The iterative version carries the last two terms in two variables. Binet's
// formula F(n) = (phi^n − psi^n)/√5 gives a closed form; we round it back to
// the exact integer for small n. Both agree, which the tests cross-check.
//
// soma run fibonacci.cell run
// ============================================================================
cell Fibonacci {
face {
signal fib(n: Int) -> Int
signal binet(n: Int) -> Int
signal fib_list(n: Int) -> List
signal run() -> Map
}
on fib(n: Int) {
if n < 2 { return n }
let a = 0
let b = 1
for i in range(2, n + 1) {
let next = a + b
a = b
b = next
}
return b
}
on binet(n: Int) {
let phi = (1.0 + sqrt(5.0)) / 2.0
let psi = (1.0 - sqrt(5.0)) / 2.0
return round((pow(phi, n) - pow(psi, n)) / sqrt(5.0))
}
on fib_list(n: Int) {
let xs = []
for i in range(0, n) { xs = push(xs, fib(i)) }
return xs
}
on run() {
return map(
"fib_10", fib(10),
"binet_10", binet(10),
"first_8", fib_list(8)
)
}
}
cell test FibTests {
rules {
assert fib(0) == 0
assert fib(1) == 1
assert fib(10) == 55
assert fib(20) == 6765
// Binet's closed form agrees with the recurrence
assert binet(10) == 55
assert binet(15) == 610
// the list of the first eight Fibonacci numbers sums to 33
assert sum(fib_list(8)) == 33
}
}What the toolchain says
$ soma check fibonacci.cell
✓ All checks passed.$ soma test fibonacci.cell
test FibTests ...
✓ assert fib(0) == 0
✓ assert fib(1) == 1
✓ assert fib(10) == 55
✓ assert fib(20) == 6765
✓ assert binet(10) == 55
✓ assert binet(15) == 610
✓ assert sum(fib_list(8)) == 33
7 tests: 7 passed, 0 failed$ soma verify fibonacci.cell
Verifying fibonacci.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 fibonacci.cell run
{"fib_10": 55, "binet_10": 55, "first_8": [0, 1, 1, 2, 3, 5, 8, 13]}