Skip to content
BranchesTags

Repository files navigation

Math-KAT: Mathematical Known Answer Test

Fail-Fast, Iterate-Faster — Streaming SHA-256 verification for mathematical sequences.

Math-KAT lets you verify that a sequence generator produces correct output without writing any files to disk. It streams terms through a SHA-256 hash and compares the result against a stored manifest — a technique borrowed from KAT (Known Answer Test) vectors in cryptography.

The Problem: Validation is the Bottleneck

Traditional sequence verification:

  1. Generate for hours → GBs/TBs of temp files
  2. Write to disk → SSD wear, controller waits, I/O bottlenecks
  3. Hash the file → minutes of pure I/O
  4. Mismatch? Delete TBs of data, fix bug, repeat

Math-KAT replaces this with:

Hack → Stream → Judge → (✓ Keep | ✗ RIP OUT Instantly)

No files. No cleanup. No SSD wear. Instant verdict.

Sandbox Loop

Measured Savings

Benchmark of PrimeGenerator (Python simple sieve) at the dev tier:

Tier Primes File I/O Streaming Speedup Disk Avoided
min 100 0.6 ms 0.6 ms 1.0× 0.5 KB
ci_smoke 1,000 0.6 ms 0.6 ms 1.0× 5 KB
dev 100,000 77 ms 81 ms 1.0× 5 MB
extended* 1,000,000 ~1.2 s ~1.1 s ~1.1× 50 MB
hpc* 10¹² 14 TB 0 B written ∞ 14 TB

* Projected. Streaming advantage grows with scale and generator speed. At 10¹² primes, file-based verification writes 14 TB per run — consuming an enterprise SSD in a few iterations. Math-KAT writes zero bytes.

Hardware Comparison

Full benchmarking methodology →

Quick Start

# Install
pip install -e .

# Verify a sequence (CI smoke tier)
math-kat verify A000040 --tier ci_smoke

# List available sequences and tiers
math-kat list

# Generate a manifest for a new sequence
math-kat generate-manifest A000045 -t ci_smoke count 1000

# Check manifest integrity
math-kat check

The Algorithmic Sandbox Loop

A development rhythm for fearless optimization:

# Hack: modify generator
def my_sieve(limit):
    ...  # try a wheel, SIMD, whatever

# Stream: pipe to verifier (no file, no temp)
verifier = StreamingVerifier(expected_hash="abc...")
result = verifier.feed_stream(my_sieve(limit))

# Judge: instant verdict
if result.matched:
    print("✓ PASS — keep it, benchmark, commit")
else:
    print("✗ FAIL — rip it out, zero cleanup")

Full Algorithmic Sandbox philosophy →

Architecture

┌──────────────┐     ┌──────────────────┐     ┌──────────────────┐
│  Generator   │────▶│ StreamingVerifier │────▶│ VerificationResult│
│ (Python/C)   │     │  SHA-256 (64 KB)  │     │  ✓ PASS / ✗ FAIL  │
└──────────────┘     └──────────────────┘     └──────────────────┘
                            │
                            ▼
                     ┌──────────────┐
                     │   Manifests/ │
                     │  (JSON, in   │
                     │   repo)      │
                     └──────────────┘

Architecture Diagram

Core Sequences

OEIS ID Name Generator Offset
A000040 Prime numbers fastsieve subprocess 1
A000045 Fibonacci numbers Fast doubling 0
A000108 Catalan numbers Binomial coefficient 0
A000142 Factorial numbers Iterative 0
A000010 Euler's totient φ(n) Linear sieve 1

Verification Tiers

Tier Pipeline

Tier Bound Time Use Case
min 100 terms <1 ms Smoke test
ci_smoke 1,000 terms ~1 ms CI on every push
dev 100,000 terms ~80 ms Developer iteration loop
extended 1,000,000 terms ~5 min Weekly regression
hpc 10¹²+ terms Hours Final validation

Deep Dive: A000040 — Prime Numbers

A000040 (prime numbers) is the most actively benchmarked and most fully tiered sequence in the Math-KAT registry. Its manifest spans 8 orders of magnitude, from 10 primes to 10¹².

Manifest Variants

Two manifest conventions demonstrate KAT's flexibility:

Manifest Bound Type dev Means dev SHA-256
A000040.json upper_limit Primes ≤ 100,000 (9,592 terms) 448c035b...
A000040B.json count First 100,000 primes 19778d86...

Use upper_limit to match OEIS stripped-file semantics; use count to verify "first N terms" against a specific count bound.

Checkpoint Debugging

Checkpoints let you bisect failures without re-running the entire generation:

Term Cumulative SHA-256 (A000040B, count)
10 dc8c353498db9b9bb1161eab32f94206df30e014947ae64482851f3fafed07ff
100 5991e67de21b5e0aac4191be06e69b5e32e8431858a108c4029906aaa96a1371
1,000 18ac898998c81cb9eb52d37be6cd452a3b19babedbdd5cc6e8ffff20e7c2b048
10,000 de1b90e91ee8193f153cd9d6f79887a1ba05e2365a8ee230c6c6eb23c1ab5fe4
100,000 19778d8659445c92f6f2b1f5deed0932fbd2ab31fe07cc714ef64847eb1a8236

