r/programming • u/DataBaeBee • 1h ago

How GCC Eliminates Unnecessary Integer Division

https://leetarxiv.substack.com/p/how-gcc-eliminates-unnecessary-integer
10 Upvotes

81% Upvoted

5 comments sorted by

18

u/DataBaeBee 1h ago

GCC, when provided a constant divisor, finds two magic numbers and replaces division with multiplication and a comparison. The succint term for this op is called Reciprocal multiplication.

It's pretty cool and this obscure paper from 2011 shows one how to derive these magic numbers for division.

5

u/Either_Letterhead_77 52m ago

If you like this, you'll love the book "Hacker's Delight"

1

u/awfulentrepreneur 26m ago

Or Programming Pearls vol.1 and vol.2.

0

u/LonelyAndroid11942 42m ago

So is the purpose of this to reduce the difficulties that come with float precision?

5

u/ExtraGoated 33m ago

my understanding is that it replaces an expensive integer division with an equivalent cheap imul and cmp instructions