{"id":108971,"date":"2023-11-06T07:00:00","date_gmt":"2023-11-06T15:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=108971"},"modified":"2023-11-06T07:10:15","modified_gmt":"2023-11-06T15:10:15","slug":"20231106-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20231106-00\/?p=108971","title":{"rendered":"Why doesn’t reduction by modulo work for floating point values?"},"content":{"rendered":"

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.<\/p>\n

uint32_t MultiplyMod10(uint32_t a, uint32_t b)\r\n{\r\n    \/\/ Na\u00efve version: Overflow danger\r\n    return (a * b) % 10;\r\n\r\n    \/\/ Reduce modulo 10 after each step.\r\n    return ((a % 10) * (b % 10)) % 10;\r\n}\r\n<\/pre>\n
But this trick doesn’t work for floating point values.<\/p>\n
constexpr double TwoPi = 6.2831853071795864769252867665590058L;\r\n\r\ndouble MultiplyModulo2Pi(double a, double b)\r\n{\r\n    \/\/ Na\u00efve version gives correct answer\r\n    return fmod(a * b, TwoPi);\r\n\r\n    \/\/ But this gives the wrong answer\r\n    return fmod(fmod(a, TwoPi) * fmod(b, TwoPi), TwoPi);\r\n}\r\n<\/pre>\n
For example, trying to calculate 7.5 \u00d7 10 mod 2\u03c0<\/var> using the na\u00efve formula gives the correct value of 75 mod 2\u03c0<\/var> \u2248 5.8850. But using the alternate formula gives the incorrect value of (1.2168 \u00d7 3.7168) mod 2\u03c0<\/var> \u2248 4.5227.<\/p>\n
A simpler demonstration of this problem is calculating (\u00bd \u00d7 2) mod 2. The na\u00efve version gives you the correct 1 mod 2 = 1. The flawed incorrect version gives you (\u00bd mod 2) (2 mod 2) mod 2 = (\u00bd \u00d7 0) mod 2 = 0 mod 2 = 0.<\/p>\n
What’s going on? Is math broken?<\/p>\n
Math is not broken. Your expectations are broken.<\/p>\n
Let’s see why the integer modulo technique works.<\/p>\n
a<\/var> mod n<\/var> = c<\/var> means that a<\/var> = c<\/var> + k<\/var>n<\/var> for some integer k<\/var>.<\/p>\n
Therefore<\/p>\n
(a<\/var> mod n<\/var>) (b<\/var> mod n<\/var>) =
\n(c<\/var>\u2081 + k<\/var>\u2081n<\/var>) (c<\/var>\u2082 + k<\/var>\u2082n<\/var>) =
\nc<\/var>\u2081c<\/var>\u2082 + c<\/var>\u2081k<\/var>\u2082n<\/var> + c<\/var>\u2082k<\/var>\u2081n<\/var> + k<\/var>\u2081k<\/var>\u2082n<\/var>\u00b2 =
\nc<\/var>\u2081c<\/var>\u2082 + (c<\/var>\u2081k<\/var>\u2082 + c<\/var>\u2082k<\/var>\u2081 + k<\/var>\u2081k<\/var>\u2082n<\/var>)n<\/var> =
\nc<\/var>\u2081c<\/var>\u2082 + k<\/var>\u2083n<\/var>, where k<\/var>\u2083 = c<\/var>\u2081k<\/var>\u2082 + c<\/var>\u2082k<\/var>\u2081 + k<\/var>\u2081k<\/var>\u2082n<\/var>.<\/p>\n
If a<\/var>, b<\/var>, and n<\/var> are all integers, then so too will be c<\/var>\u2081k<\/var>\u2082 + c<\/var>\u2082k<\/var>\u2081 + k<\/var>\u2081k<\/var>\u2082n<\/var>, and the final expression shows that then (a<\/var> mod n<\/var>) (b<\/var> mod n<\/var>) mod n<\/var> = a<\/var>b<\/var> mod n<\/var>.<\/p>\n
But if a<\/var>, b<\/var>, and n<\/var> are not all integers, then that expression for k<\/var>\u2083 might not end up being an integer, and then the conclusion breaks down.<\/p>\n
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.<\/p>\n
Bonus chatter<\/b>: Mathematically, the modulus operation is a ring homomorphism from the ring of integers to the ring of integers modulo n<\/var>. Ring operations are addition, subtraction, and multiplication. Note that the trick doesn’t work with division: (2 \u00f7 2) mod 2 = 1 mod 2 = 1, but ((2 mod 2) \u00f7 (2 mod 2)) mod 2 = (0 \u00f7 0) mod 2 = nonsense.<\/p>\n","protected":false},"excerpt":{"rendered":"
Working out why it works for integers and seeing what goes wrong.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[26],"class_list":["post-108971","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-other"],"acf":[],"blog_post_summary":"
Working out why it works for integers and seeing what goes wrong.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/108971","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=108971"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/108971\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=108971"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=108971"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=108971"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}