# Numerical Methods: calculate $b/a$ without division

Calculate $$b/a$$ in a calculator that only adds, subtracts and multiplies.

This problem is in the textbook for my numerical methods class. Obviously you can calculate it by

$$\frac{1}{a} + \frac{1}{a} +\frac{1}{a} + ... \frac{1}{a} + = \frac{b}{a}$$

So the difficulty is in calculating $$1/a$$ without division. I would put my work here except I didn't have any idea on how to solve the problem.

The reciprocal value $$b^{-1}$$ can be computed by applying Newton's method to the non-linear equation $$f(x) = 0$$ where $$f(x) = x^{-1} - b.$$ We have $$x_{n+1} = x_n - \frac{x_n^{-1}-b}{-x_n^{-2}} = x_n + x_n(1-bx_n).$$ We see that no divisions are required to compute $$x_{n+1}$$ in terms of $$x_n$$. Moreover, this expression is of the type $$\text{new approximation} = \text{old approximation} + \text{small correction}.$$ In particular, it is irrelevant if the correction suffers from subtractive cancellation. It remains to choose $$x_0$$. The relative error is given by $$r_n = \frac{b^{-1} - x_n}{b^{-1}} = 1 - bx_n.$$ We have $$1-bx_{n+1} = 1 - b (x_n + x_n(1-bx_n)) = 1 -bx_n - bx_n(1-bx_n) = (1 - bx_n)^2$$ or equivalently $$r_{n+1} = r_n^2.$$ Convergence is assured provided we choose $$x_0$$ such that $$|r_0|^2 < 1$$. This is quite difficult in general, but if $$b > 0$$ is given in base 2, say, $$b = f \times 2^m, \quad x \in [1,2), \quad m \in \mathbb{Z},$$ then $$b^{-1} = f^{-1} \times 2^{-m}.$$ We conclude that it suffices to consider the case where $$b \in [1,2)$$. In this case $$b^{-1} \in \left(\frac{1}{2},1\right].$$ The constant initial guess $$x_0 = \frac{3}{4}$$ has an error which is bounded by $$\frac{1}{4}$$ and a relative error which is bounded by $$\frac{1}{2}$$. It is possible to construct a better value for $$x_0$$ using the best uniform approximation of $$x \rightarrow x^{-1}$$ on the interval $$[1,2]$$.

• Nice use of Newton method, for sure ! Apr 14 '19 at 7:16
• @ClaudeLeibovici Thank you for your kind words. Apr 14 '19 at 10:02

Hint: apply Newton's method. Do the calculations and all the divisions will vanish.

• I need an extra tip: apply Newton's method on what function? Apr 13 '19 at 19:42

Do you know how long division by hand works? Subtract the largest multiple of $$a$$ from $$b$$.

That will be the quotient (value before the decimal point). Let the difference (reminder) be $$d$$. Then put a decimal point and consider $$10 \cdot d$$. Repeat the procedure to as many decimal values needed or until you get a repeated $$d$$.

Eg: Consider $$\frac{25}{7}$$

$$25 = \underline3\cdot 7 + 4 \tag{3.}$$ $$\color{red}{3}\cdot 10 = 30 = \underline4\cdot 7 + 2 \tag{3.4}$$ $$2 \cdot 10 = 20 = \underline2\cdot 7 + 6 \tag{3.42}$$ $$6 \cdot 10 = 60 = \underline8\cdot 7 + 4 \tag{3.428}$$ $$4 \cdot 10 = 40 = \underline5\cdot 7 + 5 \tag{3.4285}$$ $$5 \cdot 10 = 50 = \underline7\cdot 7 + 1 \tag{3.42857}$$ $$1 \cdot 10 = 10 = \underline1\cdot 7 + \color{red}{3} \tag{3.428571}$$

The last reminder $$3$$ is a repeated one and the repetition starts at the decimal starting with $$4$$, so the value is $$3.\overline{428571}$$

• while Euclid's algorithm solves the problem, it's likely to not be accepted in a numerical methods class. Appreciate your idea anyway. Apr 13 '19 at 19:23