Introduction

oCAS (Open Computer Algebra System) is a high-performance computer algebra system (CAS) written in Rust, released under the LGPL-3.0-or-later license. The project aims to match or exceed Symbolica and SageMath in core symbolic-computation performance, while providing multi-language interfaces through Python (PyO3) and C/C++ (cbindgen) bindings.

oCAS uses a layered crate architecture: 13 workspace members from the low-level arena allocator up to the top-level language bindings, with dependencies strictly pointing downward. All coefficient domains (arbitrary-precision integers/rationals, finite fields, real balls, complex numbers, double-precision floats) are abstracted behind a unified Domain trait, and the polynomial algebra, Gröbner basis, symbolic calculus, and ODE solving modules share the same expression infrastructure.

Version Feature Matrix

The table below lists the key features added in each oCAS release (0.1 → 0.27):

Module Architecture

oCAS consists of 13 crates with the following dependency graph (arrow A → B means A depends on B; ocas-py/ocas-c also depend on ocas-eval, ocas-rewrite and other core crates — only representative edges are shown; dashed edges are optional dependencies):

graph TD
    CORE["ocas-core<br/>Arena, Fuel, thread pool"]
    DOMAIN["ocas-domain<br/>coefficient domains, number theory, algebraic numbers"]
    POLY["ocas-poly<br/>polynomials, matrices, Gröbner bases"]
    ATOM["ocas-atom<br/>expression tree Atom, tensors"]
    PARSE["ocas-parse<br/>parser"]
    REWRITE["ocas-rewrite<br/>pattern matching, simplification"]
    CALC["ocas-calc<br/>calculus, ODE, integration"]
    EVAL["ocas-eval<br/>evaluation, JIT, numeric integration"]
    GPL["ocas-gpl<br/>GPL backend isolation"]
    TOP["ocas<br/>top-level crate + prelude"]
    PY["ocas-py<br/>Python bindings (PyO3)"]
    C["ocas-c<br/>C/C++ bindings (cbindgen)"]
    TESTS["ocas-tests<br/>correctness comparisons, 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 overview:

Key Features

• 13 crates — layered Rust architecture from the arena runtime to language bindings, with dependencies strictly downward.
• 7 coefficient domains — arbitrary-precision integers/rationals, finite fields $\mathbb{F}_p$, real balls, complex numbers, double-precision floats (DoubleF64 ~31 digits), algebraic number fields $\mathbb{Q}(\alpha)$ / $\mathrm{GF}(p^d)$.
• Polynomial algebra — dense univariate/sparse multivariate polynomials, Karatsuba multiplication, GCD (Brown's modular GCD), multivariate GCD, factorization (Cantor–Zassenhaus + Hensel + Wang EEZ), algebraic number field factorization (Trager).
• Gröbner bases — three algorithms (Buchberger / F4 / F5), FGLM change of order, ideal operations (membership/sum/product/quotient/saturation/intersection/elimination/radical/primary decomposition), Hilbert series.
• Symbolic calculus — differentiation, Taylor expansion, layered integration pipeline (rational → Risch → trigonometric → special functions → heuristic → unevaluated form).
• ODE solving — first-order (separable/linear/Bernoulli/exact/homogeneous/integrating factors), second-order (constant coefficient/Cauchy–Euler/reduction of order/undetermined coefficients/variation of parameters), power-series and Frobenius solutions, Laplace IVP, 2×2 systems.
• Evaluation engine — stack VM interpreter, SIMD batch evaluation (f64x4), Cranelift JIT (f64/f32), streaming evaluation (constant memory).
• Automatic differentiation — forward mode with hyper-dual numbers HyperDual<T>, first- and higher-order partial derivatives.
• Tensor algebra — index slots, explicit contraction, McKay graph-isomorphism canonicalization (1-WL refinement + path invariant pruning), Young projectors.
• Numeric integration — adaptive Monte Carlo (Vegas), supporting high-dimensional definite integrals.
• Number theory — BPSW primality testing, integer factorization (trial division/Pollard rho/p−1/p+1/ECM), discrete logarithms (BSGS + Pohlig–Hellman), Euler φ / Möbius / divisor functions.
• Rewriting and simplification — AC backtracking pattern matching, wildcards (x__/x___), fixpoint simplification, fuel-limited simplification, optional egg e-graph equality saturation.
• Three-language bindings — Rust prelude API, Python (PyO3, 25 classes + 32 functions), C/C++ (cbindgen, 91 exports + RAII wrappers).
• Correctness framework — cross-validation against SymPy, SageMath, and Symbolica across multiple mathematical modules (1550 #[test]/#[tokio::test] annotations as of 0.28.0).
• Optional numeric backends — GMP/MPFR/FLINT behind feature flags, with GPL backends isolated in ocas-gpl.

Quick Navigation

Project Status

oCAS is currently at version 0.28.0. The core symbolic engine, polynomial algebra, Gröbner bases and algebraic geometry, ODE solving, JIT evaluation, three-language bindings, and the correctness comparison framework are feature-complete. The roadmap to a stable 1.0 can be found in the roadmap.

Getting Started

This chapter gets you up and running with oCAS in about 5 minutes. oCAS 0.24 supports three language interfaces: Rust, Python, and C/C++.

System requirements

Language	Minimum version	Notes
Rust	1.97+ (edition 2024)	Install via rustup recommended
Python	3.10+	Use pip install or build from source
C/C++	C11 / C++17	Building the C library requires cargo

Rust

Installation

Add oCAS to your Cargo.toml:

[dependencies]
ocas = "0.24"

To enable optional backends, turn on features:

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

Commonly used features:

See the Rust API reference for the complete feature list.

Verify the Installation

Create a minimal project to confirm everything works:

cargo new ocas-test && cd ocas-test

Add the dependency to Cargo.toml:

[dependencies]
ocas = "0.24"

Write the following to 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);
    // Output: d/dx(x² + 2x + 1) = 2 + 2*x
}

Run it:

cargo run

If it prints 2 + 2*x, the installation succeeded.

Basic Usage

Symbolic Differentiation and Simplification

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

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

    // Parse the expression
    let expr = parse(&ctx, "x^2").unwrap();

    // Differentiate
    let d = diff(&ctx, expr, Symbol::new("x"));
    println!("derivative: {}", d);
    // Output: 2*x

    // Simplify (default rule set: identity removal, constant folding)
    let e2 = parse(&ctx, "x + 0 + y*0 + z*1").unwrap();
    let rules = default_rules(&ctx, &());
    let s = simplify(&ctx, e2, &rules, 100);
    println!("simplified: {}", s);
    // Output: x + z
}

Polynomial Arithmetic

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 does not implement Display; assert coefficients
    assert_eq!(quot.coeffs(), &[Rational::new(1, 1), Rational::new(1, 1)]); // 1 + x
    assert_eq!(rem.coeffs(), &[]); // remainder 0
}

Solving Linear Systems

use ocas_calc::solve::solve_linear_rational;

fn main() {
    // Solve 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);
    // Output: x = 2/1, y = 1/1
}

Number Theory

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

fn main() {
    println!("is_prime(97) = {}", is_prime(&97.into()));
    // Output: is_prime(97) = true

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

    println!("φ(360) = {}", euler_phi(&360.into()));
    // Output: φ(360) = 96
}

For more Rust APIs, see:

• Expression system — Arena, Symbol, Atom, pattern matching
• Coefficient domains — Integer, Rational, FiniteField, etc.
• Polynomials — univariate/multivariate polynomials, monomial orders
• Matrices — determinant, solving, multiplication
• Calculus — diff, integrate, taylor
• Solvers — linear equations, Diophantine, ODEs
• Number theory — primality, factorization, discrete logarithms

Python

Installation

pip install ocas

Requires Python ≥ 3.10 (uses the PyO3 abi3 stable ABI).

Verify the Installation

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

If it prints 2*x, the installation succeeded. To verify in an interactive Python session:

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

Basic Usage

Symbolic Differentiation and Simplification

import ocas

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

# Differentiate
d = e.diff("x")
print(f"derivative: {d}")
# Output: derivative: 2*x

# Simplify (default rule set: identity removal, constant folding)
e2 = ocas.Expression("x + 0 + y*0 + z*1")
s = e2.simplify()
print(f"simplified: {s}")
# Output: simplified: x + z

Polynomial Arithmetic

import ocas

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

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

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

Finite Field Arithmetic

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

Matrix Operations

import ocas

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

Number Theory

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 Solving

import ocas

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

# Classify the available solving methods
methods = ocas.classify_ode(e, "y", "x")
print(methods)

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

For more Python APIs, see the Python API reference.

C/C++

Building the C Library

oCAS's C library is built with cargo. Clone the source repository and compile:

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

The build artifacts are placed in target/release/:

The header file ocas.h lives in the ocas-c/include/ directory. C++ users can also use ocas.hpp in the same directory (RAII wrappers covering the expression, number theory, and tensor domains).

Windows users: the MSYS2 MINGW64 environment is recommended. See Building on Windows.

Verify the Installation

Create a minimal test file 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, "parse failed\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);
    /* Output: d/dx(x² + 2x + 1) = 2 + 2*x */

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

Compile and run (Linux example; adjust the paths to match your environment):

# assuming oCAS is built at /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

If it prints 2 + 2*x, the installation succeeded.

Basic Usage

Symbolic Differentiation

#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("derivative: %s\n", s);
    /* Output: derivative: 2*x */

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

Number Theory

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

int main(void) {
    char *result;

    /* Primality test */
    int prime = ocas_ntheory_isprime("97", NULL);
    printf("is_prime(97) = %s\n", prime ? "true" : "false");
    /* Output: is_prime(97) = true */

    /* Integer factorization */
    result = ocas_ntheory_factorint("360", NULL);
    printf("360 = %s\n", result);
    /* Output: 360 = 2:3,3:2,5:1 */
    ocas_string_free(result);

    /* Euler φ function */
    result = ocas_ntheory_totient("360", NULL);
    printf("φ(360) = %s\n", result);
    /* Output: φ(360) = 96 */
    ocas_string_free(result);

    return 0;
}

C++ RAII Wrappers

If you use C++, the RAII wrappers in ocas.hpp save you from manual memory management:

#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;
    // Output: d/dx = 2 + 2*x

    // Number theory (no manual 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;
}

For more C/C++ APIs, see the C/C++ API reference.

FAQ

Rust

Q: Compilation is slow, what can I do?

oCAS contains a lot of generic code, so the first build can be slow. Suggestions:

• During development use cargo build (dev profile, dependencies already use opt-level = 3)
• For releases use cargo build --release (enables LTO)
• Use sccache or cargo-nextest to speed up incremental builds

Q: The gmp feature fails because the GMP library is not found?

On Linux/macOS, make sure the GMP development package is installed:

# Ubuntu/Debian
sudo apt install libgmp-dev

