A teammate proposes swapping the 1e9+7 modulus for a prime near 1e18. What breaks, and what would you say?
answer
- what does multiplying two residues cost?
- the accumulator has a fixed width
- square the modulus, then count bits
- the conventional modulus sits under 2^30
- a modulus may occupy half the accumulator
basics
~20 sFixed-width multiplication breaks. Two residues below 10^18 multiply to about 10^36, roughly 120 bits, which silently wraps a 64-bit accumulator. The conventional modulus is prime and sits just under 2^30 precisely so the squared product still fits.
solid answer
~50 sThe proposal trades a working multiply for a property nobody asked for. Reducing modulo `m` bounds each operand at `m - 1`, so a multiply-based pipeline needs an accumulator that holds `(m-1)^2`. With `m` near `10^9` that is under `10^18`, safely inside a 64-bit signed range; with `m` near `10^18` it is about `10^36`, roughly 120 bits, which wraps silently and corrupts every product. Adding is fine either way — sums need only one extra bit — so if the pipeline never multiplies, the objection weakens considerably. If a wider modulus is genuinely required for collision resistance, the honest answer is that you now need a double-width multiply path: a 128-bit intermediate where the platform offers one, a split-operand multiply, or Montgomery reduction. Each costs cycles and portability, so make it a deliberate decision with a benchmark, not a one-line constant change.
go deeper
Know that the conventional modulus is prime and roughly a billion, and that these choices are deliberate rather than arbitrary. Do not change such a constant without understanding what depends on it.
Explain the width budget: two residues multiply to nearly the modulus squared, so the modulus can occupy at most half the accumulator's bits. Derive the 2^30 ceiling for a 64-bit accumulator on the spot.
Run the calculation live, name the silent-wrap failure that passes small tests, and separate the counting motive from the collision-resistance motive before accepting or rejecting the change.
Own the decision with its costs attached: a wide modulus buys output space and charges a double-width multiply path in cycles, portability and reviewability. Offer the paired-moduli alternative and require a benchmark before the arithmetic anyone can reason about is traded away.
## What the constant is actually chosen for `1000000007` looks arbitrary and is not. Two properties are doing the work. **It is prime.** Every nonzero residue modulo a prime has a multiplicative inverse, so a pipeline that needs to "divide" — averaging, undoing a factor, binomial coefficients built from factorials — can do it by multiplying with an inverse. A composite modulus leaves some residues uninvertible and, worse, collapses values that share a factor with the modulus into a systematically smaller output range. **It sits just under 2^30.** `2^30` is about `1.07 * 10^9`, so every residue fits in 30 bits. That single fact drives everything downstream: a sum of two residues needs 31 bits, and — the binding constraint — a *product* of two residues needs at most 60 bits, which fits a 64-bit accumulator with several bits of headroom for an add-then-reduce step. The modulus was picked to make fixed-width modular multiplication safe and unremarkable. ## Doing the arithmetic on the proposal The rule to internalize: in a multiply-based modular pipeline, the accumulator must hold `(m-1)^2`. Equivalently, `m` may occupy at most half the accumulator's bits. - 64-bit signed accumulator: roughly 63 usable bits, so `m` may be up to about `2^31`. `1000000007` fits with room to spare. - Modulus near `10^18` (about `2^60`): the product needs about 120 bits. A 64-bit accumulator drops more than half of them, silently. So the proposal does not merely reduce headroom — it removes the ability to multiply at all on the existing accumulator. Nothing throws; the numbers just become unrelated to the answer, and small test inputs may still pass if their products happen to stay small. ## Interrogating the motive "Bigger modulus" is usually motivated by collision resistance: if two distinct inputs must rarely share a residue, a larger output space helps. That is a *checksum* motive, and it deserves a real answer rather than dismissal. But it is not a *counting* motive: a combinatorial count reported modulo a prime is a residue either way, and widening the modulus does not make the answer more exact — it does not make it exact at all. So the first question is what the modulus is for. If collision resistance is genuinely the requirement, there are options, and each has a price: - **A double-width intermediate.** Where the platform exposes a 128-bit multiply, this is the cheapest fix, at the cost of portability to platforms that do not. - **Two independent moduli near 2^30.** Carrying a pair of residues gives an effective space near `2^60` while every individual multiply stays a plain 64-bit operation. Twice the state and twice the arithmetic, but no exotic instruction needed. - **Montgomery or Barrett reduction.** Standard techniques for fast modular multiplication with wide moduli, meaningfully more code and more ways to get an edge case wrong. The two-moduli option is often the right recommendation, because it buys the output space without leaving the arithmetic anyone can reason about. ## The conversation, not just the verdict A senior answer separates three things: what the modulus is for (counting versus collision detection), what the accumulator can hold (a bit-width calculation anyone can check), and what it would cost to change (a wider multiply path, benchmarked). The failure mode to name explicitly is that the proposed change is *silent* — no exception, no warning, a fast program producing plausible numbers. That is what makes it a review-blocking issue rather than a preference. It is also worth saying what does *not* argue against a wide modulus. If the pipeline only ever adds and subtracts, the width requirement is roughly `2m` rather than `m^2`, and a modulus near `2^62` would be fine. Objecting reflexively without checking whether a multiply exists is as sloppy as accepting the change without checking. ## The durable takeaway Do not memorize the constant; memorize the derivation. Given an accumulator width `w` bits and a pipeline that multiplies, the largest safe modulus is about `2^(w/2)`. Every other property — primality for inverses, a prime rather than a power of two to avoid structure in the residues — layers on top of that width budget. An engineer who can run that calculation live can pick a modulus for any platform, and can spot the day someone's convenient round constant quietly stopped fitting.
- The team genuinely needs an output space near 2^60 for collision resistance. What do you recommend?Carry two independent moduli near `2^30` instead of one wide one. The pair gives an effective space near `2^60`, while every individual multiply stays an ordinary fixed-width operation that anyone can reason about. The alternatives — a 128-bit intermediate where the platform offers it, or Montgomery reduction — are faster in state but cost portability or code complexity. Benchmark before choosing.
- Why prime rather than a convenient round modulus like 10^9?Primality gives every nonzero residue a multiplicative inverse, which is what makes division-by-inverse available for averaging or factorial-based counting. A composite modulus also collapses inputs sharing its factors into a systematically restricted output range, which weakens it as a checksum. A power of two is worse still: reduction keeps only the low bits, so any structure in those bits survives untouched.
- Does the objection hold if the pipeline only adds, never multiplies?Much less. A sum of two residues needs only one bit more than the modulus, so an addition-only pipeline could use a modulus near `2^62` in a 64-bit accumulator without trouble. The `m^2` bound is entirely driven by multiplication. Check whether a multiply exists anywhere in the path — including inside an exponentiation or an inverse computation — before objecting.
saying these in an interview costs you the question
- Assumes a larger modulus is automatically safer
- Forgets that a product of residues needs double the width
- Expects a fixed-width multiply to signal overflow
- Thinks a bigger modulus makes counting answers exact
- Picks a power of two as a convenient modulus
- Objects without checking whether the pipeline multiplies