A

Algorithms in pure Rust, with no dependencies:

• Sorting (a::sort): 23 sorting algorithms by comparison and by key, and a default sort.
• Integers of any size (a::math::numbers): Number, with its arithmetic up to transforms for the longest products, roots, powers modulo a number, greatest common divisors, primes and text in any radix.
• Elliptic curves (a::math::ec): Weierstrass, Montgomery and Edwards curves over prime fields, secp256k1, P-256, P-384, P-521, Curve25519 and Ed25519 among them.
• Complex numbers (a::math::complex) and matrices (a::math::matrix): decompositions, eigenvalues, singular values and functions of matrices of floats and complex numbers, and exact algorithms on matrices of integers.

Every algorithm has a page with its method, examples and measurements against the reference implementations (GMP, OpenSSL, faer, nalgebra and others); the tables below link to them. The API reference is on docs.rs. The crate needs Rust 1.88 (edition 2024). Its fastest paths are NEON and assembly kernels on aarch64, and assembly for the products of integers on x86_64; everything else is portable Rust.

Usage

Add the crate with cargo add nettrash-a, or to Cargo.toml:

[dependencies]
nettrash-a = "0.1"

Its library is named a:

use a::math::matrix::Matrix;
use a::math::numbers::Number;
use a::sort::sort;

fn main() {
    let mut v = vec![5, 1, 4, 2, 8, 0, 3, 9, 7, 6];
    sort(&mut v);
    assert_eq!(v, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);

    let x: Number = "123456789012345678901234567890".parse().unwrap();
    assert_eq!((&x * &x).to_string(), "15241578753238836750495351562536198787501905199875019052100");

    let a: Matrix<f64> = Matrix::from_rows(&[[4.0, 2.0], [2.0, 3.0]]);
    let b = Matrix::from_rows(&[[2.0], [1.0]]);
    let solution = a.solve(&b).unwrap();
    assert!((solution[(0, 0)] - 0.5).abs() < 1e-15 && solution[(1, 0)].abs() < 1e-15);
}

Sorting

Every sort takes a mutable slice and leaves it sorted; the extra memory is what a sort uses besides the slice. sort is the default: use it when there is no reason to prefer a particular algorithm.

Comparison sorts

These sort any T: Ord.

¹ About n·log₁.₃ n comparisons in practice; no O(n log n) bound has been proved, and no known input reaches O(n²).

² No exact bound is known; measured, 1.6–2.8·n·log₂ n comparisons up to a million elements. The worst case is O(n^(4/3)) with Sedgewick's gaps (elements larger than 8 bytes); no bound is known for Ciura's (the others).

Key sorts

These sort by integer or float keys without comparing elements. k is the number of possible keys between the smallest and the largest; integer keys are the primitive integers, char and bool.

Sleep sort is a joke: a thread per element sleeps in proportion to its value, the result is not always sorted, and sleep returns whether it is.

Against the standard library

Measured on an Apple M4 Max with new input for every sort; each page has the other inputs, sizes and element types:

Math

Integers of any size

a::math::numbers::Number is an integer of any size, its sign and the bytes of its absolute value in either byte order. Operators take owned or borrowed operands and build the result in an operand's vector when it has room.

Measured on an Apple M4 Max in cycles per call, over random operands of the length given, little-endian, against GMP 6.3 and num-bigint 0.4; each page has the conditions, more sizes and the other operations. GMP is faster on some short operands; "–" is not measured:

Elliptic curves

Measured on an Apple M4 Max in cycles, against OpenSSL 3.6 and curve25519-dalek 4.1; k·P multiplies a point, k·G the generator, by a table where the library has one. OpenSSL's and dalek's products of a point are constant-time, which costs them time this crate doesn't spend:

Complex numbers

Measured on an Apple M4 Max for Complex<f64>, in nanoseconds per operation over 1,024 independent ones, against num-complex 0.4.6, whose division by |b|² as it is overflows from |b| of about 10¹⁵⁴:

Matrices

a::math::matrix::Matrix<T> is a dense matrix of any size, column after column, of f32, f64, Complex<f32>, Complex<f64> or Number. The algorithms are LAPACK's, arranged so that most of their work is products of blocks, and the products run on NEON kernels; real matrices stay in real arithmetic. Costs are for n × n matrices.

In f64 on one core of an Apple M4 Max, each of the twelve operations measured was at least as fast as faer's and nalgebra's at every size from 8 × 8 to 1024 × 1024; at 1024 × 1024, in milliseconds:

Apple's Accelerate, which runs its products on the M4's matrix unit, is faster than all three at this size; it has no exp.

Not constant-time

Nothing here is written to take the same time whatever its operands: pow_mod and the elliptic curves in particular branch on the values of their exponents and scalars. Use them on public data, for verification and research, not on secret keys or scalars.

Changelog

What each version added, changed and fixed is in CHANGELOG.md.

License

MIT.