Replace repeated 512-by-256 Knuth division with a reusable Barrett quotient/remainder plan

perfloop/uint256 · INEFFICIENT ALGORITHM

https://perfloop.ai/t/oss/case_0ca0y6120x

Verdict

VERIFIED · settled 2026-08-31

What happened: The paired measurements met the required improvement.

Hypothesis

MulDivOverflowRem always builds an eight-word product and hands it with a raw divisor and quotient buffer to udivrem; udivrem scans both operand widths, normalizes into dn and un scratch storage, and sends every multiword case to udivremKnuth, whose quotient-digit loop invokes subMulTo across the divisor limbs and can add the divisor back. For the four-word-divisor class, mod.go already supplies the missing cross-spine representation: Reciprocal builds a five-word reciprocal, MulModWithReciprocal demonstrates caller-side reuse, and reduce4 already forms a Barrett quotient estimate before discarding it while reducing the same eight-word product. A divisor plan can preserve and correct that estimate alongside the remainder, making the steady-state floor the full product plus fixed reciprocal high-products and bounded corrections rather than normalized digit-at-a-time long division; the existing generic route remains for inputs the current reciprocal deliberately does not cover. The hypothesis is falsified if an end-to-end benchmark of repeated full-width-divisor MulDivOverflowRem calls, comparing the plan path with the raw path while checking quotient, remainder, and overflow against big.Int including correction boundaries, does not show a lower steady-state latency or CPU cost.

Change to test: Add an immutable four-limb MulDivPlan holding a copied divisor and Reciprocal's five-limb mu, expose MulDivOverflowRemWithPlan, and route that entry through a quotient-preserving version of reduce4: retain and correct the Barrett quotient estimate while producing the remainder, write its low four limbs to z, and derive overflow from its fifth limb instead of entering udivrem, udivremKnuth, and subMulTo. Keep the raw generic path as the compatibility fallback for one-shot or narrow divisors.

Where it lives

perfloop/uint256 · uint256.go

Evidence

repeated full-product four-word-divisor MulDivOverflowRem quotient and remainder · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 142.2 122.7 −13.6% (−19.35) −23.5 to −14.3 < −7.108 PASSED
B/op 0 0 0 0 to 0 ≤ 0 PASSED
allocs/op 0 0 0 0 to 0 ≤ 0 PASSED

reused dense four-word-divisor MulDivOverflowRem quotient and remainder · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 136.5 49.97 −63.4% (−86.51) −88.24 to −84.39 < −6.825 PASSED
B/op 0 0 0 0 to 0 ≤ 0 PASSED
allocs/op 0 0 0 0 to 0 ≤ 0 PASSED

Checks: 4 of 4 passed. Verification: no defect found.

Timeline