1
$\begingroup$

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.

$\endgroup$
0
2
$\begingroup$

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]$.

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

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

$\endgroup$
1
  • $\begingroup$ I need an extra tip: apply Newton's method on what function? $\endgroup$
    – Sigma
    Apr 13 '19 at 19:42
1
$\begingroup$

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}$

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

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.