5
$\begingroup$

My favourite algorithm textbook: The Algorithm Design Manual S. Skiena.pdf had this interesting problem:

1-28. [5] Write a function to perform integer division without using either the / or * operators. Find a fast way to do it.

What's the lower bound for asymptotic complexity of this problem? `

P.S: I know repeated subtraction with a will work. It has asymptotic linear complexity with b (case where a = 1). However, repeated subtraction has exponential complexity with $n$ where $n$ is the number of bits needed to represent the number. Specifically it is $\Theta(2^n)$. So it is definitely not fast.

$\endgroup$
1
  • 1
    $\begingroup$ It'd be interesting to try implementing Goldschmidt's algorithm and seeing how that goes. $\endgroup$
    – Pseudonym
    Dec 24, 2016 at 2:40

3 Answers 3

9
$\begingroup$

Wikipedia has a nice page about the complexity of mathematical operations, and there is also a dedicated page about division. Asymptotically, division has the same complexity as multiplication. The fastest known algorithm, due to Harvey and van der Hoeven, runs in time $O(n\log n)$. However, this algorithm isn't practical (it is not fast in practice, since the integers aren't large enough). Wikipedia lists no known lower bounds, though some people believe that the complexity should be $\Omega(n\log n)$, and there are some bounds in weak models. See for example Lower Bounds for Multiplication via Network Coding by Afshani, Freksen, Kamma, and Larsen.

$\endgroup$
0
0
$\begingroup$

I believe that the answer the author has in mind is something more in the line of binary long division, which can be "efficiently" implemented with shifts, subtractions and comparisons in $O(W)$ steps where $W$ is the machine word length in bits.

Notice that using bit shifts, which could be interpreted as a way to reintroduce multiplication thru the back door, is not a necessary condition to obtain an algorithm linear in $W$ given that they can in turn be substituted by iterated doubling of the dividend,

const int W = 8*sizeof(int);
int p2w[W];
p2w[0]=p;
for (int w=0; w<W-1; ++w)
    p2w[w+1]=p2w[w]+p2w[w];

which can generate all the necessary elements in the sequence ${2^w p}$ for $0\le w \le W$ also in linear time, at the cost of $O(W)$ extra memory.

We can then divide $q=a/p$ using no more than $O(W)$ operations as follows:

int q=0;
for (int w=W-1; w>=0; --w) {
    q+=q; // same idea as before
    // binary long division
    if (a>p2w[w]) {
        a-=p2w[w];
        ++q;
    }
}

This analysis obviates the complexity and delay of the digital circuits implemented in hardware and assumes addition and the other instructions run in constant time. A more sophisticated analysis could take into account the combined algorithmic+circuit complexity by counting the total number of gates and the cycles necessary to execute the solution, which is similar to the concept of PDP (power-delay product) in electronic engineering.

$\endgroup$
0
$\begingroup$

If you don’t have a multiplication operation, you can implement for example a 64x64 bit product with 63 additions, in constant time. So your asymptotic behaviour doesn’t change.

$\endgroup$

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.