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"?


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.

  • $\begingroup$ Cool, I'll take a look at those. Any ideas for division of a constant? $\endgroup$ – Realz Slaw Oct 9 '13 at 17:51
  • 2
    $\begingroup$ 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. $\endgroup$ – Wandering Logic Oct 9 '13 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.