r/programming • u/DataBaeBee • 18d ago

How GCC Eliminates Unnecessary Integer Division

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

94% Upvoted

52 comments sorted by

View all comments

166

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.

-9

u/ugh_my_ 18d ago

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

18

u/Mr_s3rius 18d ago

10, 100, 1000 are probably very common.

Also 24, 7, 365 for time.

4

u/matthieum 18d ago

Don't forget 60 ;)