rma

Crates.iorma
lib.rsrma
version0.4.0
created_at2025-05-28 14:46:25.18237+00
updated_at2025-07-17 01:02:59.784713+00
descriptionRare, high-performance mathematical algorithms for Rust.
homepagehttps://github.com/bogwi/r-math
repositoryhttps://github.com/bogwi/r-math
max_upload_size
id1692860
size251,351
Dan Vi (bogwi)

documentation

https://docs.rs/rma

README

R-Math Algorithms

crates.io docs.rs

A Rust crate for rare, high-performance mathematical algorithms not commonly found in mainstream libraries.


Current Features

  • Chakravala method: Solves Pell's equation x² - Dy² = 1 for a given non-square integer D.

  • Berlekamp's Algorithm: Factorization of polynomials over finite fields (GF(p))

    • This implementation supports polynomials over GF(p) for prime p, using u128 for all arithmetic.
    • Uses Karatsuba multiplication for all degree polynomials.
    • On M4Pro12, solves 256 degree polynomial over prime p, the largest 64 bit prime 18_446_744_073_709_551_557 in
      berlekamp_roots_dense_deg256_p64b time:   [14.323 ms 14.345 ms 14.366 ms]
      berlekamp_roots_sparse_deg256_p64b time:  [15.582 ms 15.609 ms 15.635 ms]
      
    • 128 bit primes are not the part of the benchmark, but values close to the above 64 bit prime will give you similar performance on 256 degree polynomial.
  • Tonelli-Shanks: Modular square roots (r^2 ≡ n mod p) over prime moduli (constant-time version)

  • Cuthill–McKee & Reverse Cuthill–McKee: Bandwidth reduction for sparse symmetric matrices (adjacency list, CSR, and CSC formats)

    • Supports conversion from sprs sparse matrix types
  • Fast Minimum Degree Algorithm: Exact elimination ordering for sparse matrices with O(nm) complexity

    • First algorithm to improve on the naive O(n³) approach (Cummings et al., 2020)
    • Achieves output-sensitive bounds of O(min{m√m*, Δm*} log n)
    • Based on breakthrough theoretical results from Cummings, Fahrbach, and Fatehpuria
  • Freivalds' Algorithm: Fast probabilistic verification of matrix multiplication (scalar, modular, and SIMD-accelerated variants)

  • Well-documented, tested, and benchmarked implementations

  • SIMD acceleration for Freivalds' algorithm (nightly Rust required)

More about the algorithms here

R-Math Algorithms Overview


Installation

Add to your Cargo.toml:

[dependencies]
rma = "0.3"

Enable SIMD features (nightly Rust required):

[dependencies]
rma = { version = "0.3", features = ["simd"] }

Benchmarks

Benchmarks are provided using criterion in the benches/ directory.

On stable Rust:

  • Run all benchmarks:
    cargo bench
    
  • Run a specific benchmark (e.g., only Freivalds):
    cargo bench --bench freivalds_bench
    

On nightly Rust (to enable SIMD):

  • Run all benchmarks with SIMD (freivalds_bench is the only one that uses SIMD):
    cargo bench --features simd
    
  • Run a specific benchmark with SIMD:
    cargo bench --bench freivalds_bench --features simd
    

becnhes naming convention is filename with the _bench suffix; you check all in Cargo.toml


Testing

On stable Rust:

  • Run all tests:
    cargo test
    

On nightly Rust (to enable SIMD tests):

  • Run all tests with SIMD:
    cargo test --features simd
    

Documentation


Minimum Supported Rust Version

  • Nightly Rust required for SIMD features (#![feature(portable_simd)])
  • Stable Rust for scalar and modular algorithms

Roadmap & Contributions

This crate will be updated with new algorithms over time, focusing on rare, advanced, or otherwise unported mathematical algorithms.


License

Licensed under either of

  • Apache License, Version 2.0
  • MIT license

r-math aims to be a home for rare, advanced, and high-performance mathematical algorithms in Rust.

Commit count: 2

cargo fmt