# Why integer division is of equal complexity as multiplication

I am trying to understand the fact that integer division is no more difficult than integer multiplication. I found some references - here and this lecture note. Wikipedia says if there is a way to multiply integers in time M(n), then we can divide them in CM(n). When I think of division a/b as finding integers d and r such that a = bd + r, then this above fact somehow aligns with my intuition. But I could not find any way to mathematically prove this. Although the lecture note has proof, but I am not able to understand. Can anybody please give me a simple mathematical proof or any idea how to do it?

The wikipedia page suggests using Newton-Raphson Division to get $$O(M(n))$$.

The way Newton-Raphson Division works is by finding the solution $$x$$ of $$\frac{1}{x}-b=0$$ (so that $$x=1/b$$), and then returning $$ax$$.

A Newton-Raphson iteration in general is

$$x_{i+1} = x_i - \frac{f(x_i)}{f'(x_i)}.$$

In this case $$f(x)=\frac{1}{x}-b$$ and $$f'(x)=\frac{-1}{x^2}$$, so the iteration works out to

$$x_{i+1} = x_i(2-bx_i),$$ which takes 2 multiplications per iteration.

Given a good enough starting guess, $$x_0$$, Newton-Raphson is guaranteed to double the number of accurate bits per iteration, so needs to be run for $$O(\log n)$$ iterations for $$n$$ bits of accuracy.

All of the above is for real $$x$$. To make it work for integers the trick is to actually calculate $$x=\frac{2^n}{b}$$ instead of $$x=\frac{1}{b}$$, which (with a little bit of "normalization") lets you do all the arithmetic with integer multiplies, subtracts, and shifts.

And now how you do it in the same time as multiplication:

Say you want a 1024 bit result, and you have 16 correct bits.

You do one iteration step with 32 bit precision, getting a 32 bit result. Then you do an iteration with 64 bit precision, then 128 bits, then 256 bits, then 512, then 1024.

So the cost isn’t M(n) every time, it’s M(n/64), M(n/32), ..., M(n/2), M(n). Adding up to 2M(n).

• It should be noted that $O( D(n) ) = ( M(n/64) + .... + M(n) )$ isn't equivalent to $O( M(n) )$ for every function M(n). It is indeed $O( M(n) )$ if $M(n)$ grows at least linearly (that is, if $M(n) = \Omega(n)$ then $D(n)$ roughly grows as quickly as $M(n)$); however it is $o(n)$ if $M(n)$ is sublinear (then $M(n)$ grows assymp. faster). In this case, we know M(n) must be at least linear (indeed in CS complexity is usually at least linear due to input), so all is well. – Real Nov 27 at 13:12