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