Scrambled Multiply-with-Carry Pseudorandom Number Generators

Core Contribution

Vigna gives a thorough theoretical and practical treatment of multiply-with-carry (MWC) and generalized MWC (GMWC) pseudorandom number generators. The paper makes five contributions:

1. Structural limitation. For every MWC generator, whatever the lag and multiplier, the triples (x_n, x_{n+1}, x_{n+k+1})/b lie in equidistant planes at least about 1/(1.28√b) apart. The proof is a Hermite-constant argument on a 2D sublattice, plus an exact characterization of ν_{k+2}. Propositions 4.4 and 4.5 generalize this to GMWC generators and to further families of dual vectors. The bounds are tight, as the best multipliers come within 0.02% of them.

2. Scrambler X. It xors each digit with ⌊τ/b⌋, which generalizes Thomas's MWC64X and costs one off-critical-path instruction. In the author's tests it removes the lattice defect, including a 3 TB birthday-spacings test that detects the defect in plain MWC128 (81 collisions against 1.62 expected) and finds none with X.

3. Ranking criterion. Classical selection criteria (worst-case figure of merit, harmonic score) fail when some dimensions are structurally bad. The paper proposes a weighted geometric mean, justified by a social-choice characterization (normalization-invariant, independent of the other candidates).

4. Search and recommendation. More than 52 million candidates are searched for nine configurations. Safe-prime moduli are proven prime, and multipliers are suggested for 64–256 bits of state. The recommended generator is MWC192X (about 0.5 ns/output, period ~2^191, jump functions).

5. Errata. The paper corrects three errors in Goresky–Klapper: the carry formula, the sign in the exponential representation, and three parameter sets without maximal period, with the original author confirming these.

Methodological Rigor

The mathematics is clean, with complete proofs and a self-contained b-adic presentation. The bounds are validated against exhaustive or large searches. Figures of merit are cross-checked with two independent lattice tools (LatticeTester and fplll). Primality is certified with APR-CL, and the experiments include a clever large-scale birthday-spacings test. The benchmarks are carefully designed: fixed frequency, two compilers, the harness of Blackman–Vigna, and an explanation via dependency chains.

The main weaknesses concern the claims about X:

Potential Impact

The direct audience is PRNG designers and library maintainers (Erlang/OTP already ships a related generator; the author's prng.di.unimi.it is widely used). The practical outputs, concrete multipliers and code, are immediately usable. The theoretical result settles a long-standing folk observation about weak triples in MWC generators with a clean, tight bound. Because the bound is independent of lag, the earlier intuition that a larger lag fixes the defect is corrected. The geometric-mean selection principle is transferable to any multiplier search with heterogeneous figures of merit, including LCG/MCG work. The scope is nonetheless niche: PRNGs for simulation and software, and not cryptography. MWC192X competes with xoshiro, PCG, and SFC64, so adoption is plausible but not certain.

Timeliness

64-bit hardware with fast 128-bit multiplication makes MWC attractive, and there is continued interest in fast, jumpable, high-quality generators. Statistical test suites have limited power against lattice structure at 64-bit moduli, a point the paper makes concretely. The correction of literature errors is useful for anyone implementing GMWC from Goresky–Klapper.

Strengths

Limitations

Overall

This is a solid, careful contribution in a specialized area. It will likely be cited by PRNG practitioners and in follow-up lattice and spectral-test work, but it is unlikely to reshape a broad field.

```json

{

"score": 6.5,

"score_reason": "Rigorous, tight theory plus ready-to-use generators and errata, but confined to a niche area and with the key scrambler claim resting on empirical testing.",

"significance": 6.0,

"significance_reason": "Gives practitioners a vetted fast jumpable generator (MWC192X) and settles the MWC lattice-defect question, but the audience is the PRNG subcommunity.",

"rigor": 8.0,

"rigor_reason": "Complete proofs, tight bounds verified against 52M-candidate searches, dual-tool cross-checks, certified primality, and careful benchmarking; scrambler efficacy lacks theory and PractRand coverage is partial.",

"novelty": 6.0,

"novelty_reason": "The explicit, lag-independent bound on ν_{k+2}, the generalized scrambler X, and the normalization-invariant geometric-mean criterion are new angles, though built on existing lattice and carry-generator frameworks.",

"clarity": 7.0,

"clarity_reason": "Well-structured with explicit propositions and a self-contained b-adic exposition, though dense, with heavy notation and cross-references.",

"difficulty": 7.5,

"difficulty_reason": "Requires lattice theory, Hermite constants, b-adic arithmetic, number theory, and low-level performance and test engineering.",

"surprisingness": 4.5,

"surprisingness_reason": "The defect was suspected, but its lag independence and tightness, and the full removal of the defect at 3 TB scale by a one-instruction xor, are moderately unexpected.",

"reproducibility": 8.5,

"reproducibility_reason": "Full C code, multipliers, search details, tools (NTL, LatticeTester, fplll), published candidate data, and a test crate are provided; hardware-specific timings are the main variability.",

"translational_potential": 6.0,

"translational_potential_reason": "Drop-in generators already partly adopted (Erlang/OTP mwc59, author's library), though they compete with entrenched PRNGs and are not cryptographic.",

"evidence_strength": 7.0,

"evidence_strength_reason": "The theoretical claims are proven and the defect and its removal are demonstrated at massive scale, but the 'passes all tests' claim for X is only partially tested across generators.",

"generalisability": 5.0,

"generalisability_reason": "Results cover the whole (G)MWC family across bases 2^32/2^64 and lags 1–3, but the scrambler's effect is empirical and specific to the tested multipliers.",

"interdisciplinarity": 3.0,

"interdisciplinarity_reason": "Mostly relevant to PRNG/simulation, with some links to number theory, lattice computation, and a social-choice-based ranking argument.",

"refutation_value": 3.0,

"refutation_value_reason": "Corrects specific errors in Goresky–Klapper and qualifies the belief that larger lags or classical criteria suffice, but contests no central result.",

"replication_value": 1.5,

"replication_value_reason": "Confirms Thomas's observation of failing triples for 32-bit MWC and re-verifies some prior parameters, but is not framed as a replication.",

"resource_intensity": 4.0,

"resource_intensity_reason": "Requires large multiplier searches and terabyte-scale birthday-spacings tests plus 32 TB PractRand runs, but is feasible for a single well-equipped group.",

"foundationality": 5.0,

"foundationality_reason": "The bounds, scrambler X, geometric-mean criterion, and multiplier tables are reusable building blocks for later generator designs, though the paper is largely a self-contained design."

}

```