RustMath vs SageMath Performance Benchmarks

Last Updated: November 2025 Test Environment: SageMath 10.x, RustMath 0.1.0, Python 3.12

Executive Summary

RustMath's Python bindings (via PyO3) are currently limited to 64-bit integers due to implementation issues. Within this limitation, performance is mixed:

Operation	Performance	Notes
Single GCD	✅ Competitive (0.93-1.12x)	RustMath sometimes faster
Batch GCD	❌ 5x slower	Python FFI overhead
Extended GCD	❌ 9x slower	Needs optimization
Primality Testing	❌❌ 1261x slower	Critical performance issue
Factorization	✅✅ 26x faster	Surprising advantage

Critical Limitations

⚠️ BLOCKING ISSUE: No Arbitrary Precision Support

# ❌ FAILS - Numbers > 19 digits
a = rustmath.PyInteger(12345678901234567890123456789)
# OverflowError: Python int too large to convert to C long

# ❌ ALSO FAILS - String conversion doesn't help
a = rustmath.PyInteger.from_string("12345678901234567890123456789")
# ValueError: Invalid integer: 12345678901234567890123456789

Root Cause: Both PyInteger.__new__() and from_string() parse to Rust's i64 type, limiting to ±9,223,372,036,854,775,807 (~19 decimal digits).

Impact: RustMath Python bindings are unusable for serious mathematical work until this is fixed.

Benchmark Code

Setup

When running in a SageMath Jupyter notebook, you must explicitly use Python's built-in types to avoid SageMath's preparser:

import rustmath
import time
from sage.all import ZZ, gcd

# CRITICAL: Force Python built-in types (bypass SageMath preparser)
import builtins
pyint = builtins.int
pyrange = builtins.range

PyInt = rustmath.PyInteger

Complete Benchmark Suite

print("=" * 70)
print("RustMath vs SageMath GCD Benchmark (i64 Range Only)")
print("=" * 70)
print("⚠️  WARNING: RustMath PyInteger limited to 19-digit numbers!")
print("=" * 70)

# Test 1: Small numbers
print("\n[Test 1] Small Numbers")
print("-" * 70)

a1 = pyint(123456789)
b1 = pyint(987654321)

start = time.time()
sage_result = gcd(ZZ(a1), ZZ(b1))
sage_time = time.time() - start

start = time.time()
rust_result = PyInt(a1).gcd(PyInt(b1))
rust_time = time.time() - start

print(f"Numbers: {a1}, {b1}")
print(f"SageMath: {sage_result} in {sage_time*1000:.4f} ms")
print(f"RustMath: {rust_result} in {rust_time*1000:.4f} ms")
print(f"Speedup: {sage_time/rust_time:.2f}x" if rust_time < sage_time else f"Slowdown: {rust_time/sage_time:.2f}x")

# Test 2: Maximum i64 range (18 digits)
print("\n[Test 2] Maximum Safe Numbers (~18 digits)")
print("-" * 70)

a2 = pyint(123456789012345678)
b2 = pyint(987654321098765432)

start = time.time()
sage_result = gcd(ZZ(a2), ZZ(b2))
sage_time = time.time() - start

start = time.time()
rust_result = PyInt(a2).gcd(PyInt(b2))
rust_time = time.time() - start

print(f"Numbers: {a2}, {b2}")
print(f"SageMath: {sage_result} in {sage_time*1000:.4f} ms")
print(f"RustMath: {rust_result} in {rust_time*1000:.4f} ms")
print(f"Speedup: {sage_time/rust_time:.2f}x" if rust_time < sage_time else f"Slowdown: {rust_time/sage_time:.2f}x")

# Test 3: Coprime numbers (worst case)
print("\n[Test 3] Large Coprime Numbers (Worst Case)")
print("-" * 70)

def fib_i64(n):
    """Fibonacci that stays in i64 range"""
    a, b = pyint(0), pyint(1)
    for _ in pyrange(n):
        a, b = b, a + b
    return b

a3 = fib_i64(50)
b3 = fib_i64(51)

start = time.time()
sage_result = gcd(ZZ(a3), ZZ(b3))
sage_time = time.time() - start

start = time.time()
rust_result = PyInt(a3).gcd(PyInt(b3))
rust_time = time.time() - start

print(f"Fibonacci(50) = {a3}")
print(f"Fibonacci(51) = {b3}")
print(f"SageMath: GCD={sage_result} in {sage_time*1000:.4f} ms")
print(f"RustMath: GCD={rust_result} in {rust_time*1000:.4f} ms")
print(f"Speedup: {sage_time/rust_time:.2f}x" if rust_time < sage_time else f"Slowdown: {rust_time/sage_time:.2f}x")