# macOS (Homebrew)
brew install gmp

On Windows (MSYS2 MINGW64):

pacman -S mingw-w64-x86_64-gmp

Or use the system-libs feature to link against system-installed libraries. See Building on Windows.

Q: The flint feature is unavailable on Windows?

The upstream flint3-sys crate only supports POSIX platforms, so the flint feature is not supported on Windows for now.

Python

Q: pip install ocas fails?

Check that Python ≥ 3.10 is used:

python --version

To build from source:

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

Q: Why do some functions in the Python bindings have a py_ prefix?

Some Gröbner functions (e.g. ocas.py_groebner_basis) keep the py_ prefix because the PyO3 bindings have not yet added #[pyo3(name=...)] annotations. Just call the functions with the prefixed names.

C/C++

Q: Linking fails with undefined reference?

Make sure the link order is correct — libocas_c goes after your source file:

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

And make sure LD_LIBRARY_PATH (Linux) or PATH (Windows) contains the library directory.

Q: Some functions are missing from ocas.h?

The ocas.h shipped in the repository may not be up to date. cbindgen generates a fresh header under target/release/build/ocas-c-*/out/ at build time. Use that file instead.

Q: What functionality do the C++ wrappers in ocas.hpp cover?

ocas.hpp currently covers three domains: expressions (ocas::Expression), number theory (ocas::ntheory::*), and tensors (ocas::tensor::*). For the remaining domains (polynomials, Gröbner, ODEs, etc.) use the C API directly.

General

Q: Numeric results are imprecise?

By default oCAS uses pure-Rust num-bigint rational arithmetic, which is exact. If you need high-precision floats (interval arithmetic), enable the mpfr feature:

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

Q: How do I check the oCAS version?

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

Next Steps

• Rust API reference — complete documentation of Rust modules, types, and functions
• Python API reference — detailed documentation of all Python classes and functions
• C/C++ API reference — C exported functions, C++ RAII wrappers, memory management
• Architecture — overall design and module relationships of oCAS
• Gröbner basis implementation — Buchberger / F4 / F5 algorithms in detail
• ODE solving — classification and solution methods for ordinary differential equations

Architecture

oCAS is organized as a Cargo workspace of 12 public crates (plus ocas-tests for integration tests and benchmarks) with strict downward layering. Each crate may only depend on lower-level crates; no reverse or cyclic dependencies are permitted.

Notable modules

ocas-poly::factor — Polynomial factorization using Hensel lifting and finite-field techniques. Supports square-free decomposition and full factorization over the integers and rationals.

ocas-poly::groebner — Gröbner basis computation with three algorithms: Buchberger, F4 (production default), and F5 (signature-based). Supports configurable monomial orders (Lex, Grevlex, WeightOrder, BlockOrder) and FGLM conversion for zero-dimensional ideals.

ocas-poly::roots — Real root isolation for univariate polynomials.

ocas-tests::correctness — Cross-validation framework with 201 #[test] tests across 19 mathematical modules (as of 0.24.0), comparing oCAS results against SymPy, SageMath, and Symbolica.

See ARCHITECTURE_EN.md in the repository for the full design document.

Rust API Reference

oCAS's Rust API uses a layered crate architecture. The top-level ocas crate re-exports all commonly used types and functions through its prelude module, so a single import is all you need:

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

Module Hierarchy

graph TD
    OC["ocas<br/>top-level entry point + prelude"]
    CORE["ocas-core<br/>Arena, errors, fuel"]
    DOMAIN["ocas-domain<br/>coefficient domains, number theory, algebraic number fields"]
    ATOM["ocas-atom<br/>expression trees, tensors"]
    PARSE["ocas-parse<br/>string parsing"]
    POLY["ocas-poly<br/>polynomials, matrices, Gröbner bases"]
    REWRITE["ocas-rewrite<br/>pattern matching, simplification, rewriting"]
    CALC["ocas-calc<br/>calculus, ODEs, solvers"]
    EVAL["ocas-eval<br/>evaluator, JIT, numeric integration"]

    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 Contents

use ocas::prelude::* imports all of the following items. The most commonly used types can also be accessed directly as ocas::TypeName.

Expression Trees

Coefficient Domains

Polynomials

Matrices

Gröbner Bases

Calculus

Solvers

Rewriting & Simplification

Evaluation & JIT

Numeric Integration

Automatic Differentiation

Tensors

Runtime

Feature Flags Quick Reference

Enable optional backends and acceleration features via the features key in Cargo.toml:

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

Tip: default = [] — all backends are off by default for maximum portability (including Windows MSVC). Recommended development configuration: features = ["gmp", "jit"].

Subpage Index

Quick Start

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

fn main() {
    // 1. Create the arena and expression context
    let arena = Arena::new();
    let ctx = AtomArena::new(&arena);

    // 2. Build the expression sin(x)
    let x = ctx.var("x");
    let expr = ctx.fun("sin", &[x]);

    // 3. Differentiate symbolically (diff takes a Symbol as the variable)
    let deriv = diff(&ctx, expr, Symbol::new("x"));
    assert_eq!(deriv.to_string(), "cos(x)");

    // 4. Simplify (an empty rule set keeps the expression unchanged)
    let simplified = simplify(&ctx, expr, &[], 100);
    assert_eq!(simplified.to_string(), "sin(x)");

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

See Also

• Architecture Overview — overall design and data flow
• Mathematics Overview — background mathematics and learning paths
• Python API Reference — Python bindings
• C/C++ API Reference — C/C++ bindings

Rust API Reference: Expression System

This chapter documents the core types and functions of the oCAS expression system: the Arena allocator, symbols, expression nodes, construction contexts, parsing, normalization, and pattern matching.

Core Type Overview

The core type hierarchy of the expression system is:

Arena (bump allocator)
 └── AtomArena (hash-consing constructor)
      └── Atom (Copy handle)
           └── AtomNode (enum: Num/Var/Fun/Add/Mul/Pow)
                └── Symbol (interned string)

Design invariants: Atom is a Copy arena handle pointing to an AtomNode allocated in the Arena. Because AtomArena uses hash-consing (structurally identical subexpressions return the same pointer within the same AtomArena), structural equality is equivalent to pointer equality — the result of == agrees with pointer comparison. Note the implementation detail: Atom's PartialEq is a derived structural comparison (recursively comparing AtomNodes); hash-consing guarantees its truth value agrees with pointer equality rather than comparing pointers directly. Subtraction and division are desugared at parse time: $x - y$ becomes Add([x, Mul([Num(-1), y])]), and $x / y$ becomes Mul([x, Pow(y, Num(-1))]).

Arena

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

Arena is a bump allocator that provides bulk memory management for expression nodes. All expression nodes are allocated in an Arena, and the entire memory is freed at once when the Arena is dropped. The current version does not run destructors, so it is only safe to store Copy types.

Arena::new

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

Function: Creates an Arena using the default block size (64 KiB).

Parameters: None.

Return value: Arena.

Example:

#![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
}

Function: Creates an Arena using the given block size.

Parameters:

Return value: Arena.

Arena::allocate_with

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

Function: Allocates a value in the Arena, constructed via the closure, and returns a mutable reference bound to the Arena's lifetime.

Parameters:

Return value: &mut T.

Errors: Panics if T has zero size.

Example:

#![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]
}

Function: Copies a slice into the Arena and returns a slice reference bound to the Arena's lifetime. An empty slice returns &[].

Parameters:

Return value: &[T].

Example:

#![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)
}

Function: Resets the Arena — keeps the first memory block and resets the offset, freeing the remaining blocks. After a reset, any references allocated previously must not be used.

Parameters: None.

Return value: None.

Example:

#![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
}

Function: Returns the number of memory blocks currently held by the Arena.

Parameters: None.

Return value: 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 is a globally interned symbol name used for variable names, function names, and constant names. Symbols with identical contents point to the same static memory within the process, making comparisons $O(1)$ pointer comparisons. Symbol implements Copy.

Symbol::new

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

Function: Creates or looks up an existing Symbol. The string is interned on first call; subsequent calls return the existing Symbol.

Parameters:

Return value: Symbol.

Example:

#![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
}

Function: Returns the string slice of the symbol.

Parameters: None.

Return value: &str.

See also: 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 is a lightweight Copy handle to an AtomNode in the Arena. Copying an Atom only copies a pointer, not the underlying data. Thanks to hash-consing, the truth value of a == b agrees with pointer comparison (within the same AtomArena); the implementation is a derived structural comparison.

Atom implements Display, with the following output formats:

• Num(42) → 42
• Var("x") → x
• Fun("sin", [x]) → sin(x)
• Add([x, y]) → x + y (subexpressions are parenthesized unless they are leaf nodes)
• Mul([x, y]) → x*y
• Pow(x, n) → x^n (base/exponent parenthesized unless they are leaves)

Atom::node

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

Function: Returns a reference to the underlying node data. Used for pattern-matching the expression structure.

Parameters: None.

Return value: &'a AtomNode<'a>.

Example:

#![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>]
}

Function: Returns the slice of direct child expressions (left to right). Num and Var return an empty slice; Fun, Add, and Mul return their argument slices; Pow returns an empty slice (use binary_children to get the two operands).

Parameters: None.

Return value: &'a [Atom<'a>].

Example:

#![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>)>
}

Function: If this Atom is a Pow node, returns (base, exp); otherwise returns None.

Parameters: None.

Return value: Option<(Atom<'a>, Atom<'a>)>.

Example:

#![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");
}

See also: 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>),
}
}

The concrete data of each node in the expression tree. An Atom handle obtains an AtomNode reference via the node() method.

Variant descriptions

Design notes:

• Subtraction/division are desugared at parse time: $x - y$ becomes Add([x, Mul([Num(-1), y])]), and $x / y$ becomes Mul([x, Pow(y, Num(-1))]). There are no standalone subtraction or division nodes in the AST.
• The argument lists of Add and Mul are sorted after normalize, ensuring that structurally equal expressions produce the same AST.

Example:

#![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"),
}
}

See also: 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 is the only entry point for constructing Atoms. It wraps an Arena reference and a hash-consing table (interior mutability via RefCell). All construction methods are immutable from the caller's perspective. Structurally identical subexpressions always return the same Atom handle within the same AtomArena — this makes structural equality equivalent to pointer equality.

AtomArena::new

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

Function: Creates an AtomArena backed by the given Arena.

Parameters:

Return value: AtomArena<'a>.

Example:

#![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>
}

Function: Creates an integer literal Atom.

Parameters:

Return value: Atom<'a> — a Num(value) node.

Example:

#![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>
}

Function: Creates a variable Atom.

Parameters:

Return value: Atom<'a> — a Var(Symbol) node.

Example:

#![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>
}

Function: Creates a function-application Atom.

Parameters:

Return value: Atom<'a> — a Fun(Symbol, &[Atom]) node.

