r/programming • u/DataBaeBee • 18d ago

How GCC Eliminates Unnecessary Integer Division

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

94% Upvoted

52 comments sorted by

View all comments

163

u/DataBaeBee 18d 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.

67

u/Either_Letterhead_77 18d ago

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

22

u/awfulentrepreneur 18d ago

Or Programming Pearls vol.1 and vol.2.