简介

oCAS（Open Computer Algebra System）是一个用 Rust 编写的高性能计算机代数系统（CAS），采用 LGPL-3.0-or-later 许可证开源。项目目标是在核心符号计算性能上达到或超越 Symbolica 与 SageMath，同时通过 Python（PyO3）和 C/C++（cbindgen）绑定提供多语言接口。

oCAS 采用分层 crate 架构，从底层 arena 分配器到顶层语言绑定共 13 个 workspace 成员，依赖方向严格向下。所有系数域（任意精度整数/有理数、有限域、实数球、复数、双精度浮点）通过统一的 Domain trait 抽象，多项式代数、Gröbner 基、符号微积分、ODE 求解等模块共享同一表达式基础设施。

版本特性对照表

下表列出 oCAS 各版本的关键新增特性（0.1 → 0.30）：

模块架构

oCAS 由 13 个 crate 组成，依赖关系如下（箭头 A → B 表示 A 依赖 B； ocas-py/ocas-c 还依赖 ocas-eval、ocas-rewrite 等核心 crate， 图中仅示代表边；虚线表示可选依赖）：

graph TD
    CORE["ocas-core<br/>Arena, Fuel, 线程池"]
    DOMAIN["ocas-domain<br/>系数域, 数论, 代数数"]
    POLY["ocas-poly<br/>多项式, 矩阵, Gröbner 基"]
    ATOM["ocas-atom<br/>表达式树 Atom, 张量"]
    PARSE["ocas-parse<br/>解析器"]
    REWRITE["ocas-rewrite<br/>模式匹配, 化简"]
    CALC["ocas-calc<br/>微积分, ODE, 积分"]
    EVAL["ocas-eval<br/>求值, JIT, 数值积分"]
    GPL["ocas-gpl<br/>GPL 后端隔离"]
    TOP["ocas<br/>顶层 crate + prelude"]
    PY["ocas-py<br/>Python 绑定 (PyO3)"]
    C["ocas-c<br/>C/C++ 绑定 (cbindgen)"]
    TESTS["ocas-tests<br/>正确性对比, pytest"]

    DOMAIN --> CORE
    ATOM --> CORE
    EVAL --> CORE
    EVAL --> DOMAIN
    EVAL --> ATOM
    PARSE --> ATOM
    REWRITE --> ATOM
    REWRITE --> PARSE
    CALC --> ATOM
    CALC --> DOMAIN
    CALC --> POLY
    CALC --> REWRITE
    POLY --> DOMAIN
    TOP --> DOMAIN
    TOP --> ATOM
    TOP --> POLY
    TOP --> CALC
    TOP --> EVAL
    TOP --> REWRITE
    TOP --> PARSE
    TOP --> CORE
    TESTS --> TOP
    TOP -.-> PY
    TOP -.-> GPL
    PY --> CALC
    C --> CALC

    style CORE fill:#e8f4fd,stroke:#2196F3
    style DOMAIN fill:#e8f4fd,stroke:#2196F3
    style POLY fill:#fff3e0,stroke:#FF9800
    style ATOM fill:#e8f5e9,stroke:#4CAF50
    style CALC fill:#fce4ec,stroke:#E91E63
    style EVAL fill:#f3e5f5,stroke:#9C27B0
    style TOP fill:#fffde7,stroke:#FDD835
    style PY fill:#efebe9,stroke:#795548
    style C fill:#efebe9,stroke:#795548

crate 一览：

关键特性

• 13 个 crate —— 从 arena 运行时到语言绑定的分层 Rust 架构，依赖严格向下。
• 7 种系数域 —— 任意精度整数/有理数、有限域 $\mathbb{F}_p$、实数球、复数、双精度浮点（DoubleF64 ~31 位）、代数数域 $\mathbb{Q}(\alpha)$ / $\mathrm{GF}(p^d)$。
• 多项式代数 —— 稠密一元/稀疏多元多项式、Karatsuba 乘法、GCD（模 GCD Brown 算法）、多元 GCD、因式分解（Cantor–Zassenhaus + Hensel + Wang EEZ）、代数数域分解（Trager）。
• Gröbner 基 —— Buchberger / F4 / F5 三种算法、FGLM 换序、理想运算（成员/和/积/商/饱和/交集/消元/根式/准素分解）、Hilbert 级数。
• 符号微积分 —— 微分、Taylor 展开、分层积分管线（有理 → Risch → 三角 → 特殊函数 → 启发式 → 未求值形式）。
• ODE 求解 —— 一阶（可分离/线性/Bernoulli/恰当/齐次/积分因子）、二阶（常系数/Cauchy–Euler/降阶/待定系数/参数变易）、幂级数与 Frobenius 级数解、Laplace IVP、2×2 系统。
• 求值引擎 —— 栈式 VM 解释器、SIMD 批量求值（f64x4）、Cranelift JIT（f64/f32）、流式求值（恒定内存）。
• 自动微分 —— 超对偶数 HyperDual<T> 前向模式，一阶及高阶偏导数。
• 张量代数 —— 指标槽、显式缩并、McKay 图同构规范化（1-WL 细化 + 路径不变量剪枝）、Young 投影子。
• 数值积分 —— 自适应蒙特卡洛（Vegas），支持高维定积分。
• 数论 —— BPSW 素性判定、整数分解（试除/Pollard rho/p−1/p+1/ECM）、离散对数（BSGS + Pohlig–Hellman）、Euler φ / Möbius / 除数函数。
• 重写与化简 —— AC 回溯模式匹配、通配符（x__/x___）、不动点化简、fuel 受限化简、可选 egg e-graph 等式饱和。
• 三语言绑定 —— Rust prelude API、Python（PyO3，25 类 + 32 函数）、C/C++（cbindgen，91 个导出 + RAII 包装）。
• 正确性框架 —— 与 SymPy、SageMath、Symbolica 跨多个数学模块的交叉验证（1550 个 #[test]/#[tokio::test] 标注，截至 0.28.0）。
• 可选数值后端 —— GMP/MPFR/FLINT 隐藏在 feature flag 后，GPL 后端隔离在 ocas-gpl。

快速导航

项目状态

oCAS 当前版本为 0.30.0。核心符号引擎、多项式代数、Gröbner 基与代数几何、ODE 求解、JIT 求值、三语言绑定与正确性对比框架已达到功能完备。通往稳定 1.0 的路线见 路线图。

快速上手

本章帮助你在 5 分钟内完成 oCAS 的安装与首次运行。oCAS 0.24 支持 Rust、Python 和 C/C++ 三种语言接口。

系统要求

语言	最低版本	备注
Rust	1.97+ (edition 2024)	推荐通过 rustup 安装
Python	3.10+	使用 pip install 或从源码构建
C/C++	C11 / C++17	需要 cargo 构建 C 库

Rust

安装

在你的 Cargo.toml 中添加 oCAS：

[dependencies]
ocas = "0.24"

如需可选后端，在 features 中开启：

[dependencies]
ocas = { version = "0.24", features = ["gmp", "jit"] }

常用 feature 一览：

完整 feature 列表见 Rust API 参考。

验证安装

创建一个最小项目来确认一切正常：

cargo new ocas-test && cd ocas-test

在 Cargo.toml 中添加依赖：

[dependencies]
ocas = "0.24"

在 src/main.rs 中写入：

use ocas::prelude::*;

fn main() {
    let arena = Arena::new();
    let ctx = AtomArena::new(&arena);
    let expr = parse(&ctx, "x^2 + 2*x + 1").unwrap();
    let d = diff(&ctx, expr, Symbol::new("x"));
    println!("d/dx(x² + 2x + 1) = {}", d);
    // 输出：d/dx(x² + 2x + 1) = 2 + 2*x
}

运行：

cargo run

若输出 2 + 2*x，说明安装成功。

基本用法

符号微分与化简

use ocas::prelude::*;
use ocas::ocas_rewrite::rules::default_rules;

fn main() {
    let arena = Arena::new();
    let ctx = AtomArena::new(&arena);

    // 解析表达式
    let expr = parse(&ctx, "x^2").unwrap();

    // 微分
    let d = diff(&ctx, expr, Symbol::new("x"));
    println!("微分: {}", d);
    // 输出：2*x

    // 化简（默认规则集：恒等元移除、常量折叠）
    let e2 = parse(&ctx, "x + 0 + y*0 + z*1").unwrap();
    let rules = default_rules(&ctx, &());
    let s = simplify(&ctx, e2, &rules, 100);
    println!("化简: {}", s);
    // 输出：x + z
}

多项式运算

use ocas::prelude::*;
use ocas_poly::dense::DenseUnivariatePolynomial;
use ocas_domain::rational::RationalDomain;
use ocas_domain::Rational;

fn main() {
    let domain = RationalDomain;
    // 1 + 2x + x²
    let p = DenseUnivariatePolynomial::from_coeffs(
        domain,
        vec![Rational::new(1, 1), Rational::new(2, 1), Rational::new(1, 1)],
    );
    // 1 + x
    let q = DenseUnivariatePolynomial::from_coeffs(
        domain,
        vec![Rational::new(1, 1), Rational::new(1, 1)],
    );

    let (quot, rem) = p.div_rem(&q).unwrap();
    // DenseUnivariatePolynomial 未实现 Display，直接断言系数
    assert_eq!(quot.coeffs(), &[Rational::new(1, 1), Rational::new(1, 1)]); // 1 + x
    assert_eq!(rem.coeffs(), &[]); // 余 0
}

求解线性方程组

use ocas_calc::solve::solve_linear_rational;

fn main() {
    // 求解 2x + y = 5, x - y = 1
    let a = vec![vec![2, 1], vec![1, -1]];
    let b = vec![5, 1];

    let solution = solve_linear_rational(&a, &b).unwrap();
    println!("x = {}/{}, y = {}/{}",
        solution[0].0, solution[0].1,
        solution[1].0, solution[1].1);
    // 输出：x = 2/1, y = 1/1
}

数论

use ocas_domain::number_theory::{
    is_prime, factor::factor_integer, functions::euler_phi,
};

fn main() {
    println!("is_prime(97) = {}", is_prime(&97.into()));
    // 输出：is_prime(97) = true

    let factors = factor_integer(&360.into());
    println!("360 = {}", factors.iter()
        .map(|(p, e)| format!("{}^{}", p, e))
        .collect::<Vec<_>>()
        .join(" × "));
    // 输出：360 = 2^3 × 3^2 × 5^1

    println!("φ(360) = {}", euler_phi(&360.into()));
    // 输出：φ(360) = 96
}

更多 Rust API 详见：

• 表达式系统 — Arena、Symbol、Atom、模式匹配
• 系数域 — Integer、Rational、FiniteField 等
• 多项式 — 一元/多元多项式、单项式序
• 矩阵 — 行列式、求解、乘法
• 微积分 — diff、integrate、taylor
• 求解器 — 线性方程、丢番图、ODE
• 数论 — 素性、分解、离散对数

Python

安装

pip install ocas

要求 Python ≥ 3.10（使用 PyO3 abi3 稳定 ABI）。

验证安装

python -c "import ocas; e = ocas.Expression('x^2'); print(e.diff('x'))"

若输出 2*x，说明安装成功。如需在 Python 交互环境中验证：

>>> import ocas
>>> e = ocas.Expression("x^2 + 2*x + 1")
>>> e.diff("x")
2 + 2*x
>>> e.simplify()
1 + 2*x + x^2

基本用法

符号微分与化简

import ocas

e = ocas.Expression("x^2")

# 微分
d = e.diff("x")
print(f"微分: {d}")
# 输出：微分: 2*x

# 化简（默认规则集：恒等元移除、常量折叠）
e2 = ocas.Expression("x + 0 + y*0 + z*1")
s = e2.simplify()
print(f"化简: {s}")
# 输出：化简: x + z

多项式运算

import ocas

# 1 + 2x + x²
p = ocas.Polynomial([1, 2, 1])
print(f"次数: {p.degree()}")         # 次数: 2
print(f"p(2) = {p.eval(2)}")         # p(2) = 9

# 多项式 GCD
q = ocas.Polynomial([1, 1])          # 1 + x
g = p.gcd(q)
print(f"gcd = {g}")                   # gcd = 1 + x

# 因式分解
factors = p.factor()
print(f"因式分解: {factors}")         # 因式分解: [(1 + x, 2)]

有限域运算

import ocas

gf5 = ocas.FiniteField(5)
q = ocas.Polynomial([1, 2, 1], domain=gf5)
print(q.eval(3))  # (1 + 6 + 9) mod 5 = 16 mod 5 = 1

矩阵运算

import ocas

m = ocas.Matrix([[1, 2], [3, 4]])
print(f"行列式: {m.determinant()}")       # 行列式: -2
print(f"转置: {(m.transpose()).rows()}")   # 转置: [[1, 3], [2, 4]]
print(f"m × m: {(m @ m).rows()}")          # m × m: [[7, 10], [15, 22]]

数论

import ocas

print(ocas.isprime(97))               # True
print(ocas.factorint(360))             # [("2", 3), ("3", 2), ("5", 1)]
print(ocas.totient(360))               # 96
print(ocas.nextprime(100))             # 101
print(ocas.mobius(30))                 # -1
print(ocas.divisor_count(360))         # 24

ODE 求解

import ocas

e = ocas.Expression("Derivative(y(x), x) + y(x)")  # y' + y = 0

# 分类可用的求解方法
methods = ocas.classify_ode(e, "y", "x")
print(methods)

# 求解 y' + y = 0
sol = ocas.dsolve(e, "y", "x")
print(sol)  # y = C1*exp(-x)

更多 Python API 详见 Python API 参考。

C/C++

构建 C 库

oCAS 的 C 库通过 cargo 构建。从源码仓库克隆并编译：

git clone https://github.com/charleshzh/ocas.git
cd ocas
cargo build -p ocas-c --release

构建产物位于 target/release/：

头文件 ocas.h 位于 ocas-c/include/ 目录。C++ 用户还可以使用同目录下的 ocas.hpp（RAII 包装，覆盖表达式、数论和张量域）。

Windows 用户：推荐使用 MSYS2 MINGW64 环境。详见 在 Windows 上构建。

验证安装

创建一个最小测试文件 test_ocas.c：

#include <stdio.h>
#include "ocas.h"

int main(void) {
    struct ocas_OcasExpr *e = ocas_expr_parse("x^2 + 2*x + 1", NULL);
    if (!e) {
        fprintf(stderr, "解析失败\n");
        return 1;
    }

    struct ocas_OcasExpr *d = ocas_expr_diff(e, "x", NULL);
    char *s = ocas_expr_to_string(d, NULL);
    printf("d/dx(x² + 2x + 1) = %s\n", s);
    /* 输出：d/dx(x² + 2x + 1) = 2 + 2*x */

    ocas_string_free(s);
    ocas_expr_free(d);
    ocas_expr_free(e);
    return 0;
}

编译并运行（以 Linux 为例，调整路径以匹配你的环境）：

# 假设 oCAS 已构建在 /path/to/ocas
gcc test_ocas.c -I/path/to/ocas/ocas-c/include \
    -L/path/to/ocas/target/release -locas_c -lm -ldl -lpthread -o test_ocas
LD_LIBRARY_PATH=/path/to/ocas/target/release ./test_ocas

若输出 2 + 2*x，说明安装成功。

基本用法

符号微分

#include <stdio.h>
#include "ocas.h"

int main(void) {
    struct ocas_OcasExpr *e = ocas_expr_parse("x^2", NULL);
    struct ocas_OcasExpr *d = ocas_expr_diff(e, "x", NULL);

    char *s = ocas_expr_to_string(d, NULL);
    printf("微分: %s\n", s);
    /* 输出：微分: 2*x */

    ocas_string_free(s);
    ocas_expr_free(d);
    ocas_expr_free(e);
    return 0;
}

数论

#include <stdio.h>
#include "ocas.h"

int main(void) {
    char *result;

    /* 素性测试 */
    int prime = ocas_ntheory_isprime("97", NULL);
    printf("is_prime(97) = %s\n", prime ? "true" : "false");
    /* 输出：is_prime(97) = true */

    /* 整数分解 */
    result = ocas_ntheory_factorint("360", NULL);
    printf("360 = %s\n", result);
    /* 输出：360 = 2:3,3:2,5:1 */
    ocas_string_free(result);

    /* Euler φ 函数 */
    result = ocas_ntheory_totient("360", NULL);
    printf("φ(360) = %s\n", result);
    /* 输出：φ(360) = 96 */
    ocas_string_free(result);

    return 0;
}

C++ RAII 包装

如果你使用 C++，可以利用 ocas.hpp 中的 RAII 包装避免手动管理内存：

#include <iostream>
#include "ocas.h"
#include "ocas.hpp"

int main() {
    ocas::Expression e("x^2 + 2*x + 1");
    auto d = e.diff("x");
    std::cout << "d/dx = " << d.to_string() << std::endl;
    // 输出：d/dx = 2 + 2*x

    // 数论（无需手动 free）
    std::cout << "is_prime(97) = " << ocas::ntheory::isprime("97") << std::endl;
    std::cout << "360 = " << ocas::ntheory::factorint("360") << std::endl;
    std::cout << "φ(360) = " << ocas::ntheory::totient("360") << std::endl;

    return 0;
}

