0:00

[music] You've already seen a few different techniques for how to multiply

Â quickly. Some of those techniques include

Â quartersquares, using logarithms or a sliderule.

Â And that method of prosthaphaeresis, which involves arc cosine.

Â So yeah, there's a ton of different techniques that I can use to multiply two

Â numbers quickly. But what if I could already multiply

Â quickly, but I wanted to divide quickly? What if I wanted to calculate 1 divided by

Â b? Well, we can use Newton's method to do

Â this. Now, how we're going to use Newton's

Â method. Well, Newton's method is really a trick

Â for finding zeroes of a function. So, if I want to approximate one divided

Â by b, the reciprocal of b, what I really want to find is some function where that

Â number is a zero of the function. Newton's method will help me approximate

Â that zero and consequently help me approximate 1 over b.

Â There's a ton of different choices that are possible for such a function.

Â Well, here's one choice. The function f of x equals 1 over x minus

Â b. And let's just check, yeah, if I evaluate

Â this function at 1 over b, that's 1 over 1 over b minus b.

Â But 1 over 1 over b, the reciprocal of the reciprocal of b, is just b.

Â And b minus b is in fact 0. So, this function f does have 1 over b as

Â a 0. Now let's apply Newton's method.

Â So how are we going to do this? Here is the formula for Newtons' method,

Â right? This is the iterative formula, my next

Â guess is my old guess minus this fraction. The function evaluate of my old guess

Â divided by the derivative evaluate of my old guess.

Â And when this works, it's marching me closer to a 0 of the function.

Â And here's the good function for doing division.

Â This function has a 0 at 1 over b. So, if I can get closer and closer to a

Â zero of this function, I'm actually computing 1 over b, which is what I want

Â to do. So, let's try to rewrite this formula just

Â by using this. And the first step here is to

Â differentiate this. So, let's differentiate this.

Â Well, the differential goes back to x. So, the derivative of 1 over x is minus 1

Â over x squared, and the b here is the constant.

Â So, I have to include it. So, this is the derivative of f.

Â Now, I'll use that to try to make this Newton's method formula look a little bit

Â nicer. So, x of n plus 1 is x of n minus the

Â function evaluated, x of n, which is 1 over x of n minus b, divided by the

Â derivative evaluator x of n, which is minus 1 over x of n squared.

Â Now, to kill off this denominator, let's multiple by minus x sub n squared divided

Â by minus x sub n squared. That's just a sneaky version of 1, but it

Â manages to kill off the denominator simplify this a bit.

Â I've got x sub n. I've got minus x sub n squared times 1

Â over x sub n, that leaves me with a minus x sub n.

Â And I've got a negative b, negative x sub n squared, that's a plus b x sub n

Â squared. I'm subtracting this.

Â So, I've got x sub n plus x sub n, that's two x sub n's, minus b x of n squared.

Â And I'll factor out an x of n, so x of n times 2 minus bx of n.

Â And what I've got here now is an iterative formula that, at least when it works.

Â Applying this iterative formula is going to move me closer and closer to one over

Â b. But this formula doesn't involve division,

Â it only involves multiplying and subtracting.

Â So, this is a way to approximate 1 over b without ever dividing, right?

Â Just multiplying and subtracting over and over again.

Â Then, we'll make this even more concrete. Let's set b equals 7 so I can try to

Â approximate 1 over 7. So here we go.

Â B will be 7. So, we're trying to approximate 1 7th

Â using Newton's method. So, I make an initial guess.

Â And I'll make my initial guess 1 10th and make some of the arithmetic work out, a

Â little bit more reasonably. And I'm going to start with this initial

Â guess, and I'll use this formula we just derived to improve this initial guess to a

Â hopefully better guess. So, I take my original guess, 1 10th.

Â Multiply it by 2 minus b is 7, times my previous guess of 1 10th.

Â I can calculate this. This is 1 10th times, instead of 2 I'll

Â write 20 10th. And instead of 7 times a 10th, I'll write

Â 7 10th. I got 20 minus 7 10th, so that's 13 10th.

Â So, 1 10th times 13 10th, that's 13 100th and that's a slightly better as to the

Â value of, of 1 7th, but I can now repeat this process using this formula again.

Â So, I'll get a better guess here x sub 2 by starting with my previous guess, which

Â is 13 100th. Multiply that by 2 minus 7 times my

Â previous guess of 13 100th. I can calculate what this is.

Â So, 13 100th. Instead of 2, I'll write 200 100th, that's

Â another name for 2 minus. Instead of 7 times 13, I'll multiply that

Â out. I'll get 91 100th.

Â Now, 200 minus 91, that's 109 100th times 13 100th.

Â And 13 times 109 is 1417, and 100 times 100 is 10,000.

Â So, that's an even better approximation to the actual value of 1 7th.

Â And I could appreciate the process again. The arithmetic gets, you know, sort of

Â awful. But the point here isn't so much, you

Â know, that I can actually do this on paper, or that I would want to do this on

Â paper. But that this procedure only involves

Â adding, subtracting, and multiplying, and yet it ends up calculating a division

Â problem. Well, how close are we to the actual value

Â of 1 7th? 1 7th is about 0.142857 and it keeps on

Â going. So yeah, we're doing really quite well.

Â I mean, 0.14 is a pretty good guess as to the actual value of 1 7th.

Â This method has a name. So, this technique usually goes by the

Â name Newton-Raphson Division. And we just saw that it works for finding

Â recipricols, but if you can find recipricols and you can multiply, you can

Â do division in general. Alright, if you wanted to approximate 3

Â 7th using this technique, well, you just point out that 3 7th is 3 times 1 7th,

Â right? And imagine that you can multiply, add,

Â subtract, but the division is hard. Okay, well a moment ago, we approximated 1

Â 7th, alright? We approximated 1 7th to be about 1,417

Â over 10,000. This was the second stage in the

Â approximation. And 3 times 1,417 is 4251 over 10,000.

Â Which isn't so far off of 3 7th, right? The point though is that, you know, if

Â division, but if division that only involves repeated adding, subtracting, and

Â multiplying.

Â