CHAPTER 03.04: NEWTON-RAPHSON METHOD: Supercomputers have No Divide Unit - Example
Let's take an example in this segment of no divide unit. So, we're talking about that if you have a . . . if you want to find the inverse of R, let's suppose you want to find inverse of R, then the formula which you get is x-sub-i-plus-1 is equal to xi times 2 minus R times xi. So this has been derived from the Newton-Raphson method, that if you are trying to find the inverse of a number R, which is simply 1 divided by R, then you can do so without using any division by using this recursive formula here, which has been derived from the Newton-Raphson method, that you will choose an initial guess for x, and you will find a new guess for the x, and then you will, again, put if back in here, and you will continue this process until you find out what the inverse of R is within a prespecified tolerance.
So we'll go ahead and take an example. Let's suppose somebody gives you R equal to 0 . . . let's suppose 2.5. So let's suppose somebody says, hey, I'm going to give you the number to be 2.5, and I'm going to ask you to find what 1 divided by R is, and I want you to find 1 divided by R without using the divide unit on your calculator or anything like that, or in your computer. So we can use this particular formula to be able to do that. So let's go ahead and see how that will work. I'll get x-sub-i-plus-1 is equal to xi times 2 minus 2.5 times xi. So that becomes my formula now to find out what the inverse of 2.5 is. So I'm going to start with an initial guess, so let's suppose I say i is equal to 0, I know that x1 is equal to x0 times 2 minus 2.5 times x0, and I'm going to let x0 be equal to 0.5, let's suppose. So I'm going to choose initial guess to be 0.5. As I said that this initial guess which you're going to choose depends on a lookup table, so if you want something to be computationally efficient, you can choose the initial guess from a lookup table, which means that you're going to base your initial guess on what you are trying to find the inverse of, so you're trying to find the inverse of 2.5, there might be a lookup table which will tell you, hey, this is a good starting value for you . . . for the inverse of R. This is not from a lookup table, but I'm just using it as an example. So, let's go ahead and see what we get, we get x1 is equal to 0.5, times 2 minus 2.5 times 0.5, and this number here turns out to be 0.375. So that's what you're getting is the first guess, you started with 0.5 as your initial guess, and you're getting the next estimate of 1 divided by R to be 0.375, so let's conduct some more iterations.
Now, if i is equal to 1, then I'll get x2 is equal to x1 times 2 minus 2.5 times x1, it's the same formula, except for that i is equal to 1 now. I just found out my next estimate of the root, which is . . . of the root of the equation, x is equal to 1 divided by R, or the inverse of R, to be 0.375, then 2 minus 2.5 times 0.375, and this number here turns out to be 0.3984, that's what I get as the value of x2. Let me conduct one more iteration, I'll get i equal to 2, x3 will turn out to be 0.3999, so I'm going to ask you to do that as homework.
And you choose i equal to 3, you'll get x4 equal to 0.4000, again, I'm going to ask you to do that as homework. And what you are finding out is that after four iterations you are getting the exact value of the inverse of 2.5, because 1 divided by 2.5 is equal to 0.4 exactly, right? You can do that in your calculator or just by hand, and after four iterations you are getting the exact value of the inverse of 2.5 within four significant digits there. So that is the power of using the Newton-Raphson method formula to find the inverse of a . . . inverse of a number, without having to resort to any kind of divide unit.
It took us about four iterations to be able to do this, but, as I said that if you use a lookup table, it would have taken us much less number of iterations to be able to get as exact a value as we got here. And that's the end of this segment. |