Cheap and Secure Web Hosting Provider : See Now

[Solved]: Division by a constant

, , No Comments
Problem Detail: 

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

Asked By : Realz Slaw

Answered By : Wandering Logic

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback