4
$\begingroup$

Problem. Given positive integers $a$ and $b$, obtain $\frac{a}{b}$ without using division ($/$) directly, though addition ($+$), subtraction ($-$), multiplication ($\times$) and bit-shifts ($\gg$ and $\ll$) are allowed.


Is there a good algorithm to solve the aforementioned problem? This algorithm does not have to be very accurate and $4$ decimal places would be good enough, e.g.,

$$\frac{222}{103} \approx 2.1553$$

Could anyone please give some advice or references?

$\endgroup$
8
  • 4
    $\begingroup$ en.wikipedia.org/wiki/Division_algorithm $\endgroup$
    – Joel Reyes Noche
    Jul 23 at 14:07
  • $\begingroup$ several algorithms are at techiedelight.com/… $\endgroup$
    – Carlo Beenakker
    Jul 24 at 15:16
  • $\begingroup$ let the task be to determine the bit-sequence of $\frac{n}{d}$, then the way to go is to first left-shift $n$ by a sufficiently high value $k$ so we can work in integer arithmetic. The position of the first 1-bit of the result is given by $\max(m): d\cdot 2^m \le n\cdot 2^k$. After having determined the next 1-bit of the result, set $n:=n-d\cdot 2^m$ for finding the next 1-bit. Finally undo the initial left-shifts. $\endgroup$
    – Manfred Weis
    Jul 24 at 16:31
  • $\begingroup$ Are you allowed to compute $x\mod 2$? $\endgroup$
    – nir shahar
    Jul 24 at 17:49
  • $\begingroup$ @nirshahar Since shifts and subtraction are allowed and operands are positive, x mod 2 = x - ((x >> 1) << 1). $\endgroup$
    – njuffa
    Jul 24 at 19:11
5
$\begingroup$

Newton's method is pretty good for this. Specifically, a good strategy is to first calculate an approximation $x \approx \dfrac{1}{b}$ so that $ax$ is then a good approximation for $\dfrac{a}{b}$. To do this, we will use Newton's method to approximate a root of the function $f(x) = \dfrac{1}{x} - b$.

Newton's method asks us to recursively calculate approximations $x_n$ given by the formula $$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$ A priori, this looks like using division but since $f'(x) = \dfrac{-1}{x^2}$, the formula boils down to $$x_{n+1} = x_n + x_n^2\left(\frac{1}{x_n} - b\right) = x_n + (x_n - bx_n^2) = (2 - bx_n)x_n,\tag{$*$}$$ which only involves addition and multiplication.

In order to ensure good convergence of this method, it helps to have $b$ very close to $1$. Of course, there are very few integers that are close to $1$. However, if $b$ is an $n$-bit integer then $b_0 = \dfrac{b}{2^{n-1}}$ is between $1$ and $2$. Since the denominator is a power of $2$ this is really just a bit shift and not a division per se. Incorporating this in the formula ($*$) we obtain the iteration $$ x_{n+1} = (2 - b_0x_n)x_n = \left(2 - \frac{bx_n}{2^{n-1}}\right)x_n = \frac{(2^n - bx_n)x_n}{2^{n-1}} \tag{$\dagger$}$$ which still involves no division. Note that this gives a method for approximating $1/b_0$ but we can recover a good approximation to $\dfrac{1}{b} = \dfrac{1/b_0}{2^{n-1}}$ by shifting.

Further analysis shows that, starting with $x_0 = 0.75$, the absolute error $\varepsilon_n = \left|x_n - \dfrac{2^{n-1}}{b}\right|$ for $(\dagger)$ satisfies $\varepsilon_{n+1} \leq \varepsilon_n^2$. So the number of correct bits doubles at each step!

Let's illustrate by approximating $22/7$. Then $n=3$ and $b_0 = 7/4 = 1.75$. Then $(\dagger)$ gives the approximations $$\begin{aligned} x_0 &= 0.750\,000\,000 \\ x_1 &= 0.515\,625\,000 \\ x_2 &= 0.565\,979\,004 \\ x_3 &= 0.571\,376\,600 \\ x_4 &= 0.571\,428\,567 \\ x_5 &= 0.571\,428\,571 \\ \end{aligned}$$ All the digits shown for $x_5$ are exact for $$ \frac{1}{b_0} = \frac{4}{7} = 0.571\,428\,571\,428\,571\,428\,571\,428\ldots $$ Thus $$ \frac{22x_5}{4} = 3.142\,857\,141 $$ is a good approximation to $$ \frac{22}{7} = 3.142\,857\,142\,857\,142\,857\,142\,857\ldots $$

$\endgroup$
2
$\begingroup$

There certainly are division algorithms around, check e.g. Knuth's "Seminumerical Algorithms" or the book describing how libtommath works (this library was written more to explain how to do things than for utmost speed).

With today's machines, where the speed is more limited by memory access than computation as such, brilliant hacks like the fast inverse square root are (fortunately) not in much demand anymore.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy