Skip to content

README.md

Latest commit

 

History

History
460 lines (325 loc) · 29.3 KB

README.md

File metadata and controls

460 lines (325 loc) · 29.3 KB
Raw

math

pi.py pi-rs prime-rs fib.py fib-rs sq.py sq-rs twin-primes-rs e.py e-rs factorial-py factorial-rs perfect-numbers-py perfect-numbers-rs collatz-py collatz-rs goldbach-rs amicable.py amicable-rs triangle.py scripts

High-performance mathematical computation tools.

Project Description Implementation CI
pi/ Calculate π to N decimal places Python + Rust pi.py pi-rs
prime/ Find all primes up to 10^N Rust prime-rs
fib/ Generate all Fibonacci numbers with up to 10^X digits Python + Rust fib.py fib-rs
sq/ Generate all perfect squares with up to 10^N digits (N=1 max) Python + Rust sq.py sq-rs
twin-primes/ Find all twin prime pairs up to 10^N Rust twin-primes-rs
e/ Calculate e to N decimal places Python + Rust e.py e-rs
factorial/ Compute N! to arbitrary precision (prime swing algorithm) Python + Rust factorial-py factorial-rs
perfect-numbers/ Find all perfect numbers up to 10^N (Lucas-Lehmer + sigma) Python + Rust perfect-numbers-py perfect-numbers-rs
collatz/ Find Collatz chain record-setters up to 10^N Python + Rust collatz-py collatz-rs
goldbach/ Find all Goldbach pairs for even numbers up to 10^N Rust goldbach-rs
amicable/ Find all amicable pairs (a,b) with b ≤ 10^N (proper-divisor sum sieve) Python + Rust amicable.py amicable-rs
triangle/ Solve a triangle from any three sides/angles; area, perimeter, braille drawing Python triangle.py

Coverage

CLI Python Rust
amicable python rust
collatz python rust
e python rust
factorial python rust
fib python rust
goldbach — rust
perfect-numbers python rust
pi python rust
prime — rust
sq python rust
triangle python —
twin-primes — rust

pi

Calculates π to an arbitrary number of decimal places using the Chudnovsky algorithm with binary splitting.

  • Python implementation (pi/pi.py) — best for up to ~50M digits
  • Rust implementation (pi/pi-rs/) — best for 50M+ digits; shared-memory rayon parallelism with zero IPC overhead

See pi/README.md for full details.

prime

Finds every prime number up to 10^N using a parallel segmented Sieve of Eratosthenes.

  • Rust implementation (prime/prime-rs/) — packed bitset segments (32 KB each, fits in L2 cache), rayon-parallelised across all cores, streams output to file to keep peak RAM ≤ ~50 MB

See prime/README.md for full details.

fib

Generates every Fibonacci number with at most 10^X decimal digits.

  • Python implementation (fib/fib.py) — uses Python's built-in arbitrary-precision int; no external dependencies
  • Rust implementation (fib/fib-rs/) — uses rug/GMP for best performance at large digit counts

See fib/README.md for full details.

sq

Generates every perfect square with at most 10^N decimal digits. N=1 is the only valid value (produces 99,999 squares up to 10 digits).

  • Python implementation (sq/sq.py) — Python stdlib only, no external dependencies
  • Rust implementation (sq/sq-rs/) — plain u64 arithmetic, no GMP required

See sq/README.md for full details.

twin-primes

Finds every twin prime pair (p, p+2) where both primes are less than 10^N.

  • Rust implementation (twin-primes/twin-primes-rs/) — packed bitset segments (32 KB each, fits in L2 cache), constant memory usage regardless of N

See twin-primes/README.md for full details.

e

Calculates Euler's number e to an arbitrary number of decimal places using the Taylor series with binary splitting.

  • Python implementation (e/e.py) — gmpy2/GMP fast path with mpmath fallback
  • Rust implementation (e/e-rs/) — shared-memory rayon parallelism with zero IPC overhead

See e/README.md for full details.

factorial

Computes N! (N factorial) to arbitrary precision using the prime swing algorithm (n! = swing(n) × (⌊n/2⌋!)²).

  • Python implementation (factorial/factorial.py) — gmpy2/GMP fast path with plain int fallback; parallel swing via ProcessPoolExecutor
  • Rust implementation (factorial/factorial-rs/) — rug/GMP with rayon parallel chunks

See factorial/README.md for full details.

perfect-numbers

Finds all perfect numbers up to 10^N using the Lucas-Lehmer primality test (even perfect numbers via Mersenne primes) and a sigma divisor-sum sieve (odd perfect numbers, none known but checked for completeness).

  • Python implementation (perfect-numbers/perfect_numbers.py) — pure Python stdlib, no external dependencies
  • Rust implementation (perfect-numbers/perfect-numbers-rs/) — rug/GMP for arbitrary-precision sigma computation

See perfect-numbers/README.md for full details.

Quick Reference

Python CLI contract

The size-N Python programs share one command line (<module> is pi, fib, sq, e, factorial, perfect_numbers, collatz or amicable); triangle has its own flags (see its section):

