nx_poly.nx source
↩ module page · 107 lines · 2900 B
1// nx_poly.nx -- polynomial operations over i64 coefficients.
2//
3// Polynomials stored as arrays: p[0] + p[1]*x + p[2]*x^2 + ... + p[deg]*x^deg.
4//
5// genealogy_id: descartes_geometrie_1637 + newton_arithmetica_universalis
6// lineage_id: algebra_distributivity + commutativity
7// axioms: NX_AX_ALG_DISTRIBUTIVITY, NX_AX_PEANO_PA5_INDUCTION
8
9// nx_safety_envelope:
10// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
11// sil_target: SIL1
12// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
13// verdict: NOT_YET_EVALUATED
14
15import "syscalls.nx"
16import "nx_axioms.nx"
17import "nx_i128.nx"
18
19// Evaluate polynomial at x via Horner's method.
20// p has degree deg (length = deg+1).
21func nx_poly_eval(p: *i64, deg: i64, x: i64) -> i64 {
22 if deg < 0 { return 0 }
23 var result: i64 = p[deg]
24 var i: i64 = deg - 1
25 while i >= 0 {
26 result = result * x + p[i]
27 i = i - 1
28 }
29 return result
30}
31
32// Derivative. out has degree deg-1 (length = deg).
33func nx_poly_derivative(p: *i64, deg: i64, out: *i64) -> i64 {
34 var i: i64 = 1
35 while i <= deg {
36 out[i - 1] = i * p[i]
37 i = i + 1
38 }
39 return deg - 1
40}
41
42// Multiplication. out has degree deg_a + deg_b.
43// Caller pre-allocates out with (deg_a + deg_b + 1) i64 slots.
44func nx_poly_mul(a: *i64, deg_a: i64, b: *i64, deg_b: i64, out: *i64) -> i64 {
45 let out_deg: i64 = deg_a + deg_b
46 var i: i64 = 0
47 while i <= out_deg {
48 out[i] = 0
49 i = i + 1
50 }
51 var ja: i64 = 0
52 while ja <= deg_a {
53 var jb: i64 = 0
54 while jb <= deg_b {
55 out[ja + jb] = out[ja + jb] + a[ja] * b[jb]
56 jb = jb + 1
57 }
58 ja = ja + 1
59 }
60 return out_deg
61}
62
63// Addition. out has degree max(deg_a, deg_b).
64func nx_poly_add(a: *i64, deg_a: i64, b: *i64, deg_b: i64, out: *i64) -> i64 {
65 var out_deg: i64 = deg_a
66 if deg_b > out_deg { out_deg = deg_b }
67 var i: i64 = 0
68 while i <= out_deg {
69 var av: i64 = 0
70 var bv: i64 = 0
71 if i <= deg_a { av = a[i] }
72 if i <= deg_b { bv = b[i] }
73 out[i] = av + bv
74 i = i + 1
75 }
76 return out_deg
77}
78
79// Scalar multiply in place.
80func nx_poly_scalar_mul(p: *i64, deg: i64, k: i64) -> i64 {
81 var i: i64 = 0
82 while i <= deg {
83 p[i] = p[i] * k
84 i = i + 1
85 }
86 return deg
87}
88
89// Faulhaber's formula application: returns sum_{k=1}^{n} k^p for given p.
90// We use a direct computation for verification; the closed form is
91// p+1 degree polynomial in n.
92func nx_poly_power_sum(n: i64, p: i64) -> i64 {
93 if n < 1 { return 0 }
94 var sum: i64 = 0
95 var k: i64 = 1
96 while k <= n {
97 var term: i64 = 1
98 var j: i64 = 0
99 while j < p {
100 term = term * k
101 j = j + 1
102 }
103 sum = sum + term
104 k = k + 1
105 }
106 return sum
107}