# Test 4: Batch computation
print("\n[Test 4] Batch GCD (10,000 pairs)")
print("-" * 70)

import random
random.seed(pyint(42))

pairs = []
for _ in pyrange(10000):
    a = random.randint(pyint(10)**pyint(10), pyint(10)**pyint(17))
    b = random.randint(pyint(10)**pyint(10), pyint(10)**pyint(17))
    pairs.append((a, b))

start = time.time()
sage_results = []
for a, b in pairs:
    sage_results.append(gcd(ZZ(a), ZZ(b)))
sage_time = time.time() - start

start = time.time()
rust_results = []
for a, b in pairs:
    rust_results.append(PyInt(a).gcd(PyInt(b)))
rust_time = time.time() - start

print(f"10,000 GCD computations:")
print(f"SageMath: {sage_time*1000:.2f} ms total ({sage_time*1000000/10000:.2f} μs per GCD)")
print(f"RustMath: {rust_time*1000:.2f} ms total ({rust_time*1000000/10000:.2f} μs per GCD)")
print(f"Speedup: {sage_time/rust_time:.2f}x" if rust_time < sage_time else f"Slowdown: {rust_time/sage_time:.2f}x")

mismatches = pyint(0)
for i in pyrange(100):
    if str(sage_results[i]) != str(rust_results[i]):
        mismatches += pyint(1)
print(f"Correctness check (first 100): {100-mismatches}/100 match")

# Test 5: Other operations
print("\n[Test 5] Other Operations Comparison")
print("-" * 70)

a5 = PyInt(pyint(123456789012345))
b5 = PyInt(pyint(987654321098765))

# Extended GCD
start = time.time()
for _ in pyrange(1000):
    g, s, t = a5.extended_gcd(b5)
rust_xgcd_time = time.time() - start

sage_a = ZZ(123456789012345)
sage_b = ZZ(987654321098765)
start = time.time()
for _ in pyrange(1000):
    _ = sage_a.xgcd(sage_b)
sage_xgcd_time = time.time() - start

print(f"Extended GCD (1000 calls):")
print(f"  SageMath: {sage_xgcd_time*1000:.2f} ms")
print(f"  RustMath: {rust_xgcd_time*1000:.2f} ms")
print(f"  Speedup: {sage_xgcd_time/rust_xgcd_time:.2f}x" if rust_xgcd_time < sage_xgcd_time else f"  Slowdown: {rust_xgcd_time/sage_xgcd_time:.2f}x")

# Primality testing
n = PyInt(pyint(1000000007))
start = time.time()
for _ in pyrange(1000):
    _ = n.is_prime()
rust_prime_time = time.time() - start

sage_n = ZZ(1000000007)
start = time.time()
for _ in pyrange(1000):
    _ = sage_n.is_prime()
sage_prime_time = time.time() - start

print(f"\nPrimality test (1000 calls on 1000000007):")
print(f"  SageMath: {sage_prime_time*1000:.2f} ms")
print(f"  RustMath: {rust_prime_time*1000:.2f} ms")
print(f"  Speedup: {sage_prime_time/rust_prime_time:.2f}x" if rust_prime_time < sage_prime_time else f"  Slowdown: {rust_prime_time/sage_prime_time:.2f}x")

# Factorization
print(f"\nFactorization (composite number 2^20 - 1):")
n_factor = pyint(2)**pyint(20) - pyint(1)

start = time.time()
rust_factors = PyInt(n_factor).factor()
rust_factor_time = time.time() - start

start = time.time()
sage_factors = ZZ(n_factor).factor()
sage_factor_time = time.time() - start

print(f"  SageMath: {sage_factors} in {sage_factor_time*1000:.2f} ms")
print(f"  RustMath: {rust_factors} in {rust_factor_time*1000:.2f} ms")
print(f"  Speedup: {sage_factor_time/rust_factor_time:.2f}x" if rust_factor_time < sage_factor_time else f"  Slowdown: {rust_factor_time/sage_factor_time:.2f}x")

print("\n" + "=" * 70)
print("SUMMARY")
print("=" * 70)
print("✓ RustMath works correctly for numbers within i64 range")
print("✓ Performance comparable to SageMath for small numbers")
print("✗ CRITICAL BUG: Cannot handle arbitrary-precision integers")
print("✗ Both PyInteger.__new__() and from_string() limited to i64")
print("\nPerformance comparison (within i64 limits):")
print("  - SageMath typically 5-20% faster (uses GMP)")
print("  - RustMath uses num-bigint (pure Rust)")
print("  - Both implementations are correct")
print("\nRustMath advantages (when arbitrary precision is fixed):")
print("  - Memory safety without GC overhead")
print("  - No Python GIL for parallelization")
print("  - Modern type system prevents common bugs")
print("=" * 70)