更多 C/C++ API 详见 C/C++ API 参考。

常见问题

Rust 相关

Q：编译很慢怎么办？

oCAS 包含大量泛型代码，首次编译可能较慢。建议：

• 开发时使用 cargo build（dev profile，已对依赖开 opt-level = 3）
• 发布时使用 cargo build --release（启用 LTO）
• 利用 sccache 或 cargo-nextest 加速增量编译

Q：gmp feature 报错找不到 GMP 库？

在 Linux/macOS 上，确保已安装 GMP 开发包：

# Ubuntu/Debian
sudo apt install libgmp-dev

# macOS (Homebrew)
brew install gmp

在 Windows（MSYS2 MINGW64）上：

pacman -S mingw-w64-x86_64-gmp

或使用 system-libs feature 链接系统预装库。详见 在 Windows 上构建。

Q：flint feature 在 Windows 上不可用？

上游 flint3-sys 仅支持 POSIX 平台，Windows 上暂不支持 flint feature。

Python 相关

Q：pip install ocas 失败？

确认 Python 版本 ≥ 3.10：

python --version

如需从源码构建：

pip install maturin
maturin develop --release -m ocas-py/Cargo.toml

Q：Python 绑定中的函数名为什么有 py_ 前缀？

部分 Gröbner 函数（如 ocas.py_groebner_basis）保留了 py_ 前缀，这是因为 PyO3 绑定尚未添加 #[pyo3(name=...)] 注解。实际调用时使用带前缀的名称即可。

C/C++ 相关

Q：链接时报 undefined reference？

确保链接顺序正确——libocas_c 放在源文件之后：

gcc test.c -locas_c -lm -ldl -lpthread

并确保 LD_LIBRARY_PATH（Linux）或 PATH（Windows）包含库文件所在目录。

Q：ocas.h 中缺少某些函数？

仓库中附带的 ocas.h 可能不是最新的。构建时 cbindgen 会在 target/release/build/ocas-c-*/out/ 下生成最新的头文件。以该文件为准。

Q：C++ 包装 ocas.hpp 覆盖了哪些功能？

ocas.hpp 目前覆盖三个域：表达式（ocas::Expression）、数论（ocas::ntheory::*）和张量（ocas::tensor::*）。其余域（多项式、Gröbner、ODE 等）需直接使用 C API。

通用问题

Q：数值结果不精确？

默认使用纯 Rust num-bigint 有理数算术，完全精确。若需高精度浮点（区间算术），启用 mpfr feature：

ocas = { version = "0.24", features = ["mpfr"] }

Q：如何查看 oCAS 版本？

cargo metadata --format-version=1 | jq '.packages[] | select(.name=="ocas") | .version'

下一步

• Rust API 参考 — 完整的 Rust 模块、类型与函数文档
• Python API 参考 — 所有 Python 类与函数的详细说明
• C/C++ API 参考 — C 导出函数、C++ RAII 包装、内存管理
• 架构 — oCAS 的整体设计与模块关系
• Gröbner 基实现 — Buchberger / F4 / F5 算法详解
• ODE 求解 — 常微分方程分类与求解方法

架构

oCAS 由 12 个公共 crate（外加用于集成测试与基准测试的 ocas-tests） 组成的 Cargo workspace，层间依赖严格向下。每个 crate 只能依赖更底层的 crate， 不允许反向或循环依赖。

重点模块

ocas-poly::factor — 多项式因式分解，使用 Hensel 提升与有限域技术。 支持无平方因子分解以及整数域与有理数域上的完全因式分解。

ocas-poly::groebner — Gröbner 基计算，提供三种算法：Buchberger、F4（生产默认）和 F5（基于签名）。支持可配置的单项式序（Lex、Grevlex、WeightOrder、BlockOrder）以及零维理想的 FGLM 转换。

ocas-poly::roots — 单变量多项式实根隔离。

ocas-tests::correctness — 交叉验证框架，包含 201 项 #[test] 测试，覆盖 19 个数学模块（截至 0.24.0），将 oCAS 结果与 SymPy、SageMath、Symbolica 进行对比。

完整设计文档见仓库中的 ARCHITECTURE_CN.md。

Rust API 参考

oCAS 的 Rust API 采用分层 crate 架构，顶层 ocas crate 通过 prelude 模块统一导出所有常用类型和函数。用户只需一行导入即可开始使用：

#![allow(unused)]
fn main() {
use ocas::prelude::*;
}

模块层级

graph TD
    OC["ocas<br/>顶层统一入口 + prelude"]
    CORE["ocas-core<br/>Arena、错误、燃料"]
    DOMAIN["ocas-domain<br/>系数域、数论、代数数域"]
    ATOM["ocas-atom<br/>表达式树、张量"]
    PARSE["ocas-parse<br/>字符串解析"]
    POLY["ocas-poly<br/>多项式、矩阵、Gröbner 基"]
    REWRITE["ocas-rewrite<br/>模式匹配、化简、重写"]
    CALC["ocas-calc<br/>微积分、ODE、求解器"]
    EVAL["ocas-eval<br/>求值器、JIT、数值积分"]

    OC --> CORE
    OC --> DOMAIN
    OC --> ATOM
    OC --> PARSE
    OC --> POLY
    OC --> REWRITE
    OC --> CALC
    OC --> EVAL

    ATOM --> CORE
    ATOM --> DOMAIN
    PARSE --> CORE
    PARSE --> ATOM
    POLY --> CORE
    POLY --> DOMAIN
    REWRITE --> CORE
    REWRITE --> ATOM
    REWRITE --> PARSE
    CALC --> CORE
    CALC --> DOMAIN
    CALC --> ATOM
    CALC --> POLY
    CALC --> REWRITE
    EVAL --> CORE
    EVAL --> ATOM
    EVAL --> DOMAIN

    style OC fill:#4a9eff,stroke:#2d7ad4,color:#fff
    style CORE fill:#6c757d,stroke:#545b62,color:#fff
    style DOMAIN fill:#28a745,stroke:#1e7e34,color:#fff
    style ATOM fill:#17a2b8,stroke:#117a8b,color:#fff
    style PARSE fill:#6f42c1,stroke:#59359a,color:#fff
    style POLY fill:#fd7e14,stroke:#ca6510,color:#fff
    style REWRITE fill:#e83e8c,stroke:#b82d6e,color:#fff
    style CALC fill:#20c997,stroke:#17a085,color:#fff
    style EVAL fill:#ffc107,stroke:#d39e00,color:#333

prelude 导入内容清单

use ocas::prelude::* 导入以下所有项。同时也可通过 ocas::TypeName 直接访问最常用的类型。

表达式树

系数域

多项式

矩阵

Gröbner 基

微积分

求解器

重写与化简

求值与 JIT

数值积分

自动微分

张量

运行时

Feature Flags 速查表

在 Cargo.toml 中通过 features 启用可选后端和加速功能：

[dependencies]
ocas = { version = "0.24", features = ["gmp", "jit"] }

提示：default = []，所有后端默认关闭以保持最大可移植性（包括 Windows MSVC）。推荐开发配置：features = ["gmp", "jit"]。

子页面索引

快速开始

use ocas::prelude::*;
use ocas_core::arena::Arena;

fn main() {
    // 1. 创建 arena 和表达式上下文
    let arena = Arena::new();
    let ctx = AtomArena::new(&arena);

    // 2. 构造表达式 sin(x)
    let x = ctx.var("x");
    let expr = ctx.fun("sin", &[x]);

    // 3. 符号微分（diff 接受 Symbol 作为求导变量）
    let deriv = diff(&ctx, expr, Symbol::new("x"));
    assert_eq!(deriv.to_string(), "cos(x)");

    // 4. 化简（空规则集保持表达式不变）
    let simplified = simplify(&ctx, expr, &[], 100);
    assert_eq!(simplified.to_string(), "sin(x)");

    println!("d/dx sin(x) = {}", deriv);
}

参见

• 架构概览 — 整体设计与数据流
• 数学基础总览 — 背景数学知识与学习路径
• Python API 参考 — Python 绑定
• C/C++ API 参考 — C/C++ 绑定

Rust API 参考：表达式系统

本章记录 oCAS 表达式系统的核心类型与函数，涵盖 Arena 分配器、符号、表达式节点、构造上下文、解析、规范化以及模式匹配。

核心类型概览

表达式系统的核心类型层次如下：

Arena (bump 分配器)
 └── AtomArena (hash-consing 构造器)
      └── Atom (Copy 句柄)
           └── AtomNode (enum: Num/Var/Fun/Add/Mul/Pow)
                └── Symbol (interned 字符串)

设计不变量：Atom 是一个 Copy 的 Arena 句柄，指向 Arena 中分配的 AtomNode。由于 AtomArena 使用 hash-consing（相同结构的子表达式在同一个 AtomArena 中返回同一个指针），结构相等等价于指针相等——== 的结果与指针比较一致。注意实现细节：Atom 的 PartialEq 是派生的结构比较（递归比较 AtomNode），hash-consing 保证其真值与指针相等一致，而非直接比较指针。减法和除法在解析时脱糖：$x - y$ 变为 Add([x, Mul([Num(-1), y])])，$x / y$ 变为 Mul([x, Pow(y, Num(-1))])。

Arena

#![allow(unused)]
fn main() {
use ocas_core::arena::Arena;
}

Arena 是 bump 分配器，为表达式节点提供批量内存管理。所有表达式节点分配在 Arena 中，Arena 销毁时一次性释放全部内存。当前版本不运行析构函数，因此仅安全存储 Copy 类型。

Arena::new

#![allow(unused)]
fn main() {
pub fn new() -> Self
}

功能：创建使用默认块大小（64 KiB）的 Arena。

参数：无。

返回值：Arena。

示例：

#![allow(unused)]
fn main() {
use ocas_core::arena::Arena;

let arena = Arena::new();
let value = arena.allocate_with(|| 42);
assert_eq!(*value, 42);
}

Arena::with_capacity

#![allow(unused)]
fn main() {
pub fn with_capacity(block_size: usize) -> Self
}

功能：创建使用指定块大小的 Arena。

参数：

返回值：Arena。

Arena::allocate_with

#![allow(unused)]
fn main() {
pub fn allocate_with<T>(&self, init: impl FnOnce() -> T) -> &mut T
}

功能：在 Arena 中分配一个值，通过闭包构造，返回与 Arena 生命周期绑定的可变引用。

参数：

返回值：&mut T。

错误：若 T 的大小为零则 panic。

示例：

#![allow(unused)]
fn main() {
use ocas_core::arena::Arena;

let arena = Arena::new();
let value = arena.allocate_with(|| "hello");
assert_eq!(*value, "hello");
}

Arena::allocate_slice

#![allow(unused)]
fn main() {
pub fn allocate_slice<T: Copy>(&self, values: &[T]) -> &[T]
}

功能：将一个切片复制到 Arena 中，返回与 Arena 生命周期绑定的切片引用。空切片返回 &[]。

参数：

返回值：&[T]。

示例：

#![allow(unused)]
fn main() {
use ocas_core::arena::Arena;

let arena = Arena::new();
let data = [1, 2, 3];
let slice = arena.allocate_slice(&data);
assert_eq!(slice, &[1, 2, 3]);
}

Arena::reset

#![allow(unused)]
fn main() {
pub fn reset(&self)
}

功能：重置 Arena——保留第一个内存块并重置偏移量，释放其余块。重置后，之前分配的任何引用不得继续使用。

参数：无。

返回值：无。

示例：

#![allow(unused)]
fn main() {
use ocas_core::arena::Arena;

let arena = Arena::new();
let _ = arena.allocate_with(|| 1);
arena.reset();
let value = arena.allocate_with(|| 2);
assert_eq!(*value, 2);
}

Arena::chunk_count

#![allow(unused)]
fn main() {
pub fn chunk_count(&self) -> usize
}

功能：返回 Arena 当前持有的内存块数量。

参数：无。

返回值：usize。

Symbol

#![allow(unused)]
fn main() {
use ocas_atom::Symbol;
}

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct Symbol(&'static str);
}

Symbol 是全局 interned 的符号名称，用于变量名、函数名和常量名。相同内容的 Symbol 在进程中指向同一块静态内存，比较为 $O(1)$ 指针比较。Symbol 实现了 Copy。

Symbol::new

#![allow(unused)]
fn main() {
pub fn new(name: &str) -> Self
}

功能：创建或查找一个已存在的 Symbol。首次调用时 intern 字符串，后续调用返回已有的 Symbol。

参数：

返回值：Symbol。

示例：

#![allow(unused)]
fn main() {
use ocas_atom::Symbol;

let x = Symbol::new("x");
let also_x = Symbol::new("x");
assert_eq!(x, also_x);
assert_eq!(x.as_str(), "x");
}

Symbol::as_str

#![allow(unused)]
fn main() {
pub fn as_str(&self) -> &str
}

功能：返回符号的字符串切片。

参数：无。

返回值：&str。

参见：Atom、AtomArena

Atom

#![allow(unused)]
fn main() {
use ocas_atom::Atom;
}

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct Atom<'a>(&'a AtomNode<'a>);
}

Atom 是指向 Arena 中 AtomNode 的轻量 Copy 句柄。复制 Atom 仅复制一个指针，不复制底层数据。由于 hash-consing，a == b 的真值与指针比较一致（同一 AtomArena 内）；其实现是派生的结构比较。

Atom 实现了 Display，输出格式为：

• Num(42) → 42
• Var("x") → x
• Fun("sin", [x]) → sin(x)
• Add([x, y]) → x + y（子表达式若非叶子节点则加括号）
• Mul([x, y]) → x*y
• Pow(x, n) → x^n（底数/指数若非叶子则加括号）

Atom::node

#![allow(unused)]
fn main() {
pub fn node(&self) -> &'a AtomNode<'a>
}

功能：获取底层节点数据的引用。用于模式匹配表达式结构。

参数：无。

返回值：&'a AtomNode<'a>。

示例：

#![allow(unused)]
fn main() {
use ocas_atom::{AtomArena, AtomNode};
use ocas_core::arena::Arena;

let arena = Arena::new();
let ctx = AtomArena::new(&arena);
let x = ctx.var("x");
assert!(matches!(x.node(), AtomNode::Var(_)));
}

Atom::children

#![allow(unused)]
fn main() {
pub fn children(&self) -> &'a [Atom<'a>]
}

功能：返回直接子表达式的切片（从左到右）。Num 和 Var 返回空切片；Fun、Add、Mul 返回参数切片；Pow 返回空切片（需使用 binary_children 获取两个操作数）。

参数：无。

返回值：&'a [Atom<'a>]。

示例：

#![allow(unused)]
fn main() {
use ocas_atom::AtomArena;
use ocas_core::arena::Arena;

let arena = Arena::new();
let ctx = AtomArena::new(&arena);
let x = ctx.var("x");
let y = ctx.var("y");
let sum = ctx.add(&[x, y, ctx.num(1)]);
assert_eq!(sum.children().len(), 3);
assert_eq!(x.children().len(), 0);
}

Atom::binary_children

#![allow(unused)]
fn main() {
pub fn binary_children(&self) -> Option<(Atom<'a>, Atom<'a>)>
}

功能：若此 Atom 是 Pow 节点，返回 (base, exp)；否则返回 None。

参数：无。

返回值：Option<(Atom<'a>, Atom<'a>)>。

示例：

#![allow(unused)]
fn main() {
use ocas_atom::AtomArena;
use ocas_core::arena::Arena;

let arena = Arena::new();
let ctx = AtomArena::new(&arena);
let x = ctx.var("x");
let y = ctx.var("y");
let power = ctx.pow(x, y);
let (base, exp) = power.binary_children().unwrap();
assert_eq!(base.to_string(), "x");
assert_eq!(exp.to_string(), "y");
}

参见：Atom::children、AtomNode

AtomNode

#![allow(unused)]
fn main() {
use ocas_atom::AtomNode;
}

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub enum AtomNode<'a> {
    Num(i64),
    Var(Symbol),
    Fun(Symbol, &'a [Atom<'a>]),
    Add(&'a [Atom<'a>]),
    Mul(&'a [Atom<'a>]),
    Pow(Atom<'a>, Atom<'a>),
}
}

表达式树中每个节点的具化数据。Atom 句柄通过 node() 方法获取 AtomNode 引用。

变体说明

设计说明：

• 减法/除法在解析时脱糖：$x - y$ 变为 Add([x, Mul([Num(-1), y])])，$x / y$ 变为 Mul([x, Pow(y, Num(-1))])。AST 中不存在独立的减法/除法节点。
• Add 和 Mul 的参数列表通过 normalize 后是排序的，确保结构相等的表达式产生相同的 AST。

示例：

#![allow(unused)]
fn main() {
use ocas_atom::{AtomArena, AtomNode};
use ocas_core::arena::Arena;

let arena = Arena::new();
let ctx = AtomArena::new(&arena);
let x = ctx.var("x");
match x.node() {
    AtomNode::Var(s) => assert_eq!(s.as_str(), "x"),
    _ => panic!("expected variable"),
}
}

参见：Atom、Symbol

AtomArena

#![allow(unused)]
fn main() {
use ocas_atom::AtomArena;
}

