patternMinor
Why integer division is of equal complexity as multiplication
Viewed 0 times
whydivisionmultiplicationequalintegercomplexity
Problem
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?
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?
Solution
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).
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).
Context
StackExchange Computer Science Q#104319, answer score: 6
Revisions (0)
No revisions yet.