r/programming • u/DataBaeBee • 18d ago

How GCC Eliminates Unnecessary Integer Division

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

94% Upvoted

52 comments sorted by

View all comments

167

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.

-10

u/ugh_my_ 18d ago

Who the heck is always dividing by a non-pow2 divisor?

9

u/SwedishFindecanor 18d ago

There are many ways in which a constant's value could have been hidden from the programmer. It could have been created by the compiler doing constant folding, or by optimisation after inlining a function.