#![allow(unused)]
fn main() {
pub struct AtomArena<'a> {
    arena: &'a Arena,
    cons_table: RefCell<FastHashMap<AtomNode<'a>, Atom<'a>>>,
}
}

AtomArena 是构造 Atom 的唯一入口。它封装了一个 Arena 引用和一个 hash-consing 表（内部可变性通过 RefCell 实现）。所有构造方法从调用者角度看是不可变的。相同结构的子表达式在同一个 AtomArena 中始终返回同一个 Atom 句柄——这使得结构相等等价于指针相等。

AtomArena::new

#![allow(unused)]
fn main() {
pub fn new(arena: &'a Arena) -> Self
}

功能：创建以给定 Arena 为后端的 AtomArena。

参数：

返回值：AtomArena<'a>。

示例：

#![allow(unused)]
fn main() {
use ocas_atom::AtomArena;
use ocas_core::arena::Arena;

let arena = Arena::new();
let ctx = AtomArena::new(&arena);
let n = ctx.num(42);
assert_eq!(n.to_string(), "42");
}

AtomArena::num

#![allow(unused)]
fn main() {
pub fn num(&self, value: i64) -> Atom<'a>
}

功能：创建整数字面量 Atom。

参数：

返回值：Atom<'a>——Num(value) 节点。

示例：

#![allow(unused)]
fn main() {
use ocas_atom::AtomArena;
use ocas_core::arena::Arena;

let arena = Arena::new();
let ctx = AtomArena::new(&arena);
let n = ctx.num(7);
assert_eq!(n.to_string(), "7");
}

AtomArena::var

#![allow(unused)]
fn main() {
pub fn var(&self, name: &str) -> Atom<'a>
}

功能：创建变量 Atom。

参数：

返回值：Atom<'a>——Var(Symbol) 节点。

示例：

#![allow(unused)]
fn main() {
use ocas_atom::AtomArena;
use ocas_core::arena::Arena;

let arena = Arena::new();
let ctx = AtomArena::new(&arena);
let x = ctx.var("x");
assert_eq!(x.to_string(), "x");
}

AtomArena::fun

#![allow(unused)]
fn main() {
pub fn fun(&self, name: &str, args: &[Atom<'a>]) -> Atom<'a>
}

功能：创建函数应用 Atom。

参数：

返回值：Atom<'a>——Fun(Symbol, &[Atom]) 节点。

示例：

#![allow(unused)]
fn main() {
use ocas_atom::AtomArena;
use ocas_core::arena::Arena;

let arena = Arena::new();
let ctx = AtomArena::new(&arena);
let x = ctx.var("x");
let f = ctx.fun("sin", &[x]);
assert_eq!(f.to_string(), "sin(x)");
}

AtomArena::add

#![allow(unused)]
fn main() {
pub fn add(&self, args: &[Atom<'a>]) -> Atom<'a>
}

功能：创建加法 Atom。

参数：

返回值：Atom<'a>——Add(&[Atom]) 节点。

示例：

#![allow(unused)]
fn main() {
use ocas_atom::AtomArena;
use ocas_core::arena::Arena;

let arena = Arena::new();
let ctx = AtomArena::new(&arena);
let x = ctx.var("x");
let y = ctx.var("y");
let sum = ctx.add(&[x, y]);
assert_eq!(sum.to_string(), "x + y");
}

AtomArena::mul

#![allow(unused)]
fn main() {
pub fn mul(&self, args: &[Atom<'a>]) -> Atom<'a>
}

功能：创建乘法 Atom。

参数：

返回值：Atom<'a>——Mul(&[Atom]) 节点。

示例：

#![allow(unused)]
fn main() {
use ocas_atom::AtomArena;
use ocas_core::arena::Arena;

let arena = Arena::new();
let ctx = AtomArena::new(&arena);
let x = ctx.var("x");
let y = ctx.var("y");
let product = ctx.mul(&[x, y]);
assert_eq!(product.to_string(), "x*y");
}

AtomArena::pow

#![allow(unused)]
fn main() {
pub fn pow(&self, base: Atom<'a>, exp: Atom<'a>) -> Atom<'a>
}

功能：创建幂运算 Atom。

参数：

返回值：Atom<'a>——Pow(base, exp) 节点。

示例：

#![allow(unused)]
fn main() {
use ocas_atom::AtomArena;
use ocas_core::arena::Arena;

let arena = Arena::new();
let ctx = AtomArena::new(&arena);
let x = ctx.var("x");
let p = ctx.pow(x, ctx.num(3));
assert_eq!(p.to_string(), "x^3");
}

AtomArena::slice

#![allow(unused)]
fn main() {
pub fn slice(&self, atoms: &[Atom<'a>]) -> &'a [Atom<'a>]
}

功能：将 Atom 切片分配到 Arena 中并返回引用。用于需要共享 Arena 生命周期的多结果场景（如 ODE 系统的分量解）。

参数：

返回值：&'a [Atom<'a>]。

参见：Arena、Atom

函数

parse

#![allow(unused)]
fn main() {
use ocas_parse::parse;
}

#![allow(unused)]
fn main() {
pub fn parse<'a>(ctx: &'a AtomArena<'a>, input: &str) -> Result<Atom<'a>, ParseError>
}

功能：将数学表达式字符串解析为 Atom 树。支持整数、变量、函数调用（f(x)）、加减乘除幂运算和括号。减法脱糖为加法+负系数，除法脱糖为乘法+负指数。

参数：

返回值：Result<Atom<'a>, ParseError>。

错误：

示例：

#![allow(unused)]
fn main() {
use ocas_atom::AtomArena;
use ocas_core::arena::Arena;
use ocas_parse::parse;

let arena = Arena::new();
let ctx = AtomArena::new(&arena);
let expr = parse(&ctx, "x^2 + 2*x + 1").unwrap();
assert_eq!(expr.to_string(), "((x^2) + (2*x)) + 1");
}

参见：normalize

normalize

#![allow(unused)]
fn main() {
use ocas_atom::normalize::normalize;
}

#![allow(unused)]
fn main() {
pub fn normalize<'a>(ctx: &AtomArena<'a>, atom: Atom<'a>) -> Atom<'a>
}

功能：将表达式规范化为确定性标准形式。具体操作：

• 展平嵌套的 Add 和 Mul（如 Add([Add([x, y]), z]) → Add([x, y, z])）
• 对操作数排序
• 合并数值系数（如 Add([x, Num(2), Num(3)]) → Add([Num(5), x])）

结果分配在与输入相同的 arena 中。

参数：

返回值：Atom<'a>——规范化后的表达式。

示例：

#![allow(unused)]
fn main() {
use ocas_atom::normalize::normalize;
use ocas_atom::AtomArena;
use ocas_core::arena::Arena;

let arena = Arena::new();
let ctx = AtomArena::new(&arena);
let x = ctx.var("x");
let y = ctx.var("y");
let z = ctx.var("z");
let inner = ctx.add(&[x, y]);
let outer = ctx.add(&[inner, z, ctx.num(2), ctx.num(3)]);
let result = normalize(&ctx, outer);
assert_eq!(result.to_string(), "5 + x + y + z");
}

参见：parse、transform

substitute

#![allow(unused)]
fn main() {
use ocas_calc::series::substitute;
}

#![allow(unused)]
fn main() {
pub fn substitute<'a>(
    ctx: &'a AtomArena<'a>,
    expr: Atom<'a>,
    var: Symbol,
    replacement: Atom<'a>,
) -> Atom<'a>
}

功能：将表达式中所有出现的变量 var 替换为 replacement。基于 transform 实现的便捷函数。

参数：

返回值：Atom<'a>——替换后的表达式。

示例：

#![allow(unused)]
fn main() {
use ocas_atom::{AtomArena, Symbol};
use ocas_calc::series::substitute;
use ocas_core::arena::Arena;

let arena = Arena::new();
let ctx = AtomArena::new(&arena);
let x = ctx.var("x");
let y = ctx.var("y");
let expr = ctx.add(&[ctx.pow(x, ctx.num(2)), ctx.num(1)]);
let result = substitute(&ctx, expr, Symbol::new("x"), y);
assert_eq!(result.to_string(), "(y^2) + 1");
}

参见：transform

transform

#![allow(unused)]
fn main() {
use ocas_rewrite::transform;
}

#![allow(unused)]
fn main() {
pub fn transform<'a, F>(ctx: &'a AtomArena<'a>, atom: Atom<'a>, mut f: F) -> Atom<'a>
where
    F: FnMut(Atom<'a>) -> Option<Atom<'a>>,
}

功能：自底向上遍历表达式树并对每个节点应用变换函数 f。f 在子节点已被变换之后调用。返回 Some(atom) 替换原节点，返回 None 保留原节点（已变换子节点的版本）。这是 oCAS 规则引擎和化简器使用的标准重写遍历模式。

参数：

返回值：Atom<'a>——变换后的表达式。

示例：

#![allow(unused)]
fn main() {
use ocas_atom::{Atom, AtomArena, AtomNode};
use ocas_core::arena::Arena;
use ocas_rewrite::transform;

let arena = Arena::new();
let ctx = AtomArena::new(&arena);
let x = ctx.var("x");
let y = ctx.var("y");
let sum = ctx.add(&[x, y]);

let result = transform(&ctx, sum, |a| {
    if let AtomNode::Add(args) = a.node() {
        if args.len() == 2 && args[0] == x && args[1] == y {
            return Some(ctx.add(&[y, x]));
        }
    }
    None
});

assert_eq!(result.to_string(), "y + x");
}

参见：substitute、normalize

collect_funs

#![allow(unused)]
fn main() {
use ocas_atom::walk::collect_funs;
}

#![allow(unused)]
fn main() {
pub fn collect_funs<'a>(atom: Atom<'a>) -> Vec<(Symbol, Atom<'a>)>
}

功能：收集表达式中所有函数应用，按后序（最内层优先）返回，去重（hash-consing 保证结构相同的应用只出现一次）。

参数：

返回值：Vec<(Symbol, Atom<'a>)>——(函数名, 函数应用节点) 列表。

示例：

#![allow(unused)]
fn main() {
use ocas_atom::{AtomArena, walk::collect_funs};
use ocas_core::arena::Arena;

let arena = Arena::new();
let ctx = AtomArena::new(&arena);
let x = ctx.var("x");
let sin_x = ctx.fun("sin", &[x]);
let expr = ctx.fun("cos", &[sin_x]);
let funs = collect_funs(expr);
assert_eq!(funs.len(), 2);
assert_eq!(funs[0].0.as_str(), "sin");
assert_eq!(funs[1].0.as_str(), "cos");
}

参见：collect_vars

collect_vars

#![allow(unused)]
fn main() {
use ocas_atom::walk::collect_vars;
}

#![allow(unused)]
fn main() {
pub fn collect_vars(atom: Atom) -> Vec<Symbol>
}

功能：收集表达式中所有不同的变量名，按首次出现顺序（深度优先、从左到右）返回。

参数：

返回值：Vec<Symbol>——变量名列表。

示例：

#![allow(unused)]
fn main() {
use ocas_atom::{AtomArena, walk::collect_vars};
use ocas_core::arena::Arena;

let arena = Arena::new();
let ctx = AtomArena::new(&arena);
let x = ctx.var("x");
let y = ctx.var("y");
let expr = ctx.add(&[ctx.mul(&[x, y]), x]);
let vars = collect_vars(expr);
assert_eq!(vars.len(), 2);
assert_eq!(vars[0].as_str(), "x");
assert_eq!(vars[1].as_str(), "y");
}

参见：collect_funs

模式匹配

模式匹配系统允许用带通配符的模式（Pattern）匹配 Atom 表达式树，支持结合律/交换律（AC）匹配和回溯预算控制。

Pattern

#![allow(unused)]
fn main() {
use ocas_rewrite::pattern::Pattern;
}

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub enum Pattern<'a> {
    Literal(Atom<'a>),
    Wildcard(Symbol, WildcardLevel),
    Add(Vec<Pattern<'a>>),
    Mul(Vec<Pattern<'a>>),
    Pow(Box<(Pattern<'a>, Pattern<'a>)>),
    Fun(Symbol, Vec<Pattern<'a>>),
}
}

模式镜像了 AtomNode 的结构，但增加通配符节点。Add 和 Mul 的匹配支持结合律-交换律（AC）：模式中的子模式可以匹配参数列表的任意子集。

Pattern::from_atom

#![allow(unused)]
fn main() {
pub fn from_atom(_ctx: &'a impl PatternAlloc<'a>, atom: Atom<'a>) -> Pattern<'a>
}

功能：将 Atom 转换为 Pattern。名称以 _ 结尾（或以 _ 开头）的变量被视为通配符：

• x_ → Wildcard(Symbol("x"), Single)
• x__ → Wildcard(Symbol("x"), Sequence)
• x___ → Wildcard(Symbol("x"), NullSequence)

参数：

返回值：Pattern<'a>。

示例：

#![allow(unused)]
fn main() {
use ocas_atom::AtomArena;
use ocas_core::arena::Arena;
use ocas_rewrite::pattern::{Pattern, WildcardLevel};

let arena = Arena::new();
let ctx = AtomArena::new(&arena);
let x = ctx.var("x_");
let pat = Pattern::from_atom(&(), x);
assert!(matches!(pat, Pattern::Wildcard(s, WildcardLevel::Single) if s.as_str() == "x"));
}

参见：WildcardLevel、match_pattern

WildcardLevel

#![allow(unused)]
fn main() {
use ocas_rewrite::pattern::WildcardLevel;
}

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum WildcardLevel {
    Single,
    Sequence,
    NullSequence,
}
}

通配符的匹配范围。

示例：

#![allow(unused)]
fn main() {
use ocas_rewrite::pattern::WildcardLevel;

assert!(matches!(WildcardLevel::Single, WildcardLevel::Single));
assert!(matches!(WildcardLevel::Sequence, WildcardLevel::Sequence));
assert!(matches!(WildcardLevel::NullSequence, WildcardLevel::NullSequence));
}

match_pattern

#![allow(unused)]
fn main() {
use ocas_rewrite::matcher::match_pattern;
}

#![allow(unused)]
fn main() {
pub fn match_pattern<'a>(pattern: Pattern<'a>, atom: Atom<'a>) -> Result<Bindings<'a>, MatchError>
}

功能：尝试将 pattern 与 atom 匹配，成功时返回绑定集合。使用默认回溯预算（DEFAULT_MAX_BACKTRACKS = 10_000）。Add/Mul 使用 AC 匹配（全回溯搜索），Fun 使用有序匹配（支持序列通配符）。

参数：

返回值：Result<Bindings<'a>, MatchError>。

示例：

#![allow(unused)]
fn main() {
use ocas_atom::{AtomArena, Symbol};
use ocas_core::arena::Arena;
use ocas_rewrite::pattern::{Pattern, WildcardLevel};
use ocas_rewrite::matcher::match_pattern;

let arena = Arena::new();
let ctx = AtomArena::new(&arena);
let x = ctx.var("x");
let sum = ctx.add(&[x, ctx.num(1)]);

let pat = Pattern::Add(vec![
    Pattern::Wildcard(Symbol::new("a"), WildcardLevel::Single),
    Pattern::Literal(ctx.num(1)),
]);
let bindings = match_pattern(pat, sum).unwrap();
}

match_pattern_with_budget

#![allow(unused)]
fn main() {
use ocas_rewrite::matcher::match_pattern_with_budget;
}

#![allow(unused)]
fn main() {
pub fn match_pattern_with_budget<'a>(
    pattern: Pattern<'a>,
    atom: Atom<'a>,
    max_backtracks: usize,
) -> Result<Bindings<'a>, MatchError>
}

功能：与 match_pattern 相同，但允许自定义回溯预算，防止病态输入导致指数时间爆炸。

参数：

返回值：Result<Bindings<'a>, MatchError>。

错误：若回溯次数超限，返回 MatchError::BudgetExhausted。

参见：match_pattern

Bindings

#![allow(unused)]
fn main() {
use ocas_rewrite::matcher::Bindings;
}

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, Default)]
pub struct Bindings<'a> { /* 私有字段 */ }
}

成功匹配后返回的通配符绑定集合。

Bindings::new

#![allow(unused)]
fn main() {
pub fn new() -> Self
}

功能：创建空的绑定集合。

Bindings::get

#![allow(unused)]
fn main() {
pub fn get(&self, name: Symbol) -> Option<&MatchValue<'a>>
}

功能：按通配符名称查找绑定值。

参数：

返回值：Option<&MatchValue<'a>>。

示例：

#![allow(unused)]
fn main() {
use ocas_atom::{AtomArena, Symbol};
use ocas_core::arena::Arena;
use ocas_rewrite::pattern::{Pattern, WildcardLevel};
use ocas_rewrite::matcher::match_pattern;

let arena = Arena::new();
let ctx = AtomArena::new(&arena);
let x = ctx.var("x");
let y = ctx.var("y");
let sum = ctx.add(&[x, y]);

let pat = Pattern::Add(vec![
    Pattern::Wildcard(Symbol::new("a"), WildcardLevel::Single),
    Pattern::Wildcard(Symbol::new("b"), WildcardLevel::Single),
]);
let bindings = match_pattern(pat, sum).unwrap();
let val = bindings.get(Symbol::new("a")).unwrap();
}

MatchValue

#![allow(unused)]
fn main() {
use ocas_rewrite::matcher::MatchValue;
}

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum MatchValue<'a> {
    Single(Atom<'a>),
    Sequence(&'a [Atom<'a>]),
}
}

通配符绑定的值类型。

MatchError

#![allow(unused)]
fn main() {
use ocas_rewrite::matcher::MatchError;
}

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum MatchError {
    NoMatch,
    InconsistentBinding,
    BudgetExhausted,
}
}

模式匹配错误。

参见

• 重写与化简——Rule、simplify、replace_all 等完整重写引擎
• 微积分——diff、integrate、taylor 等基于表达式系统的运算
• 系数域——Domain trait 和各种域类型

Rust API 参考：系数域

系数域是 oCAS 所有多项式、矩阵和求解器算法的基础抽象。每个域描述一组元素及其算术运算，通过 Domain 和 EuclideanDomain trait 统一接口。

模块路径：ocas_domain

导入方式：

#![allow(unused)]
fn main() {
use ocas_domain::{
    Domain, EuclideanDomain,
    Integer, IntegerDomain,
    Rational, RationalDomain,
    FiniteField, FiniteFieldElement,
    RealBall, RealBallDomain,
    Complex, ComplexDomain,
    DoubleF64, DoubleF64Domain,
    AlgebraicExtension, AlgebraicNumberField, AlgebraicElement,
};
use ocas_domain::assumptions::{Assumption, Assumptions, SymbolAssumptions};
}

Domain trait

签名：

#![allow(unused)]
fn main() {
pub trait Domain: Clone + PartialEq + Eq + std::fmt::Debug + Sized {
    type Element: Clone + PartialEq + Eq + std::fmt::Debug + 'static;

    fn zero(&self) -> Self::Element;
    fn one(&self) -> Self::Element;
    fn add(&self, a: &Self::Element, b: &Self::Element) -> Self::Element;
    fn sub(&self, a: &Self::Element, b: &Self::Element) -> Self::Element;
    fn neg(&self, a: &Self::Element) -> Self::Element;
    fn mul(&self, a: &Self::Element, b: &Self::Element) -> Self::Element;
    fn div(&self, a: &Self::Element, b: &Self::Element) -> Option<Self::Element>;
    fn inv(&self, a: &Self::Element) -> Option<Self::Element>;
    fn is_zero(&self, a: &Self::Element) -> bool;
    fn is_one(&self, a: &Self::Element) -> bool;
    fn mul_assign(&self, a: &mut Self::Element, b: &Self::Element);
    fn sub_mul_assign(&self, a: &mut Self::Element, b: &Self::Element, c: &Self::Element);
    fn pow(&self, a: &Self::Element, n: u64) -> Self::Element;
    fn cast_u64(&self, n: u64) -> Self::Element;
}
}

功能：系数域的核心 trait。域对象本身可以携带参数（如有限域的模数），因此所有运算通过 &self 进行。这与 Flint、SymPy Domain 等 CAS 库的"域对象"模式一致。

关联类型：

方法：

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{Domain, Integer, IntegerDomain};

let domain = IntegerDomain;
let a = Integer::from(3);
let b = Integer::from(5);
assert_eq!(domain.add(&a, &b), Integer::from(8));
assert_eq!(domain.mul(&a, &b), Integer::from(15));
assert_eq!(domain.pow(&a, 3), Integer::from(27));
// 输出：所有断言通过
}

参见：EuclideanDomain

EuclideanDomain trait

签名：

#![allow(unused)]
fn main() {
pub trait EuclideanDomain: Domain {
    fn div_rem(&self, a: &Self::Element, b: &Self::Element)
        -> Option<(Self::Element, Self::Element)>;
    fn gcd(&self, a: &Self::Element, b: &Self::Element) -> Self::Element;
    fn extended_gcd(&self, a: &Self::Element, b: &Self::Element)
        -> (Self::Element, Self::Element, Self::Element);
}
}

功能：支持带余除法的欧几里得域。Domain 的扩展，额外提供 div_rem（带余除法）、gcd（最大公因子）和 extended_gcd（扩展欧几里得算法）。

方法：

div_rem

签名：fn div_rem(&self, a: &Self::Element, b: &Self::Element) -> Option<(Self::Element, Self::Element)>

功能：带余除法，返回 (商, 余数)，满足 a = 商 * b + 余数，且 余数 == 0 或 deg(余数) < deg(b)。

参数：

返回值：Some((quotient, remainder))，b 为零时返回 None。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{EuclideanDomain, Integer, IntegerDomain};

let domain = IntegerDomain;
let a = Integer::from(17);
let b = Integer::from(5);
let (q, r) = domain.div_rem(&a, &b).unwrap();
assert_eq!(q, Integer::from(3));
assert_eq!(r, Integer::from(2));
// 输出：17 = 3 × 5 + 2
}

gcd

签名：fn gcd(&self, a: &Self::Element, b: &Self::Element) -> Self::Element

功能：计算最大公因子。默认实现使用欧几里得算法。

返回值：gcd(a, b)。对于域（如 FiniteField），两个非零元素的 GCD 退化为 1。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{EuclideanDomain, Integer, IntegerDomain};

let domain = IntegerDomain;
let a = Integer::from(12);
let b = Integer::from(8);
let g = domain.gcd(&a, &b);
assert_eq!(g, Integer::from(4));
// 输出：gcd(12, 8) = 4
}

extended_gcd

签名：fn extended_gcd(&self, a: &Self::Element, b: &Self::Element) -> (Self::Element, Self::Element, Self::Element)

功能：扩展欧几里得算法，返回 (g, x, y) 满足 g = gcd(a, b) = a * x + b * y。

返回值：三元组 (g, x, y)。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{EuclideanDomain, Integer, IntegerDomain};

let domain = IntegerDomain;
let a = Integer::from(35);
let b = Integer::from(15);
let (g, x, y) = domain.extended_gcd(&a, &b);
// g = 5, x = 1, y = -2，满足 5 = 35×1 + 15×(-2)
assert_eq!(g, Integer::from(5));
}

