6
$\begingroup$

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

$\endgroup$

1 Answer 1

8
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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