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