参见：Domain

Integer / IntegerDomain

IntegerDomain

签名：pub struct IntegerDomain;

功能：整数域 $\mathbb{Z}$，元素类型为 Integer。实现 Domain 和 EuclideanDomain。

特征：

• div 要求精确除法（余数为零），否则返回 None
• inv 仅对 $\pm 1$ 返回结果，其余返回 None
• pow 使用二进制快速幂

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{Domain, EuclideanDomain, Integer, IntegerDomain};

let domain = IntegerDomain;
let a = Integer::from(10);
let b = Integer::from(3);

// 精确除法：10/3 不精确
assert!(domain.div(&a, &b).is_none());

// 带余除法
let (q, r) = domain.div_rem(&a, &b).unwrap();
assert_eq!(q, Integer::from(3));
assert_eq!(r, Integer::from(1));

// 逆元：只有 ±1 有逆
assert!(domain.inv(&Integer::from(1)).is_some());
assert!(domain.inv(&Integer::from(5)).is_none());
// 输出：所有断言通过
}

Integer

签名：pub struct Integer(BigInt);

功能：任意精度整数。默认构建使用 num-bigint 的 BigInt；启用 gmp feature 时使用 GMP 后端。

Derive：Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash

构造与转换

Integer::new

签名：pub fn new<T: Into<BigInt>>(value: T) -> Self

功能：从机器整数或 BigInt 创建任意精度整数。

参数：

示例：

#![allow(unused)]
fn main() {
use ocas_domain::Integer;

let a = Integer::new(42);
let b = Integer::new(100_i64);
assert_eq!(a.to_string(), "42");
// 输出：42
}

Integer::from

签名：impl From<i64> for Integer / impl From<BigInt> for Integer

功能：从 i64 或 BigInt 转换。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::Integer;

let a = Integer::from(42);
assert_eq!(a.to_string(), "42");
// 输出：42
}

访问器

Integer::inner

签名：pub fn inner(&self) -> &BigInt

功能：访问底层 BigInt 引用。

Integer::to_bigint

签名：pub fn to_bigint(&self) -> BigInt

功能：克隆为 BigInt（不论后端）。

Integer::to_i64

签名：pub fn to_i64(&self) -> Option<i64>

功能：尝试转换为 i64。溢出时返回 None。

运算方法

Integer::pow_u32

签名：pub fn pow_u32(&self, exp: u32) -> Self

功能：计算 $n^{exp}$。

参数：

示例：

#![allow(unused)]
fn main() {
use ocas_domain::Integer;

let a = Integer::from(2);
assert_eq!(a.pow_u32(10).to_string(), "1024");
// 输出：1024
}

Integer::modpow

签名：pub fn modpow(&self, exp: &Integer, modulus: &Integer) -> Integer

功能：模幂运算 $self^{exp} \bmod modulus$。

参数：

示例：

#![allow(unused)]
fn main() {
use ocas_domain::Integer;

let base = Integer::from(3);
let exp = Integer::from(100);
let modulus = Integer::from(7);
let result = base.modpow(&exp, &modulus);
assert_eq!(result.to_string(), "4");
// 输出：3^100 mod 7 = 4
}

Integer::mod_floor

签名：pub fn mod_floor(&self, modulus: &Integer) -> Integer

功能：地板模运算，结果 $r$ 满足 $0 \leq r < |modulus|$。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::Integer;

let a = Integer::from(-7);
let m = Integer::from(3);
assert_eq!(a.mod_floor(&m).to_string(), "2");
// 输出：-7 mod_floor 3 = 2
}

Integer::div_rem

签名：pub fn div_rem(&self, other: &Integer) -> (Integer, Integer)

功能：带余除法 (商, 余数)。注意：与 EuclideanDomain::div_rem 不同，此方法不要求 other 非零（行为由底层 BigInt 决定）。

Integer::is_even

签名：pub fn is_even(&self) -> bool

功能：判断是否为偶数。

Integer::is_negative

签名：pub fn is_negative(&self) -> bool

功能：判断是否为负数。

Integer::is_zero

签名：pub fn is_zero(&self) -> bool

功能：判断是否为零。

Integer::is_one

签名：pub fn is_one(&self) -> bool

功能：判断是否为一。

Integer::abs

签名：pub fn abs(&self) -> Integer

功能：绝对值。

Integer::sqrt

签名：pub fn sqrt(&self) -> Integer

功能：整数平方根（向下取整）。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::Integer;

let a = Integer::from(10);
assert_eq!(a.sqrt().to_string(), "3");
// 输出：sqrt(10) = 3
}

运算符

Integer 实现了以下标准运算符 trait（支持所有引用组合：owned × owned、owned × &、& × owned、& × &）：

参见：Domain、Rational、数论函数

Rational / RationalDomain

RationalDomain

签名：pub struct RationalDomain;

功能：有理数域 $\mathbb{Q}$，元素类型为 Rational。实现 Domain 和 EuclideanDomain。

特征：

• div 对所有非零除数精确返回结果
• inv 对所有非零元素返回结果
• EuclideanDomain 的 div_rem 对有理数域退化：余数恒为零

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{Domain, Rational, RationalDomain};

let domain = RationalDomain;
let a = Rational::new(1, 2);
let b = Rational::new(1, 3);
let sum = domain.add(&a, &b);
assert_eq!(sum, Rational::new(5, 6));
// 输出：1/2 + 1/3 = 5/6
}

Rational

签名：pub struct Rational(BigRational);

功能：任意精度有理数。默认构建使用 num-rational 的 BigRational；启用 gmp feature 时使用 GMP 后端。

Derive：Debug, Clone, PartialEq, Eq, Hash

构造

Rational::new

签名：pub fn new(numer: i64, denom: i64) -> Self

功能：从分子和分母（i64）创建有理数。自动约简至最简分数。分母为零时行为由底层库决定。

参数：

示例：

#![allow(unused)]
fn main() {
use ocas_domain::Rational;

let a = Rational::new(3, 6);
assert_eq!(a.to_string(), "1/2");
// 输出：3/6 自动约简为 1/2
}

Rational::from_bigints

签名：pub fn from_bigints(numer: BigInt, denom: BigInt) -> Self

功能：从任意精度整数分子和分母创建有理数。

Rational::from_integer

签名：pub fn from_integer(n: Integer) -> Self

功能：从整数创建有理数（分母 = 1）。

访问器

Rational::inner

签名：pub fn inner(&self) -> &BigRational

功能：访问底层 BigRational 引用。

Rational::numer

签名：pub fn numer(&self) -> Integer

功能：返回分子（作为 Integer）。

Rational::denom

签名：pub fn denom(&self) -> Integer

功能：返回分母（作为 Integer，始终为正）。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::Rational;

let r = Rational::new(3, 4);
assert_eq!(r.numer().to_string(), "3");
assert_eq!(r.denom().to_string(), "4");
// 输出：分子 = 3，分母 = 4
}

运算符

Rational 实现了以下标准运算符 trait：

参见：Domain、Integer

FiniteField / FiniteFieldElement

FiniteField

签名：pub struct FiniteField { /* prime: BigInt, ... */ }

功能：素数有限域 $\mathbb{Z}/p\mathbb{Z}$。算术使用任意精度整数，支持大素数。实现 Domain 和 EuclideanDomain。

构造

FiniteField::new

签名：pub fn new(prime: BigInt) -> Self

功能：以给定素数为模创建有限域。

参数：

错误：debug 模式下若 prime < 2 会 panic。

示例：

#![allow(unused)]
fn main() {
use num_bigint::BigInt;
use ocas_domain::{Domain, FiniteField};

let f = FiniteField::new(BigInt::from(7));
let a = f.element(3);
let b = f.element(5);
assert_eq!(f.add(&a, &b), f.element(1));   // 3 + 5 = 1 (mod 7)
assert_eq!(f.mul(&a, &b), f.element(1));   // 3 × 5 = 1 (mod 7)
// 输出：所有断言通过
}

元素构造

FiniteField::element

签名：pub fn element(&self, value: impl Into<BigInt>) -> FiniteFieldElement

功能：从任意整数创建域元素。值自动规约到 $[0, p-1]$ 范围。

参数：

示例：

#![allow(unused)]
fn main() {
use num_bigint::BigInt;
use ocas_domain::{Domain, FiniteField};

let f = FiniteField::new(BigInt::from(7));
let a = f.element(10);
assert_eq!(a.value().to_string(), "3");
// 输出：10 mod 7 = 3
}

FiniteField::from_i64

签名：pub fn from_i64(&self, val: i64) -> FiniteFieldElement

功能：从 i64 创建域元素（规约 mod p）。

访问器

FiniteField::prime

签名：pub fn prime(&self) -> &BigInt

功能：返回域的模数。

FiniteField::prime_u64

签名：pub fn prime_u64(&self) -> u64

功能：将模数作为 u64 返回。

错误：若素数不适用 u64 表示则 panic。

FiniteField::to_i64

签名：pub fn to_i64(&self, a: &FiniteFieldElement) -> i64

功能：将域元素转换为 i64（范围 $[0, p)$）。

错误：若素数不适用 u64 表示则 panic。

Domain 实现

• div 通过 Fermat 小定理求逆：$a^{-1} \equiv a^{p-2} \pmod{p}$
• inv 同上，零元素返回 None
• pow 使用 modpow 优化（远快于默认二进制幂）

EuclideanDomain 实现

• div_rem：域中除法精确，余数恒为零
• gcd：域中 GCD 退化——两者均为零时返回 0，否则返回 1

参见：Domain、有限域数学基础

FiniteFieldElement

签名：pub struct FiniteFieldElement { value: BigInt }

功能：素数有限域的元素。值始终在 $[0, p-1]$ 范围内。

Derive：Debug, Clone, PartialEq, Eq, Hash

FiniteFieldElement::value

签名：pub fn value(&self) -> &BigInt

功能：返回 $[0, p-1]$ 范围内的标准代表元。

示例：

#![allow(unused)]
fn main() {
use num_bigint::BigInt;
use ocas_domain::FiniteField;

let f = FiniteField::new(BigInt::from(7));
let a = f.element(-3);
assert_eq!(a.value().to_string(), "4");
// 输出：-3 mod 7 = 4
}

参见：FiniteField

RealBall / RealBallDomain

RealBallDomain

签名：pub struct RealBallDomain;

功能：实数球（区间）域。元素类型为 RealBall。仅实现 Domain（不实现 EuclideanDomain，因为实数球不支持精确带余除法）。

注意：默认构建使用轻量 f64 球，适合模板和演示。启用 mpfr feature 后使用 rug::Float 和有向舍入产生严格区间。

RealBall

签名：pub struct RealBall { mid: f64, rad: f64 }（默认构建）

功能：实数球：中点 ± 半径。真实值保证包含在 $[mid - rad, mid + rad]$ 中。

Derive：Debug, Clone, PartialEq, Eq；默认构建额外实现 Copy。

构造

RealBall::new

签名（默认）：pub fn new(mid: f64, rad: f64) -> Self

功能：从中点和半径创建球。半径被钳制为非负。

参数：

RealBall::from_f64

签名：pub fn from_f64(value: f64) -> Self

功能：从 f64 值创建零半径球（精确值）。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::RealBall;