Example:

#![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>
}

Function: Creates an addition Atom.

Parameters:

Return value: Atom<'a> — an Add(&[Atom]) node.

Example:

#![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>
}

Function: Creates a multiplication Atom.

Parameters:

Return value: Atom<'a> — a Mul(&[Atom]) node.

Example:

#![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>
}

Function: Creates an exponentiation Atom.

Parameters:

Return value: Atom<'a> — a Pow(base, exp) node.

Example:

#![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>]
}

Function: Allocates a slice of Atoms into the Arena and returns the reference. Used for multi-result scenarios that share the Arena lifetime (e.g., component solutions of ODE systems).

Parameters:

Return value: &'a [Atom<'a>].

See also: Arena, Atom

Functions

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>
}

Function: Parses a mathematical expression string into an Atom tree. Supports integers, variables, function calls (f(x)), addition, subtraction, multiplication, division, exponentiation, and parentheses. Subtraction desugars to addition with a negative coefficient; division desugars to multiplication with a negative exponent.

Parameters:

Return value: Result<Atom<'a>, ParseError>.

Errors:

Example:

#![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");
}

See also: 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>
}

Function: Normalizes an expression into a deterministic canonical form. Specifically:

• Flattens nested Add and Mul (e.g., Add([Add([x, y]), z]) → Add([x, y, z]))
• Sorts the operands
• Combines numeric coefficients (e.g., Add([x, Num(2), Num(3)]) → Add([Num(5), x]))

The result is allocated in the same arena as the input.

Parameters:

Return value: Atom<'a> — the normalized expression.

Example:

#![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");
}

See also: 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>
}

Function: Replaces every occurrence of the variable var in the expression with replacement. A convenience function implemented on top of transform.

Parameters:

Return value: Atom<'a> — the substituted expression.

Example:

#![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");
}

See also: 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>>,
}

Function: Traverses the expression tree bottom-up and applies the transform function f to each node. f is called after the node's children have been transformed. Returning Some(atom) replaces the node; returning None keeps the node (with its transformed children). This is the standard rewrite traversal pattern used by the oCAS rule engine and simplifier.

Parameters:

Return value: Atom<'a> — the transformed expression.

Example:

#![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");
}

See also: 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>)>
}

Function: Collects all function applications in the expression in post-order (innermost first), deduplicated (hash-consing guarantees that structurally identical applications appear only once).

Parameters:

Return value: Vec<(Symbol, Atom<'a>)> — a list of (function name, function application node).

Example:

#![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");
}

See also: 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>
}

Function: Collects all distinct variable names in the expression, in order of first appearance (depth-first, left to right).

Parameters:

Return value: Vec<Symbol> — the list of variable names.

Example:

#![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");
}

See also: collect_funs

Pattern Matching

The pattern-matching system matches Atom expression trees against patterns with wildcards (Pattern), with support for associative/commutative (AC) matching and backtracking-budget control.

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>>),
}
}

Patterns mirror the structure of AtomNode but add wildcard nodes. Matching of Add and Mul supports associative-commutative (AC) matching: subpatterns can match any subset of the argument list.

Pattern::from_atom

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

Function: Converts an Atom into a Pattern. Variables whose names end in _ (or begin with _) are treated as wildcards:

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

Parameters:

Return value: Pattern<'a>.

Example:

#![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"));
}

See also: 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,
}
}

The matching scope of a wildcard.

Example:

#![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>
}

Function: Attempts to match pattern against atom, returning the binding set on success. Uses the default backtracking budget (DEFAULT_MAX_BACKTRACKS = 10_000). Add/Mul use AC matching (full backtracking search); Fun uses ordered matching (with sequence wildcard support).

Parameters:

Return value: Result<Bindings<'a>, MatchError>.

Example:

#![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>
}

Function: Same as match_pattern, but allows a custom backtracking budget to prevent exponential-time blowups on pathological inputs.

Parameters:

Return value: Result<Bindings<'a>, MatchError>.

Errors: Returns MatchError::BudgetExhausted if the backtracking limit is exceeded.

See also: match_pattern

Bindings

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

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

The set of wildcard bindings produced by a successful match.

Bindings::new

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

Function: Creates an empty binding set.

Bindings::get

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

Function: Looks up the bound value by wildcard name.

Parameters:

Return value: Option<&MatchValue<'a>>.

Example:

#![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>]),
}
}

The value type of a wildcard binding.

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,
}
}

Pattern-matching errors.

See also

• Rewrite & Simplification — the full rewrite engine: Rule, simplify, replace_all, and more
• Calculus — diff, integrate, taylor, and other operations built on the expression system
• Coefficient Domains — the Domain trait and the various domain types

Rust API Reference: Coefficient Domains

Coefficient domains are the foundational abstraction behind all of oCAS's polynomial, matrix, and solver algorithms. Each domain describes a set of elements and their arithmetic operations, unified through the Domain and EuclideanDomain traits.

Module path: ocas_domain

Imports:

#![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

Signature:

#![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;
}
}

Description: The core trait for coefficient domains. The domain object itself may carry parameters (such as the modulus of a finite field), so all operations go through &self. This follows the "domain object" pattern used by CAS libraries such as Flint and SymPy's Domain.

Associated types:

Methods:

Example:

#![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));
// Output: all assertions pass
}

See also: EuclideanDomain

EuclideanDomain trait

Signature:

#![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);
}
}

Description: A Euclidean domain supporting division with remainder. An extension of Domain that additionally provides div_rem (division with remainder), gcd (greatest common divisor), and extended_gcd (extended Euclidean algorithm).

Methods:

div_rem

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

Description: Division with remainder, returning (quotient, remainder) such that a = quotient * b + remainder and remainder == 0 or deg(remainder) < deg(b).

Parameters:

Return value: Some((quotient, remainder)), or None when b is zero.

Example:

#![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));
// Output: 17 = 3 × 5 + 2
}

gcd

Signature: fn gcd(&self, a: &Self::Element, b: &Self::Element) -> Self::Element

Description: Computes the greatest common divisor. The default implementation uses the Euclidean algorithm.

Return value: gcd(a, b). For a field (such as FiniteField), the GCD of two non-zero elements degenerates to 1.

Example:

#![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));
// Output: gcd(12, 8) = 4
}

extended_gcd

Signature: fn extended_gcd(&self, a: &Self::Element, b: &Self::Element) -> (Self::Element, Self::Element, Self::Element)

Description: Extended Euclidean algorithm, returning (g, x, y) such that g = gcd(a, b) = a * x + b * y.

Return value: The triple (g, x, y).

Example:

#![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, so that 5 = 35×1 + 15×(-2)
assert_eq!(g, Integer::from(5));
}

See also: Domain

Integer / IntegerDomain

IntegerDomain

Signature: pub struct IntegerDomain;

Description: The integer domain $\mathbb{Z}$, with element type Integer. Implements Domain and EuclideanDomain.

Characteristics:

• div requires exact division (zero remainder), otherwise returns None
• inv returns a result only for $\pm 1$, otherwise None
• pow uses binary exponentiation

Example:

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

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

// Exact division: 10/3 is not exact
assert!(domain.div(&a, &b).is_none());

// Division with remainder
let (q, r) = domain.div_rem(&a, &b).unwrap();
assert_eq!(q, Integer::from(3));
assert_eq!(r, Integer::from(1));

// Inverse: only ±1 have inverses
assert!(domain.inv(&Integer::from(1)).is_some());
assert!(domain.inv(&Integer::from(5)).is_none());
// Output: all assertions pass
}

Integer

Signature: pub struct Integer(BigInt);

Description: An arbitrary-precision integer. The default build uses num-bigint's BigInt; with the gmp feature enabled, a GMP backend is used.

Derives: Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash

Construction and conversion

Integer::new

Signature: pub fn new<T: Into<BigInt>>(value: T) -> Self

Description: Creates an arbitrary-precision integer from a machine integer or a BigInt.

Parameters:

Example:

#![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");
// Output: 42
}

Integer::from

Signature: impl From<i64> for Integer / impl From<BigInt> for Integer

Description: Conversion from i64 or BigInt.

Example:

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

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

Accessors

Integer::inner

Signature: pub fn inner(&self) -> &BigInt

Description: Accesses the underlying BigInt reference.

Integer::to_bigint

Signature: pub fn to_bigint(&self) -> BigInt

Description: Clones into a BigInt (regardless of backend).

Integer::to_i64

Signature: pub fn to_i64(&self) -> Option<i64>

Description: Attempts conversion to i64. Returns None on overflow.

Arithmetic methods

Integer::pow_u32

Signature: pub fn pow_u32(&self, exp: u32) -> Self

Description: Computes $n^{exp}$.

Parameters:

Example:

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

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

Integer::modpow

Signature: pub fn modpow(&self, exp: &Integer, modulus: &Integer) -> Integer

Description: Modular exponentiation $self^{exp} \bmod modulus$.

Parameters:

Example:

#![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");
// Output: 3^100 mod 7 = 4
}

Integer::mod_floor

Signature: pub fn mod_floor(&self, modulus: &Integer) -> Integer

Description: Floor modulus; the result $r$ satisfies $0 \leq r < |modulus|$.

Example:

#![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");
// Output: -7 mod_floor 3 = 2
}

Integer::div_rem

Signature: pub fn div_rem(&self, other: &Integer) -> (Integer, Integer)

Description: Division with remainder, (quotient, remainder). Note: unlike EuclideanDomain::div_rem, this method does not require other to be non-zero (behavior is determined by the underlying BigInt).

Integer::is_even

Signature: pub fn is_even(&self) -> bool

Description: Whether the integer is even.

Integer::is_negative

Signature: pub fn is_negative(&self) -> bool

Description: Whether the integer is negative.

Integer::is_zero

Signature: pub fn is_zero(&self) -> bool

Description: Whether the integer is zero.

Integer::is_one

Signature: pub fn is_one(&self) -> bool

Description: Whether the integer is one.

Integer::abs

Signature: pub fn abs(&self) -> Integer

Description: Absolute value.

Integer::sqrt

Signature: pub fn sqrt(&self) -> Integer

Description: Integer square root (floored).

Example:

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

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

Operators

Integer implements the following standard operator traits (all reference combinations are supported: owned × owned, owned × &, & × owned, & × &):

See also: Domain, Rational, Number-theoretic functions

Rational / RationalDomain

RationalDomain

Signature: pub struct RationalDomain;

Description: The rational number field $\mathbb{Q}$, with element type Rational. Implements Domain and EuclideanDomain.

Characteristics:

• div returns an exact result for every non-zero divisor
• inv returns a result for every non-zero element
• EuclideanDomain's div_rem degenerates over the rationals: the remainder is always zero

Example:

#![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));
// Output: 1/2 + 1/3 = 5/6
}

Rational

