Why integer division is of equal complexity as multiplication

Question

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?

Answer 1

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