README.md

---
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.