Signature: pub struct Rational(BigRational);

Description: An arbitrary-precision rational number. The default build uses num-rational's BigRational; with the gmp feature enabled, a GMP backend is used.

Derives: Debug, Clone, PartialEq, Eq, Hash

Construction

Rational::new

Signature: pub fn new(numer: i64, denom: i64) -> Self

Description: Creates a rational from a numerator and denominator (i64). Automatically reduced to lowest terms. Behavior for a zero denominator is determined by the underlying library.

Parameters:

Example:

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

let a = Rational::new(3, 6);
assert_eq!(a.to_string(), "1/2");
// Output: 3/6 automatically reduces to 1/2
}

Rational::from_bigints

Signature: pub fn from_bigints(numer: BigInt, denom: BigInt) -> Self

Description: Creates a rational from an arbitrary-precision integer numerator and denominator.

Rational::from_integer

Signature: pub fn from_integer(n: Integer) -> Self

Description: Creates a rational from an integer (denominator = 1).

Accessors

Rational::inner

Signature: pub fn inner(&self) -> &BigRational

Description: Accesses the underlying BigRational reference.

Rational::numer

Signature: pub fn numer(&self) -> Integer

Description: Returns the numerator (as an Integer).

Rational::denom

Signature: pub fn denom(&self) -> Integer

Description: Returns the denominator (as an Integer, always positive).

Example:

#![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");
// Output: numerator = 3, denominator = 4
}

Operators

Rational implements the following standard operator traits:

See also: Domain, Integer

FiniteField / FiniteFieldElement

FiniteField

Signature: pub struct FiniteField { /* prime: BigInt, ... */ }

Description: The prime finite field $\mathbb{Z}/p\mathbb{Z}$. Arithmetic uses arbitrary-precision integers, supporting large primes. Implements Domain and EuclideanDomain.

Construction

FiniteField::new

Signature: pub fn new(prime: BigInt) -> Self

Description: Creates a finite field with the given prime modulus.

Parameters:

Errors: panics in debug mode if prime < 2.

Example:

#![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)
// Output: all assertions pass
}

Element construction

FiniteField::element

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

Description: Creates a field element from an arbitrary integer. The value is automatically reduced to $[0, p-1]$.

Parameters:

Example:

#![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");
// Output: 10 mod 7 = 3
}

FiniteField::from_i64

Signature: pub fn from_i64(&self, val: i64) -> FiniteFieldElement

Description: Creates a field element from an i64 (reduced mod p).

Accessors

FiniteField::prime

Signature: pub fn prime(&self) -> &BigInt

Description: Returns the field's modulus.

FiniteField::prime_u64

Signature: pub fn prime_u64(&self) -> u64

Description: Returns the modulus as a u64.

Errors: panics if the prime does not fit in a u64.

FiniteField::to_i64

Signature: pub fn to_i64(&self, a: &FiniteFieldElement) -> i64

Description: Converts a field element to an i64 (in the range $[0, p)$).

Errors: panics if the prime does not fit in a u64.

Domain implementation

• div inverts via Fermat's little theorem: $a^{-1} \equiv a^{p-2} \pmod{p}$
• inv as above; returns None for the zero element
• pow uses the modpow optimization (much faster than the default binary exponentiation)

EuclideanDomain implementation

• div_rem: division is exact in a field; the remainder is always zero
• gcd: GCD degenerates in a field — returns 0 when both are zero, otherwise 1

See also: Domain, Finite field mathematics

FiniteFieldElement

Signature: pub struct FiniteFieldElement { value: BigInt }

Description: An element of a prime finite field. The value is always in $[0, p-1]$.

Derives: Debug, Clone, PartialEq, Eq, Hash

FiniteFieldElement::value

Signature: pub fn value(&self) -> &BigInt

Description: Returns the canonical representative in $[0, p-1]$.

Example:

#![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");
// Output: -3 mod 7 = 4
}

See also: FiniteField

RealBall / RealBallDomain

RealBallDomain

Signature: pub struct RealBallDomain;

Description: The real ball (interval) domain. Element type RealBall. Implements only Domain (not EuclideanDomain, because real balls do not support exact division with remainder).

Note: The default build uses lightweight f64 balls, suitable for templates and demos. With the mpfr feature enabled, rug::Float with directed rounding produces rigorous intervals.

RealBall

Signature: pub struct RealBall { mid: f64, rad: f64 } (default build)

Description: A real ball: midpoint ± radius. The true value is guaranteed to lie in $[mid - rad, mid + rad]$.

Derives: Debug, Clone, PartialEq, Eq; the default build additionally implements Copy.

Construction

RealBall::new

Signature (default): pub fn new(mid: f64, rad: f64) -> Self

Description: Creates a ball from a midpoint and radius. The radius is clamped to be non-negative.

Parameters:

RealBall::from_f64

Signature: pub fn from_f64(value: f64) -> Self

Description: Creates a zero-radius (exact) ball from an f64 value.

Example:

#![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);
// Output: exact ball
}

Accessors

RealBall::mid

Signature: pub fn mid(&self) -> f64 (default) / pub fn mid(&self) -> &rug::Float (mpfr)

Description: Returns the midpoint.

RealBall::rad

Signature: pub fn rad(&self) -> f64 (default) / pub fn rad(&self) -> &rug::Float (mpfr)

Description: Returns the radius.

RealBall::lower

Signature: pub fn lower(&self) -> f64 (default) / pub fn lower(&self) -> rug::Float (mpfr)

Description: Returns the conservative lower bound $mid - rad$ (the mpfr version rounds downward).

RealBall::upper

Signature: pub fn upper(&self) -> f64 (default) / pub fn upper(&self) -> rug::Float (mpfr)

Description: Returns the conservative upper bound $mid + rad$ (the mpfr version rounds upward).

RealBall::precision

Signature: pub fn precision(&self) -> u32 (mpfr feature only)

Description: Returns the precision (in bits) of the MPFR backend.

Domain implementation

• add: $(a \pm r_a) + (b \pm r_b) = (a+b) \pm (r_a + r_b)$ (the mpfr version additionally adds rounding error)
• sub: like addition; the radii add
• mul: four-corner method — compute the four extreme products $a_lo \cdot b_lo$, $a_lo \cdot b_hi$, etc., and take the min/max for the new interval
• div: $a / b = a \cdot b^{-1}$, returns None when the ball contains zero
• inv: $1/(mid \pm rad)$, returns None when the ball contains zero

Example:

#![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());
// Output: the product ball contains the true value 6.0
}

See also: Domain

Complex / ComplexDomain

ComplexDomain

Signature: pub struct ComplexDomain<D: Domain> { base: D, ... }

Description: The complex field built over an arbitrary base domain $D$. Element type Complex<D>. Implements only Domain.

Construction

ComplexDomain::new

Signature: pub fn new(base: D) -> Self

Description: Creates the complex field over the base domain base.

Parameters:

ComplexDomain::base

Signature: pub fn base(&self) -> &D

Description: Returns a reference to the base domain.

ComplexDomain::real_element

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

Description: Creates a purely real element.

ComplexDomain::imag_element

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

Description: Creates a purely imaginary element.

Domain implementation

• 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}$, returns None when the denominator is zero
• inv: implemented via div(one, a)

Example:

#![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));
// Output: (1+2i) + (3+4i) = 4+6i
}

See also: Domain

Complex

Signature: pub struct Complex<D: Domain> { inner: NumComplex<D::Element> }

Description: A complex number whose real and imaginary parts belong to the base domain $D$.

Derives: Debug, Clone, PartialEq, Eq, Hash

Construction and access

Complex::new

Signature: pub fn new(real: D::Element, imag: D::Element) -> Self

Description: Creates a complex number from its real and imaginary parts.

Complex::re

Signature: pub fn re(&self) -> &D::Element

Description: Returns a reference to the real part.

Complex::im

Signature: pub fn im(&self) -> &D::Element

Description: Returns a reference to the imaginary part.

Complex::inner

Signature: pub fn inner(&self) -> &NumComplex<D::Element>

Description: Returns a reference to the underlying num_complex::Complex.

See also: ComplexDomain

DoubleF64 / DoubleF64Domain

DoubleF64Domain

Signature: pub struct DoubleF64Domain;

Description: The double-double floating-point domain. Element type DoubleF64. Implements only Domain.

DoubleF64

Signature:

#![allow(unused)]
fn main() {
pub struct DoubleF64 {
    pub hi: f64,  // high component (principal value)
    pub lo: f64,  // low component (error term)
}
}

Description: A double-double floating-point number represented as $hi + lo$ with $|lo| \leq 0.5 \cdot \text{ulp}(hi)$. Provides about 31 decimal digits of precision (~84 bits), roughly twice the precision of a single f64.

Derives: Debug, Clone, Copy, PartialEq; implements Eq.

Arithmetic is based on the error-free transformation algorithms of Dekker and Knuth (TwoSum, TwoProd), significantly faster than arbitrary-precision alternatives such as MPFR.

Constants

Construction and conversion

DoubleF64::new

Signature: pub fn new(hi: f64, lo: f64) -> Self

Description: Creates from high and low components. The caller must ensure $|lo| \leq 0.5 \cdot \text{ulp}(hi)$ for correctness.

DoubleF64::from_f64

Signature: pub fn from_f64(x: f64) -> Self

Description: Creates from a single f64 ($lo = 0$).

DoubleF64::to_f64

Signature: pub fn to_f64(self) -> f64

Description: Extracts the high component.

From<f64>

Signature: impl From<f64> for DoubleF64

Description: Equivalent to from_f64.

Error-free transformations

DoubleF64::quick_two_sum

Signature: pub fn quick_two_sum(a: f64, b: f64) -> Self

Description: Error-free summation for $|a| \geq |b|$. Faster than two_sum but requires the precondition.

DoubleF64::two_sum

Signature: pub fn two_sum(a: f64, b: f64) -> Self

Description: Dekker TwoSum — error-free summation in which the rounding error is captured exactly in the lo component.

Example:

#![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 captures the rounding error
}

Queries

Arithmetic operations

DoubleF64::add / sub / mul / div

Signature:

#![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
}

Description: Double-double addition, subtraction, multiplication, and division. Internally uses TwoSum/TwoProd to capture rounding errors.

DoubleF64::powi

Signature: pub fn powi(self, n: i64) -> Self

Description: Integer power using binary exponentiation. Supports negative exponents.

Example:

#![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);
// Output: 3^3 = 27, 3^(-1) = 0.333...
}

Transcendental functions

Example:

#![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
// Output: exp(1) ≈ e, sin(π) ≈ 0
}

Operators

DoubleF64 implements Add, Sub, Mul, Div, Neg, AddAssign, SubAssign, MulAssign, DivAssign, PartialOrd, and Zero (from num_traits).

Display

