Why doesn’t reduction by modulo work for floating point values?

Raymond Chen

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.


(a mod n) (b mod n) =
(c₁ + kn) (c₂ + kn) =
cc₂ + ckn + ckn + kkn² =
cc₂ + (ck₂ + ck₁ + kkn)n =
cc₂ + kn, where k₃ = ck₂ + ck₁ + kkn.

If a, b, and n are all integers, then so too will be ck₂ + ck₁ + kkn, 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.


Comments are closed. Login to edit/delete your existing comments

  • Jacob Manaker 1

    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.)

    • Raymond ChenMicrosoft employee 0

      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!

  • Neil Rashbrook 0

    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.

Feedback usabilla icon