# How does the bitlength of the divisor affect the running-time complexity of division algorithms?

Wikipedia lists $$O(M(n))$$ as the best complexity (out of the algorithms listed) for division on two $$n$$-digit numbers, where $$M(n)$$ is the complexity of the multiplication algorithm of choice. This is the complexity of the Newton-Raphson division.

My question is this: what are some of the best known (wrt. running-time complexity as a function of $$n$$) algorithms for division of two numbers, of m, and $$n < m$$ digits respectively? That is, how much complexity can be gained when the two numbers are not assumed to be of the same length?

I wouldn't want to treat $$n$$ as a constant as I'm in particularly interested in the case of $$n \in O(\log{m})$$. So I'm not looking for answers that treat $$n$$ as in $$O(1)$$.

Let $$M(m, n)$$ and $$D(m, n)$$, respectively, be the costs of multiplying and dividing an $$m$$-digit number by an $$n$$-digit number (with $$m \ge n$$). Brent and Zimmermann give the following bounds:

$$(1) \qquad M(m,n) \le \left\lceil \frac{m}{n} \right\rceil M(n)$$ $$(2) \qquad M(m,n) \le M \left( \frac{m+n}{2} \right) (1+ o(1))$$ $$(3) \qquad D(m+n,n) \le O(M(m,n))$$ where $$M(n)$$ is the complexity of balanced $$n$$-digit multiplication.

I am not an expert in this area but I can try to summarize their explanations:

(1) is based on the idea that if $$m = kn$$, you can cut the larger operand into $$k$$ pieces, giving $$M(kn, n) = k M(n) + O(kn)$$.

(2) is based on using an evaluation-interpolation scheme and reducing the unbalanced multiplication to a balanced multiplication of two $$(m+n)/2$$-digit numbers (I realize this is a bit vague, but they don't give much details in this case).

(3) they also don't give a reference in this case; judging from the bound, it may be based on using Newton to compute the reciprocal of the $$n$$-digit number and then multiplication. One unbalanced division algorithm they do discuss explicitly is based on computing $$n$$ digits of the quotient at a time, reducing the division to several $$2n$$ by $$n$$ divisions, each of which is implemented with the recursive division algorithm. However, the latter does not seem to fit the bound (3).

For the details, have a look at Sections 1.3.5, 1.4.3, and the table at the end of their monograph.

Division of m bit numbers by n bit numbers with n ≤ $$N_0$$ for some fixed $$N_0$$ can always be done in O (m).

I think division will work in m * O (log n). Roughly, you calculate 1/n, then you do something like long division doing m / n steps each taking O (n log n) time.

• Tbh making one parameter implicit and discounting it feels a lot like cheating. You might as well say that given $m<n<N_0$ all arithmetic is O(1)... – gen Mar 18 '19 at 21:17
• Think of this answer as essentially saying "long division becomes short division when the divisor is small". Having said that, if $n$ is $O(\log m)$, then in all practical situations, $n$ fits in a constant number of machine words. So it kind of is short division in that case. – Pseudonym Mar 21 '19 at 0:57