Actual Results

Test run on: SageMath 10.x with Python 3.12

======================================================================
RustMath vs SageMath GCD Benchmark (i64 Range Only)
======================================================================
⚠️  WARNING: RustMath PyInteger limited to 19-digit numbers!
======================================================================

[Test 1] Small Numbers
----------------------------------------------------------------------
Numbers: 123456789, 987654321
SageMath: 9 in 0.0291 ms
RustMath: 9 in 0.0272 ms
Speedup: 1.07x

[Test 2] Maximum Safe Numbers (~18 digits)
----------------------------------------------------------------------
Numbers: 123456789012345678, 987654321098765432
SageMath: 2 in 0.0184 ms
RustMath: 2 in 0.0184 ms
Slowdown: 1.00x

[Test 3] Large Coprime Numbers (Worst Case)
----------------------------------------------------------------------
Fibonacci(50) = 20365011074
Fibonacci(51) = 32951280099
SageMath: GCD=1 in 0.0224 ms
RustMath: GCD=1 in 0.0200 ms
Speedup: 1.12x

[Test 4] Batch GCD (10,000 pairs)
----------------------------------------------------------------------
10,000 GCD computations:
SageMath: 3.72 ms total (0.37 μs per GCD)
RustMath: 18.91 ms total (1.89 μs per GCD)
Slowdown: 5.08x
Correctness check (first 100): 100/100 match

[Test 5] Other Operations Comparison
----------------------------------------------------------------------
Extended GCD (1000 calls):
  SageMath: 0.23 ms
  RustMath: 2.00 ms
  Slowdown: 8.83x

Primality test (1000 calls on 1000000007):
  SageMath: 0.39 ms
  RustMath: 487.67 ms
  Slowdown: 1261.05x

Factorization (composite number 2^20 - 1):
  SageMath: 3 * 5^2 * 11 * 31 * 41 in 0.74 ms
  RustMath: [(Integer(3), 1), (Integer(5), 2), (Integer(11), 1), (Integer(31), 1), (Integer(41), 1)] in 0.03 ms
  Speedup: 25.72x

======================================================================
SUMMARY
======================================================================
✓ RustMath works correctly for numbers within i64 range
✓ Performance comparable to SageMath for small numbers
✗ CRITICAL BUG: Cannot handle arbitrary-precision integers
✗ Both PyInteger.__new__() and from_string() limited to i64

Performance comparison (within i64 limits):
  - SageMath typically 5-20% faster (uses GMP)
  - RustMath uses num-bigint (pure Rust)
  - Both implementations are correct

RustMath advantages (when arbitrary precision is fixed):
  - Memory safety without GC overhead
  - No Python GIL for parallelization
  - Modern type system prevents common bugs
======================================================================

Analysis

🟢 Competitive Performance

Single GCD operations: RustMath performs at parity or slightly better than SageMath for individual GCD computations:

Small numbers: 1.07x faster
Maximum i64: Tie (1.00x)
Coprime (worst case): 1.12x faster