Debug workflow:

  1. Final hash mismatches at 100,000 → compare checkpoint at 50,000
  2. If checkpoint matches, the bug is in terms 50,001–100,000
  3. Add finer checkpoints in the failing range, fix, re-run — instant PASS

KAT vs File I/O Timing

The manifests/schassh.sh script drives fastsieve (a Go prime sieve, ~100× faster than the Python fallback) with -wheel 210 across 7 scales, comparing streaming hash generation to file output:

Primes Bound Terms File Write (real) Streaming Hash (real) File Size Speedup
10⁵ 9,592 0.00s 0.00s ~0.1 MB —
10⁶ 78,498 0.01s 0.00s ~0.8 MB —
10⁷ 664,579 0.08s 0.04s ~7 MB 2.0×
10⁸ 5,761,455 0.78s 0.48s ~65 MB 1.6×
10⁹ 50,847,534 7.72s 4.94s ~600 MB 1.6×
10¹⁰ 455,052,511 82.86s 54.10s ~5.5 GB 1.5×
10¹¹ 4,118,054,813 pending pending ~50 GB —

Timings are real wall-clock seconds from time -p in manifests/schassh.sh. File write includes I/O + sha256sum of the written file. Streaming hash computes SHA-256 during generation — zero bytes on disk. At 10¹⁰ the streaming mode saves 28.76s (35%) by avoiding the write-then-read-back cycle. The 10¹¹ row will be filled when the benchmark completes.

Why A000040 Benefits Most

  • Generator speed — fastsieve (Go) saturates CPU caches, making I/O the bottleneck even at modest scales.
  • Rich checkpointing — 30+ checkpoints across the manifest enable precise bisection without re-running full generation.
  • Two conventions — Dual manifests showcase KAT's flexibility with different bound semantics and hash storage formats.

CLI Reference

math-kat verify [--manifest DIR] [--tier TIER] [--stdin] [--format FMT] [SEQUENCE]
math-kat generate-manifest SEQUENCE -t NAME TYPE VALUE [options]
math-kat list [SEQUENCE]
math-kat check [--manifest DIR] [SEQUENCE]

Why This Saves Money

  • SSD Endurance: 0 bytes written per verification. No wear.
  • CI Minutes: <1 second vs minutes for file-based hashing.
  • Infrastructure: CPU does the math, RAM does the hash, disk sleeps.
  • Developer Time: Instant iteration eliminates the "fear of breaking things."
Resource Traditional Math-KAT Savings
SSD writes/verify GB–TB 0 bytes 100%
Peak RAM File buffer 64 KB 99.9%
Iteration time Minutes–hours Milliseconds–seconds 1,000×
CI cost/run Storage + compute Compute only ~10×

Showcase Your Verification

Projects using Math-KAT streaming verification can display this badge:

Math-KAT Verified

[![Math-KAT Verified](https://img.shields.io/badge/Math--KAT-Verified-brightgreen?style=flat-square&logo=github)](https://github.com/gilflorida2023/math-kat)

Multi-Language Samples

Implement Math-KAT streaming verification in any language:

Language File Use Case
C++ samples/cpp/stream_primes.cpp Raw performance (sieve, SIMD, cache-line tuning)
Python samples/python/verify_stream.py Quick scripting, reference testing
Rust samples/rust/src/main.rs Memory-safe, zero-cost abstractions
JavaScript samples/javascript/stream_digits.js Node.js / web-based visualizations
Go samples/go/verify_stream.go Concurrent pipelines, fast compilation
C samples/c/verify_stream.c Bare metal, embedded, FFI (OpenSSL SHA-256)
Java samples/java/VerifyStream.java JVM ecosystem, enterprise
Bash samples/bash/verify_stream.sh Quick one-liners, pipes (openssl sha256)

All samples follow the same pattern — generate terms, pipe to SHA-256, compare against the manifest. No files, no temp data, no cleanup.

How to Add New Sequences

We accept pull requests for new sequence manifests!

  1. Format — Must match the manifest.json schema exactly (see SPEC.md)
  2. Streaming — Pure ASCII text, LF (\n) delimiters only
  3. Validation — Verify hash calculation twice before submitting
  4. Naming — Use standard OIDs file name: A######.json
  5. Tier — At minimum ci_smoke; dev, extended, and hpc encouraged
# After implementing your generator:
pip install -e .
math-kat generate-manifest A###### -t ci_smoke count 1000
math-kat verify A###### --tier ci_smoke
git add manifests/A######.json

Support the Registry ☕

Maintaining massive mathematical reference datasets and updating canonical manifests takes compute and active maintenance. If this framework saved your hardware or accelerated your research, consider supporting:

Format

Each term is formatted as ASCII decimal with a trailing LF:

term1\nterm2\n...\ntermN\n

No trailing newline after the last term. This matches the OEIS "stripped" convention. For b-file compatibility, use --format bfile_index_value_lf.

License

  • Code: MIT
  • Manifests: CC0 1.0 Universal (public domain)

About

Initial Math-KAT release: streaming cryptographic verification for OEIS sequences

Topics

math-oeis-sha256-verification-sequences

Resources

Readme
Activity

Stars

0 stars

Watchers

0 watching

Forks

0 forks
Report repository

Releases

Packages

Contributors

Languages