It is commonly known that if you want to perform a calculation modulo an integer, you can apply the modulo operation at each step of the calculation, instead of carrying a huge value and then reducing it at the end.
uint32_t MultiplyMod10(uint32_t a, uint32_t b) { // Naïve version: Overflow danger return (a * b) % 10; // Reduce modulo 10 after each step. return ((a % 10) * (b % 10)) % 10; }
But this trick doesn’t work for floating point values.
constexpr double TwoPi = 6.2831853071795864769252867665590058L; double MultiplyModulo2Pi(double a, double b) { // Naïve version gives correct answer return fmod(a * b, TwoPi); // But this gives the wrong answer return fmod(fmod(a, TwoPi) * fmod(b, TwoPi), TwoPi); }
For example, trying to calculate 7.5 × 10 mod 2π using the naïve formula gives the correct value of 75 mod 2π ≈ 5.8850. But using the alternate formula gives the incorrect value of (1.2168 × 3.7168) mod 2π ≈ 4.5227.
A simpler demonstration of this problem is calculating (½ × 2) mod 2. The naïve version gives you the correct 1 mod 2 = 1. The flawed incorrect version gives you (½ mod 2) (2 mod 2) mod 2 = (½ × 0) mod 2 = 0 mod 2 = 0.
What’s going on? Is math broken?
Math is not broken. Your expectations are broken.
Let’s see why the integer modulo technique works.
a mod n = c means that a = c + kn for some integer k.
Therefore
(a mod n) (b mod n) =
(c₁ + k₁n) (c₂ + k₂n) =
c₁c₂ + c₁k₂n + c₂k₁n + k₁k₂n² =
c₁c₂ + (c₁k₂ + c₂k₁ + k₁k₂n)n =
c₁c₂ + k₃n, where k₃ = c₁k₂ + c₂k₁ + k₁k₂n.
If a, b, and n are all integers, then so too will be c₁k₂ + c₂k₁ + k₁k₂n, and the final expression shows that then (a mod n) (b mod n) mod n = ab mod n.
But if a, b, and n are not all integers, then that expression for k₃ might not end up being an integer, and then the conclusion breaks down.
In other words, taking the modulus after each operation works with integers because the trick relies on the fact that adding and multiplying integers produces another integer. Once you throw floating point values into the formula, the end result is not guaranteed to be an integer any more.
Bonus chatter: Mathematically, the modulus operation is a ring homomorphism from the ring of integers to the ring of integers modulo n. Ring operations are addition, subtraction, and multiplication. Note that the trick doesn’t work with division: (2 ÷ 2) mod 2 = 1 mod 2 = 1, but ((2 mod 2) ÷ (2 mod 2)) mod 2 = (0 ÷ 0) mod 2 = nonsense.
On the other hand, in the unlikely event that you know the integer division is going to be exact, and the divisor has an inverse with respect to the base, then you can just multiply by its multiplicative inverse instead.
On the other hand, “modulo after each step” does work if you only do addition and subtraction (formally, the quotient of abelian groups R/cZ is nontrivial).
(I’m sure you know this, but it’s never explicitly stated for the readers.)
True. This article was more to address people who blindly apply the “take mod after each step” rule and then are surprised when it doesn’t work!