给它一个数,它找出以该数为解的方程。输入 3.14159…,它告诉你 x = π;输入 7.389…,它告诉你 ln(x) = 2。这就是 RIES(RILYBOT Inverse Equation Solver)——一个”逆向计算器”。
demo:RIES
一、什么是 RIES
普通计算器:输入方程,输出数值。RIES 反过来:输入数值,输出方程。
$ ries 2.5063 2 x = 5 for x = T - 0.0063 {49} x^2 = 2 pi for x = T + 0.000328275 {55} ln(6) x = sqrt(pi)+e for x = T + 2.73037e-05 {93}原始 RIES 由 Robert P. Munafo 用 C 编写,约 25 年前。后来 Maxwell Santoro 用 Rust 重写了 ries-rs,提供了 CLI、Python 绑定和 WASM 浏览器版本。
本文的目标:用纯 JavaScript 实现一个可在 Cloudflare Pages / Vercel 上部署的 RIES,参考 cybcat 的 Demo 实现 的算法架构。
二、算法架构
核心思路
RIES 的搜索不是暴力枚举所有方程对,而是:
- 独立生成 RHS 常量(数字 + π/e/φ + 运算组合),按复杂度递增
- 独立生成 LHS 表达式(含 x 的表达式),按复杂度递增
- 对每个 LHS 在 target 处求值,然后二分查找排序后的 RHS 数组
- 对候选匹配用 Newton 法精化根
这个架构的精髓:把 O(N²) 的方程对枚举变成了 O(N log N) 的二分查找。
与暴力枚举的对比
暴力方式(我最初的实现):
for each LHS expression: ← N 个 for each RHS expression: ← N 个 Newton's method solve() ← O(N²)二分查找方式(Demo 的架构):
1. sort RHS by value ← O(N log N)2. for each LHS: evaluate at target ← O(1) binary search RHS ← O(log N) check ±8 neighborhood ← O(1)当 N = 10000 时,暴力需要 1 亿次 Newton 迭代,二分查找只需要约 10 万次。
三、常量生成器
RHS 常量不包含 x,是纯数值表达式。生成过程按复杂度级别递增:
function generateConstants(settings) { const maxC = [0,7,9,11,13,15,17,19,21,23][settings.level] || 11; const maxExpr = [0,2000,5000,12000,25000,...][settings.level]; const CAP = 500;
// 种子:数字 1-9,常量 π, e, φ for (let i = 1; i <= 9; i++) add({ s: String(i), v: i, c: 1 }); add({ s: 'π', v: Math.PI, c: 2 }); add({ s: 'e', v: Math.E, c: 2 }); add({ s: 'φ', v: (1+Math.sqrt(5))/2, c: 2 });
// 逐层扩展 for (let c = 2; c <= maxC; c++) { const buf = []; // 一元运算:对 c-w 层的表达式施加 for (const op of unOps) { const src = byC.get(c - op.w); if (!src) continue; for (const a of src) buf.push({ s: op.s(a.s), v: op.f(a.v), c }); } // 二元运算:组合互补复杂度层 for (const op of binOps) { for (const [ca, A] of byC) { const cb = c - ca - op.w; if (cb < 1) continue; const B = byC.get(cb); if (!B) continue; for (const a of A.slice(0, CAP)) for (const b of B.slice(0, CAP)) buf.push({ s: op.s(a.s, b.s), v: op.f(a.v, b.v), c }); } } flushLevel(buf, c); // 排序 + 去重 + 截断 }}关键设计:
- per-level cap(
CAP = 500):每层的 byC 数组最多保留 500 个表达式,控制二元组合的迭代量 - 增量收集(
flushLevel):每层独立排序(按复杂度、再按字符串长度),截断到LEVEL_CAP,然后全局去重 - 对象去重(
seen[k] = 1):用普通对象代替 Set,避免 V8 Set 的大小限制
复杂度权重
每个运算符有一个权重,累加得到表达式的总复杂度:
| 运算符 | 权重 | 含义 |
|---|---|---|
+ - | 1 | 加减 |
* / | 1-2 | 乘除 |
^ nrt | 3 | 幂/方根 |
neg | 1 | 取负 |
sq sqrt recip | 2 | 平方/开方/倒数 |
ln exp | 3 | 对数/指数 |
sinπ cosπ | 4 | 三角函数 |
π e φ | 2 | 常量 |
方程 ln(x) = 2 的总复杂度:ln(3) + 2(1) = 5。
四、LHS 生成器
LHS 表达式包含变量 x。生成逻辑与 RHS 类似,但二元运算只组合 LHS 和常量(不组合两个 LHS):
// 二元:LHS op 常量for (const op of binOps) { for (const [ca, A] of byC) { const cb = c - ca - op.w; if (cb < 1) continue; const B = constants.filter(k => k.c === cb); for (const a of A) { for (const b of B.slice(0, CAP_CONST)) { add({ s: op.s(a.s, b.s), c, fn: x => op.f(a.fn(x), b.v) }); if (!op.comm) add({ s: op.s(b.s, a.s), c, fn: x => op.f(b.v, a.fn(x)) }); } } }}LHS 表达式用闭包 fn: x => ... 保存求值函数,这样在 Newton 迭代时可以高效计算。
五、二分查找匹配
核心搜索逻辑:
function equationSearch(constants, lhs, settings) { const sorted = constants.slice().sort((a, b) => a.v - b.v);
for (const f of lhs) { const fv = f.fn(settings.target); // LHS 在 target 处求值 const pos = lowerBound(sorted, fv); // 二分查找最近的 RHS
// 检查 ±8 邻域 for (let j = Math.max(0, pos-8); j < Math.min(sorted.length, pos+9); j++) { const rhs = sorted[j]; const root = refineRoot(f.fn, rhs.v, settings.target); // Newton 精化 const err = Math.abs(root - settings.target); if (err > settings.tol) continue;
// 过滤恒等式(如 x/x = 1) const fv2 = f.fn(settings.target + 1); if (Math.abs(fv2 - fv) < 1e-14) continue;
// 过滤退化方程(如 exp(-x) = 0) if (Math.abs(rhs.v) < 1e-6) continue;
rows.push({ lhs: f.s, rhs: rhs.s, root, err, exact: err < 1e-12, c: f.c + rhs.c }); } } return rows.sort((a, b) => a.exact - b.exact || a.c - b.c || a.err - b.err);}三个过滤器:
- 恒等式过滤:LHS 在
target和target+1处求值相同 → 方程与 x 无关(如x - x = 0) - 退化过滤:RHS 绝对值 < 10⁻⁶ → 无意义方程(如
exp(-x) = 0) - 误差阈值:root 与 target 的距离超过容差 → 匹配太粗糙
六、Newton 法精化
function refineRoot(fn, rhs, target) { let x = target; for (let i = 0; i < 8; i++) { const y = fn(x) - rhs; const h = 1e-6 * Math.max(1, Math.abs(x)); const dy = (fn(x + h) - fn(x - h)) / (2 * h); // 中心差分 if (Math.abs(dy) < 1e-11) break; const nx = x - y / dy; if (Math.abs(nx - x) < 1e-13 * Math.max(1, Math.abs(x))) { x = nx; break; } x = nx; } return x;}8 轮迭代,中心差分求导。收敛条件:相邻迭代差 < 10⁻¹³ × max(1, |x|)。
七、表达式格式化
表达式树格式化为人类可读的中缀表达式,需要正确处理运算符优先级和括号:
function fmt(e) { if (e.type === 'var') return 'x'; if (e.type === 'const') return e.name; if (e.arity === 1) { // 取负:-(a+b) 需要括号,-x 不需要 if (e.op === 'neg') { if (c.arity === 2 && (c.op === '+' || c.op === '-')) return '-(' + inner + ')'; return '-' + inner; } // 函数:sin(x) 总是带括号 return names[e.op] + '(' + inner + ')'; } // 二元:根据优先级决定是否加括号 // ^ 优先级 100, */ 优先级 80, +- 优先级 60}特殊处理:
√(x+1)— 根号内是二元运算时加括号-(x+1)— 取负同理--x→x— 双重取负消去a√b— nrt 运算符显示为 “a次根号b”
八、UI 设计
采用 “Terminal Noir” 暗黑风格:
:root { --bg: #080808; --txt: #d4cdc0; --accent: #018574; /* 深青绿 */ --green: #3fb950; /* exact 标签 */ --red: #e06c60; /* close 标签 */}设计要点:
- CRT 颗粒纹理:SVG feTurbulence 噪声 + CSS repeating-linear-gradient 扫描线
- 字体:Cormorant Garamond(衬线)+ 系统等宽字体
- exact 标签:磷光绿 +
text-shadow辉光 - Solve 按钮:琥珀边框,hover 反色 + glow
- 表格:无框线,仅 hairline 行分隔,equation 左对齐其余右对齐
九、验证结果
用 12 个数学恒等式验证算法正确性:
| 输入值 | 预期恒等式 | RIES 找到的最佳方程 | 耗时 |
|---|---|---|---|
| √e = 1.6487 | x² = e | x = √(e) EXACT {5} | 4.6s |
| π² = 9.8696 | √x = π | x = (π)² EXACT {5} | 6.4s |
| e^π = 23.1407 | ln(x) = π | ln(x) = π EXACT {6} | 6.2s |
| π^e = 22.4592 | — | x = π^e EXACT {8} | 6.1s |
| 1/π = 0.3183 | x·π = 1 | x·π = 1 EXACT {5} | 1.2s |
| ln(π) = 1.1447 | e^x = π | exp(x) = π EXACT {6} | 6.1s |
| √(2π) = 2.5066 | x² = 2π | (x)² = 2·π EXACT {7} | 6.0s |
| π + e = 5.8599 | x-e = π | x-e = π EXACT {6} | 1.3s |
| e·π = 8.5397 | x = e·π | x = e·π EXACT {6} | 1.2s |
| φ² = 2.6180 | x = 1+φ | x = 1+φ EXACT {5} | 6.0s |
| e^(1/e) = 1.4447 | x^e = e | x = e√e EXACT {8} | 6.0s |
| 2^π = 8.8250 | — | x = 2^π EXACT {7} | 6.1s |
亮点:
- φ² 找到了
x = 1+φ——黄金比例恒等式 φ² = φ+1 - e^(1/e) 找到了
x = e√e——即 e^(3/2) 的等价形式 - 1/π 同时给出
x·π = 1和1/(x) = π两种等价形式 - 所有 12 个测试都找到了 EXACT 标记的方程
十、踩坑记录
1. 组合爆炸
最初按 expression size 枚举所有表达式,size 7 时表达式数量达到数百万,直接 OOM。
解决:改为按复杂度级别增量生成,每层独立 cap(LEVEL_CAP = 5000),用 flushLevel 排序 + 截断 + 去重。
2. 二元组合的复杂度计算
ca + cb + op.w 还是 c + op.w - 1?最初的公式错了,导致 π² + e³ 这类表达式永远生成不了。
正确公式:外层循环变量 c 是目标复杂度,内层 cb = c - ca - op.w,生成的表达式复杂度 = ca + cb + op.w = c。
3. byC 数组的 cap 策略
byC 数组(按复杂度分组的表达式)如果不 cap,二元组合的迭代量爆炸。但如果 cap 太紧,重要表达式(如 π²)被挤掉。
解决:cap = 500,按复杂度 + 字符串长度排序(简单表达式优先),确保 (π)²(5 字符)排在 neg(neg(neg(neg(x))))(20 字符)前面。
4. Set 大小限制
V8 的 Set 在超过约 1600 万个条目时抛出 RangeError: Set maximum size exceeded。
解决:改用普通 JavaScript 对象 {} 做去重,seen[key] = 1,无大小限制。
5. 退化方程过滤
exp(-x) = 0 在 x = 29.955 处残差 ~10⁻¹⁴,被误判为 exact。实际上 exp(-x) 永远不等于 0。
解决:RHS 绝对值 < 10⁻⁶ 的方程直接跳过。
6. 恒等式过滤
x/x = 1 对所有 x 成立,不是有意义的方程。
解决:在 target 和 target+1 两处求值 LHS,如果结果相同则跳过。
十一、部署
单个 index.html 文件,零依赖,直接部署:
Cloudflare Pages:推送到 Git 仓库 → Pages → Build output directory 设为 /
Vercel:import 仓库 → 自动识别静态 HTML → Deploy
本地:直接用浏览器打开 index.html
十二、参考
- RIES — Robert P. Munafo 原始 C 实现
- ries-rs — Maxwell Santoro Rust 重写,含 WASM
- cybcat/ries-demo 浏览器版 Demo,本文算法架构参考