# Division by a constant

After skimming Multiplication by a Constant is Sublinear (PDF), (slides (PDF), slides with notes (PDF)) I was wondering if this could be extended to division by a constant in sublinear time?

Additionally, what about division with a constant numerator, ie. "division of a constant"?

## 1 Answer

Division by a constant can always be recast as multiplication by a constant followed by a shift. The relevant papers are:

Robert Alverson, "Integer Division Using Reciprocals," IEEE Int'l Symp Comp Arithmetic, (ISCA-10):186-190, 1991.

Torbjörn Granlund and Peter L. Montgomery, "Division by Invariant Integers using Multiplication," ACM Conf on Prog Lang Dsgn and Impl, (PLDI-1994):61-72.

Daniel J. Magenheimer, Liz Peters, Karl W. Peters, and Dan Zuras, "Integer Multiplication and Division on the HP Precision Architecture," IEEE T. Comp., 37(8):980-990, August 1988.

• Cool, I'll take a look at those. Any ideas for division of a constant? – Realz Slaw Oct 9 '13 at 17:51
• It's been a long time since I read any of these, but if I remember correctly the Granlund and Montgomery paper gives the algorithm for calculating the reciprocal. When dividing by a constant you move the cost of calculating the reciprocal to compile time, when dividing anything by a variable you have to calculate the reciprocal dynamically. Which is pretty expensive: I wrote a routine to do this on a MIPS-like 32-bit processor about 15 years ago and it took about 55 cycles. – Wandering Logic Oct 9 '13 at 18:42