Skip to main content

qualia_core_db/specialized_libs/
symbolic_algebra.rs

1//! Symbolic algebra — a small computer-algebra system (CAS).
2//!
3//! Expression trees over rationals/reals + variables, with `simplify`,
4//! `differentiate`, numeric `eval`, and symbolic equation solving. This is the
5//! ALGEBRA_MANIFOLD_PLAN.md Phase 3 module and is DELIBERATELY distinct from
6//! `solvers/symbolic_logic` (which is SAT / defeasible LOGIC, not computer algebra).
7//!
8//! The CAS is an authoring / tooling path and may allocate (`Box`, `String`); it must
9//! NOT be used on an NQuin/SlgArena hot path. Results can be bridged back into the
10//! graph via [`expr_citation_hash`] for provenance.
11
12use crate::NQuin;
13use std::collections::HashMap;
14
15/// A symbolic expression over real constants and named variables.
16#[derive(Debug, Clone, PartialEq)]
17pub enum Expr {
18    Const(f64),
19    Var(String),
20    Add(Box<Expr>, Box<Expr>),
21    Sub(Box<Expr>, Box<Expr>),
22    Mul(Box<Expr>, Box<Expr>),
23    Div(Box<Expr>, Box<Expr>),
24    /// Integer power `base^exp`.
25    Pow(Box<Expr>, i32),
26    Neg(Box<Expr>),
27    /// Principal square root.
28    Sqrt(Box<Expr>),
29    /// Natural exponential `e^u`.
30    Exp(Box<Expr>),
31    /// Natural logarithm `ln(u)` (domain `u > 0`).
32    Ln(Box<Expr>),
33    Sin(Box<Expr>),
34    Cos(Box<Expr>),
35    /// Tangent `tan(u)` (undefined where `cos(u) = 0`).
36    Tan(Box<Expr>),
37}
38
39/// Predicate tag string for an exact 64-bit signed integer CAS leaf (`Q42-08`).
40pub const CAS_INT_CONST_TAG: &str = "cas:int_const";
41
42// ── ergonomic constructors ──────────────────────────────────────────────────────
43/// Constant leaf `Expr::Const(v)`.
44pub fn c(v: f64) -> Expr {
45    Expr::Const(v)
46}
47/// Exact integer constant leaf constructor (`Q42-08`).
48pub fn int_c(v: i64) -> Expr {
49    Expr::Const(v as f64)
50}
51/// Variable leaf `Expr::Var(name)` (names > 8 bytes are truncated at
52/// Quin encode time).
53pub fn var(name: &str) -> Expr {
54    Expr::Var(name.to_string())
55}
56/// `a + b` node.
57pub fn add(a: Expr, b: Expr) -> Expr {
58    Expr::Add(Box::new(a), Box::new(b))
59}
60/// `a − b` node.
61pub fn sub(a: Expr, b: Expr) -> Expr {
62    Expr::Sub(Box::new(a), Box::new(b))
63}
64/// `a · b` node.
65pub fn mul(a: Expr, b: Expr) -> Expr {
66    Expr::Mul(Box::new(a), Box::new(b))
67}
68/// `a / b` node.
69pub fn div(a: Expr, b: Expr) -> Expr {
70    Expr::Div(Box::new(a), Box::new(b))
71}
72/// `a^e` node with integer exponent.
73pub fn pow(a: Expr, e: i32) -> Expr {
74    Expr::Pow(Box::new(a), e)
75}
76/// Unary `−a` node.
77pub fn neg(a: Expr) -> Expr {
78    Expr::Neg(Box::new(a))
79}
80/// `√a` node.
81pub fn sqrt(a: Expr) -> Expr {
82    Expr::Sqrt(Box::new(a))
83}
84/// `e^a` node.
85pub fn exp(a: Expr) -> Expr {
86    Expr::Exp(Box::new(a))
87}
88/// `ln a` node.
89pub fn ln(a: Expr) -> Expr {
90    Expr::Ln(Box::new(a))
91}
92/// `sin a` node.
93pub fn sin(a: Expr) -> Expr {
94    Expr::Sin(Box::new(a))
95}
96/// `cos a` node.
97pub fn cos(a: Expr) -> Expr {
98    Expr::Cos(Box::new(a))
99}
100/// `tan a` node.
101pub fn tan(a: Expr) -> Expr {
102    Expr::Tan(Box::new(a))
103}
104
105impl Expr {
106    /// Numerically evaluate, given variable bindings. Returns `None` if a variable is
107    /// unbound or a non-finite value is produced (e.g. division by zero, √negative).
108    pub fn eval(&self, env: &HashMap<String, f64>) -> Option<f64> {
109        let v = match self {
110            Expr::Const(k) => *k,
111            Expr::Var(name) => *env.get(name)?,
112            Expr::Add(a, b) => a.eval(env)? + b.eval(env)?,
113            Expr::Sub(a, b) => a.eval(env)? - b.eval(env)?,
114            Expr::Mul(a, b) => a.eval(env)? * b.eval(env)?,
115            Expr::Div(a, b) => {
116                let d = b.eval(env)?;
117                if d == 0.0 {
118                    return None;
119                }
120                a.eval(env)? / d
121            }
122            Expr::Pow(a, e) => a.eval(env)?.powi(*e),
123            Expr::Neg(a) => -a.eval(env)?,
124            Expr::Sqrt(a) => {
125                let x = a.eval(env)?;
126                if x < 0.0 {
127                    return None;
128                }
129                x.sqrt()
130            }
131            Expr::Exp(a) => a.eval(env)?.exp(),
132            Expr::Ln(a) => {
133                let x = a.eval(env)?;
134                if x <= 0.0 {
135                    return None;
136                }
137                x.ln()
138            }
139            Expr::Sin(a) => a.eval(env)?.sin(),
140            Expr::Cos(a) => a.eval(env)?.cos(),
141            Expr::Tan(a) => a.eval(env)?.tan(),
142        };
143        if v.is_finite() {
144            Some(v)
145        } else {
146            None
147        }
148    }
149}
150
151/// Symbolic derivative of `expr` with respect to variable `wrt`. The result is NOT
152/// auto-simplified — call [`simplify`] on it for a compact form.
153pub fn differentiate(expr: &Expr, wrt: &str) -> Expr {
154    match expr {
155        Expr::Const(_) => c(0.0),
156        Expr::Var(name) => {
157            if name == wrt {
158                c(1.0)
159            } else {
160                c(0.0)
161            }
162        }
163        Expr::Add(a, b) => add(differentiate(a, wrt), differentiate(b, wrt)),
164        Expr::Sub(a, b) => sub(differentiate(a, wrt), differentiate(b, wrt)),
165        // (f·g)' = f'·g + f·g'
166        Expr::Mul(a, b) => add(
167            mul(differentiate(a, wrt), (**b).clone()),
168            mul((**a).clone(), differentiate(b, wrt)),
169        ),
170        // (f/g)' = (f'·g − f·g') / g²
171        Expr::Div(a, b) => div(
172            sub(
173                mul(differentiate(a, wrt), (**b).clone()),
174                mul((**a).clone(), differentiate(b, wrt)),
175            ),
176            pow((**b).clone(), 2),
177        ),
178        // (fⁿ)' = n·fⁿ⁻¹·f'
179        Expr::Pow(a, e) => mul(
180            mul(c(*e as f64), pow((**a).clone(), e - 1)),
181            differentiate(a, wrt),
182        ),
183        Expr::Neg(a) => neg(differentiate(a, wrt)),
184        // (√f)' = f' / (2·√f)
185        Expr::Sqrt(a) => div(differentiate(a, wrt), mul(c(2.0), sqrt((**a).clone()))),
186        // (e^f)' = e^f · f'
187        Expr::Exp(a) => mul(exp((**a).clone()), differentiate(a, wrt)),
188        // (ln f)' = f' / f
189        Expr::Ln(a) => div(differentiate(a, wrt), (**a).clone()),
190        // (sin f)' = cos(f) · f'
191        Expr::Sin(a) => mul(cos((**a).clone()), differentiate(a, wrt)),
192        // (cos f)' = −sin(f) · f'
193        Expr::Cos(a) => mul(neg(sin((**a).clone())), differentiate(a, wrt)),
194        // (tan f)' = f' / cos²(f)   (sec²)
195        Expr::Tan(a) => div(differentiate(a, wrt), pow(cos((**a).clone()), 2)),
196    }
197}
198
199/// Simplify an expression: constant folding, identity elimination (`x+0`, `x·1`,
200/// `x·0`, `x⁰`, `x¹`, `−(−x)`, `x/1`, `x−x`, `x/x`) and collection of an identical
201/// `x+x → 2·x`. Applied to a fixpoint (bounded).
202pub fn simplify(expr: &Expr) -> Expr {
203    let mut cur = expr.clone();
204    for _ in 0..16 {
205        let next = simplify_once(&cur);
206        if next == cur {
207            break;
208        }
209        cur = next;
210    }
211    cur
212}
213
214/// One bottom-up simplification pass: constant folding, identity
215/// elimination (x+0, x·1, x−x), and self-cases (x+x→2x, x/x→1).
216/// `simplify` iterates to fixpoint.
217fn simplify_once(expr: &Expr) -> Expr {
218    match expr {
219        Expr::Const(_) | Expr::Var(_) => expr.clone(),
220        Expr::Add(a, b) => {
221            let (a, b) = (simplify_once(a), simplify_once(b));
222            match (&a, &b) {
223                (Expr::Const(x), Expr::Const(y)) => c(x + y),
224                (Expr::Const(z), _) if *z == 0.0 => b,
225                (_, Expr::Const(z)) if *z == 0.0 => a,
226                _ if a == b => mul(c(2.0), a), // x + x → 2·x
227                _ => add(a, b),
228            }
229        }
230        Expr::Sub(a, b) => {
231            let (a, b) = (simplify_once(a), simplify_once(b));
232            match (&a, &b) {
233                (Expr::Const(x), Expr::Const(y)) => c(x - y),
234                (_, Expr::Const(z)) if *z == 0.0 => a,
235                _ if a == b => c(0.0), // x − x → 0
236                _ => sub(a, b),
237            }
238        }
239        Expr::Mul(a, b) => {
240            let (a, b) = (simplify_once(a), simplify_once(b));
241            match (&a, &b) {
242                (Expr::Const(x), Expr::Const(y)) => c(x * y),
243                (Expr::Const(z), _) | (_, Expr::Const(z)) if *z == 0.0 => c(0.0),
244                (Expr::Const(o), _) if *o == 1.0 => b,
245                (_, Expr::Const(o)) if *o == 1.0 => a,
246                _ => mul(a, b),
247            }
248        }
249        Expr::Div(a, b) => {
250            let (a, b) = (simplify_once(a), simplify_once(b));
251            match (&a, &b) {
252                (Expr::Const(x), Expr::Const(y)) if *y != 0.0 => c(x / y),
253                (Expr::Const(z), _) if *z == 0.0 => c(0.0),
254                (_, Expr::Const(o)) if *o == 1.0 => a,
255                _ if a == b => c(1.0), // x / x → 1 (assumes x ≠ 0)
256                _ => div(a, b),
257            }
258        }
259        Expr::Pow(a, e) => {
260            let a = simplify_once(a);
261            match (&a, e) {
262                (_, 0) => c(1.0),
263                (_, 1) => a,
264                (Expr::Const(x), _) => c(x.powi(*e)),
265                _ => pow(a, *e),
266            }
267        }
268        Expr::Neg(a) => {
269            let a = simplify_once(a);
270            match &a {
271                Expr::Const(x) => c(-x),
272                Expr::Neg(inner) => (**inner).clone(), // −(−x) → x
273                _ => neg(a),
274            }
275        }
276        Expr::Sqrt(a) => {
277            let a = simplify_once(a);
278            match &a {
279                Expr::Const(x) if *x >= 0.0 => {
280                    let r = x.sqrt();
281                    // fold only when exact (avoids hiding irrationality)
282                    if r.fract() == 0.0 {
283                        c(r)
284                    } else {
285                        sqrt(a)
286                    }
287                }
288                _ => sqrt(a),
289            }
290        }
291        Expr::Exp(a) => {
292            let a = simplify_once(a);
293            match &a {
294                Expr::Const(z) if *z == 0.0 => c(1.0), // e⁰ = 1
295                Expr::Ln(inner) => (**inner).clone(),  // e^{ln u} = u
296                _ => exp(a),
297            }
298        }
299        Expr::Ln(a) => {
300            let a = simplify_once(a);
301            match &a {
302                Expr::Const(o) if *o == 1.0 => c(0.0), // ln 1 = 0
303                Expr::Exp(inner) => (**inner).clone(), // ln(e^u) = u
304                _ => ln(a),
305            }
306        }
307        Expr::Sin(a) => {
308            let a = simplify_once(a);
309            match &a {
310                Expr::Const(z) if *z == 0.0 => c(0.0), // sin 0 = 0
311                _ => sin(a),
312            }
313        }
314        Expr::Cos(a) => {
315            let a = simplify_once(a);
316            match &a {
317                Expr::Const(z) if *z == 0.0 => c(1.0), // cos 0 = 1
318                _ => cos(a),
319            }
320        }
321        Expr::Tan(a) => {
322            let a = simplify_once(a);
323            match &a {
324                Expr::Const(z) if *z == 0.0 => c(0.0), // tan 0 = 0
325                _ => tan(a),
326            }
327        }
328    }
329}
330
331/// Symbolic roots of `a·x² + b·x + c = 0` with real coefficients, as exact `Expr`s
332/// `(-b ± √(b²−4ac)) / (2a)`. Returns the two root expressions (simplified). For
333/// `a = 0` returns the single linear root `-c/b`.
334pub fn solve_quadratic_symbolic(a: f64, b: f64, cc: f64) -> Vec<Expr> {
335    if a == 0.0 {
336        if b == 0.0 {
337            return Vec::new();
338        }
339        return vec![simplify(&div(neg(c(cc)), c(b)))];
340    }
341    let disc = sub(pow(c(b), 2), mul(c(4.0), mul(c(a), c(cc)))); // b² − 4ac
342    let root_plus = div(add(neg(c(b)), sqrt(disc.clone())), mul(c(2.0), c(a)));
343    let root_minus = div(sub(neg(c(b)), sqrt(disc)), mul(c(2.0), c(a)));
344    vec![simplify(&root_plus), simplify(&root_minus)]
345}
346
347/// Distribute every product over sums and expand small positive integer powers, so the
348/// result contains no `Mul`/`Pow` node with an additive child. Semantically equal to the
349/// input (verify by evaluation). Powers above 8 are left unexpanded to bound blow-up.
350pub fn expand(expr: &Expr) -> Expr {
351    match expr {
352        Expr::Const(_) | Expr::Var(_) => expr.clone(),
353        Expr::Add(a, b) => add(expand(a), expand(b)),
354        Expr::Sub(a, b) => sub(expand(a), expand(b)),
355        Expr::Neg(a) => neg(expand(a)),
356        Expr::Sqrt(a) => sqrt(expand(a)),
357        Expr::Exp(a) => exp(expand(a)),
358        Expr::Ln(a) => ln(expand(a)),
359        Expr::Sin(a) => sin(expand(a)),
360        Expr::Cos(a) => cos(expand(a)),
361        Expr::Tan(a) => tan(expand(a)),
362        Expr::Div(a, b) => div(expand(a), expand(b)),
363        Expr::Mul(a, b) => expand_mul(&expand(a), &expand(b)),
364        Expr::Pow(a, e) => expand_pow(&expand(a), *e),
365    }
366}
367
368/// Distribute `a · b` over `Add`/`Sub` children (one level).
369fn expand_mul(a: &Expr, b: &Expr) -> Expr {
370    match (a, b) {
371        (Expr::Add(a1, a2), _) => add(expand_mul(a1, b), expand_mul(a2, b)),
372        (Expr::Sub(a1, a2), _) => sub(expand_mul(a1, b), expand_mul(a2, b)),
373        (_, Expr::Add(b1, b2)) => add(expand_mul(a, b1), expand_mul(a, b2)),
374        (_, Expr::Sub(b1, b2)) => sub(expand_mul(a, b1), expand_mul(a, b2)),
375        (Expr::Neg(a1), _) => neg(expand_mul(a1, b)),
376        (_, Expr::Neg(b1)) => neg(expand_mul(a, b1)),
377        _ => mul(a.clone(), b.clone()),
378    }
379}
380
381/// Expand `base^e` into repeated `expand_mul` for small non-negative
382/// `e`; leaves `Pow` intact otherwise.
383fn expand_pow(base: &Expr, e: i32) -> Expr {
384    if e <= 1 || e > 8 {
385        return pow(base.clone(), e);
386    }
387    let mut acc = base.clone();
388    for _ in 1..e {
389        acc = expand_mul(&acc, base);
390    }
391    acc
392}
393
394/// Factor a real quadratic `a·x² + b·x + c` into `a·(x − r₁)·(x − r₂)` when it has real
395/// roots. Returns `None` when the discriminant is negative (no real factorisation) or
396/// `a = 0`. Root constants are snapped to integers/halves when numerically close, so the
397/// common rational case factors cleanly.
398pub fn factor_quadratic(a: f64, b: f64, cc: f64, varname: &str) -> Option<Expr> {
399    if a == 0.0 {
400        return None;
401    }
402    let disc = b * b - 4.0 * a * cc;
403    if disc < 0.0 {
404        return None;
405    }
406    let sq = disc.sqrt();
407    let clean = |r: f64| {
408        let halves = (r * 2.0).round() / 2.0;
409        if (halves - r).abs() < 1e-9 {
410            halves
411        } else {
412            r
413        }
414    };
415    let r1 = clean((-b + sq) / (2.0 * a));
416    let r2 = clean((-b - sq) / (2.0 * a));
417    let prod = mul(sub(var(varname), c(r1)), sub(var(varname), c(r2)));
418    Some(if (a - 1.0).abs() < 1e-12 {
419        prod
420    } else {
421        mul(c(a), prod)
422    })
423}
424
425/// A stable provenance hash of an expression's canonical form, for citing symbolic
426/// results back into the graph (Phase 3.8 bridge). Two structurally-equal expressions
427/// hash equally; this is `q_hash` over the canonical `Display` string.
428pub fn expr_citation_hash(expr: &Expr) -> u64 {
429    crate::q_hash(&format!("{expr}"))
430}
431
432// ── Expr ↔ NQuin tree encoding (Phase 3.8) ──────────────────────────────────────
433// A symbolic expression is serialised into a post-order `Vec<NQuin>`: each node is one
434// quin that references its children by their index in the vec (the root is the last
435// element). This lets symbolic results be STORED in the graph and CITED, not just hashed.
436//
437// Per-node quin layout (predicate = node-kind tag via q_hash):
438//   const   object = f64 bits
439//   var     object = name packed LE (≤ 8 bytes), metadata = byte length
440//   add/sub/mul/div  object = left child index, context = right child index
441//   pow     object = base child index, metadata = exponent (i32 as u64)
442//   neg/sqrt object = child index
443
444/// `q_hash` predicate tag for a CAS node kind (`"cas:add"`, …).
445fn name_tag(kind: &str) -> u64 {
446    crate::q_hash(kind)
447}
448
449/// Pack a variable name into (LE-packed-u64, byte-len), truncating to
450/// 8 bytes — the Quin object/metadata encoding for `cas:var`.
451fn pack_name(name: &str) -> (u64, u64) {
452    let bytes = name.as_bytes();
453    let len = bytes.len().min(8);
454    let mut v = 0u64;
455    for (i, &b) in bytes.iter().take(8).enumerate() {
456        v |= (b as u64) << (i * 8);
457    }
458    (v, len as u64)
459}
460
461/// Inverse of `pack_name` — extract up to 8 name bytes.
462fn unpack_name(v: u64, len: u64) -> String {
463    let len = (len as usize).min(8);
464    let mut s = String::with_capacity(len);
465    for i in 0..len {
466        s.push(((v >> (i * 8)) & 0xFF) as u8 as char);
467    }
468    s
469}
470
471/// Append a CAS node Quin (subject = its index in `out`, parity
472/// computed) and return that index for child references.
473fn push_node(
474    out: &mut Vec<NQuin>,
475    predicate: u64,
476    object: u64,
477    context: u64,
478    metadata: u64,
479) -> usize {
480    let idx = out.len();
481    let subject = idx as u64;
482    out.push(NQuin {
483        subject,
484        predicate,
485        object,
486        context,
487        metadata,
488        parity: NQuin::calculate_parity(subject, predicate, object, context, metadata),
489    });
490    idx
491}
492
493/// Encode `e` post-order into `out` (children before parents,
494/// index-linked); returns the root node index.
495/// Append an exact 64-bit signed integer constant leaf Quin (`cas:int_const`) with 5-field parity.
496pub fn push_int_const_node(out: &mut Vec<NQuin>, value: i64) -> usize {
497    push_node(out, name_tag(CAS_INT_CONST_TAG), value as u64, 0, 0)
498}
499
500/// Extract the exact 64-bit signed integer from a `cas:int_const` Quin leaf.
501pub fn decode_int_const_quin(quin: &NQuin) -> Option<i64> {
502    if quin.verify_ecc_parity() && quin.predicate == name_tag(CAS_INT_CONST_TAG) {
503        Some(quin.object as i64)
504    } else {
505        None
506    }
507}
508
509fn encode(e: &Expr, out: &mut Vec<NQuin>) -> usize {
510    match e {
511        Expr::Const(k) => push_node(out, name_tag("cas:const"), k.to_bits(), 0, 0),
512        Expr::Var(name) => {
513            let (packed, len) = pack_name(name);
514            push_node(out, name_tag("cas:var"), packed, 0, len)
515        }
516        Expr::Add(a, b) => {
517            let (l, r) = (encode(a, out), encode(b, out));
518            push_node(out, name_tag("cas:add"), l as u64, r as u64, 0)
519        }
520        Expr::Sub(a, b) => {
521            let (l, r) = (encode(a, out), encode(b, out));
522            push_node(out, name_tag("cas:sub"), l as u64, r as u64, 0)
523        }
524        Expr::Mul(a, b) => {
525            let (l, r) = (encode(a, out), encode(b, out));
526            push_node(out, name_tag("cas:mul"), l as u64, r as u64, 0)
527        }
528        Expr::Div(a, b) => {
529            let (l, r) = (encode(a, out), encode(b, out));
530            push_node(out, name_tag("cas:div"), l as u64, r as u64, 0)
531        }
532        Expr::Pow(a, exp) => {
533            let l = encode(a, out);
534            push_node(out, name_tag("cas:pow"), l as u64, 0, (*exp as i64) as u64)
535        }
536        Expr::Neg(a) => {
537            let l = encode(a, out);
538            push_node(out, name_tag("cas:neg"), l as u64, 0, 0)
539        }
540        Expr::Sqrt(a) => {
541            let l = encode(a, out);
542            push_node(out, name_tag("cas:sqrt"), l as u64, 0, 0)
543        }
544        Expr::Exp(a) => {
545            let l = encode(a, out);
546            push_node(out, name_tag("cas:exp"), l as u64, 0, 0)
547        }
548        Expr::Ln(a) => {
549            let l = encode(a, out);
550            push_node(out, name_tag("cas:ln"), l as u64, 0, 0)
551        }
552        Expr::Sin(a) => {
553            let l = encode(a, out);
554            push_node(out, name_tag("cas:sin"), l as u64, 0, 0)
555        }
556        Expr::Cos(a) => {
557            let l = encode(a, out);
558            push_node(out, name_tag("cas:cos"), l as u64, 0, 0)
559        }
560        Expr::Tan(a) => {
561            let l = encode(a, out);
562            push_node(out, name_tag("cas:tan"), l as u64, 0, 0)
563        }
564    }
565}
566
567/// Serialise an expression into a post-order `Vec<NQuin>` (the root is the last element).
568pub fn to_quins(expr: &Expr) -> Vec<NQuin> {
569    let mut out = Vec::new();
570    encode(expr, &mut out);
571    out
572}
573
574/// Decode node `idx` (and its index-linked children) back into an
575/// `Expr`; errors on unknown predicates, parity failure, or non-postorder/cyclic child references.
576fn decode(quins: &[NQuin], idx: usize) -> Result<Expr, String> {
577    let node = quins
578        .get(idx)
579        .ok_or_else(|| format!("child index {idx} out of range"))?;
580    if !node.verify_ecc_parity() {
581        return Err(format!("CAS quin {idx} failed 5-field ECC parity check"));
582    }
583    let p = node.predicate;
584    let child = |i: u64| -> Result<Expr, String> {
585        let child_idx = usize::try_from(i)
586            .map_err(|_| format!("child index {i} overflows usize at quin {idx}"))?;
587        if child_idx >= idx {
588            return Err(format!(
589                "non-postorder or cyclic child reference: child_idx {child_idx} >= current_idx {idx}"
590            ));
591        }
592        decode(quins, child_idx)
593    };
594    if p == name_tag("cas:const") {
595        Ok(c(f64::from_bits(node.object)))
596    } else if p == name_tag("cas:int_const") {
597        Ok(int_c(node.object as i64))
598    } else if p == name_tag("cas:var") {
599        Ok(var(&unpack_name(node.object, node.metadata)))
600    } else if p == name_tag("cas:add") {
601        Ok(add(child(node.object)?, child(node.context)?))
602    } else if p == name_tag("cas:sub") {
603        Ok(sub(child(node.object)?, child(node.context)?))
604    } else if p == name_tag("cas:mul") {
605        Ok(mul(child(node.object)?, child(node.context)?))
606    } else if p == name_tag("cas:div") {
607        Ok(div(child(node.object)?, child(node.context)?))
608    } else if p == name_tag("cas:pow") {
609        Ok(pow(child(node.object)?, node.metadata as i64 as i32))
610    } else if p == name_tag("cas:neg") {
611        Ok(neg(child(node.object)?))
612    } else if p == name_tag("cas:sqrt") {
613        Ok(sqrt(child(node.object)?))
614    } else if p == name_tag("cas:exp") {
615        Ok(exp(child(node.object)?))
616    } else if p == name_tag("cas:ln") {
617        Ok(ln(child(node.object)?))
618    } else if p == name_tag("cas:sin") {
619        Ok(sin(child(node.object)?))
620    } else if p == name_tag("cas:cos") {
621        Ok(cos(child(node.object)?))
622    } else if p == name_tag("cas:tan") {
623        Ok(tan(child(node.object)?))
624    } else {
625        Err(format!("unknown CAS node tag in quin {idx}"))
626    }
627}
628
629/// Reconstruct an expression from a post-order `Vec<NQuin>` produced by [`to_quins`].
630pub fn from_quins(quins: &[NQuin]) -> Result<Expr, String> {
631    if quins.is_empty() {
632        return Err("empty quin sequence".to_string());
633    }
634    decode(quins, quins.len() - 1)
635}
636
637// ── parser: text → Expr (recursive descent) ─────────────────────────────────────
638// Grammar:  expr = term (('+'|'-') term)*
639//           term = factor (('*'|'/') factor)*
640//           factor = unary ('^' integer)?
641//           unary = '-' unary | base
642//           base = number | ident | 'sqrt' '(' expr ')' | '(' expr ')'
643
644/// Parse a textual expression like `"x^3 - 2*x^2 + 5"` or `"sqrt(b^2 - 4*a*c)"` into an
645/// [`Expr`]. Supports `+ - * / ^`, parentheses, `sqrt(...)`, numbers and identifiers.
646pub fn parse(input: &str) -> Result<Expr, String> {
647    let tokens = tokenize(input)?;
648    let mut p = Parser { tokens, pos: 0 };
649    let e = p.parse_expr()?;
650    if p.pos != p.tokens.len() {
651        return Err(format!("unexpected trailing tokens at {}", p.pos));
652    }
653    Ok(e)
654}
655
656#[derive(Debug, Clone, PartialEq)]
657enum Tok {
658    Num(f64),
659    Ident(String),
660    Plus,
661    Minus,
662    Star,
663    Slash,
664    Caret,
665    LParen,
666    RParen,
667}
668
669/// Lex `s` into tokens (numbers, names, operators, parens).
670fn tokenize(s: &str) -> Result<Vec<Tok>, String> {
671    let mut out = Vec::new();
672    let chars: Vec<char> = s.chars().collect();
673    let mut i = 0;
674    while i < chars.len() {
675        let ch = chars[i];
676        match ch {
677            ' ' | '\t' | '\n' | '\r' => i += 1,
678            '+' => {
679                out.push(Tok::Plus);
680                i += 1;
681            }
682            '-' => {
683                out.push(Tok::Minus);
684                i += 1;
685            }
686            '*' => {
687                out.push(Tok::Star);
688                i += 1;
689            }
690            '/' => {
691                out.push(Tok::Slash);
692                i += 1;
693            }
694            '^' => {
695                out.push(Tok::Caret);
696                i += 1;
697            }
698            '(' => {
699                out.push(Tok::LParen);
700                i += 1;
701            }
702            ')' => {
703                out.push(Tok::RParen);
704                i += 1;
705            }
706            c if c.is_ascii_digit() || c == '.' => {
707                let start = i;
708                while i < chars.len() && (chars[i].is_ascii_digit() || chars[i] == '.') {
709                    i += 1;
710                }
711                let num: String = chars[start..i].iter().collect();
712                out.push(Tok::Num(
713                    num.parse().map_err(|_| format!("bad number '{num}'"))?,
714                ));
715            }
716            c if c.is_ascii_alphabetic() || c == '_' => {
717                let start = i;
718                while i < chars.len() && (chars[i].is_ascii_alphanumeric() || chars[i] == '_') {
719                    i += 1;
720                }
721                out.push(Tok::Ident(chars[start..i].iter().collect()));
722            }
723            other => return Err(format!("unexpected character '{other}'")),
724        }
725    }
726    Ok(out)
727}
728
729struct Parser {
730    tokens: Vec<Tok>,
731    pos: usize,
732}
733
734impl Parser {
735    /// Current token without consuming it.
736    fn peek(&self) -> Option<&Tok> {
737        self.tokens.get(self.pos)
738    }
739    /// Consume and return the current token.
740    fn next(&mut self) -> Option<Tok> {
741        let t = self.tokens.get(self.pos).cloned();
742        if t.is_some() {
743            self.pos += 1;
744        }
745        t
746    }
747
748    /// expr := term (('+'|'-') term)* — lowest precedence level.
749    fn parse_expr(&mut self) -> Result<Expr, String> {
750        let mut left = self.parse_term()?;
751        while let Some(op) = self.peek() {
752            match op {
753                Tok::Plus => {
754                    self.next();
755                    left = add(left, self.parse_term()?);
756                }
757                Tok::Minus => {
758                    self.next();
759                    left = sub(left, self.parse_term()?);
760                }
761                _ => break,
762            }
763        }
764        Ok(left)
765    }
766
767    /// term := factor (('*'|'/') factor)*.
768    fn parse_term(&mut self) -> Result<Expr, String> {
769        let mut left = self.parse_factor()?;
770        while let Some(op) = self.peek() {
771            match op {
772                Tok::Star => {
773                    self.next();
774                    left = mul(left, self.parse_factor()?);
775                }
776                Tok::Slash => {
777                    self.next();
778                    left = div(left, self.parse_factor()?);
779                }
780                _ => break,
781            }
782        }
783        Ok(left)
784    }
785
786    /// factor := unary ('^' unary)* — right-binding power level.
787    fn parse_factor(&mut self) -> Result<Expr, String> {
788        let base = self.parse_unary()?;
789        if let Some(Tok::Caret) = self.peek() {
790            self.next();
791            // exponent must be an integer literal (optionally negated)
792            let neg_exp = matches!(self.peek(), Some(Tok::Minus));
793            if neg_exp {
794                self.next();
795            }
796            match self.next() {
797                Some(Tok::Num(n)) if n.fract() == 0.0 => {
798                    let e = n as i32 * if neg_exp { -1 } else { 1 };
799                    Ok(pow(base, e))
800                }
801                _ => Err("'^' requires an integer exponent".to_string()),
802            }
803        } else {
804            Ok(base)
805        }
806    }
807
808    /// unary := '-' unary | base — prefix negation.
809    fn parse_unary(&mut self) -> Result<Expr, String> {
810        if let Some(Tok::Minus) = self.peek() {
811            self.next();
812            return Ok(neg(self.parse_unary()?));
813        }
814        self.parse_base()
815    }
816
817    /// base := number | name | name '(' args ')' | '(' expr ')' —
818    /// function calls map to `exp`/`ln`/`sin`/`cos`/`tan`/`sqrt`.
819    fn parse_base(&mut self) -> Result<Expr, String> {
820        match self.next() {
821            Some(Tok::Num(n)) => Ok(c(n)),
822            Some(Tok::Ident(name)) => {
823                // Unary functions: name '(' expr ')'.
824                let unary: Option<fn(Expr) -> Expr> = match name.as_str() {
825                    "sqrt" => Some(sqrt),
826                    "exp" => Some(exp),
827                    "ln" => Some(ln),
828                    "sin" => Some(sin),
829                    "cos" => Some(cos),
830                    "tan" => Some(tan),
831                    _ => None,
832                };
833                if let Some(ctor) = unary {
834                    self.expect(Tok::LParen)?;
835                    let inner = self.parse_expr()?;
836                    self.expect(Tok::RParen)?;
837                    Ok(ctor(inner))
838                } else {
839                    Ok(var(&name))
840                }
841            }
842            Some(Tok::LParen) => {
843                let inner = self.parse_expr()?;
844                self.expect(Tok::RParen)?;
845                Ok(inner)
846            }
847            other => Err(format!("unexpected token: {other:?}")),
848        }
849    }
850
851    /// Consume the next token, erroring unless it equals `t`.
852    fn expect(&mut self, t: Tok) -> Result<(), String> {
853        if self.next().as_ref() == Some(&t) {
854            Ok(())
855        } else {
856            Err(format!("expected {t:?}"))
857        }
858    }
859}
860
861impl std::fmt::Display for Expr {
862    /// Infix pretty-print with parenthesized children.
863    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
864        match self {
865            Expr::Const(k) => write!(f, "{k}"),
866            Expr::Var(name) => write!(f, "{name}"),
867            Expr::Add(a, b) => write!(f, "({a} + {b})"),
868            Expr::Sub(a, b) => write!(f, "({a} - {b})"),
869            Expr::Mul(a, b) => write!(f, "({a} * {b})"),
870            Expr::Div(a, b) => write!(f, "({a} / {b})"),
871            Expr::Pow(a, e) => write!(f, "({a}^{e})"),
872            Expr::Neg(a) => write!(f, "(-{a})"),
873            Expr::Sqrt(a) => write!(f, "sqrt({a})"),
874            Expr::Exp(a) => write!(f, "exp({a})"),
875            Expr::Ln(a) => write!(f, "ln({a})"),
876            Expr::Sin(a) => write!(f, "sin({a})"),
877            Expr::Cos(a) => write!(f, "cos({a})"),
878            Expr::Tan(a) => write!(f, "tan({a})"),
879        }
880    }
881}
882
883// ── Sum of Three Cubes (x^3 + y^3 + z^3 = k), Divisor Cascade, & 4-Prime RNS CRT (Q42-08) ──
884
885/// Canonical symbolic expression for `x^3 + y^3 + z^3 - k` using exact `Expr::IntConst(k)`.
886pub fn sum_of_three_cubes_expr(k: i64) -> Expr {
887    sub(
888        add(add(pow(var("x"), 3), pow(var("y"), 3)), pow(var("z"), 3)),
889        int_c(k),
890    )
891}
892
893/// Encode `x^3 + y^3 + z^3 - k` into a post-order `Vec<NQuin>` with canonical 5-field XOR parity
894/// and an exact `cas:int_const` leaf for `k`.
895pub fn sum_of_three_cubes_quins(k: i64) -> Vec<NQuin> {
896    let mut out = Vec::new();
897    let sum_cubes = add(add(pow(var("x"), 3), pow(var("y"), 3)), pow(var("z"), 3));
898    let l = encode(&sum_cubes, &mut out);
899    let r = push_int_const_node(&mut out, k);
900    push_node(&mut out, name_tag("cas:sub"), l as u64, r as u64, 0);
901    out
902}
903
904#[inline]
905const fn u256_add_limbs(a: [u64; 4], b: [u64; 4]) -> [u64; 4] {
906    let mut out = [0u64; 4];
907    let mut carry = 0u128;
908    let mut i = 0;
909    while i < 4 {
910        let sum = (a[i] as u128) + (b[i] as u128) + carry;
911        out[i] = sum as u64;
912        carry = sum >> 64;
913        i += 1;
914    }
915    out
916}
917
918#[inline]
919const fn i256_cube_from_i64(v: i64) -> [u64; 4] {
920    let neg = v < 0;
921    let mag = v.unsigned_abs();
922    let sq = (mag as u128) * (mag as u128);
923    let sq_lo = sq as u64;
924    let sq_hi = (sq >> 64) as u64;
925    let p0 = (sq_lo as u128) * (mag as u128);
926    let p1 = (sq_hi as u128) * (mag as u128) + (p0 >> 64);
927    let cube = [p0 as u64, p1 as u64, (p1 >> 64) as u64, 0u64];
928    if neg {
929        u256_add_limbs([!cube[0], !cube[1], !cube[2], !cube[3]], [1, 0, 0, 0])
930    } else {
931        cube
932    }
933}
934
935/// Returns `true` iff `k ≡ 4 or 5 (mod 9)` (`k ≡ ±4 (mod 9)`), proving global algebraic
936/// impossibility of `x^3 + y^3 + z^3 = k` over `ℤ^3` (`Q42-08` / §6.2.3).
937#[inline]
938pub const fn has_sum_of_three_cubes_mod9_obstruction(k: i64) -> bool {
939    matches!(k.rem_euclid(9), 4 | 5)
940}
941
942/// Zero-heap exact signed 256-bit verification of `x^3 + y^3 + z^3 == k` over `[u64; 4]` stack limbs.
943#[inline]
944pub fn verify_sum_of_three_cubes_exact(
945    x: i64,
946    y: i64,
947    z: i64,
948    k: i64,
949) -> Result<bool, &'static str> {
950    if has_sum_of_three_cubes_mod9_obstruction(k) {
951        return Ok(false);
952    }
953    let sum = u256_add_limbs(
954        u256_add_limbs(i256_cube_from_i64(x), i256_cube_from_i64(y)),
955        i256_cube_from_i64(z),
956    );
957    let ext = if k < 0 { u64::MAX } else { 0u64 };
958    Ok(sum == [k as u64, ext, ext, ext])
959}
960
961/// Zero-heap `i128` Divisor / Discriminant reduction cascade for `x^3 + y^3 + z^3 = k`:
962/// Given `(k, z)` and divisor `s = x + y` of `r = k - z^3 = s(x^2 - xy + y^2)`:
963/// 1. `q = r / s` (`r % s == 0`)
964/// 2. `p = (s^2 - q) / 3` (`(s^2 - q) % 3 == 0`)
965/// 3. `D = s^2 - 4p = (x - y)^2 = u^2 >= 0`
966/// Returns recovered `(x, y)` with `x >= y` when all cascade conditions hold.
967pub fn reduce_sum_of_three_cubes_divisor_discriminant(
968    k: i128,
969    z: i128,
970    s: i128,
971) -> Option<(i128, i128)> {
972    if s == 0 {
973        return None;
974    }
975    let z3 = z.checked_mul(z)?.checked_mul(z)?;
976    let r = k.checked_sub(z3)?;
977    if r % s != 0 {
978        return None;
979    }
980    let q = r / s;
981    let s2 = s.checked_mul(s)?;
982    let s2_minus_q = s2.checked_sub(q)?;
983    if s2_minus_q % 3 != 0 {
984        return None;
985    }
986    let p = s2_minus_q / 3;
987    let d = s2.checked_sub(p.checked_mul(4)?)?;
988    if d < 0 {
989        return None;
990    }
991    let u = (d as u128).isqrt() as i128;
992    if u * u != d || (s + u) % 2 != 0 {
993        return None;
994    }
995    Some(((s + u) / 2, (s - u) / 2))
996}
997
998/// Arbitrary-precision Divisor / Discriminant cascade verifier over `BigInt` (`Q42-08` / §6.2.3),
999/// capable of verifying 170-bit witnesses such as Booker & Sutherland's `k = 42` solution:
1000/// `r = k - z^3`, `s = x + y`, `q = r / s`, `p = (s^2 - q) / 3`, `D = s^2 - 4p = (x - y)^2 = u^2`.
1001pub fn verify_divisor_discriminant_cascade_bigint(
1002    x: i64,
1003    y: i64,
1004    z: i64,
1005    k: i64,
1006) -> Result<bool, String> {
1007    use crate::solvers::exact::BigInt;
1008    let bx = BigInt::from_i64(x);
1009    let by = BigInt::from_i64(y);
1010    let bz = BigInt::from_i64(z);
1011    let bk = BigInt::from_i64(k);
1012
1013    let s = bx.add(&by);
1014    if s.is_zero() {
1015        return Ok(false);
1016    }
1017    let r = bk.sub(&bz.pow(3));
1018    let (q, rem_r) = r.divmod(&s).ok_or_else(|| "division by zero".to_string())?;
1019    if !rem_r.is_zero() {
1020        return Ok(false);
1021    }
1022    let s2 = s.mul(&s);
1023    let (p, rem_3) = s2
1024        .sub(&q)
1025        .divmod(&BigInt::from_i64(3))
1026        .ok_or_else(|| "division by 3".to_string())?;
1027    if !rem_3.is_zero() {
1028        return Ok(false);
1029    }
1030    let disc = s2.sub(&p.mul(&BigInt::from_i64(4)));
1031    let u = bx.sub(&by);
1032    let u2 = u.mul(&u);
1033    Ok(disc == u2 && bx.pow(3).add(&by.pow(3)) == r)
1034}
1035
1036/// Four pairwise-coprime 31-bit primes for zero-heap RNS / CRT verification (`∏ m_i ≈ 2^124 > 2B`).
1037pub const RNS_CRT_PRIMES_4: [u64; 4] = [
1038    2_147_483_647, // 2^31 - 1
1039    2_147_483_629,
1040    2_147_483_587,
1041    2_147_483_579,
1042];
1043
1044#[inline]
1045const fn mod_cube_i64(v: i64, m: u64) -> u64 {
1046    let r = v.rem_euclid(m as i64) as u64;
1047    let r2 = ((r as u128 * r as u128) % m as u128) as u64;
1048    ((r2 as u128 * r as u128) % m as u128) as u64
1049}
1050
1051/// Zero-heap 4-prime RNS residual `(x^3 + y^3 + z^3 - k) mod m_i` across [`RNS_CRT_PRIMES_4`].
1052/// By CRT, all 4 lanes are `0` iff `∏ m_i` divides `x^3 + y^3 + z^3 - k` (exact for `|residual| < ∏ m_i / 2`).
1053#[inline]
1054pub const fn rns_4prime_cubic_residuals(x: i64, y: i64, z: i64, k: i64) -> [u64; 4] {
1055    let mut out = [0u64; 4];
1056    let mut i = 0;
1057    while i < 4 {
1058        let m = RNS_CRT_PRIMES_4[i];
1059        let cx = mod_cube_i64(x, m);
1060        let cy = mod_cube_i64(y, m);
1061        let cz = mod_cube_i64(z, m);
1062        let ck = k.rem_euclid(m as i64) as u64;
1063        let sum = (cx + cy + cz) % m;
1064        out[i] = (sum + m - ck) % m;
1065        i += 1;
1066    }
1067    out
1068}
1069
1070/// Returns `true` iff `(x, y, z, k)` vanishes in all 4 RNS prime lanes (`RNS_CRT_PRIMES_4`).
1071#[inline]
1072pub const fn verify_sum_of_three_cubes_rns_4prime(x: i64, y: i64, z: i64, k: i64) -> bool {
1073    let r = rns_4prime_cubic_residuals(x, y, z, k);
1074    r[0] == 0 && r[1] == 0 && r[2] == 0 && r[3] == 0
1075}
1076
1077#[cfg(test)]
1078mod tests {
1079    use super::*;
1080
1081    fn env1(name: &str, v: f64) -> HashMap<String, f64> {
1082        let mut m = HashMap::new();
1083        m.insert(name.to_string(), v);
1084        m
1085    }
1086
1087    #[test]
1088    fn differentiate_matches_finite_difference() {
1089        // f(x) = x³ − 2x² + 5  → f'(x) = 3x² − 4x. Check at several points against a
1090        // central finite difference of the ORIGINAL expression (strong correctness test).
1091        let f = add(sub(pow(var("x"), 3), mul(c(2.0), pow(var("x"), 2))), c(5.0));
1092        let df = simplify(&differentiate(&f, "x"));
1093        for &x in &[-2.0, -0.5, 1.0, 3.7] {
1094            let h = 1e-6;
1095            let fd = (f.eval(&env1("x", x + h)).unwrap() - f.eval(&env1("x", x - h)).unwrap())
1096                / (2.0 * h);
1097            let sym = df.eval(&env1("x", x)).unwrap();
1098            assert!((sym - fd).abs() < 1e-4, "x={x}: symbolic {sym} vs fd {fd}");
1099        }
1100    }
1101
1102    #[test]
1103    fn simplify_identities() {
1104        assert_eq!(simplify(&add(var("x"), c(0.0))), var("x"));
1105        assert_eq!(simplify(&mul(var("x"), c(1.0))), var("x"));
1106        assert_eq!(simplify(&mul(var("x"), c(0.0))), c(0.0));
1107        assert_eq!(simplify(&pow(var("x"), 0)), c(1.0));
1108        assert_eq!(simplify(&neg(neg(var("x")))), var("x"));
1109        assert_eq!(simplify(&sub(var("x"), var("x"))), c(0.0));
1110        assert_eq!(simplify(&add(var("x"), var("x"))), mul(c(2.0), var("x")));
1111        assert_eq!(simplify(&add(c(2.0), c(3.0))), c(5.0));
1112    }
1113
1114    #[test]
1115    fn symbolic_quadratic_agrees_with_numeric() {
1116        // x² − 5x + 6 → roots {3, 2}; evaluate the symbolic root expressions.
1117        let roots = solve_quadratic_symbolic(1.0, -5.0, 6.0);
1118        assert_eq!(roots.len(), 2);
1119        let empty = HashMap::new();
1120        let mut vals: Vec<f64> = roots.iter().map(|r| r.eval(&empty).unwrap()).collect();
1121        vals.sort_by(|a, b| a.partial_cmp(b).unwrap());
1122        assert!((vals[0] - 2.0).abs() < 1e-12 && (vals[1] - 3.0).abs() < 1e-12);
1123    }
1124
1125    #[test]
1126    fn parse_and_differentiate_roundtrip() {
1127        // Parse a textual polynomial, differentiate symbolically, and check the
1128        // derivative numerically (d/dx of x^3 - 2x^2 + 5 is 3x^2 - 4x → at x=2: 4).
1129        let f = parse("x^3 - 2*x^2 + 5").unwrap();
1130        let df = simplify(&differentiate(&f, "x"));
1131        assert!((df.eval(&env1("x", 2.0)).unwrap() - 4.0).abs() < 1e-9);
1132        // precedence: 2 + 3 * 4 = 14, not 20
1133        assert_eq!(
1134            parse("2 + 3 * 4").unwrap().eval(&HashMap::new()).unwrap(),
1135            14.0
1136        );
1137        // sqrt + parens
1138        let g = parse("sqrt((a + 3))").unwrap();
1139        assert!((g.eval(&env1("a", 1.0)).unwrap() - 2.0).abs() < 1e-12);
1140        // bad input errors, not panics
1141        assert!(parse("2 +* 3").is_err());
1142    }
1143
1144    #[test]
1145    fn expand_distributes_and_preserves_value() {
1146        // (x + 1)·(x + 2) expands to a sum with no Mul-over-sum; value matches at samples.
1147        let e = mul(add(var("x"), c(1.0)), add(var("x"), c(2.0)));
1148        let ex = expand(&e);
1149        for &x in &[-3.0, 0.0, 2.5, 7.0] {
1150            let want = e.eval(&env1("x", x)).unwrap();
1151            let got = ex.eval(&env1("x", x)).unwrap();
1152            assert!((want - got).abs() < 1e-9, "expand changed value at x={x}");
1153        }
1154        // (x + 1)^3 expands and still evaluates correctly.
1155        let cube = pow(add(var("x"), c(1.0)), 3);
1156        let cube_x = expand(&cube);
1157        assert!((cube_x.eval(&env1("x", 2.0)).unwrap() - 27.0).abs() < 1e-9);
1158    }
1159
1160    #[test]
1161    fn factor_quadratic_inverts_expand() {
1162        // x² − 5x + 6 factors to (x−2)(x−3); expanding the factors recovers the value.
1163        let f = factor_quadratic(1.0, -5.0, 6.0, "x").unwrap();
1164        let original = add(sub(pow(var("x"), 2), mul(c(5.0), var("x"))), c(6.0));
1165        for &x in &[-1.0, 0.0, 2.0, 3.0, 5.5] {
1166            let a = f.eval(&env1("x", x)).unwrap();
1167            let b = original.eval(&env1("x", x)).unwrap();
1168            assert!((a - b).abs() < 1e-9, "factored != original at x={x}");
1169        }
1170        // Negative discriminant → no real factorisation.
1171        assert!(factor_quadratic(1.0, 0.0, 1.0, "x").is_none());
1172    }
1173
1174    #[test]
1175    fn expr_quin_roundtrip() {
1176        // Encode an expression to NQuins and decode it back unchanged.
1177        let e = parse("x^2 + 3*x + 2").unwrap();
1178        let quins = to_quins(&e);
1179        assert!(!quins.is_empty());
1180        assert!(
1181            quins.iter().all(|q| q.verify_ecc_parity()),
1182            "CAS Quins must carry five-field ECC so a v3 volume verify can accept them"
1183        );
1184        let back = from_quins(&quins).unwrap();
1185        assert_eq!(e, back);
1186
1187        // Multi-char variable names (≤ 8 bytes) and sqrt/neg survive the round-trip.
1188        let e2 = sqrt(neg(sub(var("price"), c(4.0))));
1189        assert_eq!(from_quins(&to_quins(&e2)).unwrap(), e2);
1190    }
1191
1192    #[test]
1193    fn transcendental_diff_eval_parse_and_quins() {
1194        // d/dx[sin x] = cos x, d/dx[e^x] = e^x, d/dx[ln x] = 1/x, d/dx[tan x] = 1/cos²x —
1195        // checked against a central finite difference of the original (strong test).
1196        for f in [
1197            sin(var("x")),
1198            cos(var("x")),
1199            exp(var("x")),
1200            ln(var("x")),
1201            tan(var("x")),
1202        ] {
1203            let df = simplify(&differentiate(&f, "x"));
1204            for &x in &[0.4, 1.1, 2.3] {
1205                let h = 1e-6;
1206                let fd = (f.eval(&env1("x", x + h)).unwrap() - f.eval(&env1("x", x - h)).unwrap())
1207                    / (2.0 * h);
1208                let sym = df.eval(&env1("x", x)).unwrap();
1209                assert!(
1210                    (sym - fd).abs() < 1e-4,
1211                    "{f}: symbolic {sym} vs fd {fd} at x={x}"
1212                );
1213            }
1214        }
1215        // Inverse-pair simplifications.
1216        assert_eq!(simplify(&ln(exp(var("x")))), var("x"));
1217        assert_eq!(simplify(&exp(ln(var("x")))), var("x"));
1218        assert_eq!(simplify(&sin(c(0.0))), c(0.0));
1219        assert_eq!(simplify(&cos(c(0.0))), c(1.0));
1220        // Parser + Display + quin round-trip on a transcendental expression.
1221        let e = parse("sin(x) + exp(2*x) - ln(x)").unwrap();
1222        assert!(
1223            (e.eval(&env1("x", 1.0)).unwrap() - (1.0_f64.sin() + 2.0_f64.exp() - 1.0_f64.ln()))
1224                .abs()
1225                < 1e-9
1226        );
1227        assert_eq!(from_quins(&to_quins(&e)).unwrap(), e);
1228    }
1229
1230    #[test]
1231    fn citation_hash_is_structural() {
1232        let a = add(var("x"), c(1.0));
1233        let b = add(var("x"), c(1.0));
1234        assert_eq!(expr_citation_hash(&a), expr_citation_hash(&b));
1235        assert_ne!(expr_citation_hash(&a), expr_citation_hash(&var("x")));
1236    }
1237
1238    #[test]
1239    fn sum_of_three_cubes_k42_exact_256bit_vs_f64_catastrophic_cancellation_and_mod9_obstruction() {
1240        // Booker & Sutherland (2019) witness for x^3 + y^3 + z^3 = 42:
1241        let x: i64 = -80_538_738_812_075_974;
1242        let y: i64 = 80_435_758_145_817_515;
1243        let z: i64 = 12_602_123_297_335_631;
1244
1245        // 1. Naive IEEE-754 f64 evaluation loses ~117 bits of precision on ~170-bit cubes:
1246        let f64_sum = (x as f64).powi(3) + (y as f64).powi(3) + (z as f64).powi(3);
1247        assert_ne!(
1248            f64_sum, 42.0,
1249            "IEEE-754 f64 must fail to resolve 42 at 10^51 scale (got {f64_sum})"
1250        );
1251
1252        // 2. Exact zero-heap 256-bit stack-limb verifier proves x^3 + y^3 + z^3 == 42:
1253        assert_eq!(verify_sum_of_three_cubes_exact(x, y, z, 42), Ok(true));
1254        assert_eq!(verify_sum_of_three_cubes_exact(x, y, z + 1, 42), Ok(false));
1255
1256        // 3. Mod-9 algebraic obstruction (k ≡ ±4 mod 9 => rem_euclid(9) in {4, 5}):
1257        for obstructed_k in [4, 5, 13, 14, -4, -5, -13, -14] {
1258            assert!(
1259                has_sum_of_three_cubes_mod9_obstruction(obstructed_k),
1260                "k={obstructed_k} must trigger mod 9 obstruction"
1261            );
1262            assert_eq!(
1263                verify_sum_of_three_cubes_exact(x, y, z, obstructed_k),
1264                Ok(false)
1265            );
1266        }
1267        assert!(!has_sum_of_three_cubes_mod9_obstruction(42));
1268        assert!(!has_sum_of_three_cubes_mod9_obstruction(3));
1269        assert!(!has_sum_of_three_cubes_mod9_obstruction(-42));
1270    }
1271
1272    #[test]
1273    fn sum_of_three_cubes_quins_postorder_and_divisor_discriminant_and_rns_4prime() {
1274        // Encode x^3 + y^3 + z^3 - 42 as post-order Vec<NQuin> with 5-field parity:
1275        let expr_42 = sum_of_three_cubes_expr(42);
1276        let quins = sum_of_three_cubes_quins(42);
1277        assert!(quins.iter().all(|q| q.verify_ecc_parity()));
1278        let decoded = from_quins(&quins).expect("decode post-order CAS quins");
1279        assert_eq!(decoded, expr_42);
1280
1281        // Enforce child_idx < current_idx in from_quins (reject self-loop / forward reference):
1282        let mut cyclic = quins.clone();
1283        let last_idx = cyclic.len() - 1;
1284        cyclic[last_idx].object = last_idx as u64;
1285        cyclic[last_idx].recalculate_parity();
1286        assert!(
1287            from_quins(&cyclic).is_err(),
1288            "from_quins must reject cyclic/non-postorder child_idx >= current_idx"
1289        );
1290
1291        // Divisor / discriminant reduction cascade on k = 3: (-5)^3 + 4^3 + 4^3 = -125 + 64 + 64 = 3
1292        // With z = 4: r = 3 - 64 = -61, s = x + y = -1 => q = 61, p = (1 - 61)/3 = -20, D = 1 - 4(-20) = 81 = 9^2
1293        let recovered = reduce_sum_of_three_cubes_divisor_discriminant(3, 4, -1)
1294            .expect("divisor/discriminant reduction for k=3, z=4, s=-1");
1295        assert_eq!(recovered, (4, -5));
1296
1297        // Arbitrary-precision Divisor / Discriminant cascade on Booker & Sutherland's k = 42 witness:
1298        let x: i64 = -80_538_738_812_075_974;
1299        let y: i64 = 80_435_758_145_817_515;
1300        let z: i64 = 12_602_123_297_335_631;
1301        assert!(
1302            verify_divisor_discriminant_cascade_bigint(x, y, z, 42).unwrap(),
1303            "k=42 witness must satisfy r = k - z^3 = s*q, 3p = s^2 - q, D = s^2 - 4p = (x - y)^2"
1304        );
1305        assert!(!verify_divisor_discriminant_cascade_bigint(x, y, z + 1, 42).unwrap());
1306
1307        // 4-prime RNS CRT batch verification on k = 42 witness and perturbed non-witness:
1308        assert!(verify_sum_of_three_cubes_rns_4prime(x, y, z, 42));
1309        assert!(!verify_sum_of_three_cubes_rns_4prime(x, y, z + 1, 42));
1310    }
1311}