1use crate::NQuin;
13use std::collections::HashMap;
14
15#[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 Pow(Box<Expr>, i32),
26 Neg(Box<Expr>),
27 Sqrt(Box<Expr>),
29 Exp(Box<Expr>),
31 Ln(Box<Expr>),
33 Sin(Box<Expr>),
34 Cos(Box<Expr>),
35 Tan(Box<Expr>),
37}
38
39pub const CAS_INT_CONST_TAG: &str = "cas:int_const";
41
42pub fn c(v: f64) -> Expr {
45 Expr::Const(v)
46}
47pub fn int_c(v: i64) -> Expr {
49 Expr::Const(v as f64)
50}
51pub fn var(name: &str) -> Expr {
54 Expr::Var(name.to_string())
55}
56pub fn add(a: Expr, b: Expr) -> Expr {
58 Expr::Add(Box::new(a), Box::new(b))
59}
60pub fn sub(a: Expr, b: Expr) -> Expr {
62 Expr::Sub(Box::new(a), Box::new(b))
63}
64pub fn mul(a: Expr, b: Expr) -> Expr {
66 Expr::Mul(Box::new(a), Box::new(b))
67}
68pub fn div(a: Expr, b: Expr) -> Expr {
70 Expr::Div(Box::new(a), Box::new(b))
71}
72pub fn pow(a: Expr, e: i32) -> Expr {
74 Expr::Pow(Box::new(a), e)
75}
76pub fn neg(a: Expr) -> Expr {
78 Expr::Neg(Box::new(a))
79}
80pub fn sqrt(a: Expr) -> Expr {
82 Expr::Sqrt(Box::new(a))
83}
84pub fn exp(a: Expr) -> Expr {
86 Expr::Exp(Box::new(a))
87}
88pub fn ln(a: Expr) -> Expr {
90 Expr::Ln(Box::new(a))
91}
92pub fn sin(a: Expr) -> Expr {
94 Expr::Sin(Box::new(a))
95}
96pub fn cos(a: Expr) -> Expr {
98 Expr::Cos(Box::new(a))
99}
100pub fn tan(a: Expr) -> Expr {
102 Expr::Tan(Box::new(a))
103}
104
105impl Expr {
106 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
151pub 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 Expr::Mul(a, b) => add(
167 mul(differentiate(a, wrt), (**b).clone()),
168 mul((**a).clone(), differentiate(b, wrt)),
169 ),
170 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 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 Expr::Sqrt(a) => div(differentiate(a, wrt), mul(c(2.0), sqrt((**a).clone()))),
186 Expr::Exp(a) => mul(exp((**a).clone()), differentiate(a, wrt)),
188 Expr::Ln(a) => div(differentiate(a, wrt), (**a).clone()),
190 Expr::Sin(a) => mul(cos((**a).clone()), differentiate(a, wrt)),
192 Expr::Cos(a) => mul(neg(sin((**a).clone())), differentiate(a, wrt)),
194 Expr::Tan(a) => div(differentiate(a, wrt), pow(cos((**a).clone()), 2)),
196 }
197}
198
199pub 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
214fn 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), _ => 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), _ => 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), _ => 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(), _ => 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 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), Expr::Ln(inner) => (**inner).clone(), _ => 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), Expr::Exp(inner) => (**inner).clone(), _ => 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(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(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(a),
326 }
327 }
328 }
329}
330
331pub 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)))); 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
347pub 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
368fn 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
381fn 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
394pub 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
425pub fn expr_citation_hash(expr: &Expr) -> u64 {
429 crate::q_hash(&format!("{expr}"))
430}
431
432fn name_tag(kind: &str) -> u64 {
446 crate::q_hash(kind)
447}
448
449fn 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
461fn 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
471fn 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
493pub 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
500pub 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
567pub fn to_quins(expr: &Expr) -> Vec<NQuin> {
569 let mut out = Vec::new();
570 encode(expr, &mut out);
571 out
572}
573
574fn 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
629pub 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
637pub 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
669fn 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 fn peek(&self) -> Option<&Tok> {
737 self.tokens.get(self.pos)
738 }
739 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 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 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 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 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 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 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 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 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 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
883pub 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
893pub 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#[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#[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
961pub 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
998pub 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
1036pub const RNS_CRT_PRIMES_4: [u64; 4] = [
1038 2_147_483_647, 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#[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#[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 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 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 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 assert_eq!(
1134 parse("2 + 3 * 4").unwrap().eval(&HashMap::new()).unwrap(),
1135 14.0
1136 );
1137 let g = parse("sqrt((a + 3))").unwrap();
1139 assert!((g.eval(&env1("a", 1.0)).unwrap() - 2.0).abs() < 1e-12);
1140 assert!(parse("2 +* 3").is_err());
1142 }
1143
1144 #[test]
1145 fn expand_distributes_and_preserves_value() {
1146 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 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 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 assert!(factor_quadratic(1.0, 0.0, 1.0, "x").is_none());
1172 }
1173
1174 #[test]
1175 fn expr_quin_roundtrip() {
1176 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 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 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 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 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 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 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 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 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 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 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 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 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 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}