python3 <module>.py SIZE [--show] [--yes]   # never reads stdin; always writes the output file, --show also prints
python3 <module>.py --smoke                 # quick check at the program's SMOKE_SIZE
python3 <module>.py                         # interactive prompts at a terminal; exit 2 with usage if stdin is not one

Large runs need --yes: pi and e above 1,000,000 digits, fib X >= 4 (otherwise exit 1 naming --yes). The other programs accept and ignore it.

Python (pi/)

cd pi
make run       # python3 pi.py
make lint      # ruff check . && ruff format --check .
make test      # lint, then pytest test_pi.py -v
make coverage  # pytest --cov=pi --cov-report=term-missing

All Rust crates

make test-rust   # make test in all 11 crates concurrently (JOBS=N, default 8); prints ok/FAIL per crate

Rust (pi/pi-rs/)

cd pi/pi-rs
make pi        # cargo build --release
make lint      # cargo fmt --check, then cargo clippy --all-targets -- -D warnings
make test      # lint, then cargo test

Rust (prime/prime-rs/)

cd prime/prime-rs
make prime     # cargo build --release
make lint      # cargo fmt --check, then cargo clippy --all-targets -- -D warnings
make test      # lint, then cargo test

Python (fib/)

cd fib
make run       # python3 fib.py
make lint      # ruff check . && ruff format --check .
make test      # lint, then pytest test_fib.py -v
make coverage  # pytest --cov=fib --cov-report=term-missing

Rust (fib/fib-rs/)

cd fib/fib-rs
make fib       # cargo build --release
make lint      # cargo fmt --check, then cargo clippy --all-targets -- -D warnings
make test      # lint, then cargo test

Python (sq/)

cd sq
make run       # python3 sq.py
make lint      # ruff check . && ruff format --check .
make test      # lint, then pytest test_sq.py -v
make coverage  # pytest --cov=sq --cov-report=term-missing

Rust (sq/sq-rs/)

cd sq/sq-rs
make sq        # cargo build --release
make lint      # cargo fmt --check, then cargo clippy --all-targets -- -D warnings
make test      # lint, then cargo test

Rust (twin-primes/twin-primes-rs/)

cd twin-primes/twin-primes-rs
make twin-primes  # cargo build --release
make lint         # cargo fmt --check, then cargo clippy --all-targets -- -D warnings
make test         # lint, then cargo test

Python (e/)

cd e
make run       # python3 e.py
make lint      # ruff check . && ruff format --check .
make test      # lint, then pytest test_e.py -v
make coverage  # pytest --cov=e --cov-report=term-missing

Rust (e/e-rs/)

cd e/e-rs
make e         # cargo build --release
make lint      # cargo fmt --check, then cargo clippy --all-targets -- -D warnings
make test      # lint, then cargo test

Python (factorial/)

cd factorial
make run       # python3 factorial.py
make lint      # ruff check . && ruff format --check .
make test      # lint, then pytest test_factorial.py -v
make coverage  # pytest --cov=factorial --cov-report=term-missing

Rust (factorial/factorial-rs/)

cd factorial/factorial-rs
make factorial # cargo build --release
make lint      # cargo fmt --check, then cargo clippy --all-targets -- -D warnings
make test      # lint, then cargo test

Python (perfect-numbers/)

cd perfect-numbers
make run       # python3 perfect_numbers.py
make lint      # ruff check . && ruff format --check .
make test      # lint, then pytest test_perfect_numbers.py -v
make coverage  # pytest --cov=perfect_numbers --cov-report=term-missing

Rust (perfect-numbers/perfect-numbers-rs/)

cd perfect-numbers/perfect-numbers-rs
make perfect-numbers  # cargo build --release
make lint             # cargo fmt --check, then cargo clippy --all-targets -- -D warnings
make test             # lint, then cargo test

Python (collatz/)

cd collatz
make run       # python3 collatz.py
make lint      # ruff check . && ruff format --check .
make test      # lint, then pytest test_collatz.py -v
make coverage  # pytest --cov=collatz --cov-report=term-missing

Rust (collatz/collatz-rs/)

cd collatz/collatz-rs
make collatz   # cargo build --release
make lint      # cargo fmt --check, then cargo clippy --all-targets -- -D warnings
make test      # lint, then cargo test

Rust (goldbach/goldbach-rs/)

cd goldbach/goldbach-rs
make goldbach  # cargo build --release
make lint      # cargo fmt --check, then cargo clippy --all-targets -- -D warnings
make test      # lint, then cargo test

Python (amicable/)

cd amicable
make run       # python3 amicable.py
make lint      # ruff check . && ruff format --check .
make test      # lint, then pytest test_amicable.py -v
make coverage  # pytest --cov=amicable --cov-report=term-missing

Rust (amicable/amicable-rs/)

cd amicable/amicable-rs
make amicable  # cargo build --release
make lint      # cargo fmt --check, then cargo clippy --all-targets -- -D warnings
make test      # lint, then cargo test

collatz

Finds Collatz chain record-setters up to 10^N using vector memoization.

  • Python implementation (collatz/collatz.py) — stdlib only, practical for N≤7
  • Rust implementation (collatz/collatz-rs/) — Vec<u32> memoization, handles N≤9 comfortably

