Floating point modulo *completely* "wrong"

Question

I don't mean a tiny precision error, I mean a completely "wrong" result, for a harmless-looking calculation:

expected: 1.7306687640440686
got:      0.08453630115074517

The calculation (Try it online!):

from math import pi

a = 60.9
mod = 2 * pi

print('expected:', a**2 % mod)
print('got:     ', (a % mod)**2 % mod)

The second calculation above uses a % mod before squaring. With integers, when we want to modulo at the end anyway, such early modulos are a well-known and often-used way to keep intermediate results small (to avoid overflow of fixed-size ints or slowness of arbitrary-size ints). With floats, I expected a small precision error but got entirely different results. Even for the above example of moduloing before a simple squaring.

Why do I get a completely "wrong" number with floats, when the same technique works perfectly for ints?

Writing "wrong" in quotes because most certainly it's my expectation that's wrong, not the result. Though apparently I'm not the only one with that expectation (which is why I found it useful enough to point out as question and hopefully an answer): This came from another question's comment suggesting to "implement your own fast exponentiation with modulo in each iteration", which got five upvotes, two answers implementing that, four upvotes for those answers, and nobody batted an eye about this severe issue even though people did point out precision worries about it (which don't even matter). (I also tried it, utterly failed, even for small exponents, and my above snippet is what I reduced / tracked down the problem to).

user_12671057 · Answer

Indeed the result is mathematically correct (except for a tiny precision error of course which the floats do have). It's just wrong to use an early modulo on floats like that, expecting it to stay mathematically equivalent to only doing one final modulo later.

When we do an early a % m, we subtract a multiple of the modulus m. That is, we get a - mq with some integer q. Squaring that gives:

  (a - mq)²
= a² - 2amq + (mq)²
= a² - m(2aq - mq²)

That differs from a² by m(2aq - mq²), which is not a multiple of m, unless 2aq - mq² happens to be an integer. And that's just not the case here, as both a = 60.9 and m = 2π aren't integers.

So unlike when doing this with integers, such an "early modulo" with floats to "keep intermediate results small" is not compatible with an overall final modulo (which does subtract a multiple of the modulus).

(This answer is based on someone's comment that had pointed out the essence of this.)

Floating point modulo completely "wrong"

1 Answers