Displays the hi value when lo == 0; otherwise displays the sum $hi + lo$ in 31-digit scientific notation.

See also: Domain, RealBall

AlgebraicExtension / AlgebraicNumberField / AlgebraicElement

AlgebraicExtension

Signature: pub struct AlgebraicExtension<D: Domain> { base: D, min_poly: Vec<D::Element> }

Description: The algebraic extension $D[\alpha]/(m(\alpha))$, where $m$ is a monic polynomial. When the base domain $D$ is a field and $m$ is irreducible, the quotient ring is a field:

• AlgebraicExtension<RationalDomain> = algebraic number field $\mathbb{Q}(\alpha)$
• AlgebraicExtension<FiniteField> = Galois field $\mathrm{GF}(p^d)$

Elements are residue classes represented by the unique polynomial representative of degree less than $\deg(m)$. Inverses use the extended Euclidean algorithm over the base domain.

⚠️ Note: irreducibility of the minimal polynomial is not checked. Under a reducible modulus the ring has zero divisors, and Domain::inv returns None for non-units.

Implements: Domain, EuclideanDomain

Construction

AlgebraicExtension::new

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

Description: Creates an algebraic extension from a base domain and a monic minimal polynomial.

Parameters:

Errors: debug-mode checks: (1) degree $\geq 1$ (i.e. min_poly.len() >= 2); (2) monic.

Example:

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

// ℚ(√2): minimal polynomial α² − 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));
// Output: α² = 2
}

Accessors

AlgebraicExtension::base_domain

Signature: pub fn base_domain(&self) -> &D

Description: Returns a reference to the base domain.

AlgebraicExtension::min_poly

Signature: pub fn min_poly(&self) -> &[D::Element]

Description: Returns the minimal polynomial coefficients (ascending order, monic).

AlgebraicExtension::extension_degree

Signature: pub fn extension_degree(&self) -> usize

Description: Returns the extension degree $\deg(m)$.

Element construction

AlgebraicExtension::from_base

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

Description: Embeds a base-domain constant into the extension.

AlgebraicExtension::alpha

Signature: pub fn alpha(&self) -> AlgebraicElement<D::Element>

Description: Returns the generator $\alpha$ of the extension.

AlgebraicExtension::element

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

Description: Creates an element from coefficients (ascending order), reducing modulo the minimal polynomial automatically.

Domain implementation

• mul: multiply first, then reduce modulo $m(\alpha)$
• inv: extended Euclidean algorithm — if $\gcd(a, m) = 1$ (a constant), then $a^{-1} = s \bmod m$
• div: $a/b = a \cdot b^{-1}$
• is_zero: the coefficient vector is empty

EuclideanDomain implementation

• div_rem: division is exact in a field; the remainder is always zero
• gcd: degenerates in a field — 0 when both are zero, otherwise 1

Example (Galois field $\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)));
// The multiplicative group has order 8: (1+α)⁸ = 1
let a = field.add(&field.one(), &alpha);
assert_eq!(field.pow(&a, 8), field.one());
// Output: α² = 2, (1+α)⁸ = 1
}

See also: Domain, Algebraic number fields

AlgebraicNumberField

Signature: pub type AlgebraicNumberField = AlgebraicExtension<RationalDomain>;

Description: Type alias for $\mathbb{Q}(\alpha)$.

AlgebraicElement

Signature: pub struct AlgebraicElement<E> { coeffs: Vec<E> }

Description: An element of an algebraic extension — a polynomial residue class in $\alpha$ of degree less than the extension degree. Coefficients are stored in ascending order with trailing zeros trimmed. The zero element has an empty coefficient vector.

Derives: Debug, Clone, PartialEq, Eq, Hash

AlgebraicElement::coeffs

Signature: pub fn coeffs(&self) -> &[E]

Description: Returns the coefficient slice (ascending order, trailing zeros trimmed).

Display

Display format: 0 (zero element), c (pure constant), (c1)·α + c0, (c2)·α^2 + (c1)·α + c0, etc. (the constant term is not parenthesized; terms are joined with +).

Example:

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

// ℚ(i): minimal polynomial α² + 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)]);
// Output: 1/(1+i) = (1/2) - (1/2)·α
}

See also: AlgebraicExtension

Assumptions system

The assumptions system declares properties of symbolic variables (such as "x is real" or "n is a positive integer"). Solvers and simplifiers use assumptions to choose algorithms and validate solutions.

Module path: ocas_domain::assumptions

Assumption

Signature:

#![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,
}
}

Description: A single predicate that can be declared about a symbolic variable. Assumptions are independent — a variable may carry several assumptions at once (e.g. Positive | Integer).

Variant descriptions

Assumption::implied

Signature: pub fn implied(&self) -> &'static [Assumption]

Description: Returns the list of assumptions logically implied by this assumption. When an assumption is inserted, its implications propagate automatically.

Implication table:

Assumption::conflicts

Signature: pub fn conflicts(&self) -> &'static [Assumption]

Description: Returns the list of assumptions this assumption conflicts with. A set containing both an assumption and one of its conflicts is inconsistent.

Conflict table:

All other assumptions have no conflicts.

BitOr support

Assumption | Assumption returns Assumptions:

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

let a = Assumption::Positive | Assumption::Integer;
assert!(a.implies(Assumption::Real));
// Output: Positive | Integer implies Real
}

See also: Assumptions, SymbolAssumptions

Assumptions

Signature: pub struct Assumptions { inner: Vec<Assumption> }

Description: A set of assumptions about one symbolic variable. Stored internally as a sorted, de-duplicated vector for small-scale efficiency. Operations are closed under logical implication — inserting Positive makes NonNegative and Real available.

Derives: Debug, Clone, PartialEq, Eq, Default

Construction

Assumptions::new

Signature: pub fn new() -> Self

Description: Creates an empty assumption set.

Assumptions::single

Signature: pub fn single(a: Assumption) -> Self

Description: Creates a set containing a single assumption (and its implications).

Queries

Assumptions::len

Signature: pub fn len(&self) -> usize

Description: Returns the number of explicitly stored assumptions.

Assumptions::is_empty

Signature: pub fn is_empty(&self) -> bool

Description: Whether the set is empty.

Assumptions::contains

Signature: pub fn contains(&self, a: Assumption) -> bool

Description: Checks whether this set implies the assumption (as a direct member or via logical implication).

Assumptions::implies

Signature: pub fn implies(&self, other: Assumption) -> bool

Description: Checks whether this set logically implies other.

Example:

#![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 implies Real
assert!(a.implies(Assumption::NonZero));    // Positive implies NonZero
assert!(!a.implies(Assumption::Even));      // does not imply Even
// Output: all assertions pass
}

Modification

Assumptions::insert

Signature: pub fn insert(&mut self, a: Assumption) -> bool

Description: Inserts the assumption and all of its logical implications. Returns false if the insertion creates a contradiction (the inconsistent assumption is still stored; check is_consistent).

Assumptions::remove

Signature: pub fn remove(&mut self, a: Assumption)

Description: Removes the assumption. Does not remove assumptions implied by it (they may still be implied by other stored assumptions).

Assumptions::is_consistent

Signature: pub fn is_consistent(&self) -> bool

Description: Checks whether the set is consistent (no conflicting assumptions).

Assumptions::iter

Signature: pub fn iter(&self) -> impl Iterator<Item = Assumption> + '_

Description: Iterates over the stored assumptions.

Operators

• Assumption | Assumption → Assumptions
• Assumptions | Assumption → Assumptions
• Assumptions | Assumptions → Assumptions (union)
• FromIterator<Assumption> → Assumptions

Example:

#![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());
// Output: Positive + Integer is consistent; Positive + Negative is inconsistent
}

See also: Assumption, SymbolAssumptions

SymbolAssumptions

Signature: pub struct SymbolAssumptions { entries: Vec<(String, Assumptions)> }

Description: A mapping from symbol names to assumptions. Solvers and simplifiers use it to determine which transformations are legal. For example, $\sqrt{x^2} \to x$ is valid only when x is assumed NonNegative.

Derives: Debug, Clone, PartialEq, Eq, Default

Construction

SymbolAssumptions::new

Signature: pub fn new() -> Self

Description: Creates an empty mapping.

Queries and modification

SymbolAssumptions::set

Signature: pub fn set(&mut self, symbol: &str, assumptions: Assumptions)

Description: Sets the assumptions for a symbol (replacing any existing entry).

SymbolAssumptions::get

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

Description: Gets the assumptions for a symbol.

SymbolAssumptions::remove

Signature: pub fn remove(&mut self, symbol: &str)

Description: Removes the assumptions for a symbol.

SymbolAssumptions::check

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

Description: Checks whether a symbol satisfies a particular assumption.

SymbolAssumptions::len

Signature: pub fn len(&self) -> usize

Description: Returns the number of symbols with assumptions.

SymbolAssumptions::is_empty

Signature: pub fn is_empty(&self) -> bool

Description: Whether no symbol has assumptions.

SymbolAssumptions::iter

Signature: pub fn iter(&self) -> impl Iterator<Item = &(String, Assumptions)>

Description: Iterates over all (symbol name, assumption set) pairs.

Example:

#![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 implies Real
assert!(sa.check("n", Assumption::NonZero));   // Positive implies NonZero
assert!(!sa.check("x", Assumption::Integer));  // does not imply Integer
// Output: all assertions pass
}

See also: Assumptions, Assumption

Rust API Reference: Polynomials

This chapter documents oCAS's polynomial system, covering three core data structures:

• DenseUnivariatePolynomial<D> — dense univariate polynomials
• SparseMultivariatePolynomial<D, O> — sparse multivariate polynomials
• RationalPolynomial<D, O> — elements of the polynomial fraction field

as well as the monomial order trait MonomialOrder and its implementations for various orders.

Module path: ocas_poly

Table of Contents

• Monomial Orders
  • MonomialOrder trait
  • Lex
  • Grlex
  • Grevlex
  • WeightOrder
  • BlockOrder and SubOrder
  • MatrixOrder
• DenseUnivariatePolynomial
  • Construction and Properties
  • Basic Arithmetic
  • EuclideanDomain Operations
  • Factorization and Resultants
• SparseMultivariatePolynomial
  • Construction and Properties
  • Basic Arithmetic
  • Gröbner Basis Support
  • Multivariate Factorization
• RationalPolynomial
• Helper Functions

Monomial Orders

MonomialOrder trait

Signature:

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

Description: Defines a total order on monomials. A polynomial's leading term, sorting, and Gröbner basis computations all depend on it.

Parameters:

Returns: std::cmp::Ordering — Less means lhs comes before rhs in the order (i.e., lhs is larger), Greater means lhs is smaller.

Design notes: The simple orders (Lex, Grevlex, Grlex) are zero-sized types with no runtime overhead. The parameterized orders (WeightOrder, BlockOrder, MatrixOrder) store their configuration at construction time.