let ball = RealBall::from_f64(3.14);
assert_eq!(ball.mid(), 3.14);
assert_eq!(ball.rad(), 0.0);
// 输出：精确球
}

访问器

RealBall::mid

签名：pub fn mid(&self) -> f64（默认） / pub fn mid(&self) -> &rug::Float（mpfr）

功能：返回中点。

RealBall::rad

签名：pub fn rad(&self) -> f64（默认） / pub fn rad(&self) -> &rug::Float（mpfr）

功能：返回半径。

RealBall::lower

签名：pub fn lower(&self) -> f64（默认） / pub fn lower(&self) -> rug::Float（mpfr）

功能：返回保守下界 $mid - rad$（mpfr 版本使用向下舍入）。

RealBall::upper

签名：pub fn upper(&self) -> f64（默认） / pub fn upper(&self) -> rug::Float（mpfr）

功能：返回保守上界 $mid + rad$（mpfr 版本使用向上舍入）。

RealBall::precision

签名：pub fn precision(&self) -> u32（仅 mpfr feature）

功能：返回 MPFR 后端的精度（位数）。

Domain 实现

• add：$(a \pm r_a) + (b \pm r_b) = (a+b) \pm (r_a + r_b)$（mpfr 版本额外加舍入误差）
• sub：类似加法，半径相加
• mul：四角法——计算四个极端乘积 $a_lo \cdot b_lo$、$a_lo \cdot b_hi$ 等，取最小/最大值得到新区间
• div：$a / b = a \cdot b^{-1}$，当球包含零时返回 None
• inv：$1/(mid \pm rad)$，当球包含零时返回 None

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{Domain, RealBall, RealBallDomain};

let domain = RealBallDomain;
let a = RealBall::from_f64(2.0);
let b = RealBall::from_f64(3.0);
let prod = domain.mul(&a, &b);
assert!(prod.lower() <= 6.0 && 6.0 <= prod.upper());
// 输出：乘积球包含真值 6.0
}

参见：Domain

Complex / ComplexDomain

ComplexDomain

签名：pub struct ComplexDomain<D: Domain> { base: D, ... }

功能：在任意基域 $D$ 上构造的复数域。元素类型为 Complex<D>。仅实现 Domain。

构造

ComplexDomain::new

签名：pub fn new(base: D) -> Self

功能：在基域 base 上创建复数域。

参数：

ComplexDomain::base

签名：pub fn base(&self) -> &D

功能：返回基域引用。

ComplexDomain::real_element

签名：pub fn real_element(&self, re: D::Element) -> Complex<D>

功能：创建纯实数元素。

ComplexDomain::imag_element

签名：pub fn imag_element(&self, im: D::Element) -> Complex<D>

功能：创建纯虚数元素。

Domain 实现

• mul：$(a+bi)(c+di) = (ac-bd) + (ad+bc)i$
• div：$(a+bi)/(c+di) = \frac{(ac+bd)+(bc-ad)i}{c^2+d^2}$，分母为零时返回 None
• inv：通过 div(one, a) 实现

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{Complex, ComplexDomain, Domain, Integer, IntegerDomain};

let domain = ComplexDomain::new(IntegerDomain);
let a = Complex::new(Integer::from(1), Integer::from(2));
let b = Complex::new(Integer::from(3), Integer::from(4));
let sum = domain.add(&a, &b);
assert_eq!(*sum.re(), Integer::from(4));
assert_eq!(*sum.im(), Integer::from(6));
// 输出：(1+2i) + (3+4i) = 4+6i
}

参见：Domain

Complex

签名：pub struct Complex<D: Domain> { inner: NumComplex<D::Element> }

功能：复数，实部和虚部属于基域 $D$。

Derive：Debug, Clone, PartialEq, Eq, Hash

构造与访问

Complex::new

签名：pub fn new(real: D::Element, imag: D::Element) -> Self

功能：从实部和虚部创建复数。

Complex::re

签名：pub fn re(&self) -> &D::Element

功能：返回实部引用。

Complex::im

签名：pub fn im(&self) -> &D::Element

功能：返回虚部引用。

Complex::inner

签名：pub fn inner(&self) -> &NumComplex<D::Element>

功能：返回底层 num_complex::Complex 引用。

参见：ComplexDomain

DoubleF64 / DoubleF64Domain

DoubleF64Domain

签名：pub struct DoubleF64Domain;

功能：双精度浮点域。元素类型为 DoubleF64。仅实现 Domain。

DoubleF64

签名：

#![allow(unused)]
fn main() {
pub struct DoubleF64 {
    pub hi: f64,  // 高阶分量（主值）
    pub lo: f64,  // 低阶分量（误差项）
}
}

功能：双精度浮点数，表示为 $hi + lo$，满足 $|lo| \leq 0.5 \cdot \text{ulp}(hi)$。提供约 31 位十进制有效数字（~84 位二进制），约为单个 f64 精度的两倍。

Derive：Debug, Clone, Copy, PartialEq；实现 Eq。

算术基于 Dekker 和 Knuth 的无误差变换算法（TwoSum、TwoProd），显著快于 MPFR 等任意精度替代方案。

常量

构造与转换

DoubleF64::new

签名：pub fn new(hi: f64, lo: f64) -> Self

功能：从高阶和低阶分量创建。调用者需确保 $|lo| \leq 0.5 \cdot \text{ulp}(hi)$ 以保证正确性。

DoubleF64::from_f64

签名：pub fn from_f64(x: f64) -> Self

功能：从单个 f64 创建（$lo = 0$）。

DoubleF64::to_f64

签名：pub fn to_f64(self) -> f64

功能：提取高阶分量。

From<f64>

签名：impl From<f64> for DoubleF64

功能：等价于 from_f64。

无误差变换

DoubleF64::quick_two_sum

签名：pub fn quick_two_sum(a: f64, b: f64) -> Self

功能：当 $|a| \geq |b|$ 时的无误差求和。比 two_sum 快但有前提条件。

DoubleF64::two_sum

签名：pub fn two_sum(a: f64, b: f64) -> Self

功能：Dekker TwoSum——无误差求和，舍入误差精确捕获到 lo 分量。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::DoubleF64;

let s = DoubleF64::two_sum(1.0, f64::EPSILON);
assert_eq!(s.hi, 1.0 + f64::EPSILON);
// s.lo 捕获了舍入误差
}

查询

算术运算

DoubleF64::add / sub / mul / div

签名：

#![allow(unused)]
fn main() {
pub fn add(self, other: Self) -> Self
pub fn sub(self, other: Self) -> Self
pub fn mul(self, other: Self) -> Self
pub fn div(self, other: Self) -> Self
}

功能：双精度加减乘除。内部使用 TwoSum/TwoProd 捕获舍入误差。

DoubleF64::powi

签名：pub fn powi(self, n: i64) -> Self

功能：整数次幂，使用二进制快速幂。支持负指数。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::DoubleF64;

let x = DoubleF64::from_f64(3.0);
assert_eq!(x.powi(3).hi, 27.0);
assert_eq!(x.powi(-1).hi, 1.0 / 3.0);
// 输出：3^3 = 27, 3^(-1) = 0.333...
}

超越函数

示例：

#![allow(unused)]
fn main() {
use ocas_domain::DoubleF64;

let x = DoubleF64::from_f64(1.0);
let e = x.exp();
// e ≈ 2.718281828...
assert!((e.hi - std::f64::consts::E).abs() < 1e-15);

let pi = DoubleF64::from_f64(std::f64::consts::PI);
let s = pi.sin();
assert!(s.hi.abs() < 1e-15); // sin(π) ≈ 0
// 输出：exp(1) ≈ e, sin(π) ≈ 0
}

运算符

DoubleF64 实现了 Add、Sub、Mul、Div、Neg、AddAssign、SubAssign、MulAssign、DivAssign、PartialOrd、Zero（num_traits）。

Display

当 lo == 0 时显示 hi 值；否则以 31 位科学计数法显示 $hi + lo$ 的和。

参见：Domain、RealBall

AlgebraicExtension / AlgebraicNumberField / AlgebraicElement

AlgebraicExtension

签名：pub struct AlgebraicExtension<D: Domain> { base: D, min_poly: Vec<D::Element> }

功能：代数扩张 $D[\alpha]/(m(\alpha))$，其中 $m$ 是首一多项式。当基域 $D$ 是域且 $m$ 不可约时，商环是域：

• AlgebraicExtension<RationalDomain> = 代数数域 $\mathbb{Q}(\alpha)$
• AlgebraicExtension<FiniteField> = Galois 域 $\mathrm{GF}(p^d)$

元素是剩余类，由次数小于 $\deg(m)$ 的唯一多项式代表表示。逆元使用基域上的扩展欧几里得算法。

⚠️ 注意：不检查极小多项式的不可约性。在可约模下，环有零因子，Domain::inv 对非单位返回 None。

实现：Domain、EuclideanDomain

构造

AlgebraicExtension::new

签名：pub fn new(base: D, min_poly: Vec<D::Element>) -> Self

功能：从基域和首一极小多项式创建代数扩张。

参数：

错误：debug 模式下检查：(1) 次数 $\geq 1$（即 min_poly.len() >= 2）；(2) 首一性。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{AlgebraicExtension, Domain, Rational, RationalDomain};

// ℚ(√2)：极小多项式 α² − 2
let two = Rational::new(2, 1);
let neg_two = RationalDomain.neg(&two);
let field = AlgebraicExtension::new(
    RationalDomain,
    vec![neg_two, Rational::new(0, 1), Rational::new(1, 1)],
);
let sqrt2 = field.alpha();
// √2 · √2 = 2
assert_eq!(field.mul(&sqrt2, &sqrt2), field.from_base(two));
// 输出：α² = 2
}

访问器

AlgebraicExtension::base_domain

签名：pub fn base_domain(&self) -> &D

功能：返回基域引用。

AlgebraicExtension::min_poly

签名：pub fn min_poly(&self) -> &[D::Element]

功能：返回极小多项式系数（升序，首一）。

AlgebraicExtension::extension_degree

签名：pub fn extension_degree(&self) -> usize

功能：返回扩张次数 $\deg(m)$。

元素构造

AlgebraicExtension::from_base

签名：pub fn from_base(&self, c: D::Element) -> AlgebraicElement<D::Element>

功能：将基域常量嵌入扩张域。

AlgebraicExtension::alpha

签名：pub fn alpha(&self) -> AlgebraicElement<D::Element>

功能：返回扩张的生成元 $\alpha$。

AlgebraicExtension::element

签名：pub fn element(&self, coeffs: Vec<D::Element>) -> AlgebraicElement<D::Element>

功能：从系数（升序）创建元素，自动规约模极小多项式。

Domain 实现

• mul：先多项式乘法，再规约模 $m(\alpha)$
• inv：使用扩展欧几里得算法——若 $\gcd(a, m) = 1$（常数），则 $a^{-1} = s \bmod m$
• div：$a/b = a \cdot b^{-1}$
• is_zero：系数向量为空

EuclideanDomain 实现

• div_rem：域上除法精确，余数恒为零
• gcd：域中退化——两者均零返回 0，否则返回 1

示例（Galois 域 $\mathrm{GF}(3^2)$）：

#![allow(unused)]
fn main() {
use ocas_domain::{AlgebraicExtension, Domain};
use ocas_domain::FiniteField;
use num_bigint::BigInt;

let base = FiniteField::new(BigInt::from(3));
let field = AlgebraicExtension::new(
    base.clone(),
    vec![base.element(1), base.element(0), base.element(1)], // α² + 1
);
let alpha = field.alpha();
// α² = −1 = 2 (mod 3)
assert_eq!(field.mul(&alpha, &alpha), field.from_base(base.element(2)));
// 乘法群阶为 8：(1+α)⁸ = 1
let a = field.add(&field.one(), &alpha);
assert_eq!(field.pow(&a, 8), field.one());
// 输出：α² = 2, (1+α)⁸ = 1
}

参见：Domain、代数数域数学基础

AlgebraicNumberField

签名：pub type AlgebraicNumberField = AlgebraicExtension<RationalDomain>;

功能：$\mathbb{Q}(\alpha)$ 的类型别名。

AlgebraicElement

签名：pub struct AlgebraicElement<E> { coeffs: Vec<E> }

功能：代数扩张的元素——$\alpha$ 的多项式剩余类，次数小于扩张次数。系数升序存储，尾随零被裁剪。零元素的系数向量为空。

Derive：Debug, Clone, PartialEq, Eq, Hash

AlgebraicElement::coeffs

签名：pub fn coeffs(&self) -> &[E]

功能：返回系数切片（升序，尾随零已裁剪）。

Display

显示格式：0（零元素）、c（纯常数）、(c1)·α + c0、(c2)·α^2 + (c1)·α + c0 等（常数项不加括号，各次项之间以 + 连接）。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{AlgebraicExtension, Domain, Rational, RationalDomain};

// ℚ(i)：极小多项式 α² + 1
let field = AlgebraicNumberField::new(
    RationalDomain,
    vec![Rational::new(1, 1), Rational::new(0, 1), Rational::new(1, 1)],
);
let i = field.alpha();
let one_plus_i = field.add(&field.one(), &i);
// (1+i)⁻¹ = (1-i)/2
let inv = field.inv(&one_plus_i).unwrap();
assert_eq!(inv.coeffs(), &[Rational::new(1, 2), Rational::new(-1, 2)]);
// 输出：1/(1+i) = (1/2) - (1/2)·α
}

参见：AlgebraicExtension

Assumptions 系统

假设系统用于声明符号变量的性质（如"x 是实数"、"n 是正整数"）。求解器和化简器通过假设来选择算法和验证解。

模块路径：ocas_domain::assumptions

Assumption

签名：

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum Assumption {
    Real, Complex, Integer, Rational,
    Positive, Negative, NonNegative, NonPositive, NonZero, Finite,
    Even, Odd, Prime,
}
}

功能：可对符号变量声明的单一谓词。假设相互独立——一个变量可同时携带多个假设（如 Positive | Integer）。

变体说明

Assumption::implied

签名：pub fn implied(&self) -> &'static [Assumption]

功能：返回此假设逻辑蕴含的其他假设列表。插入假设时，其蕴含会自动传播。

蕴含关系表：

Assumption::conflicts

签名：pub fn conflicts(&self) -> &'static [Assumption]

功能：返回与之矛盾的假设列表。同时包含一个假设及其冲突项的集合是不一致的。

冲突关系表：

其他假设无冲突项。

BitOr 支持

Assumption | Assumption 返回 Assumptions：

#![allow(unused)]
fn main() {
use ocas_domain::assumptions::{Assumption, Assumptions};

let a = Assumption::Positive | Assumption::Integer;
assert!(a.implies(Assumption::Real));
// 输出：Positive | Integer 蕴含 Real
}

参见：Assumptions、SymbolAssumptions

Assumptions

签名：pub struct Assumptions { inner: Vec<Assumption> }

功能：关于一个符号变量的假设集合。内部以排序、去重向量存储以优化小规模效率。操作在逻辑蕴含下封闭——插入 Positive 会使 NonNegative 和 Real 可用。

Derive：Debug, Clone, PartialEq, Eq, Default

构造

Assumptions::new

签名：pub fn new() -> Self

功能：创建空假设集。

Assumptions::single

签名：pub fn single(a: Assumption) -> Self

功能：创建包含单个假设（及其蕴含）的集合。

查询

Assumptions::len

签名：pub fn len(&self) -> usize

功能：返回显式存储的假设数量。

Assumptions::is_empty

签名：pub fn is_empty(&self) -> bool

功能：是否为空集。

Assumptions::contains

签名：pub fn contains(&self, a: Assumption) -> bool

功能：检查假设是否被此集合蕴含（直接成员或逻辑蕴含）。

Assumptions::implies

签名：pub fn implies(&self, other: Assumption) -> bool

功能：检查此集合是否逻辑蕴含 other。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::assumptions::{Assumption, Assumptions};

let mut a = Assumptions::new();
a.insert(Assumption::Positive);
a.insert(Assumption::Integer);
assert!(a.contains(Assumption::Real));      // Positive 蕴含 Real
assert!(a.implies(Assumption::NonZero));    // Positive 蕴含 NonZero
assert!(!a.implies(Assumption::Even));      // 不蕴含 Even
// 输出：所有断言通过
}

修改

Assumptions::insert

签名：pub fn insert(&mut self, a: Assumption) -> bool

功能：插入假设及其所有逻辑蕴含。返回 false 若插入导致矛盾（不一致假设仍被存储，应检查 is_consistent）。

Assumptions::remove

签名：pub fn remove(&mut self, a: Assumption)

功能：移除假设。不移除由被移除假设所蕴含的其他假设（它们可能仍由其他存储的假设蕴含）。

Assumptions::is_consistent

签名：pub fn is_consistent(&self) -> bool

功能：检查集合是否一致（无矛盾假设）。

Assumptions::iter

签名：pub fn iter(&self) -> impl Iterator<Item = Assumption> + '_

功能：遍历存储的假设。

运算符

• Assumption | Assumption → Assumptions
• Assumptions | Assumption → Assumptions
• Assumptions | Assumptions → Assumptions（并集）
• FromIterator<Assumption> → Assumptions

示例：

