| --- |
| tags: |
| - modular-arithmetic |
| - neural-arithmetic |
| - sair-competition |
| library_name: pytorch |
| --- |
| |
| # Neural Bignum ALU — Modular Multiplication |
|
|
| A submission for the [SAIR Foundation Modular Arithmetic Challenge](https://competition.sair.foundation/competitions/modular-arithmetic-challenge/overview): |
| compute `(a · b) mod p` for a prime `p` and integers `a, b`, where the answer must be produced by **trained parameters**, not hand-coded arithmetic. |
|
|
| ## What it is |
|
|
| A router over two trained specialists, selected by the bit-length of `p`: |
|
|
| 1. **Small-prime specialist** (`p < 256`): a ~10.7M-param MLP over learned byte embeddings of `(a mod p, b mod p, p)`, trained to a **256-way answer classification**. Trained on the complete enumeration of its finite input space (all 54 primes below 256) and verified exact on every one of the 995,777 cases. |
|
|
| 2. **Neural bignum pipeline** (`p` up to 2048 bits): a composition of four small trained cells — |
| - `mul8`: (byte, byte) → (hi, lo) |
| - `add2`: (byte, byte, carry) → (byte, carry) |
| - `subb`: (byte, byte, borrow) → (byte, borrow) |
| - `sel`: (overflow, borrow) → select-bit |
|
|
| Each cell is an embedding+MLP trained from random initialization and **verified exhaustively exact over its entire finite input domain** (e.g. all 65,536 byte pairs for `mul8`). A fixed loop applies the cells across byte limbs to form the product `a·b` and reduce it mod `p` by **Barrett reduction**. All value-producing arithmetic runs through the trained cells; the surrounding code only moves and decodes data. |
|
|
| Operands are reduced two at a time (`a mod p`, `b mod p`) and decomposed into byte limbs. `preprocess_p` supplies a single conditioning constant derived from `p` alone: the Barrett constant `mu = floor(256^(2k)/p)`, where `k` is the byte-limb count of `p`. **No operand is pre-scaled and no modular product is formed outside the trained cells** — the reduction runs entirely through the cells on `a·b`. Answers are emitted as base-256 digits, MSB-first. Problems outside the specialists' range fall back to `[0]`. |
|
|
| ## Results |
|
|
| Evaluated through the official pipeline (public benchmark and multiple secret-style seeds), and in the official CPU sandbox (4 CPU / 8 GB / 300 s): |
|
|
| | Metric | Value | |
| |---|---| |
| | `overall_accuracy` (tiers 1–10) | **1.000** | |
| | `highest_tier_above_90` | **10** | |
| | Per-tier accuracy (T1–T10) | 100 / 100 each | |
| | Deterministic | ✓ | |
| | Inference wall-clock (1100 problems) | ~200 s of 300 s budget | |
|
|
| Every parameter is trained from random initialization; randomizing any cell's weights collapses end-to-end accuracy (the rules' operational test for a learned model rather than a hard-coded circuit). |
|
|
| ## Files |
|
|
| - `manifest.json` — entry class + `output_base` |
| - `model.py` — router entry point (`NeuralBignumModel`) |
| - `specialists/` — the two trained specialists |
| - `weights/` — trained cell + classifier weights |
|
|
| ## Provenance |
|
|
| All weights obtained by supervised training from random initialization (AdamW), with exhaustive full-domain verification of every arithmetic cell. Training code, logs, and seeds are retained and available on request. |
|
|
