CHAPTER 03.04: NEWTON-RAPHSON METHOD: Supercomputers have No Divide Unit - A Newton-Raphson Method Approach

In this segment, we're going to talk about divide unit missing. What I mean by that is that let's suppose if you are trying to find the number a divided by b, so you are simply trying to find out what is a divided by b.  So, this can be also looked at as something like this, we are multiplying a by 1 divided by b.  So, basically it is a multiplication process when you are dividing, but the multiplication process is between a and the inverse of b.  And in some supercomputers, you'll find out that the divide unit is missing . . . the divide unit is missing in . . . in some supercomputers. Now, why is that the case?

It is as follows, that the divide unit is the unit which takes the most amount of time when you . . . when you're trying to divide, it takes about twenty to twenty-five clock cycles on a typical computer to do a division. For a multiplication it might take about five cycles or so. Addition and subtraction may take two . . . two cycles or so. So, you're finding out the divide unit is taking the most amount of time, so what they try to do is they try to not have a divide unit, and be able to do the division without having the divide unit, but we do need division, so you cannot just get around that, so what they use, they use Newton- Raphson method to be able to do the division of a number.  So, going back here, we somehow have to find out what the inverse of a number is, because if we are able to find the inverse of a number when we're dividing two numbers, we can just multiply a by the inverse of the number, and we will get what we are looking for.  So, the question is that how do we use Newton- Raphson method, how do we . . . how do we use Newton-Raphson method to find inverse of a number?  Because that's what it means, if you're able to find out the inverse of a number, you should be able to take that inverse of a number, multiply it by the numerator, and then that means that you'll be able to divide one number by another number. 

So let's go ahead and look at it this way, so since we are using Newton-Raphson method, so it has something to do with solving an equation.  So let's suppose somebody says, hey, you can solve the equation x is equal to 1 by R, where you are trying to find 1 by R.  So if you look at this, because I'm interested in finding inverse of a number, so it seems that if I write down the equation x is equal to 1 by R, and if I'm able to solve for x, that means I'll be able to find out what the inverse of R is, so as simple as that.  So that means that what I can do is I can take the function f of x equal to x minus 1 by R equal to 0, because from the Newton-Raphson method, I have to write down my equation in the form f of x equal to 0, so I'm going to take my minus 1 by R to the left-hand side, and write down the equation as x minus 1 by R equal to 0. So if you look at Newton-Raphson method, it tells me Newton-Raphson method is given as follows by this recursive formula, or this . . . by this iterative formula, that the new guess is obtained by knowing the previous guess of whatever you're trying to find the root of equation of, and you will need the value of the function at that particular point and the derivative of the function at that particular point.  So if you look at f of x is x minus 1 by R, that means that f prime of x is nothing but 1, right?  So if I substitute the value of the function f of x and f prime of x in this particular formula here, what do I get? I will get as follows, I'll get x-sub-i-plus-1 is equal to xi minus the value of the function at xi, is just xi minus 1 divided by R, divided by the derivative of the function, which is just simply 1, and if I simplify this, I just get 1 divided by R. But this is not going to help me any. The reason why it's not going to help me any, because I still have 1 divided by R, and that's what I want to find in  the first place, and I want to avoid the divided unit, so this is not going to help me at all, so this is not the right formula to use by Newton-Raphson method to be able to find the root of the . . . to find the root of the equation x is equal to 1 divided by R.

I might take a different route, the route which I'm going to take is I'm going to say x is equal to 1 divided by R, that means that 1 divided by x is equal to R, because if x is the inverse of R, that means R is the inverse of x, and I'll get 1 divided by x minus R equal to 0, and that's my function now.  So that is the equation of which I'm going to find the root, f of x is equal to 1 divided by x minus R, I need the derivative of the function, which is minus 1 divided by x squared, of this function here for the Newton-Raphson method, because this is 1 divided by x, the derivative of R is 0, because it's a constant, so I get minus 1 divided by x squared.  Now, if I substitute it back into my Newton-Raphson method formula, I'll get x-sub-i-plus-1 is equal to xi minus f of xi divided by f prime of xi.  So what is xi?  xi is xi, f of xi is 1 divided by xi minus R, divided by minus 1 divided by xi squared. So here, of course you are seeing lots of division taking place here, but let's go ahead and see that if we can simplify this a little bit.  So this will become plus xi squared times 1 divided by xi minus R, that's simply by taking minus minus is plus, and xi squared, I take it to the numerator, and I get xi plus xi minus R xi squared here, and here I get 2 xi minus R xi squared, and then if I take xi common, I get 2 minus R xi. So I think I have done it, by using this recursive formula, there is no division involved in this recursive formula.  I can choose an initial guess, find out a new guess, put that back in here, and whatever turns out to be the final guess, wherever I stop this iteration, wherever I stop the iterations will give me an estimate of the inverse of R.  Now, there are implications here, now, somebody might say that, hey, this seems to be a lot of work, because I have to find R times xi, then I have to subtract it from 2, then I have to multiply it by xi, and then I have to do the iterations and things like that, it does involve work, because you're going to be doing a multiplication here, a subtraction here, and a multiplication here, and that's not the end of it, because you may have to do it several times in an iterative fashion. 

So there are several things which are used to be able to circumvent, or try to make it computationally efficient.  One of the things which I want to mention here is that since Newton-Raphson method converges quadratically it takes about six iterations to get an accurate value in double precision. So that's the good part of it, since the Newton-Raphson method converges quadratically, it will take about six iterations to get an accurate value in double precision.  Again, this seems to be high, but there are other things which you can do. You can have a look-up table, and there's a reference given in the . . . in the documentation connected to this video, you can do a look-up table, and then you need only two iterations. So that's the good part, if you have a look-up table for the initial guess, look-up table for initial guess, you need only two iterations. Other things which people do is they, for 2 minus R xi which I have in my formula, they will have something which is called a fused . . . something which is called a fused multiply subtract unit. So you can have a fused multiply subtract unit which does this operation specifically for dividing, or finding inverse of a number, and that also can make the process . . . process efficient.  And in the next segment we'll take an example, but this is the end of this segment.