4
$\begingroup$

The article Computational complexity of mathematical operations mentions that the complexity of division in $O(M(n))$, and that "$M(n)$ below stands in for the complexity of the chosen multiplication algorithm".

But I'm not sure how to read that $M(n)$ embedded in $O(M(n))$: does it mean that the division has the same complexity as multiplication?

If I use, say, Karatsuba multiplication algorithm, will the division also take $O(n^{1.585})$

$\endgroup$
  • $\begingroup$ Wikipedia is being sloppy. You can do approximate division in time $O(M(n))$, using Newton's method or Goldschmidt's method. But for exact division, you will need do super-constant amount of multiplications. Wikipedia doesn't give any source in this case, and I would consider it unreliable. $\endgroup$ – Yuval Filmus May 14 '16 at 23:04
  • 1
    $\begingroup$ The notation $O(M(n))$ means that if you can multiply integers in time $M(n)$, then you can divide them in $CM(n)$ for some universal constant $C$. This is sloppy not only for the reason stated above, but also because, as far as I understand, the reduction from division to multiplication doesn't use $n$-bit integers; so we are making some assumptions on $M(n)$ to handle this subtlety. $\endgroup$ – Yuval Filmus May 14 '16 at 23:06
5
$\begingroup$

The paper

Torbjörn Granlund and Peter L. Montgomery; "Division by Invariant Integers using Multiplication", Proceedings of the ACM SIGPLAN '94 conference on Programming Language Design and Implementation (PLDI):61-72, 1994.

gives the method used, in practice, to calculate (exact) integer division by producing an appropriate reciprocal (accurate to $n$ bits) of the divisor and also a shift amount. The division is then done by multiplying the dividend by the reciprocal and shifting.

The reciprocal can be found by Newton's method or Goldschmidt's method, as @Yuval stated in the comments. Those methods produce the reciprocal accurate to $n$ bits in $O(\log n)$ iterations. Each iteration requires a constant number of multiplications, and once you have the reciprocal you need one more multiplication to multiply the reciprocal by the dividend.

As pointed out by @gnasher729 in the comments, however, you don't need to do each iteration with full precision. Newton's iteration doubles the number of useful digits each iteration. So you can use, for example, 32 bit multiplies in the firsts iteration, 64 bit multiplies in the second, etc. Since that's a geometric sum it sums to a constant and you get $O(M(n))$.

$\endgroup$
  • 1
    $\begingroup$ So I did a bit more digging, and the paper Asymptotically fast division for GMP says "Until version 4.2.1, GNU MP (GMP for short) division has complexity $O(M(n) log n)$, which is not asymptotically optimal. We propose here some division algorithms that achieve $O(M(n))$ with small constants". $\endgroup$ – Ecir Hana May 15 '16 at 9:12
  • 1
    $\begingroup$ You need O (log n) iterations, but you don't need to do them with full precision. Calculate 1/n with 32 bit precision, then use Newton's method to get 64 bit, then 128 bit (using 128 bit arithmetic), then 256 bit (using 256 bit arithmetic) etc. The last iteration takes M(n), the second to last M(n/2), the one before M(n/4) etc. So the execution time is only 2 M(n), very roughly, not log n * M(n), even if M(n) is linear. I think Knuth mentioned that already. $\endgroup$ – gnasher729 Oct 3 '17 at 19:36

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.