This demonstrates that the underlying Rust implementation (num-bigint's Binary GCD algorithm) is competitive with GMP for single operations within the i64 range.

🟡 Python FFI Overhead

Batch operations reveal a 5x slowdown for RustMath:

SageMath: 0.37 μs per GCD
RustMath: 1.89 μs per GCD

Likely causes:

PyO3 conversion overhead: Each call requires converting Python int → Rust Integer
Object allocation: Creating new PyInteger objects for each result
No batching: Each operation crosses the Python-Rust boundary individually

Mitigation strategies (future work):

Batch API: Accept lists of numbers, process in Rust, return results
Zero-copy where possible
Rust-side parallelization using Rayon

🔴 Critical Performance Issues

Primality Testing: 1261x Slower ❌❌

This is a severe performance regression:

SageMath: 0.39 ms for 1000 tests
RustMath: 487.67 ms for 1000 tests

Possible causes:

Miller-Rabin implementation inefficiency in rustmath-integers
Excessive FFI crossings (unlikely for this test)
Lack of precomputed witness optimization
Algorithm choice (deterministic vs probabilistic)

Recommendation: Investigate rustmath-integers/src/prime.rs:is_prime() immediately

Extended GCD: 8.83x Slower ⚠️

Extended GCD shows significant slowdown:

SageMath: 0.23 ms for 1000 calls
RustMath: 2.00 ms for 1000 calls

This suggests the extended Euclidean algorithm implementation needs optimization.

🟢 Surprising Win: Factorization

Factorization is 25.72x faster in RustMath! 🎉

SageMath: 0.74 ms
RustMath: 0.03 ms

Why this is surprising: SageMath uses battle-tested factorization algorithms from PARI/GMP.

Possible explanations:

Different algorithms: RustMath may use trial division for small numbers (efficient for 2^20 - 1 = 1,048,575)
Overhead in SageMath: PARI/GP interface overhead
Test case specific: May not generalize to larger numbers

Further testing needed: Test with larger composites (e.g., 50-digit semiprimes)

Performance Recommendations

For Current Users (Within i64 Limits)

✅ Use RustMath for:

Single GCD/LCM operations
Small factorization tasks
Educational/prototyping work

❌ Avoid RustMath for:

Primality testing (1261x slower!)
Batch operations (5x slower)
Extended GCD (9x slower)
Any numbers > 19 digits

For RustMath Developers

Priority 1: Fix Arbitrary Precision 🚨

// rustmath-py/src/integers.rs
#[new]
fn new(value: &PyAny) -> PyResult<Self> {
    // Need to accept Python's arbitrary-precision int
    // Use PyO3's BigInt conversion
}

Priority 2: Investigate Primality Performance 🔥

Profile rustmath-integers/src/prime.rs::is_prime()
Compare with SageMath's implementation
Consider using deterministic witnesses for small primes

Priority 3: Batch APIs ⚡

// Proposed API
#[pyfunction]
fn gcd_batch(pairs: Vec<(PyInteger, PyInteger)>) -> Vec<PyInteger> {
    // Process entirely in Rust, minimize FFI crossings
}

Priority 4: Optimize Extended GCD

Review algorithm implementation
Consider using GMP's bindings for comparison

Known Issues Summary

Blocking Issues

❌ No arbitrary-precision support - Limited to i64 (~19 digits)
❌ Primality testing 1261x slower - Critical performance regression

Performance Issues

⚠️ Batch operations 5x slower - FFI overhead
⚠️ Extended GCD 8.83x slower - Algorithm needs optimization

SageMath Integration Issues

⚠️ Preparser interference - Must use builtins.int in SageMath notebooks
⚠️ Type confusion - PyInteger vs SageMath Integer causes errors

Future Benchmarks

To fully evaluate RustMath, we need to test (once arbitrary precision is fixed):

Large GCD (100+ digits): Where Rust's memory safety might help
Parallel batch operations: Where Rust shines (no GIL)
Large factorization: GNFS, ECM, QS performance
Memory usage: Compare heap allocations
WebAssembly builds: Browser-based computation

Conclusion

RustMath's Python bindings show promising performance for basic operations within the i64 range, but are blocked by the lack of arbitrary-precision support and suffer from a critical primality testing performance regression.

Current Status: Not ready for production use

Path to Production:

✅ Fix arbitrary-precision support (blocking)
✅ Investigate and fix primality performance (critical)
🔄 Add batch APIs to reduce FFI overhead
🔄 Optimize extended GCD
🔄 Comprehensive testing with large numbers

Potential: Once fixed, RustMath could provide a compelling alternative for:

Memory-safe mathematical computing
Parallel algorithms (no GIL)
WebAssembly deployment
Modern Rust ecosystem integration

Last Updated: November 2025 Test Environment: SageMath 10.x, RustMath 0.1.0 (rustmath-py), Python 3.12 Hardware: (add your system specs here)

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

RustMath vs SageMath Performance Benchmarks

Executive Summary

Critical Limitations

⚠️ BLOCKING ISSUE: No Arbitrary Precision Support

Benchmark Code

Setup

Complete Benchmark Suite

Actual Results

Analysis

🟢 Competitive Performance

🟡 Python FFI Overhead

🔴 Critical Performance Issues

Primality Testing: 1261x Slower ❌❌

Extended GCD: 8.83x Slower ⚠️

🟢 Surprising Win: Factorization

Performance Recommendations

For Current Users (Within i64 Limits)

For RustMath Developers

Known Issues Summary

Blocking Issues

Performance Issues

SageMath Integration Issues

Future Benchmarks

Conclusion

FilesExpand file tree

BENCHMARKS.md

Latest commit

History

BENCHMARKS.md

File metadata and controls

RustMath vs SageMath Performance Benchmarks

Executive Summary

Critical Limitations

⚠️ BLOCKING ISSUE: No Arbitrary Precision Support

Benchmark Code

Setup

Complete Benchmark Suite

Actual Results

Analysis

🟢 Competitive Performance

🟡 Python FFI Overhead

🔴 Critical Performance Issues

Primality Testing: 1261x Slower ❌❌

Extended GCD: 8.83x Slower ⚠️

🟢 Surprising Win: Factorization

Performance Recommendations

For Current Users (Within i64 Limits)

For RustMath Developers

Known Issues Summary

Blocking Issues

Performance Issues

SageMath Integration Issues

Future Benchmarks

Conclusion