Newton Raphson C++ class for float division and other functions

Some months ago when I was searching for a job, a company asked to write a class to evaluate float divisions and find srq() of a number using Microsoft Visual C++. But the challenge was in create a class to perform this operations avoiding the division operator “/”.

I decided to use a old methodology I learnt when I was in college, more specifically in the computer methods. The name of method is Newton Raphson.

About the Newton-Raphson’s Method

The idea is very simple… given a function you guess a initial x0. Then you evaluate the tangent function on that point using derivative function. You will have x1… then you do the same with x1, and even so…

Check the gif below.. when we are very “close” to the root, the variation of x’s are decreased. For example, the “distance” between x4 and x5 in the graph below is minor than x1 and x2.. if you keeping interacting evaluating x6, x7, etc.. the distance will be very close to 0, and you will increase the precision of the root you found.

source: http://en.wikipedia.org/wiki/File:NewtonIteration_Ani.gif

So, if you understood the idea, you will realize for every tangent function what really matters are the X’s encountered when Y=0.

According Newton-Raphson method we have:

source: http://en.wikipedia.org/wiki/Newton’s_method

What hell Mr. Newton Raphson will help us with float divisions and sqr() ?

If you have idea what a computer yes, you should know your computer does not know how to divide. The computer only “knows” how to make additions and if you are dividing two float numbers (f1 and f2) you have something like this:

f1 / f2 = f1 * (f2 ^ -1)

ok.. multiplication is a series of adds but what about f2 power -1 ?

let’s think as a function:

x = 1 / f2

x – (1/f2) = 0

ops!!! zero ? what method we use to find roots ? oh yeah.. I guess now we have a deal:

x – (1/f2) = f(x)

according to Newton Raphson we have:

x(i+1) = xi – f(x)/f'(x)

replacing our function: x(i+1) = 2*xi – (f2 * xi ^ 2)

if you find the root of the function about you will know what is the 1/f2, and if you dividing two floats, you only multiply (series of adds) f1 per the result of your method interaction.

How to use the class

The class created is very simple. You create the instance saying the precision and number max of interactions and using templates you define the type of data your are working on. Something like this:

For a real computational method, you should set a precision expected and the maximum number interactions.

NewtonRaphsonRoots<float> newtonf(0.001f, 100);

Then the idea is to specify the first guess, the function and the function constants.


// computing the float division using Newton (FUNC_NUMB_POWER_MINUS_ONE)
 float f1, f2, fr;
 f1= 5.001f;
 f2= 2.001f;

// creating a obj to evalutare newton methodology using
 // defining the delta and max number of interactions
 NewtonRaphsonRoots<float> newtonf(0.001f, 100);

// so we can evaluate the division without the division operator
 fr = f1 * newtonf.compute(0.01f, NewtonRaphsonRoots<float>::FUNC_NUMB_POWER_MINUS_ONE, f2);

The class implementation

The implementation is very simple.. we have the constructor as explained above and we have a method called compute(). This method considers some classes that you need to register in enum functions_available:

</pre>
/* Register here is you wanna add a new function
 and include the function as private member */
 typedef enum {
 FUNC_SQRT,
 FUNC_NUMB_POWER_MINUS_ONE,
 FUNC_MAX /* INVALID */
 } functions_available;
<pre>

Take a look in the source code attached the implementation for float point division and sqr() function (read the function comments you will understand how the Newton-Raphson was used for this one).

To Do

As I mentioned before, this code was used for an interview. So I did not have time enough for a sophisticated implementation but we could create a scheme for function pointer registers on compute() method and the variable number of constants called in the method.

Other method for computational division – Goldschmidt

There is another method used by AMD Athlon processors called Goldschmidt. In my opinion is more efficient and safe than Newthon-Raphson method, for example, imagine if the processor is computing a division but the function involved does not have roots ? Of course, Mr Newton will fail on this case.

For more information related Goldschmidt check this link.

Source code

Click here to download!

2 thoughts on “Newton Raphson C++ class for float division and other functions

  1. Pingback: lash extensions bellevue

  2. Pingback: real mink lashes

Leave a Reply