3
$\begingroup$

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

$\endgroup$
4
+50
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)... $\endgroup$ – gen Mar 18 at 21:17
  • $\begingroup$ 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. $\endgroup$ – Pseudonym Mar 21 at 0:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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