See also: Lex, Grevlex, Grlex, WeightOrder, BlockOrder, MatrixOrder

Lex

Signature:

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

Description: Lexicographic order. Compares exponent vectors component by component from left to right.

Comparison rule: lhs > rhs if and only if there exists an $i$ such that $\alpha_j = \beta_j$ for all $j < i$ and $\alpha_i > \beta_i$.

Example:

#![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 is larger in Lex order (first component 2 > 1)
}

See also: MonomialOrder trait

Grlex

Signature:

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

Description: Graded lexicographic order. Orders by total degree descending first, then lexicographically among monomials of equal degree.

Comparison rule:

1. The monomial with the larger total degree $\sum \alpha_i$ comes first
2. Monomials of equal total degree are compared lexicographically

Example:

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

let a = [2, 0]; // x^2, degree 2
let b = [1, 1]; // xy, degree 2
let c = [0, 3]; // y^3, degree 3
// c has the highest degree, so it comes first
assert_eq!(Grlex.cmp(&c, &a), std::cmp::Ordering::Less);
// a and b have the same degree; lexicographically a > b
assert_eq!(Grlex.cmp(&a, &b), std::cmp::Ordering::Greater);
}

See also: MonomialOrder trait

Grevlex

Signature:

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

Description: Graded reverse lexicographic order. Orders by total degree descending first, then compares in reverse lexicographic order (starting from the last component, with the direction reversed).

Comparison rule:

1. The monomial with the larger total degree comes first
2. For equal total degree, compare starting from the last component, where the smaller component comes first

Properties: Grevlex typically produces the smallest intermediate matrices in Gröbner basis computations and is the default order.

Example:

#![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);
// Under Grevlex, a < b (reverse lexicographic order flips the direction)
}

See also: MonomialOrder trait

WeightOrder

Signature:

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

Description: Weighted order. Orders by $\sum_i w_i \cdot \alpha_i$ descending. Suitable for elimination orders that cannot be expressed with a zero-sized type.

Construction:

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

Parameters:

Default: all weights set to 1 (i.e., the total degree order).

Example:

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

let ord = WeightOrder::new(smallvec![2, 1]);
// [1,0] → weight 2, [0,1] → weight 1 → [1,0] is larger
assert_eq!(ord.cmp(&[1, 0], &[0, 1]), std::cmp::Ordering::Less);
}

See also: MonomialOrder trait

BlockOrder and SubOrder

Signature:

#![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,
}
}

Description: Block elimination order. Partitions the variables into consecutive blocks, each block using its own sub-order.

Construction:

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

Parameters:

Notes: boundaries = [2] with orders = [Lex, Grevlex] on a polynomial in 4 variables means: compare variables 0–1 first (Lex), and if equal, compare variables 2–3 (Grevlex).

Default: a single Grevlex block.

Example:

#![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 within the block: [1,0] > [0,1]
assert_eq!(ord.cmp(&a, &b), std::cmp::Ordering::Greater);
}

See also: MonomialOrder trait

MatrixOrder

Signature:

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

Description: Matrix order. Multiplies exponent vectors by an integer matrix and compares the results lexicographically. Given an $n \times n$ matrix $M$, a monomial $\alpha > \beta$ if and only if $M\alpha >_{\text{lex}} M\beta$. It generalizes all standard orders and is especially suitable for constructing elimination orders.

Construction:

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

Parameters:

elimination_order: Constructs a matrix order equivalent to BlockOrder([elim_vars in Lex, rest in Grevlex]).

Default: the $1 \times 1$ identity matrix.

Example:

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

// 2×2 identity matrix = Lex order
let ord = MatrixOrder::new(vec![vec![1, 0], vec![0, 1]]);
assert_eq!(ord.cmp(&[1, 0], &[0, 1]), std::cmp::Ordering::Greater);
}

See also: MonomialOrder trait

DenseUnivariatePolynomial

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct DenseUnivariatePolynomial<D: Domain> {
    coeffs: Vec<D::Element>,  // starts at the constant term, trailing zeros removed
    domain: D,
}
}

A dense univariate polynomial. Coefficients are stored in a contiguous vector, from the constant term $a_0$ to the highest-degree term $a_n$. The zero polynomial is represented by an empty vector. Multiplication automatically selects between Karatsuba (when both polynomials have at least 32 coefficients) and schoolbook multiplication.

Dense Construction and Properties

DenseUnivariatePolynomial::new

Signature: pub fn new(domain: D) -> Self

Description: Creates the zero polynomial.

Parameters:

Returns: the zero polynomial (an empty coefficient vector).

See also: from_coeffs

DenseUnivariatePolynomial::from_coeffs

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

Description: Constructs a polynomial from a coefficient vector. Trailing zero coefficients are removed automatically.

Parameters:

Returns: the polynomial $a_0 + a_1 x + \cdots + a_n x^n$.

Example:

#![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, the middle zero coefficient is kept (not a trailing zero)
}

See also: new

DenseUnivariatePolynomial::domain

Signature: pub fn domain(&self) -> &D

Description: Returns a reference to the coefficient domain.

DenseUnivariatePolynomial::coeffs

Signature: pub fn coeffs(&self) -> &[D::Element]

Description: Returns the coefficient slice, starting from the constant term.

DenseUnivariatePolynomial::is_zero

Signature: pub fn is_zero(&self) -> bool

Description: Returns whether the polynomial is zero.

DenseUnivariatePolynomial::degree

Signature: pub fn degree(&self) -> Option<usize>

Description: Returns the degree of the polynomial. Returns None for the zero polynomial.

DenseUnivariatePolynomial::coeff

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

Description: Returns the coefficient of $x^n$, or None if it does not exist.

DenseUnivariatePolynomial::leading_coeff

Signature: pub fn leading_coeff(&self) -> Option<&D::Element>

Description: Returns the leading coefficient. Returns None for the zero polynomial.

DenseUnivariatePolynomial::lcoeff

Signature: pub fn lcoeff(&self) -> D::Element

Description: Convenience alias for the leading coefficient. Returns the domain's zero for the zero polynomial.

Returns: the leading coefficient, or the domain's zero.

See also: leading_coeff

DenseUnivariatePolynomial::constant

Signature: pub fn constant(&self) -> D::Element

Description: Returns the constant term (the coefficient of $x^0$). Returns the domain's zero for the zero polynomial.

DenseUnivariatePolynomial::zero

Signature: pub fn zero(&self) -> Self

Description: Returns the zero polynomial over the same domain.

DenseUnivariatePolynomial::one

Signature: pub fn one(&self) -> Self

Description: Returns the constant polynomial $1$.

DenseUnivariatePolynomial::is_one

Signature: pub fn is_one(&self) -> bool

Description: Returns whether the polynomial is the constant $1$.

Dense Basic Arithmetic

The following methods are available for D: Domain:

DenseUnivariatePolynomial::neg

Signature: pub fn neg(&self) -> Self

Description: Returns $-p(x)$.

DenseUnivariatePolynomial::add

Signature: pub fn add(&self, other: &Self) -> Self

Description: Polynomial addition.

DenseUnivariatePolynomial::sub

Signature: pub fn sub(&self, other: &Self) -> Self

Description: Polynomial subtraction.

DenseUnivariatePolynomial::mul_scalar

Signature: pub fn mul_scalar(&self, scalar: &D::Element) -> Self

Description: Scalar multiplication. Multiplies every coefficient by scalar.

DenseUnivariatePolynomial::mul

Signature: pub fn mul(&self, other: &Self) -> Self

Description: Polynomial multiplication. Automatically selects between schoolbook multiplication and Karatsuba based on the degree.

Example:

#![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
}

See also: mul_into

DenseUnivariatePolynomial::mul_into

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

Description: Multiplication that writes the result into a buffer (avoiding repeated heap allocations in hot loops). The buffer is cleared and reused.

Parameters:

DenseUnivariatePolynomial::eval

Signature: pub fn eval(&self, x: &D::Element) -> D::Element

Description: Evaluates the polynomial at $x$ using Horner's method. Returns the domain's zero for the zero polynomial.

Example:

#![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

Signature: pub fn derivative(&self) -> Self

Description: Returns the formal derivative $p'(x)$.

DenseUnivariatePolynomial::integral

Signature: pub fn integral(&self) -> Self

Description: Returns the formal integral $\int p(x),dx$ with zero constant term. Requires a domain that supports division (such as RationalDomain).

EuclideanDomain Operations

The following methods require D: EuclideanDomain:

DenseUnivariatePolynomial::mul_coeff

Signature: pub fn mul_coeff(&self, c: &D::Element) -> Self

Description: Multiplies every coefficient by the constant $c$. Equivalent to mul_scalar, but restricted to EuclideanDomain.

See also: mul_scalar

DenseUnivariatePolynomial::div_coeff

Signature: pub fn div_coeff(&self, c: &D::Element) -> Self

Description: Divides every coefficient by the constant $c$ (which must divide exactly).

Errors: panics unconditionally if $c$ is not invertible in the domain (e.g. over $\mathbb{Z}$ when $c$ is not $\pm 1$), even if every coefficient is divisible by $c$.

DenseUnivariatePolynomial::div_rem

Signature: pub fn div_rem(&self, divisor: &Self) -> Option<(Self, Self)>

Description: Division with remainder. Returns $(q, r)$ such that $p = q \cdot \text{divisor} + r$, where $\deg(r) < \deg(\text{divisor})$.

Returns: Some((quotient, remainder)), or None if the divisor is zero.

Example:

#![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, remainder 0
}

See also: gcd

DenseUnivariatePolynomial::gcd

Signature: pub fn gcd(&self, other: &Self) -> Self

Description: Computes the greatest common divisor of two polynomials. Uses the Euclidean algorithm (with pseudo-remainders when the coefficient domain is not a field). The result is always primitive (content-free).

Example:

#![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
}

See also: extended_gcd_poly

DenseUnivariatePolynomial::content

Signature: pub fn content(&self) -> D::Element

Description: Returns the greatest common divisor of all coefficients. Returns the domain's zero for the zero polynomial.

Returns: the GCD of the coefficients.

See also: primitive_part

DenseUnivariatePolynomial::primitive_part

Signature: pub fn primitive_part(&self) -> Self

Description: Returns the primitive part $p / \text{content}(p)$. The result has content 1 (or is the zero polynomial).

See also: content

DenseUnivariatePolynomial::extended_gcd_poly

Signature: pub fn extended_gcd_poly(&self, other: &Self) -> (Self, Self, Self)

Description: Extended Euclidean algorithm. Returns $(g, s, t)$ such that $s \cdot p + t \cdot q = g$, where $g = \gcd(p, q)$ and $g$ is monic.

Returns: (gcd, bezout_s, bezout_t)

Example:

#![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
}

See also: gcd

DenseUnivariatePolynomial::pow

