# Dividing by Multiplying

Every divisor has a magic number, and most have more than one! A magic number for

dis nothing more than a precomputed quotient: a power of 2 divided bydand then rounded up. At runtime, we do the same thing, except backwards: multiply by this magic number and then divide by the power of 2, rounding down. The tricky part is finding a power big enough that the “rounding up” part doesn’t hurt anything. If we are lucky, a multiple ofdwill happen to be only slightly larger than a power of 2, so rounding up doesn’t change much and our magic number will fit in 32 bits. If we are unlucky, well, we can always fall back to a 33 bit number, which is almost as efficient.

## 1 Comment

Stay up-to-date by subscribing to the Comments RSS Feed for this post.

[…] Previously: Dividing by Multiplying. […]