Modular Arithmetic That Doesn't Overflow
In short: a % m is the remainder after dividing a by m, and it always
lands in [0, m) in Python — negatives wrap around to the top of the
range instead of going below zero. Other languages (C, Java, JavaScript)
truncate toward zero instead, so a negative a gives a negative remainder
there. For a running total, mod after every add or multiply, not once at
the end — the in-between value can overflow in other languages, and even in
Python it just gets slower to work with as it grows into a giant integer.
Spreading load across shards
Quarry assigns a record to one of shard_count shards with
record_id % shard_count. Record ids are usually positive, but a signed hash
or a delta between two ids can go negative — and that's where languages
disagree.
In Python this is always a safe shard index. Port the same formula to C,
Java or JavaScript and -3 % 8 comes back -3 — a negative array index,
which crashes or silently reads the wrong shard. Rule: if a value can go
negative, normalize it yourself: ((x % m) + m) % m works the same in every
language, because it adds one more m before the final mod, and a value
already in range is unaffected.
def safe_mod(x, m):
return ((x % m) + m) % m
print(safe_mod(-3, 8), safe_mod(11, 8), safe_mod(-16, 8))Hour arithmetic on a 24-hour clock
A scheduler adds a duration to a start hour and wants the hour it lands on, on a 24-hour clock. "3 hours before midnight" should land at 21, not -3.
Walk a token around the clock, one delta at a time — this is the same
(pos + delta) % m formula, applied repeatedly instead of once:
Step through it: 9 + 5 = 14, wraps to 2. 2 - 3 = -1, wraps to 11.
11 + 100 = 111, wraps all the way around to 3 — you never need to
subtract m by hand and count how many times it wraps; % already did that
in one step. 3 - 1 = 2.
Keeping a hash from overflowing
Quarry's hash kernel folds a string into one number by repeatedly doing
h = h * base + code_of_char. Left alone, h grows by roughly one digit per
character — a 1,000-character string produces a number with hundreds of
digits. Mod every step, not just the return value, and h never leaves
[0, mod):
def digits_without_modding(s, base):
h = 0
for ch in s:
h = h * base + ord(ch) # no % here — h just keeps growing
return len(str(h))
print(digits_without_modding("a" * 500, 131) > 1000)In C or Java, h * base would silently overflow a 64-bit integer for a
string like this and give a wrong number outright — modding every step is
what keeps every intermediate value small enough to multiply safely.
Why % disagrees between languages
Python's % always returns a result with the same sign as the divisor
(floored division): -7 % 3 is 2, because -7 = -3*3 + 2. C, Java and
JavaScript's % returns a result with the same sign as the dividend
(truncated division): -7 % 3 is -1, because -7 = -2*3 + (-1). Same
inputs, different answers — and it's a real source of bugs when porting a
formula between languages.
What it costs
| operation | cost | why |
|---|---|---|
(a + b) % m |
O(1) | one add, one mod |
(a * b) % m |
O(1) in Python (big ints); O(1) but can overflow in fixed-width languages | mod every step, not at the end |
| normalizing a possibly-negative value | O(1) | ((x % m) + m) % m |
| folding a length-n string into a hash | O(n) | one multiply-add-mod per character |
Quick practice
print(-1 % 5, 1 % -5, -1 % -5)def shard_for(record_id, shard_count):
return record_id % shard_count
print(shard_for(-3, 8), shard_for(-3, 8) - 8)🎯 Your turn
Build poly_hash(s, base, mod): fold a string into one number with
h = (h * base + ord(ch)) % mod, modding after every character, left to
right, starting from h = 0.
poly_hash("", 131, 1000000007)→0poly_hash("a", 131, 1000000007)→97poly_hash("abc", 131, 1000000007)→1677554
Hint: one loop, one running total, % mod inside the loop on every
iteration — never after it.
Press ▶ Run, then ✓ Check.