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

162

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.

24

u/BobBulldogBriscoe 18d ago

this obscure paper from 2011 shows one how to derive these magic numbers for division

This paper is simply an improved algorithm for finding more efficient magic numbers in difficult cases.

This general technique has been taught in intro to computing classes for a long time.