2

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

Kelly Bundy
  • 23,480
  • 7
  • 29
  • 65
  • 2
    @EricPostpischil The technique is frequently used (for ints) in *programming*. I also know it from studying mathematics, but I've mostly *used* it in *programming*. I mean, in math I don't even have the problem of intermediate numbers getting "too big". But in coding it's an issue, for fixed-size ints because of overflow, and for arbitrary-size ints because of efficiency. Neither are math issues. Also, given how many people got this wrong (see the question's last paragraph), I do think it's useful to point that out as a question here and an answer would also be useful. – Kelly Bundy May 31 '22 at 21:03
  • 1
    If all questions, where somebody did something wrong, were closed, there would not be many left. Why not keep it as warning with a good answer explaining the issue? – Sebastian May 31 '22 at 21:20

1 Answers1

3

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

Kelly Bundy
  • 23,480
  • 7
  • 29
  • 65