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

Question

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)$.

Answer 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.

Answer 2

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.