#![allow(unused)]
fn main() {
use ocas_domain::assumptions::{Assumption, Assumptions};

let a: Assumptions = [Assumption::Positive, Assumption::Integer].into_iter().collect();
assert!(a.is_consistent());

let b = Assumption::Positive | Assumption::Negative;
assert!(!b.is_consistent());
// 输出：Positive + Integer 一致；Positive + Negative 不一致
}

参见：Assumption、SymbolAssumptions

SymbolAssumptions

签名：pub struct SymbolAssumptions { entries: Vec<(String, Assumptions)> }

功能：符号名到假设的映射。求解器和化简器用此确定合法变换。例如 $\sqrt{x^2} \to x$ 仅在 $x$ 被假设为 NonNegative 时有效。

Derive：Debug, Clone, PartialEq, Eq, Default

构造

SymbolAssumptions::new

签名：pub fn new() -> Self

功能：创建空映射。

查询与修改

SymbolAssumptions::set

签名：pub fn set(&mut self, symbol: &str, assumptions: Assumptions)

功能：为符号设置假设（替换已有条目）。

SymbolAssumptions::get

签名：pub fn get(&self, symbol: &str) -> Option<&Assumptions>

功能：获取符号的假设。

SymbolAssumptions::remove

签名：pub fn remove(&mut self, symbol: &str)

功能：移除符号的假设。

SymbolAssumptions::check

签名：pub fn check(&self, symbol: &str, assumption: Assumption) -> bool

功能：检查符号是否满足特定假设。

SymbolAssumptions::len

签名：pub fn len(&self) -> usize

功能：返回有假设的符号数量。

SymbolAssumptions::is_empty

签名：pub fn is_empty(&self) -> bool

功能：是否无符号有假设。

SymbolAssumptions::iter

签名：pub fn iter(&self) -> impl Iterator<Item = &(String, Assumptions)>

功能：遍历所有 (符号名, 假设集) 对。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::assumptions::{Assumption, Assumptions, SymbolAssumptions};

let mut sa = SymbolAssumptions::new();
sa.set("x", Assumptions::single(Assumption::Positive));
sa.set("n", Assumption::Integer | Assumption::Positive);

assert!(sa.check("x", Assumption::Real));      // Positive 蕴含 Real
assert!(sa.check("n", Assumption::NonZero));   // Positive 蕴含 NonZero
assert!(!sa.check("x", Assumption::Integer));  // 不蕴含 Integer
// 输出：所有断言通过
}

参见：Assumptions、Assumption

Rust API 参考：多项式

本章记录 oCAS 的多项式系统，涵盖三类核心数据结构：

• DenseUnivariatePolynomial<D> — 稠密一元多项式
• SparseMultivariatePolynomial<D, O> — 稀疏多元多项式
• RationalPolynomial<D, O> — 多项式分式域元素

以及单项式序 trait MonomialOrder 和多种序的实现。

模块路径：ocas_poly

目录

• 单项式序
  • MonomialOrder trait
  • Lex
  • Grlex
  • Grevlex
  • WeightOrder
  • BlockOrder 与 SubOrder
  • MatrixOrder
• DenseUnivariatePolynomial
  • 构造与属性
  • 基本算术
  • EuclideanDomain 操作
  • 因式分解与结式
• SparseMultivariatePolynomial
  • 构造与属性
  • 基本算术
  • Gröbner 基支持
  • 多元因式分解
• RationalPolynomial
• 辅助函数

单项式序

MonomialOrder trait

签名：

#![allow(unused)]
fn main() {
pub trait MonomialOrder: Clone + PartialEq + Eq + std::fmt::Debug + Default {
    fn cmp(&self, lhs: &[usize], rhs: &[usize]) -> std::cmp::Ordering;
}
}

功能：定义单项式之间的全序关系。多项式的首项、排序和 Gröbner 基计算都依赖于此。

参数：

返回值：std::cmp::Ordering — Less 表示 lhs 在序中排在 rhs 之前（即 lhs 更大），Greater 表示 lhs 更小。

设计说明：简单序（Lex、Grevlex、Grlex）是零大小类型，无运行时开销。参数化序（WeightOrder、BlockOrder、MatrixOrder）在构造时存储配置。

参见：Lex、Grevlex、Grlex、WeightOrder、BlockOrder、MatrixOrder

Lex

签名：

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub struct Lex;
}

功能：字典序。从左到右逐分量比较指数向量。

比较规则：lhs > rhs 当且仅当存在 $i$ 使得 $\alpha_j = \beta_j$ 对所有 $j < i$ 且 $\alpha_i > \beta_i$。

示例：

#![allow(unused)]
fn main() {
use ocas_poly::sparse::{Lex, MonomialOrder};

let a = [2, 1]; // x^2 y
let b = [1, 1]; // x y
assert_eq!(Lex.cmp(&a, &b), std::cmp::Ordering::Greater);
// a 在 Lex 序中更大（首分量 2 > 1）
}

参见：MonomialOrder trait

Grlex

签名：

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub struct Grlex;
}

功能：分次字典序。先按总次数降序排列，同次再按字典序。

比较规则：

1. 总次数 $\sum \alpha_i$ 更大者排在前面
2. 总次数相同时，按字典序比较

示例：

#![allow(unused)]
fn main() {
use ocas_poly::sparse::{Grlex, MonomialOrder};

let a = [2, 0]; // x^2, 次数 2
let b = [1, 1]; // xy, 次数 2
let c = [0, 3]; // y^3, 次数 3
// c 次数最高，排在最前
assert_eq!(Grlex.cmp(&c, &a), std::cmp::Ordering::Less);
// a 和 b 次数相同，按字典序 a > b
assert_eq!(Grlex.cmp(&a, &b), std::cmp::Ordering::Greater);
}

参见：MonomialOrder trait

Grevlex

签名：

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub struct Grevlex;
}

功能：分次反字典序。先按总次数降序排列，同次再按反向字典序比较（从最后一个分量开始，方向反转）。

比较规则：

1. 总次数更大者排在前面
2. 总次数相同时，从最后一个分量开始比较，更小者排在前面

特点：Grevlex 序在 Gröbner 基计算中通常产生最小的中间矩阵，是默认序。

示例：

#![allow(unused)]
fn main() {
use ocas_poly::sparse::{Grevlex, Lex, MonomialOrder};

let a = [2, 1];
let b = [1, 1];
assert_eq!(Lex.cmp(&a, &b), std::cmp::Ordering::Greater);
assert_eq!(Grevlex.cmp(&a, &b), std::cmp::Ordering::Less);
// Grevlex 下 a < b（反向字典序反转了方向）
}

参见：MonomialOrder trait

WeightOrder

签名：

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct WeightOrder {
    weights: SmallVec<[i64; 4]>,
}
}

功能：加权序。按 $\sum_i w_i \cdot \alpha_i$ 降序排列。适用于无法用零大小类型表达的消元序。

构造方法：

#![allow(unused)]
fn main() {
pub fn new(weights: SmallVec<[i64; 4]>) -> Self
pub fn from_slice(weights: &[i64]) -> Self
}

参数：

Default：全 1 权重（即总次数序）。

示例：

#![allow(unused)]
fn main() {
use ocas_poly::sparse::{MonomialOrder, WeightOrder};
use smallvec::smallvec;

let ord = WeightOrder::new(smallvec![2, 1]);
// [1,0] → 权重 2, [0,1] → 权重 1 → [1,0] 更大
assert_eq!(ord.cmp(&[1, 0], &[0, 1]), std::cmp::Ordering::Less);
}

参见：MonomialOrder trait

BlockOrder 与 SubOrder

签名：

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct BlockOrder {
    boundaries: SmallVec<[usize; 4]>,
    orders: SmallVec<[SubOrder; 4]>,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SubOrder {
    Lex,
    Grevlex,
    Grlex,
}
}

功能：分块消元序。将变量分为连续的块，每个块内使用独立的子序。

构造方法：

#![allow(unused)]
fn main() {
pub fn new(boundaries: SmallVec<[usize; 4]>, orders: SmallVec<[SubOrder; 4]>) -> Self
}

参数：

说明：boundaries = [2] 加 orders = [Lex, Grevlex] 在 4 变量多项式上表示：先比较变量 0–1（Lex），相等再比较变量 2–3（Grevlex）。

Default：单块 Grevlex。

示例：

#![allow(unused)]
fn main() {
use ocas_poly::sparse::{BlockOrder, MonomialOrder, SubOrder};
use smallvec::smallvec;

let ord = BlockOrder::new(
    smallvec![2],
    smallvec![SubOrder::Lex, SubOrder::Grevlex],
);
let a = [1, 0, 0, 0]; // x₀
let b = [0, 1, 0, 0]; // x₁
// 块内 Lex：[1,0] > [0,1]
assert_eq!(ord.cmp(&a, &b), std::cmp::Ordering::Greater);
}

参见：MonomialOrder trait

MatrixOrder

签名：

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct MatrixOrder {
    matrix: Vec<Vec<i64>>,
    n_vars: usize,
}
}

功能：矩阵序。将指数向量乘以整数矩阵后按字典序比较。给定 $n \times n$ 矩阵 $M$，单项式 $\alpha > \beta$ 当且仅当 $M\alpha >_{\text{lex}} M\beta$。泛化所有标准序，特别适合构造消元序。

构造方法：

#![allow(unused)]
fn main() {
pub fn new(matrix: Vec<Vec<i64>>) -> Self
pub fn elimination_order(elim_vars: usize, n_vars: usize) -> Self
}

参数：

elimination_order：构造等价于 BlockOrder([elim_vars in Lex, rest in Grevlex]) 的矩阵序。

Default：$1 \times 1$ 单位矩阵。

示例：

#![allow(unused)]
fn main() {
use ocas_poly::sparse::{MatrixOrder, MonomialOrder};

// 2×2 单位矩阵 = Lex 序
let ord = MatrixOrder::new(vec![vec![1, 0], vec![0, 1]]);
assert_eq!(ord.cmp(&[1, 0], &[0, 1]), std::cmp::Ordering::Greater);
}

参见：MonomialOrder trait

DenseUnivariatePolynomial

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct DenseUnivariatePolynomial<D: Domain> {
    coeffs: Vec<D::Element>,  // 从常数项开始，已去除尾零
    domain: D,
}
}

稠密一元多项式。系数存储在连续向量中，从常数项 $a_0$ 到最高次项 $a_n$。零多项式用空向量表示。乘法自动在 Karatsuba（两个多项式系数个数均 $\geq 32$ 时）和学校乘法之间选择。

Dense 构造与属性

DenseUnivariatePolynomial::new

签名：pub fn new(domain: D) -> Self

功能：创建零多项式。

参数：

返回值：零多项式（空系数向量）。

参见：from_coeffs

DenseUnivariatePolynomial::from_coeffs

签名：pub fn from_coeffs(domain: D, coeffs: Vec<D::Element>) -> Self

功能：从系数向量构造多项式。自动去除尾零系数。

参数：

返回值：多项式 $a_0 + a_1 x + \cdots + a_n x^n$。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{IntegerDomain, Integer};
use ocas_poly::DenseUnivariatePolynomial;

let domain = IntegerDomain;
let p = DenseUnivariatePolynomial::from_coeffs(
    domain,
    vec![Integer::from(1), Integer::from(0), Integer::from(2)],
);
assert_eq!(p.degree(), Some(2));
assert_eq!(p.coeff(2), Some(&Integer::from(2)));
// p(x) = 1 + 2x^2，中间的零系数被保留（非尾零）
}

参见：new

DenseUnivariatePolynomial::domain

签名：pub fn domain(&self) -> &D

功能：返回系数域的引用。

DenseUnivariatePolynomial::coeffs

签名：pub fn coeffs(&self) -> &[D::Element]

功能：返回系数切片，从常数项开始。

DenseUnivariatePolynomial::is_zero

签名：pub fn is_zero(&self) -> bool

功能：判断是否为零多项式。

DenseUnivariatePolynomial::degree

签名：pub fn degree(&self) -> Option<usize>

功能：返回多项式的次数。零多项式返回 None。

DenseUnivariatePolynomial::coeff

签名：pub fn coeff(&self, n: usize) -> Option<&D::Element>

功能：返回 $x^n$ 的系数，不存在则返回 None。

DenseUnivariatePolynomial::leading_coeff

签名：pub fn leading_coeff(&self) -> Option<&D::Element>

功能：返回首项系数。零多项式返回 None。

DenseUnivariatePolynomial::lcoeff

签名：pub fn lcoeff(&self) -> D::Element

功能：返回首项系数的便捷别名。零多项式返回域的零元。

返回值：首项系数，或域的零元。

参见：leading_coeff

DenseUnivariatePolynomial::constant

签名：pub fn constant(&self) -> D::Element

功能：返回常数项（$x^0$ 的系数）。零多项式返回域的零元。

DenseUnivariatePolynomial::zero

签名：pub fn zero(&self) -> Self

功能：返回同域的零多项式。

DenseUnivariatePolynomial::one

签名：pub fn one(&self) -> Self

功能：返回常数多项式 $1$。

DenseUnivariatePolynomial::is_one

签名：pub fn is_one(&self) -> bool

功能：判断是否为常数多项式 $1$。

Dense 基本算术

以下方法在 D: Domain 上可用：

DenseUnivariatePolynomial::neg

签名：pub fn neg(&self) -> Self

功能：返回 $-p(x)$。

DenseUnivariatePolynomial::add

签名：pub fn add(&self, other: &Self) -> Self

功能：多项式加法。

DenseUnivariatePolynomial::sub

签名：pub fn sub(&self, other: &Self) -> Self

功能：多项式减法。

DenseUnivariatePolynomial::mul_scalar

签名：pub fn mul_scalar(&self, scalar: &D::Element) -> Self

功能：标量乘法。所有系数乘以 scalar。

DenseUnivariatePolynomial::mul

签名：pub fn mul(&self, other: &Self) -> Self

功能：多项式乘法。根据次数自动选择学校乘法或 Karatsuba。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{IntegerDomain, Integer};
use ocas_poly::DenseUnivariatePolynomial;

let domain = IntegerDomain;
let a = DenseUnivariatePolynomial::from_coeffs(
    domain,
    vec![Integer::from(1), Integer::from(1)],
);
let b = DenseUnivariatePolynomial::from_coeffs(
    domain,
    vec![Integer::from(1), Integer::from(-1)],
);
let c = a.mul(&b);
assert_eq!(c.coeffs(), &[
    Integer::from(1),
    Integer::from(0),
    Integer::from(-1),
]);
// (1 + x)(1 - x) = 1 - x^2
}

参见：mul_into

DenseUnivariatePolynomial::mul_into

签名：pub fn mul_into(&self, other: &Self, buf: &mut Vec<D::Element>)

功能：乘法，将结果写入缓冲区（避免热循环中的重复堆分配）。缓冲区被清空后重用。

参数：

DenseUnivariatePolynomial::eval

签名：pub fn eval(&self, x: &D::Element) -> D::Element

功能：用 Horner 法在 $x$ 处求值。零多项式返回域的零元。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{IntegerDomain, Integer};
use ocas_poly::DenseUnivariatePolynomial;

let domain = IntegerDomain;
let p = DenseUnivariatePolynomial::from_coeffs(
    domain,
    vec![Integer::from(1), Integer::from(2), Integer::from(3)],
);
let value = p.eval(&Integer::from(2));
assert_eq!(value, Integer::from(17));
// p(2) = 1 + 2·2 + 3·4 = 17
}

DenseUnivariatePolynomial::derivative

签名：pub fn derivative(&self) -> Self

功能：返回形式导数 $p'(x)$。

DenseUnivariatePolynomial::integral

签名：pub fn integral(&self) -> Self

功能：返回形式积分 $\int p(x),dx$，常数项为零。要求域支持除法（如 RationalDomain）。

EuclideanDomain 操作

以下方法要求 D: EuclideanDomain：

DenseUnivariatePolynomial::mul_coeff

签名：pub fn mul_coeff(&self, c: &D::Element) -> Self

功能：所有系数乘以常数 $c$。等价于 mul_scalar，但限于 EuclideanDomain。

参见：mul_scalar

DenseUnivariatePolynomial::div_coeff

签名：pub fn div_coeff(&self, c: &D::Element) -> Self

功能：所有系数除以常数 $c$（必须整除）。

错误：若 $c$ 在域中不可逆（例如 $\mathbb{Z}$ 上 $c$ 不是 $\pm 1$），则无条件 panic（即使所有系数都能被 $c$ 整除）。

DenseUnivariatePolynomial::div_rem

签名：pub fn div_rem(&self, divisor: &Self) -> Option<(Self, Self)>

功能：带余除法。返回 $(q, r)$ 使得 $p = q \cdot \text{divisor} + r$，其中 $\deg(r) < \deg(\text{divisor})$。

返回值：Some((quotient, remainder))，除数为零时返回 None。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{IntegerDomain, Integer};
use ocas_poly::DenseUnivariatePolynomial;

let domain = IntegerDomain;
let p = DenseUnivariatePolynomial::from_coeffs(
    domain,
    vec![Integer::from(1), Integer::from(0), Integer::from(-1)],
);
let q = DenseUnivariatePolynomial::from_coeffs(
    domain,
    vec![Integer::from(1), Integer::from(1)],
);
let (quot, rem) = p.div_rem(&q).unwrap();
assert_eq!(quot.coeffs(), &[Integer::from(1), Integer::from(-1)]);
assert!(rem.is_zero());
// (x^2 - 1) / (x + 1) = x - 1，余数为 0
}

