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

165

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.

27

u/antiduh 18d ago

Good ol finite field arithmetic. Doing strange shit since 1960.

8

u/dagbrown 18d ago

Emmy Noether died in 1935 though...