Suppose, we live in a world where there was no division operator like we have for addition, subtraction and multiplication. In fact, we don't need to suppose this scenario, because in highly efficient computers such as supercomputers, using a division operator takes significantly more time than multiplication, addition and subtraction. Fortunately, division can be done just by using multiplication and subtraction, and with proper initial guess, within 6 steps in general. Interesting isn't it?
Enter Newton Raphson Method
It is an iterative method to find out roots of an equation. For example, we can find the roots of the equation: $$x^2 - 2x + 5 = 0$$ $$or, f(x) = x^2 - 2x + 5 = 0$$ without performing analytical operations like factoring.
The steps are:
- Find the derivative of the function analytically. In the above case it is $$f'(x) = 2x - 2$$
- Start with a guess for $x$.
- The next value for $x$ is given by $$x_{i+1} = x_i - f(x_i)/f'(x_i)$$ where $i$ is iteration number initially 0.
- Repeat the above process until the values obtained for $x$ seem to converge.
But how does this help our division?
We can think of division $a/b$ as $a * (1/b)$ that is, multiplication of $a$ and the inverse of $b$. Hence our task is just to find out the inverse of $b$.
If $x$ is the inverse of $b$, we have: $$x = 1 / b$$ $$or, b = 1/x$$ that is, $$f(x) = 1/x - b = 0$$ The derivative $$f'(x) = -1/x^2$$
So far so good. Unless... You notice that the formula for $x_{i+1}$ itself involves division: $\frac{f(x_i)}{f'(x_i)}$.
We'll simplify it!
Continuing with our inverse calculation, and using the formula for iteration we have: $$x_{i+1} = x_i - f(x_i)/f'(x_i)$$ $$or, x_{i+1} = x_i - \frac{1/x_i - b}{-1/x_i^2}$$ $$or, x_{i+1} = x_i + x_i^2(1/x_i - b)$$ $$or, x_{i+1} = x_i + x_i - b x_i^2$$ $$or, x_{i+1} = 2x_i - b x_i^2$$
That's it. No division!
Seeing it in action
Let's find out the inverse of 5. $$b = 5$$ Start with an initial guess $x_0 = 0.1$
Note: There are lookup tables for finding out initial guess(And initial guess does matter!) But a general rule of thumb is that we can use 0.1 for single digit number, 0.01 for two digit numbers, 0.001 for 3 digit numbers and so on.
So, with our initial guess of 0.1, the next values for $x$ will be $$x_1 = 2 x_0 - 5 x_0^2 = 2 * 0.1 - 5 * 0.1^2 = 0.19$$ $$x_2 = 2 x_1 - 5 x_1^2 = 2 * 0.19 - 5* 0.19^2 = 0.1995$$ $$x_3 = 2 x_2 - 5 x_2^2 = 2 * 0.1995 - 5 * 0.1995^2 = 0.2000$$
In just 3 steps ! Without division.
I hope this was interesting.
[Tuesday, January 5 2021. Bharatpur]