参见：gcd

DenseUnivariatePolynomial::gcd

签名：pub fn gcd(&self, other: &Self) -> Self

功能：计算两个多项式的最大公因式。使用 Euclid 算法（非域时用伪余式）。结果总是本原的（content-free）。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{IntegerDomain, Integer};
use ocas_poly::DenseUnivariatePolynomial;

let d = IntegerDomain;
let a = DenseUnivariatePolynomial::from_coeffs(d, vec![
    Integer::from(-1), Integer::from(0), Integer::from(1),
]); // x^2 - 1
let b = DenseUnivariatePolynomial::from_coeffs(d, vec![
    Integer::from(1), Integer::from(2), Integer::from(1),
]); // (x+1)^2
let g = a.gcd(&b);
assert_eq!(g.coeffs(), &[Integer::from(1), Integer::from(1)]);
// gcd = x + 1
}

参见：extended_gcd_poly

DenseUnivariatePolynomial::content

签名：pub fn content(&self) -> D::Element

功能：返回所有系数的最大公因式。零多项式返回域的零元。

返回值：系数的 GCD。

参见：primitive_part

DenseUnivariatePolynomial::primitive_part

签名：pub fn primitive_part(&self) -> Self

功能：返回本原部分 $p / \text{content}(p)$。结果的 content 为 1（或为零多项式）。

参见：content

DenseUnivariatePolynomial::extended_gcd_poly

签名：pub fn extended_gcd_poly(&self, other: &Self) -> (Self, Self, Self)

功能：扩展 Euclid 算法。返回 $(g, s, t)$ 使得 $s \cdot p + t \cdot q = g$，其中 $g = \gcd(p, q)$，$g$ 为首一多项式。

返回值：(gcd, bezout_s, bezout_t)

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{RationalDomain, Rational};
use ocas_poly::DenseUnivariatePolynomial;

let d = RationalDomain;
let a = DenseUnivariatePolynomial::from_coeffs(d, vec![
    Rational::new(1, 1), Rational::new(0, 1), Rational::new(1, 1),
]); // x^2 + 1
let b = DenseUnivariatePolynomial::from_coeffs(d, vec![
    Rational::new(1, 1), Rational::new(1, 1),
]); // x + 1
let (g, s, t) = a.extended_gcd_poly(&b);
// s·a + t·b = g
}

参见：gcd

DenseUnivariatePolynomial::pow

签名：pub fn pow(&self, n: u32) -> Self

功能：快速幂（反复平方法）。$p^0 = 1$。

参数：

返回值：$p(x)^n$。

DenseUnivariatePolynomial::p_adic_expansion

签名：pub fn p_adic_expansion(&self, p: &Self) -> Vec<Self>

功能：$p$-adic 展开。返回 $[a_0, a_1, a_2, \dots]$ 使得 $\text{self} = a_0 + a_1 \cdot p + a_2 \cdot p^2 + \cdots$，每个 $a_k$ 的次数小于 $\deg(p)$。

实现：通过反复带余除法。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{IntegerDomain, Integer};
use ocas_poly::DenseUnivariatePolynomial;

let d = IntegerDomain;
// 对 f(x) = x^3 关于 p(x) = x + 1 做 p-adic 展开
let f = DenseUnivariatePolynomial::from_coeffs(d, vec![
    Integer::from(0), Integer::from(0), Integer::from(0), Integer::from(1),
]);
let p = DenseUnivariatePolynomial::from_coeffs(d, vec![
    Integer::from(1), Integer::from(1),
]);
let expansion = f.p_adic_expansion(&p);
// expansion = [a0, a1, a2, ...] 使得 f = a0 + a1*p + a2*p^2 + ...
}

参见：div_rem

DenseUnivariatePolynomial::diophantine

签名：pub fn diophantine(polys: &mut [Self], b: &Self) -> Vec<Self>

功能：多项式 CRT（丢番图求解器）。给定两两互素的多项式列表 polys 和目标 $b$，返回 $[s_0, \dots, s_n]$ 使得：

$$\sum_i s_i \cdot \prod_{j \neq i} p_j \equiv b \pmod{\prod_i p_i}$$

参数：

返回值：余式列表 $[s_0, \dots, s_n]$。

错误：若多项式非两两互素则 panic。

因式分解与结式

DenseUnivariatePolynomial::square_free_factorization

签名：pub fn square_free_factorization(&self) -> SquareFreeFactors<D>

功能：无平方分解。使用 Yun 算法：$g = \gcd(f, f')$，$w = f/g$，迭代 $h = \gcd(w, g)$，$z = w/h$ 收集重数 $k$ 因子。

返回值：Vec<(DenseUnivariatePolynomial<D>, usize)> — (因子, 重数) 对的列表。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{IntegerDomain, Integer};
use ocas_poly::DenseUnivariatePolynomial;

let d = IntegerDomain;
// (x+1)^2*(x-1) = x^3 + x^2 - x - 1
let p = DenseUnivariatePolynomial::from_coeffs(d, vec![
    Integer::from(-1), Integer::from(-1), Integer::from(1), Integer::from(1),
]);
let factors = p.square_free_factorization();
assert_eq!(factors.len(), 2);
}

参见：factor、gcd

DenseUnivariatePolynomial::is_square_free

签名：pub fn is_square_free(&self) -> bool

功能：判断多项式是否无平方（$\gcd(p, p') = 1$）。

DenseUnivariatePolynomial::factor（IntegerDomain）

签名：impl DenseUnivariatePolynomial<IntegerDomain> { pub fn factor(&self) -> Factors<IntegerDomain> }

功能：将本原整数多项式完全分解为不可约因子。使用无平方分解 + Berlekamp–Zassenhaus + Hensel 提升算法。

前置条件：输入必须是本原的（content = 1）。对任意多项式先调用 primitive_part()。

返回值：Vec<(DenseUnivariatePolynomial<IntegerDomain>, usize)> — (不可约因子, 重数) 对。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{Integer, IntegerDomain};
use ocas_poly::DenseUnivariatePolynomial;

let d = IntegerDomain;
// x^2 - 1 = (x-1)(x+1)
let p = DenseUnivariatePolynomial::from_coeffs(d, vec![
    Integer::from(-1), Integer::from(0), Integer::from(1),
]);
let factors = p.factor();
assert_eq!(factors.len(), 2);
}

参见：square_free_factorization

DenseUnivariatePolynomial::factor（FiniteField）

签名：impl DenseUnivariatePolynomial<FiniteField> { pub fn factor(&self) -> Factors<FiniteField> }

功能：将 $\mathbb{F}_p$ 上的多项式完全分解。使用 Berlekamp 算法（或 Cantor–Zassenhaus）。

返回值：Vec<(DenseUnivariatePolynomial<FiniteField>, usize)> — (不可约因子, 重数) 对。

示例：

#![allow(unused)]
fn main() {
use num_bigint::BigInt;
use ocas_domain::{Domain, FiniteField};
use ocas_poly::DenseUnivariatePolynomial;

let f = FiniteField::new(BigInt::from(5));
// x^2 - 1 over F_5
let p = DenseUnivariatePolynomial::from_coeffs(
    f.clone(), vec![f.element(4), f.element(0), f.element(1)]);
let factors = p.factor();
assert!(!factors.is_empty());
}

参见：factor（IntegerDomain）

DenseUnivariatePolynomial::resultant

签名：pub fn resultant(&self, other: &Self) -> D::Element

功能：用 Brown PRS 算法计算结式 $\operatorname{Res}(a, b)$。结式为零当且仅当 $a$ 和 $b$ 有非常数公因子。

实现细节：子结式 PRS，每步用 $\beta$ 精确除法（子结式定理保证整除）。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{IntegerDomain, Integer};
use ocas_poly::DenseUnivariatePolynomial;

let d = IntegerDomain;
// Res(x - 1, x - 2) = 1 - 2 = -1
let a = DenseUnivariatePolynomial::from_coeffs(d, vec![
    Integer::from(-1), Integer::from(1),
]);
let b = DenseUnivariatePolynomial::from_coeffs(d, vec![
    Integer::from(-2), Integer::from(1),
]);
assert_eq!(a.resultant(&b), Integer::from(-1));
}

性质：$\operatorname{Res}(a, b) = (-1)^{\deg a \cdot \deg b} \operatorname{Res}(b, a)$。

参见：gcd

SparseMultivariatePolynomial

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct SparseMultivariatePolynomial<D: Domain, O: MonomialOrder = Grevlex> {
    terms: HashMap<SmallVec<[usize; 4]>, D::Element>,
    domain: D,
    n_vars: usize,
    pub order: O,
}
}

稀疏多元多项式。只存储非零项，以指数向量 $\vec{e} = [e_1, e_2, \dots]$ 为键、系数为值的 HashMap。指数向量 $\vec{e}$ 表示单项式 $x_1^{e_1} x_2^{e_2} \cdots$。单项式序由类型参数 O 控制，默认为 Grevlex。

Sparse 构造与属性

SparseMultivariatePolynomial::new

签名：pub fn new(domain: D, n_vars: usize) -> Self

功能：创建零多项式，使用默认单项式序。

参数：

参见：new_with_order

SparseMultivariatePolynomial::new_with_order

签名：pub fn new_with_order(domain: D, n_vars: usize, order: O) -> Self

功能：创建零多项式，指定单项式序。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::IntegerDomain;
use ocas_poly::sparse::{SparseMultivariatePolynomial, WeightOrder};

let order = WeightOrder::from_slice(&[2, 1]);
let p = SparseMultivariatePolynomial::<_, WeightOrder>::new_with_order(
    IntegerDomain, 2, order,
);
assert_eq!(p.n_vars(), 2);
}

SparseMultivariatePolynomial::from_terms

签名：pub fn from_terms(domain: D, n_vars: usize, terms: Vec<(Vec<usize>, D::Element)>) -> Self

功能：从（指数向量, 系数）对的列表构造多项式。零系数项自动丢弃。

参数：

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{IntegerDomain, Integer};
use ocas_poly::sparse::Grevlex;
use ocas_poly::SparseMultivariatePolynomial;

let domain = IntegerDomain;
let p = SparseMultivariatePolynomial::<IntegerDomain, Grevlex>::from_terms(
    domain,
    2,
    vec![(vec![1, 0], Integer::from(2)), (vec![0, 1], Integer::from(3))],
);
assert_eq!(p.n_terms(), 2);
assert_eq!(p.coeff(&[1, 0]), Integer::from(2));
// p = 2x + 3y
}

参见：new

SparseMultivariatePolynomial::domain

签名：pub fn domain(&self) -> &D

功能：返回系数域的引用。

SparseMultivariatePolynomial::n_vars

签名：pub fn n_vars(&self) -> usize

功能：返回变量数。

SparseMultivariatePolynomial::n_terms

签名：pub fn n_terms(&self) -> usize

功能：返回非零项数。

SparseMultivariatePolynomial::is_zero

签名：pub fn is_zero(&self) -> bool

功能：判断是否为零多项式。

SparseMultivariatePolynomial::terms_ref

签名：pub fn terms_ref(&self) -> &HashMap<SmallVec<[usize; 4]>, D::Element>

功能：返回内部项映射的引用（指数 → 系数）。

SparseMultivariatePolynomial::set_term_external

签名：pub fn set_term_external(&mut self, exp: Vec<usize>, coeff: D::Element)

功能：设置单项式的系数。零系数会移除该项。

SparseMultivariatePolynomial::total_degree

签名：pub fn total_degree(&self) -> Option<usize>

功能：返回总次数（所有单项式次数的最大值）。零多项式返回 None。

SparseMultivariatePolynomial::coeff

签名：pub fn coeff(&self, exp: &[usize]) -> D::Element

功能：返回给定单项式的系数，不存在则返回域的零元。

SparseMultivariatePolynomial::degree_in

签名：pub fn degree_in(&self, var_index: usize) -> usize

功能：返回关于变量 var_index 的次数。零多项式返回 0。

参数：

返回值：该变量在所有项中的最大指数。

SparseMultivariatePolynomial::zero / one

签名：

#![allow(unused)]
fn main() {
pub fn zero(&self) -> Self
pub fn one(&self) -> Self
}

功能：返回同形状的零多项式或常数 $1$。

Sparse 基本算术

SparseMultivariatePolynomial::neg

签名：pub fn neg(&self) -> Self

功能：返回 $-p$。

SparseMultivariatePolynomial::add

签名：pub fn add(&self, other: &Self) -> Self

功能：多项式加法。

错误：若变量数不同则 panic。

SparseMultivariatePolynomial::sub

签名：pub fn sub(&self, other: &Self) -> Self

功能：多项式减法。

错误：若变量数不同则 panic。

SparseMultivariatePolynomial::mul_scalar

签名：pub fn mul_scalar(&self, scalar: &D::Element) -> Self

功能：标量乘法。

SparseMultivariatePolynomial::mul

签名：pub fn mul(&self, other: &Self) -> Self

功能：多项式乘法。对每对项分别相乘后合并同类项。

错误：若变量数不同则 panic。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{IntegerDomain, Integer};
use ocas_poly::sparse::Grevlex;
use ocas_poly::SparseMultivariatePolynomial;

let domain = IntegerDomain;
let p = SparseMultivariatePolynomial::<IntegerDomain, Grevlex>::from_terms(
    domain,
    2,
    vec![(vec![1, 0], Integer::from(2)), (vec![0, 1], Integer::from(3))],
);
let q = SparseMultivariatePolynomial::<IntegerDomain, Grevlex>::from_terms(
    domain,
    2,
    vec![(vec![1, 0], Integer::from(1)), (vec![0, 0], Integer::from(1))],
);
let r = p.mul(&q);
assert_eq!(r.coeff(&[1, 0]), Integer::from(2));
assert_eq!(r.coeff(&[0, 1]), Integer::from(3));
assert_eq!(r.coeff(&[2, 0]), Integer::from(2));
// (2x + 3y)(x + 1) = 2x^2 + 2x + 3xy + 3y
}

SparseMultivariatePolynomial::mul_monomial

签名：pub fn mul_monomial(&self, exp: &[usize]) -> Self

功能：每个项的指数向量逐分量加上 exp。用于 Gröbner 基归约。

SparseMultivariatePolynomial::sorted_terms

签名：pub fn sorted_terms(&self) -> Vec<(&SmallVec<[usize; 4]>, &D::Element)>

功能：按单项式序返回排序后的（指数, 系数）对。

SparseMultivariatePolynomial::eval

签名：pub fn eval(&self, var_index: usize, value: &D::Element) -> Self

功能：将变量 var_index 替换为值 value，返回少一个变量的多项式。

参数：

返回值：少一个变量的多项式（剩余变量保持相对顺序）。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{Integer, IntegerDomain};
use ocas_poly::SparseMultivariatePolynomial;
use ocas_poly::Lex;

let p = SparseMultivariatePolynomial::<_, Lex>::from_terms(
    IntegerDomain, 2,
    vec![
        (vec![1, 1], Integer::from(1)), // xy
        (vec![0, 1], Integer::from(2)), // 2y
    ],
);
// 代入 x=3：结果 = 3y + 2y = 5y
let r = p.eval(0, &Integer::from(3));
assert_eq!(r.coeff(&[1]), Integer::from(5));
}

SparseMultivariatePolynomial::eval_keep

签名：pub fn eval_keep(&self, var_index: usize, value: &D::Element) -> Self

功能：将变量 var_index 替换为值，但保持变量总数不变（被替换变量的指数置零）。用于 Hensel 提升中变量位置需保持固定的场景。

SparseMultivariatePolynomial::leading_term

签名：pub fn leading_term(&self) -> Option<(&SmallVec<[usize; 4]>, &D::Element)>

功能：返回首项（指数向量, 系数）。零多项式返回 None。$O(n)$ 扫描 HashMap。

SparseMultivariatePolynomial::leading_monomial

签名：pub fn leading_monomial(&self) -> Option<&SmallVec<[usize; 4]>>

功能：返回首单项式的指数向量。

SparseMultivariatePolynomial::leading_coeff

签名：pub fn leading_coeff(&self) -> Option<&D::Element>

功能：返回首项系数。

SparseMultivariatePolynomial::content

签名：

#![allow(unused)]
fn main() {
pub fn content(&self) -> D::Element
where D: EuclideanDomain
}

功能：返回所有系数的 GCD。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{Integer, IntegerDomain};
use ocas_poly::SparseMultivariatePolynomial;
use ocas_poly::Lex;

let p = SparseMultivariatePolynomial::<_, Lex>::from_terms(
    IntegerDomain, 1,
    vec![(vec![2], Integer::from(6)), (vec![1], Integer::from(9)), (vec![0], Integer::from(3))],
);
assert_eq!(p.content(), Integer::from(3));
}

参见：primitive_part

SparseMultivariatePolynomial::primitive_part

签名：

#![allow(unused)]
fn main() {
pub fn primitive_part(&self) -> Self
where D: EuclideanDomain
}

功能：返回本原部分（多项式 / content）。