Signature: pub fn pow(&self, n: u32) -> Self

Description: Fast exponentiation by repeated squaring. $p^0 = 1$.

Parameters:

Returns: $p(x)^n$.

DenseUnivariatePolynomial::p_adic_expansion

Signature: pub fn p_adic_expansion(&self, p: &Self) -> Vec<Self>

Description: $p$-adic expansion. Returns $[a_0, a_1, a_2, \dots]$ such that $\text{self} = a_0 + a_1 \cdot p + a_2 \cdot p^2 + \cdots$, where each $a_k$ has degree less than $\deg(p)$.

Implementation: by repeated division with remainder.

Example:

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

let d = IntegerDomain;
// p-adic expansion of f(x) = x^3 with respect to p(x) = x + 1
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, ...] such that f = a0 + a1*p + a2*p^2 + ...
}

See also: div_rem

DenseUnivariatePolynomial::diophantine

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

Description: Polynomial CRT (Diophantine solver). Given a list of pairwise coprime polynomials polys and a target $b$, returns $[s_0, \dots, s_n]$ such that:

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

Parameters:

Returns: the list of remainders $[s_0, \dots, s_n]$.

Errors: panics if the polynomials are not pairwise coprime.

Factorization and Resultants

DenseUnivariatePolynomial::square_free_factorization

Signature: pub fn square_free_factorization(&self) -> SquareFreeFactors<D>

Description: Square-free factorization. Uses Yun's algorithm: $g = \gcd(f, f')$, $w = f/g$, then iterate $h = \gcd(w, g)$, $z = w/h$ to collect the factors of multiplicity $k$.

Returns: Vec<(DenseUnivariatePolynomial<D>, usize)> — a list of (factor, multiplicity) pairs.

Example:

#![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);
}

See also: factor, gcd

DenseUnivariatePolynomial::is_square_free

Signature: pub fn is_square_free(&self) -> bool

Description: Returns whether the polynomial is square-free ($\gcd(p, p') = 1$).

DenseUnivariatePolynomial::factor (IntegerDomain)

Signature: impl DenseUnivariatePolynomial<IntegerDomain> { pub fn factor(&self) -> Factors<IntegerDomain> }

Description: Completely factors a primitive integer polynomial into irreducible factors. Uses the square-free factorization + Berlekamp–Zassenhaus + Hensel lifting algorithms.

Preconditions: the input must be primitive (content = 1). Call primitive_part() first on arbitrary polynomials.

Returns: Vec<(DenseUnivariatePolynomial<IntegerDomain>, usize)> — (irreducible factor, multiplicity) pairs.

Example:

#![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);
}

See also: square_free_factorization

DenseUnivariatePolynomial::factor (FiniteField)

Signature: impl DenseUnivariatePolynomial<FiniteField> { pub fn factor(&self) -> Factors<FiniteField> }

Description: Completely factors a polynomial over $\mathbb{F}_p$. Uses Berlekamp's algorithm (or Cantor–Zassenhaus).

Returns: Vec<(DenseUnivariatePolynomial<FiniteField>, usize)> — (irreducible factor, multiplicity) pairs.

Example:

#![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());
}

See also: factor (IntegerDomain)

DenseUnivariatePolynomial::resultant

Signature: pub fn resultant(&self, other: &Self) -> D::Element

Description: Computes the resultant $\operatorname{Res}(a, b)$ using the Brown PRS algorithm. The resultant is zero if and only if $a$ and $b$ have a non-constant common factor.

Implementation details: subresultant PRS, with an exact division by $\beta$ at each step (the subresultant theorem guarantees exactness).

Example:

#![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));
}

Properties: $\operatorname{Res}(a, b) = (-1)^{\deg a \cdot \deg b} \operatorname{Res}(b, a)$.

See also: 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,
}
}

A sparse multivariate polynomial. Only nonzero terms are stored, in a HashMap keyed by the exponent vector $\vec{e} = [e_1, e_2, \dots]$ with the coefficient as value. An exponent vector $\vec{e}$ represents the monomial $x_1^{e_1} x_2^{e_2} \cdots$. The monomial order is controlled by the type parameter O, which defaults to Grevlex.

Sparse Construction and Properties

SparseMultivariatePolynomial::new

Signature: pub fn new(domain: D, n_vars: usize) -> Self

Description: Creates the zero polynomial with the default monomial order.

Parameters:

See also: new_with_order

SparseMultivariatePolynomial::new_with_order

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

Description: Creates the zero polynomial with the given monomial order.

Example:

#![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

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

Description: Constructs a polynomial from a list of (exponent vector, coefficient) pairs. Terms with zero coefficients are dropped automatically.

Parameters:

Example:

#![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
}

See also: new

SparseMultivariatePolynomial::domain

Signature: pub fn domain(&self) -> &D

Description: Returns a reference to the coefficient domain.

SparseMultivariatePolynomial::n_vars

Signature: pub fn n_vars(&self) -> usize

Description: Returns the number of variables.

SparseMultivariatePolynomial::n_terms

Signature: pub fn n_terms(&self) -> usize

Description: Returns the number of nonzero terms.

SparseMultivariatePolynomial::is_zero

Signature: pub fn is_zero(&self) -> bool

Description: Returns whether the polynomial is zero.

SparseMultivariatePolynomial::terms_ref

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

Description: Returns a reference to the internal term map (exponent → coefficient).

SparseMultivariatePolynomial::set_term_external

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

Description: Sets the coefficient of a monomial. A zero coefficient removes the term.

SparseMultivariatePolynomial::total_degree

Signature: pub fn total_degree(&self) -> Option<usize>

Description: Returns the total degree (the maximum degree over all monomials). Returns None for the zero polynomial.

SparseMultivariatePolynomial::coeff

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

Description: Returns the coefficient of the given monomial, or the domain's zero if it is absent.

SparseMultivariatePolynomial::degree_in

Signature: pub fn degree_in(&self, var_index: usize) -> usize

Description: Returns the degree in the variable var_index. Returns 0 for the zero polynomial.

Parameters:

Returns: the maximum exponent of that variable over all terms.

SparseMultivariatePolynomial::zero / one

Signature:

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

Description: Returns the zero polynomial or the constant $1$ with the same shape.

Sparse Basic Arithmetic

SparseMultivariatePolynomial::neg

Signature: pub fn neg(&self) -> Self

Description: Returns $-p$.

SparseMultivariatePolynomial::add

Signature: pub fn add(&self, other: &Self) -> Self

Description: Polynomial addition.

Errors: panics if the numbers of variables differ.

SparseMultivariatePolynomial::sub

Signature: pub fn sub(&self, other: &Self) -> Self

Description: Polynomial subtraction.

Errors: panics if the numbers of variables differ.

SparseMultivariatePolynomial::mul_scalar

Signature: pub fn mul_scalar(&self, scalar: &D::Element) -> Self

Description: Scalar multiplication.

SparseMultivariatePolynomial::mul

Signature: pub fn mul(&self, other: &Self) -> Self

Description: Polynomial multiplication. Multiplies each pair of terms and combines like terms.

Errors: panics if the numbers of variables differ.

Example:

#![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

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

Description: Adds exp component-wise to the exponent vector of every term. Used in Gröbner basis reduction.

SparseMultivariatePolynomial::sorted_terms

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

Description: Returns the (exponent, coefficient) pairs sorted by the monomial order.

SparseMultivariatePolynomial::eval

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

Description: Substitutes the value value for the variable var_index, returning a polynomial in one fewer variable.

Parameters:

Returns: a polynomial in one fewer variable (the remaining variables keep their relative order).

Example:

#![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
    ],
);
// Substitute x=3: the result is 3y + 2y = 5y
let r = p.eval(0, &Integer::from(3));
assert_eq!(r.coeff(&[1]), Integer::from(5));
}

SparseMultivariatePolynomial::eval_keep

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

Description: Substitutes the variable var_index with a value but keeps the total number of variables unchanged (the substituted variable's exponents are zeroed). Used in scenarios where variable positions must stay fixed during Hensel lifting.

SparseMultivariatePolynomial::leading_term

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

Description: Returns the leading term (exponent vector, coefficient). Returns None for the zero polynomial. An $O(n)$ scan of the HashMap.

SparseMultivariatePolynomial::leading_monomial

Signature: pub fn leading_monomial(&self) -> Option<&SmallVec<[usize; 4]>>

Description: Returns the exponent vector of the leading monomial.

SparseMultivariatePolynomial::leading_coeff

Signature: pub fn leading_coeff(&self) -> Option<&D::Element>

Description: Returns the leading coefficient.

SparseMultivariatePolynomial::content

Signature:

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

Description: Returns the GCD of all coefficients.

Example:

#![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));
}

See also: primitive_part

SparseMultivariatePolynomial::primitive_part

Signature:

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

Description: Returns the primitive part (polynomial / content).

See also: content

SparseMultivariatePolynomial::div_exact

Signature: pub fn div_exact(&self, divisor: &Self) -> Self

Description: Exact division (assumes no remainder). Used in rational function normalization where the GCD is known to divide.

Errors: panics in debug mode if the division is not exact.

See also: checked_div_exact

SparseMultivariatePolynomial::checked_div_exact

Signature: pub fn checked_div_exact(&self, divisor: &Self) -> Option<Self>

Description: Exact division, returning None when the division is not exact.

Returns: Some(quotient) or None.

SparseMultivariatePolynomial::derivative

Signature: pub fn derivative(&self, var_index: usize) -> Self

Description: Computes the formal partial derivative with respect to the variable var_index.

SparseMultivariatePolynomial::taylor_coefficients

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

Description: Computes the Taylor coefficients in the variable var_index at the point $a$. Returns $[t_0, t_1, \dots, t_d]$ such that $f = \sum_j t_j (x_{\text{var}} - a)^j$.

Gröbner Basis Support

SparseMultivariatePolynomial::reduce

Signature: pub fn reduce(&self, basis: &[Self]) -> Self

Description: Multivariate polynomial division. Repeatedly finds a basis element whose leading term divides the current leading term and subtracts the appropriate multiple; otherwise the leading term is moved into the remainder. Requires the coefficient domain to be a field (division always succeeds).

Parameters:

Returns: the reduced remainder.

SparseMultivariatePolynomial::spoly

Signature: pub fn spoly(&self, other: &Self) -> Self

Description: Computes the S-polynomial. $S(f, g) = \frac{\text{lcm}}{\text{lt}(f)} \cdot f - \frac{\text{lcm}}{\text{lt}(g)} \cdot g$.

SparseMultivariatePolynomial::make_monic_inplace

Signature: pub fn make_monic_inplace(&mut self) -> bool

Description: Normalizes the polynomial to be monic in place (divides by the leading coefficient). Returns false if the leading coefficient is not invertible.

SparseMultivariatePolynomial::exponents_iter