See collatz/README.md for full details.

goldbach

Finds all Goldbach pairs for even numbers up to 10^N.

  • Rust implementation (goldbach/goldbach-rs/) — packed bitset sieve, BufWriter streaming, practical up to N=6 (~20 GB output)

See goldbach/README.md for full details.

amicable

Finds all amicable pairs (a, b) where a < b ≤ 10^N using a proper-divisor sum sieve (sigma function over all numbers up to the limit, then cross-checking pairs).

  • Python implementation (amicable/amicable.py) — stdlib only, no external dependencies
  • Rust implementation (amicable/amicable-rs/) — plain u64 arithmetic with a pre-computed sigma sieve

See amicable/README.md for full details.

triangle

Solves a triangle from any three of its sides and angles, reports area and perimeter, and draws it in braille.

  • Python implementation (triangle/triangle.py) — stdlib only, no external dependencies; there is no Rust crate

See triangle/README.md for full details.

Development Setup

After cloning, install the git hooks and root-scope Python dependencies:

make install-hooks   # symlinks pre-commit, pre-push and commit-msg
make install-deps    # installs what tests/, scripts/ and .claude/scripts/ import

install-deps reads requirements-dev.txt — the third-party modules root-scope Python actually imports (defusedxml, pyyaml), not a tool list. It refuses on a PEP 668 externally-managed interpreter rather than using --break-system-packages, and the refusal names the remedy: python3 -m venv .venv && . .venv/bin/activate. Without it, make test fails at import — scripts/pre-push runs the root suite on any push touching scripts/, tests/ or .claude/scripts/. Pushes to master or main are also judged by ai-config's shared push-content gate (ADR-0091): scripts/pre-push loads it from GitHub and refuses the push when it cannot load; a feature push makes no network call.

install-hooks symlinks scripts/pre-commit into .git/hooks/pre-commit. The hook runs make lint on staged sub-projects, runs root make lint-python once when root-scope Python (scripts/, tests/, .claude/scripts/, typings/) is staged, and scans for secrets with ggshield (skipped gracefully if not installed). CI secret-scan via gitleaks is a backstop — local scanning catches secrets before they leave the machine.

Install ggshield: brew install gitguardian/tap/ggshield && ggshield auth login.

  • brew install git-cliff — CHANGELOG generation (make changelog)

Rust crates use scripts/rust-check.sh for make lint and make test. By default it sets CARGO_HOME to a repo-local writable cache path and can run offline when dependencies are cached:

RUST_CHECK_OFFLINE=1 make test

Every Rust sub-project also has make bench (Criterion benchmarks). CI alerts when any benchmark regresses more than 30% vs the previous run. cargo test includes CLI integration tests from tests/cli.rs alongside the unit tests.

Python CI runs two additional quality steps per sub-project: pyright (static type checking) and pip-audit (dependency security scan). These run in CI only — there is no local make target for them. Run them manually with pyright from the sub-project directory and python3 scripts/pip_audit_advisory.py from the repo root (the wrapper CI runs: findings and skipped dependencies warn, an audit that did not happen fails; ADR-0016).

Architectural Decisions

Key decisions are recorded in docs/adr/: algorithm choices (Chudnovsky, segmented sieve), language strategy (Python vs Rust), library choices (GMP/rug, rayon), and CI structure.

Verifying releases

Release binaries are signed with cosign using keyless Sigstore signing. Each release includes the binary plus:

  • {name}.sha256 — SHA256 checksum
  • {name}.sbom.spdx.json — SPDX bill of materials
  • {name}.bundle — cosign signature bundle (v4 format; supersedes the separate .sig/.pem pair)
  • THIRD-PARTY-NOTICES.txt — third-party licence notices. For the five binaries that statically link GMP, MPFR and MPC through rug/gmp-mpfr-sys (pi, e, fib, factorial, perfect-numbers) it names the LGPL-3.0-or-later components and where their source is, and includes the LGPL-3.0 and GPL-3.0 texts

To verify a release binary (example for factorial):

cosign verify-blob factorial \
  --bundle factorial.bundle \
  --certificate-identity \
    "https://github.com/brujack/math/.github/workflows/release-factorial-rs.yml@refs/heads/master" \
  --certificate-oidc-issuer "https://token.actions.githubusercontent.com"

Replace factorial with the sub-project name (e.g. fib), and release-factorial-rs.yml with that sub-project's own release workflow filename (e.g. release-fib-rs.yml) — the certificate identity is the workflow that requested the signing certificate, not the tag being released. This identity was confirmed against real releases on 2026-10-31: every v0.1.0 and v0.2.0 binary verifies with it (cosign v3.1.4), and the same command fails for another sub-project's workflow identity or a different binary.

License

MIT — see LICENSE. The binaries that link GMP, MPFR and MPC also carry those libraries' LGPL-3.0-or-later terms; each release's THIRD-PARTY-NOTICES.txt lists them. Dependency licences are checked by cargo deny against deny.toml (ADR-0035).