# Complexity of division

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

• 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. – Yuval Filmus May 14 '16 at 23:04
• 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. – Yuval Filmus May 14 '16 at 23:06

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))$.
• 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". – Ecir Hana May 15 '16 at 9:12