参见：content

SparseMultivariatePolynomial::div_exact

签名：pub fn div_exact(&self, divisor: &Self) -> Self

功能：精确除法（假设无余式）。用于有理函数规范化中已知 GCD 整除的场景。

错误：debug 模式下若除法不精确则 panic。

参见：checked_div_exact

SparseMultivariatePolynomial::checked_div_exact

签名：pub fn checked_div_exact(&self, divisor: &Self) -> Option<Self>

功能：精确除法，不精确时返回 None。

返回值：Some(quotient) 或 None。

SparseMultivariatePolynomial::derivative

签名：pub fn derivative(&self, var_index: usize) -> Self

功能：对变量 var_index 求形式偏导。

SparseMultivariatePolynomial::taylor_coefficients

签名：pub fn taylor_coefficients(&self, var_index: usize, a: &D::Element) -> Vec<Self>

功能：计算关于变量 var_index 在点 $a$ 处的 Taylor 系数。返回 $[t_0, t_1, \dots, t_d]$ 使得 $f = \sum_j t_j (x_{\text{var}} - a)^j$。

Gröbner 基支持

SparseMultivariatePolynomial::reduce

签名：pub fn reduce(&self, basis: &[Self]) -> Self

功能：多元多项式除法。反复寻找能除尽当前首项的基元素，减去适当倍数；否则将首项移入余式。要求域为域（div 总是成功）。

参数：

返回值：归约后的余式。

SparseMultivariatePolynomial::spoly

签名：pub fn spoly(&self, other: &Self) -> Self

功能：计算 S-多项式。$S(f, g) = \frac{\text{lcm}}{\text{lt}(f)} \cdot f - \frac{\text{lcm}}{\text{lt}(g)} \cdot g$。

SparseMultivariatePolynomial::make_monic_inplace

签名：pub fn make_monic_inplace(&mut self) -> bool

功能：原地将多项式化为首一（除以首项系数）。首项系数不可逆时返回 false。

SparseMultivariatePolynomial::exponents_iter

签名：pub fn exponents_iter(&self) -> impl Iterator<Item = &SmallVec<[usize; 4]>>

功能：按单项式序（降序）迭代所有指数向量。用于 F4 算法的符号预处理。

多元因式分解

SparseMultivariatePolynomial::factor（IntegerDomain, Lex）

签名：

#![allow(unused)]
fn main() {
impl SparseMultivariatePolynomial<IntegerDomain, Lex> {
    pub fn factor(&self) -> Vec<(Self, usize)>
}
}

功能：将多元整数多项式分解为不可约因子。二元且主变量首项系数为常数时使用双变量 Hensel 提升（Wang）；三元及以上、或主变量首项系数非常数的二元情形使用 EEZ 算法。

返回值：(不可约因子, 重数) 对的列表。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{Integer, IntegerDomain};
use ocas_poly::SparseMultivariatePolynomial;
use ocas_poly::Lex;

// (x^2 + y + 1)(x + y + 2)
let f = SparseMultivariatePolynomial::<_, Lex>::from_terms(
    IntegerDomain, 2,
    vec![
        (vec![3, 0], Integer::from(1)),
        (vec![2, 1], Integer::from(1)),
        (vec![2, 0], Integer::from(2)),
        (vec![1, 1], Integer::from(1)),
        (vec![1, 0], Integer::from(1)),
        (vec![0, 2], Integer::from(1)),
        (vec![0, 1], Integer::from(3)),
        (vec![0, 0], Integer::from(2)),
    ],
);
let factors = f.factor();
assert!(factors.len() >= 2);
}

参见：factor（FiniteField）

SparseMultivariatePolynomial::factor（FiniteField, Lex）

签名：

#![allow(unused)]
fn main() {
impl SparseMultivariatePolynomial<FiniteField, Lex> {
    pub fn factor(&self) -> Vec<(Self, usize)>
}
}

功能：将多元 $\mathbb{F}_p$ 多项式分解。二元用求值–Hensel 路径，三元及以上用 EEZ。

参见：factor（IntegerDomain）

RationalPolynomial

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct RationalPolynomial<D: Domain, O: MonomialOrder = Grevlex> {
    pub numerator: SparseMultivariatePolynomial<D, O>,
    pub denominator: SparseMultivariatePolynomial<D, O>,
}
}

多项式分式域元素 $\frac{\text{num}}{\text{den}}$。通过 from_num_den 构造时自动规范化为最简形式（分子分母互素，分母首项系数归一化）。

RationalPolynomial::new

签名：

#![allow(unused)]
fn main() {
pub fn new(
    numerator: SparseMultivariatePolynomial<D, O>,
    denominator: SparseMultivariatePolynomial<D, O>,
) -> Self
}

功能：不化简地构造有理多项式。调用者须确保分母非零。

参见：from_num_den

RationalPolynomial::from_num_den

签名：

#![allow(unused)]
fn main() {
impl<D: EuclideanDomain, O: MonomialOrder> RationalPolynomial<D, O> {
    pub fn from_num_den(
        numerator: SparseMultivariatePolynomial<D, O>,
        denominator: SparseMultivariatePolynomial<D, O>,
    ) -> Self
}
}

功能：从分子分母构造并规范化。结果为最简形式：分子分母互素，分母首项系数归一化（有限域下为 1，整数域下为正）。

前置条件：分母非零。

规范化步骤：

1. 计算 $\gcd(\text{num}, \text{den})$ 并约去
2. 一元时用稠密 Euclid 算法精确 GCD 约简
3. 归一化分母首项系数

错误：分母为零时 panic。

参见：new

RationalPolynomial::from_polynomial

签名：pub fn from_polynomial(poly: SparseMultivariatePolynomial<D, O>) -> Self

功能：从多项式构造（分母 = 1）。

RationalPolynomial::zero / one

签名：

#![allow(unused)]
fn main() {
pub fn zero(domain: &D, n_vars: usize) -> Self
pub fn one(domain: &D, n_vars: usize) -> Self
}

功能：返回零或单位有理多项式。

RationalPolynomial::is_zero / is_one

签名：

#![allow(unused)]
fn main() {
pub fn is_zero(&self) -> bool
pub fn is_one(&self) -> bool
}

功能：判断是否为零或 $1/1$。

RationalPolynomial::n_vars

签名：pub fn n_vars(&self) -> usize

功能：返回变量数。

RationalPolynomial::domain

签名：pub fn domain(&self) -> &D

功能：返回系数域引用。

RationalPolynomial::neg

签名：pub fn neg(&self) -> Self

功能：返回 $-\frac{n}{d}$。

RationalPolynomial::inv

签名：pub fn inv(&self) -> Option<Self>

功能：返回乘法逆 $\frac{d}{n}$。分子为零时返回 None。

返回值：Some(逆) 或 None（分子为零）。

RationalPolynomial::pow

签名：pub fn pow(&self, k: u32) -> Self

功能：快速幂。$\left(\frac{n}{d}\right)^k$，分子分母分别用反复平方法。

RationalPolynomial::add

签名：

#![allow(unused)]
fn main() {
impl<D: EuclideanDomain, O: MonomialOrder> RationalPolynomial<D, O> {
    pub fn add(&self, other: &Self) -> Self
}
}

功能：有理多项式加法。同分母时直接加分子；异分母时交叉相乘后规范化。

RationalPolynomial::sub

签名：pub fn sub(&self, other: &Self) -> Self

功能：有理多项式减法。等价于 self.add(&other.neg())。

RationalPolynomial::mul

签名：pub fn mul(&self, other: &Self) -> Self

功能：有理多项式乘法。交叉相乘后规范化。

RationalPolynomial::div

签名：pub fn div(&self, other: &Self) -> Option<Self>

功能：有理多项式除法。$\frac{a/b}{c/d} = \frac{ad}{bc}$。

返回值：Some(商) 或 None（除数分子为零）。

辅助函数

以下函数位于 ocas_poly::sparse 模块中：

monomial_divides

签名：pub fn monomial_divides(a: &[usize], b: &[usize]) -> bool

功能：判断单项式 $b$ 是否整除 $a$（即 $a$ 是 $b$ 的倍式）。返回 true 当且仅当 $a_i \geq b_i$ 对所有 $i$。

参数：

返回值：true 若 $b$ 整除 $a$。

monomial_lcm

签名：pub fn monomial_lcm(a: &[usize], b: &[usize]) -> SmallVec<[usize; 4]>

功能：计算两个单项式的最小公倍式：逐分量取最大值。

$$\text{lcm}(x^a y^b, x^c y^d) = x^{\max(a,c)} y^{\max(b,d)}$$

monomial_are_coprime

签名：pub fn monomial_are_coprime(a: &[usize], b: &[usize]) -> bool

功能：判断两个单项式是否互素（没有变量同时出现在两者中）。

类型别名

#![allow(unused)]
fn main() {
/// 无平方分解结果：(因子, 重数) 对的列表。
pub type SquareFreeFactors<D> = Vec<(DenseUnivariatePolynomial<D>, usize)>;

/// 完全分解结果：(不可约因子, 重数) 对的列表。
pub type Factors<D> = Vec<(DenseUnivariatePolynomial<D>, usize)>;
}

矩阵

来源：ocas-poly/src/matrix.rs

Matrix<D> 是 oCAS 中通用的稠密矩阵类型，元素来自任意 EuclideanDomain。采用行优先存储，所有消元操作使用 无分数（fraction-free） 算法，避免域元素的分数膨胀。

MatrixError

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum MatrixError {
    ShapeMismatch,
    RightHandSideIsNotVector,
    Inconsistent,
    Underdetermined { rank: usize },
    ResultNotInDomain,
}
}

矩阵运算中可能产生的错误。实现了 Display 和 std::error::Error。

ShapeMismatch

功能：矩阵形状不兼容。

触发场景：trace 用于非方阵；matmul 的 self.ncols != other.nrows；solve 中 self.nrows != b.len()；augment 中行数不一致。

RightHandSideIsNotVector

功能：右端不是列向量。

触发场景：当前版本中未直接由 solve 使用（solve 接受 &[D::Element] 切片），但保留供扩展。

Inconsistent

功能：线性方程组无解（不相容）。

触发场景：solve 中消元后增广矩阵的自由行在最后一列（常数项）非零。

Underdetermined { rank }

功能：线性方程组有无穷多解（欠定）。

触发场景：solve 中系数矩阵的秩 rank 小于变量数 nvars。

ResultNotInDomain

功能：解不在目标域中。

触发场景：solve 的最终除法步骤中，div 返回 None（例如整数域中不能整除）。

Display 输出：

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{Integer, IntegerDomain};
use ocas_poly::matrix::{Matrix, MatrixError};

let d = IntegerDomain;

// 不相容系统：两行相同但常数项不同
let a = Matrix::from_rows(
    vec![vec![Integer::from(1), Integer::from(1)],
         vec![Integer::from(1), Integer::from(1)]],
    d,
);
let b = vec![Integer::from(1), Integer::from(2)];
assert_eq!(a.solve(&b), Err(MatrixError::Inconsistent));
}

参见：solve

Matrix<D>

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Matrix<D: EuclideanDomain> {
    data: Vec<D::Element>,   // 行优先存储
    nrows: usize,
    ncols: usize,
    domain: D,
}
}

功能：域 D 上的稠密矩阵，元素以行优先顺序存储于 Vec<D::Element> 中。

设计不变量：

• data.len() == nrows * ncols（由构造函数保证）
• 元素 (i, j) 在 data 中的位置为 i * ncols + j
• D 约束为 EuclideanDomain，支持 div、gcd 等操作，使无分数消元成为可能

Trait 实现：

• Index<(usize, usize)> / IndexMut<(usize, usize)> — 通过 matrix[(i, j)] 访问元素
• Display — 每行一行，元素间空格分隔
• Debug、Clone、PartialEq、Eq

构造方法

new

签名：pub fn new(nrows: usize, ncols: usize, data: Vec<D::Element>, domain: D) -> Self

功能：从行优先的一维数据创建矩阵。

参数：

返回值：Matrix<D>

错误：若 data.len() != nrows * ncols，运行时 panic。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{Integer, IntegerDomain};
use ocas_poly::matrix::Matrix;

let d = IntegerDomain;
// 创建 2×3 矩阵：
// [ 1  2  3 ]
// [ 4  5  6 ]
let m = Matrix::new(2, 3, vec![
    Integer::from(1), Integer::from(2), Integer::from(3),
    Integer::from(4), Integer::from(5), Integer::from(6),
], d);
assert_eq!(m.nrows(), 2);
assert_eq!(m.ncols(), 3);
assert_eq!(m[(0, 0)], Integer::from(1));
assert_eq!(m[(1, 2)], Integer::from(6));
}

参见：from_rows、zeros、identity

zeros

签名：pub fn zeros(nrows: usize, ncols: usize, domain: D) -> Self

功能：创建指定形状的零矩阵。

参数：

返回值：所有元素为 domain.zero() 的 Matrix<D>。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{Integer, IntegerDomain};
use ocas_poly::matrix::Matrix;

let d = IntegerDomain;
let z = Matrix::zeros(2, 3, d);
assert_eq!(z[(0, 0)], Integer::from(0));
assert_eq!(z[(1, 2)], Integer::from(0));
}

参见：identity、new

identity

签名：pub fn identity(n: usize, domain: D) -> Self

功能：创建 n × n 单位矩阵。

参数：

返回值：对角线为 domain.one()、其余为 domain.zero() 的方阵。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{Integer, IntegerDomain};
use ocas_poly::matrix::Matrix;

let d = IntegerDomain;
let id = Matrix::identity(3, d);
assert_eq!(id[(0, 0)], Integer::from(1));
assert_eq!(id[(0, 1)], Integer::from(0));
assert_eq!(id[(2, 2)], Integer::from(1));
}

参见：zeros

from_rows

签名：pub fn from_rows(rows: Vec<Vec<D::Element>>, domain: D) -> Self

功能：从嵌套行向量创建矩阵。

参数：

返回值：Matrix<D>

错误：若行长度不一致，运行时 panic。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{Integer, IntegerDomain};
use ocas_poly::matrix::Matrix;

let d = IntegerDomain;
let m = Matrix::from_rows(
    vec![
        vec![Integer::from(1), Integer::from(2), Integer::from(3)],
        vec![Integer::from(4), Integer::from(5), Integer::from(6)],
    ],
    d,
);
assert_eq!(m.nrows(), 2);
assert_eq!(m.ncols(), 3);
assert_eq!(m[(0, 2)], Integer::from(3));
}

参见：new、into_rows

访问器方法

nrows

签名：pub fn nrows(&self) -> usize

功能：返回矩阵行数。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{Integer, IntegerDomain};
use ocas_poly::matrix::Matrix;

let d = IntegerDomain;
let m = Matrix::new(3, 2, vec![Integer::from(0); 6], d);
assert_eq!(m.nrows(), 3);
}

ncols

签名：pub fn ncols(&self) -> usize

功能：返回矩阵列数。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{Integer, IntegerDomain};
use ocas_poly::matrix::Matrix;

let d = IntegerDomain;
let m = Matrix::new(3, 2, vec![Integer::from(0); 6], d);
assert_eq!(m.ncols(), 2);
}

shape

矩阵没有单独的 shape() 方法。形状通过组合 nrows() 和 ncols() 获取：

#![allow(unused)]
fn main() {
use ocas_domain::{Integer, IntegerDomain};
use ocas_poly::matrix::Matrix;

let d = IntegerDomain;
let m = Matrix::new(3, 4, vec![Integer::from(0); 12], d);
let (rows, cols) = (m.nrows(), m.ncols());
assert_eq!((rows, cols), (3, 4));
}

domain

签名：pub fn domain(&self) -> &D

功能：返回矩阵系数域的引用。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{IntegerDomain, EuclideanDomain};
use ocas_poly::matrix::Matrix;

let d = IntegerDomain;
let m = Matrix::zeros(1, 1, d);
let dom = m.domain();
assert!(dom.is_zero(&dom.zero()));
}

data

签名：pub fn data(&self) -> &[D::Element]

功能：返回底层行优先存储的只读切片。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{Integer, IntegerDomain};
use ocas_poly::matrix::Matrix;

let d = IntegerDomain;
let m = Matrix::from_rows(
    vec![vec![Integer::from(1), Integer::from(2)],
         vec![Integer::from(3), Integer::from(4)]],
    d,
);
let raw = m.data();
assert_eq!(raw.len(), 4);
assert_eq!(raw[0], Integer::from(1));  // (0,0)
assert_eq!(raw[3], Integer::from(4));  // (1,1)
}

row

签名：pub fn row(&self, i: usize) -> Vec<D::Element>

功能：返回第 i 行的拷贝。

参数：

返回值：Vec<D::Element>，长度等于 ncols。

错误：索引越界时 panic。

示例：

#![allow(unused)]
fn main() {
use ocas_domain::{Integer, IntegerDomain};
use ocas_poly::matrix::Matrix;

let d = IntegerDomain;
let m = Matrix::from_rows(
    vec![vec![Integer::from(1), Integer::from(2)],
         vec![Integer::from(3), Integer::from(4)]],
    d,
);
let r = m.row(1);
assert_eq!(r, vec![Integer::from(3), Integer::from(4)]);
}