binomial_step
std.elementwise.binomial_step · Level L4One factor of the multiplicative formula for C(n, k): where i ≤ k, multiply by n − k + i and divide by i. The division is exact, since the running value is C(n − k + i − 1, i − 1). The body binomial runs.
(i, acc) → (i + 1, acc·(n − k + i)/i) while i ≤ k
Signature
binomial_step(i: i64[s], acc: i64[s], n: i64[s], k: i64[s]) → i64[s], i64[s]
Structure
The function as NOVA stores it: one box per input, operation and output, and arrows that carry values. A double border marks another library function this one runs — called once, or by Scan once per element; select it to open that function.
- input
- operation
- constant
- call
- output
Verification
- Signature proven by NOVA’s shape solver, for every size.
- Equal to the reference
where i <= k: i + 1, acc*(n - k + i) // iin exact rational arithmetic, on all 40 test cases. - All 284 int64 results are exact: the error is zero.
- Interpreter and NumPy backend return bit-identical results.
- At float32 too: the 40 test cases rounded to float32, and 40 of them exact, with zero error.
Accuracy in detail
- correctly rounded (the int64 nearest the exact value)
- 100%
- bit-equal to the NumPy formula in int64
- 100%
- largest error, in units in the last place
- 0
Identity
sha256:0aecbf3f56d71a9aaf5a243639bddac97a2aa119c8cf27b5d109d74f4931ffe6The semantic hash of the graph. It changes when the program changes, and never when only its documentation does.
Control handle
- Symbol
- Ω:std.elementwise.binomial_step · Ω:binomial_step
- Pins
sha256:32f7f2a09ea1374b6e53e5707796c4c1061bd9d844f4da703a6d3e3f0bee2982this graph alone- Evidence
sha256:f9077d489a387b9bc52e9ce0ded927be3f652a2067fa031d5918cad2091e2bdethe hash of its verification record- Needs
- no capability: a pure function
Through NOVA’s control layer, the symbol launches this function only while the program still matches what it pins: a change to this graph, or to any graph it reaches, needs a migration first.