nx_binomial.nx source
↩ module page · 30 lines · 935 B
1// nx_binomial.nx -- C(n, k) iterative, overflow-safe.
2//
3// genealogy_id: pascal_1654_triangle
4// lineage_id: combinatorics
5// license: public_domain
6// complexity: O(min(k, n-k))
7
8// nx_safety_envelope:
9// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
10// sil_target: SIL1
11// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
12// verdict: NOT_YET_EVALUATED
13
14import "nx_syscalls.nx"
15import "nx_tier.nx"
16
17// Choose-k from n. Returns 0 for invalid (negative, k > n) and overflow.
18func nx_binomial(n: nx_int, k: nx_int) -> nx_int {
19 if k < 0 { return 0 }
20 if k > n { return 0 }
21 var kk: nx_int = k
22 if kk > n - kk { kk = n - kk } // symmetry: C(n,k) = C(n, n-k)
23 var result: nx_int = 1
24 var i: nx_int = 1
25 while i <= kk {
26 result = result * (n - kk + i) / i
27 i = i + 1
28 }
29 return result
30}