Signature: pub fn exponents_iter(&self) -> impl Iterator<Item = &SmallVec<[usize; 4]>>

Description: Iterates over all exponent vectors in monomial order (descending). Used for the symbolic preprocessing of the F4 algorithm.

Multivariate Factorization

SparseMultivariatePolynomial::factor (IntegerDomain, Lex)

Signature:

#![allow(unused)]
fn main() {
impl SparseMultivariatePolynomial<IntegerDomain, Lex> {
    pub fn factor(&self) -> Vec<(Self, usize)>
}
}

Description: Factors a multivariate integer polynomial into irreducible factors. Bivariate polynomials with a constant leading coefficient in the main variable use bivariate Hensel lifting (Wang); polynomials in three or more variables, or bivariate ones with a non-constant leading coefficient, use the EEZ algorithm.

Returns: a list of (irreducible factor, multiplicity) pairs.

Example:

#![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);
}

See also: factor (FiniteField)

SparseMultivariatePolynomial::factor (FiniteField, Lex)

Signature:

#![allow(unused)]
fn main() {
impl SparseMultivariatePolynomial<FiniteField, Lex> {
    pub fn factor(&self) -> Vec<(Self, usize)>
}
}

Description: Factors a multivariate $\mathbb{F}_p$ polynomial. Bivariate polynomials use the evaluation–Hensel path; three or more variables use EEZ.

See also: 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>,
}
}

An element of the polynomial fraction field $\frac{\text{num}}{\text{den}}$. Constructing via from_num_den automatically normalizes to lowest terms (coprime numerator and denominator, with the denominator's leading coefficient normalized).

RationalPolynomial::new

Signature:

#![allow(unused)]
fn main() {
pub fn new(
    numerator: SparseMultivariatePolynomial<D, O>,
    denominator: SparseMultivariatePolynomial<D, O>,
) -> Self
}

Description: Constructs a rational polynomial without normalization. The caller must ensure the denominator is nonzero.

See also: from_num_den

RationalPolynomial::from_num_den

Signature:

#![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
}
}

Description: Constructs from numerator and denominator and normalizes. The result is in lowest terms: coprime numerator and denominator, with the denominator's leading coefficient normalized (1 over a finite field, positive over the integers).

Preconditions: the denominator must be nonzero.

Normalization steps:

1. Compute $\gcd(\text{num}, \text{den})$ and cancel it
2. In the univariate case, reduce by an exact GCD via the dense Euclidean algorithm
3. Normalize the denominator's leading coefficient

Errors: panics when the denominator is zero.

See also: new

RationalPolynomial::from_polynomial

Signature: pub fn from_polynomial(poly: SparseMultivariatePolynomial<D, O>) -> Self

Description: Constructs from a polynomial (denominator = 1).

RationalPolynomial::zero / one

Signature:

#![allow(unused)]
fn main() {
pub fn zero(domain: &D, n_vars: usize) -> Self
pub fn one(domain: &D, n_vars: usize) -> Self
}

Description: Returns the zero or the identity rational polynomial.

RationalPolynomial::is_zero / is_one

Signature:

#![allow(unused)]
fn main() {
pub fn is_zero(&self) -> bool
pub fn is_one(&self) -> bool
}

Description: Returns whether the rational polynomial is zero or $1/1$.

RationalPolynomial::n_vars

Signature: pub fn n_vars(&self) -> usize

Description: Returns the number of variables.

RationalPolynomial::domain

Signature: pub fn domain(&self) -> &D

Description: Returns a reference to the coefficient domain.

RationalPolynomial::neg

Signature: pub fn neg(&self) -> Self

Description: Returns $-\frac{n}{d}$.

RationalPolynomial::inv

Signature: pub fn inv(&self) -> Option<Self>

Description: Returns the multiplicative inverse $\frac{d}{n}$. Returns None when the numerator is zero.

Returns: Some(inverse) or None (when the numerator is zero).

RationalPolynomial::pow

Signature: pub fn pow(&self, k: u32) -> Self

Description: Fast exponentiation. Computes $\left(\frac{n}{d}\right)^k$ by repeated squaring of the numerator and denominator separately.

RationalPolynomial::add

Signature:

#![allow(unused)]
fn main() {
impl<D: EuclideanDomain, O: MonomialOrder> RationalPolynomial<D, O> {
    pub fn add(&self, other: &Self) -> Self
}
}

Description: Addition of rational polynomials. With equal denominators the numerators are added directly; with different denominators it cross-multiplies and normalizes.

RationalPolynomial::sub

Signature: pub fn sub(&self, other: &Self) -> Self

Description: Subtraction of rational polynomials. Equivalent to self.add(&other.neg()).

RationalPolynomial::mul

Signature: pub fn mul(&self, other: &Self) -> Self

Description: Multiplication of rational polynomials. Cross-multiplies and normalizes.

RationalPolynomial::div

Signature: pub fn div(&self, other: &Self) -> Option<Self>

Description: Division of rational polynomials. $\frac{a/b}{c/d} = \frac{ad}{bc}$.

Returns: Some(quotient) or None (when the numerator of the divisor is zero).

Helper Functions

The following functions live in the ocas_poly::sparse module:

monomial_divides

Signature: pub fn monomial_divides(a: &[usize], b: &[usize]) -> bool

Description: Checks whether the monomial $b$ divides $a$ (i.e., $a$ is a multiple of $b$). Returns true iff $a_i \geq b_i$ for all $i$.

Parameters:

Returns: true if $b$ divides $a$.

monomial_lcm

Signature: pub fn monomial_lcm(a: &[usize], b: &[usize]) -> SmallVec<[usize; 4]>

Description: Computes the least common multiple of two monomials: the component-wise maximum.

$$\text{lcm}(x^a y^b, x^c y^d) = x^{\max(a,c)} y^{\max(b,d)}$$

monomial_are_coprime

Signature: pub fn monomial_are_coprime(a: &[usize], b: &[usize]) -> bool

Description: Checks whether two monomials are coprime (no variable appears in both).

Type Aliases

#![allow(unused)]
fn main() {
/// Square-free factorization result: list of (factor, multiplicity) pairs.
pub type SquareFreeFactors<D> = Vec<(DenseUnivariatePolynomial<D>, usize)>;

/// Complete factorization result: list of (irreducible factor, multiplicity) pairs.
pub type Factors<D> = Vec<(DenseUnivariatePolynomial<D>, usize)>;
}

Matrices

Source: ocas-poly/src/matrix.rs

Matrix<D> is the general dense matrix type in oCAS, with elements from an arbitrary EuclideanDomain. It uses row-major storage, and all elimination operations use fraction-free algorithms to avoid fraction blow-up of domain elements.

MatrixError

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum MatrixError {
    ShapeMismatch,
    RightHandSideIsNotVector,
    Inconsistent,
    Underdetermined { rank: usize },
    ResultNotInDomain,
}
}

Errors that may arise in matrix operations. Implements Display and std::error::Error.

ShapeMismatch

Meaning: Matrix shapes are incompatible.

Triggered when: trace is used on a non-square matrix; matmul has self.ncols != other.nrows; solve has self.nrows != b.len(); augment has mismatched row counts.

RightHandSideIsNotVector

Meaning: The right-hand side is not a column vector.

Triggered when: Not used directly by solve in the current version (solve accepts a &[D::Element] slice), but kept for extension.

Inconsistent

Meaning: The linear system has no solution (inconsistent).

Triggered when: In solve, after elimination a free row of the augmented matrix has a nonzero entry in the last (constant) column.

Underdetermined { rank }

Meaning: The linear system has infinitely many solutions (underdetermined).

Triggered when: In solve, the rank rank of the coefficient matrix is less than the number of variables nvars.

ResultNotInDomain

Meaning: The solution does not lie in the target domain.

Triggered when: In the final division step of solve, div returns None (e.g., not divisible in an integer domain).

Display output:

Example:

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

let d = IntegerDomain;

// Inconsistent system: identical rows but different constant terms
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));
}

See also: solve

Matrix<D>

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Matrix<D: EuclideanDomain> {
    data: Vec<D::Element>,   // row-major storage
    nrows: usize,
    ncols: usize,
    domain: D,
}
}

Function: A dense matrix over the domain D, with elements stored row-major in a Vec<D::Element>.

Design invariants:

• data.len() == nrows * ncols (guaranteed by constructors)
• Element (i, j) is at position i * ncols + j in data
• D is constrained to EuclideanDomain, supporting div, gcd, etc., which makes fraction-free elimination possible

Trait implementations:

• Index<(usize, usize)> / IndexMut<(usize, usize)> — element access via matrix[(i, j)]
• Display — one line per row, elements separated by spaces
• Debug, Clone, PartialEq, Eq

Constructors

new

Signature: pub fn new(nrows: usize, ncols: usize, data: Vec<D::Element>, domain: D) -> Self

Function: Creates a matrix from row-major one-dimensional data.

Parameters:

Return value: Matrix<D>

Errors: Panics at runtime if data.len() != nrows * ncols.

Example:

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

let d = IntegerDomain;
// Create a 2×3 matrix:
// [ 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));
}

See also: from_rows, zeros, identity

zeros

Signature: pub fn zeros(nrows: usize, ncols: usize, domain: D) -> Self

Function: Creates a zero matrix of the given shape.

Parameters:

Return value: A Matrix<D> with all elements equal to domain.zero().

Example:

#![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));
}

See also: identity, new

identity

Signature: pub fn identity(n: usize, domain: D) -> Self

Function: Creates the n × n identity matrix.

Parameters:

Return value: A square matrix with domain.one() on the diagonal and domain.zero() elsewhere.

Example:

#![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));
}

See also: zeros

from_rows

Signature: pub fn from_rows(rows: Vec<Vec<D::Element>>, domain: D) -> Self

Function: Creates a matrix from nested row vectors.

Parameters:

Return value: Matrix<D>

Errors: Panics at runtime if rows have inconsistent lengths.

Example:

#![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));
}

See also: new, into_rows

Accessor Methods

nrows

Signature: pub fn nrows(&self) -> usize

Function: Returns the number of rows of the matrix.

Example:

#![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

Signature: pub fn ncols(&self) -> usize

Function: Returns the number of columns of the matrix.

Example:

#![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

There is no separate shape() method. The shape is obtained by combining nrows() and 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

Signature: pub fn domain(&self) -> &D

Function: Returns a reference to the matrix's coefficient domain.

Example:

#![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

Signature: pub fn data(&self) -> &[D::Element]

Function: Returns a read-only slice of the underlying row-major storage.

Example:

#![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

Signature: pub fn row(&self, i: usize) -> Vec<D::Element>

Function: Returns a copy of the i-th row.

Parameters:

Return value: Vec<D::Element> of length ncols.

Errors: Panics if the index is out of bounds.

Example:

#![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)]);
}