5
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Real Nov 27 at 13:12

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.