commons license.

Your support will help MIT OpenCourseWare continue to

offer high-quality educational resources for free.

To make a donation, or view additional materials from

hundreds of MIT courses, visit MIT OpenCourseWare

at ocw.mit.edu .

PROFESSOR JOHN GUTTAG: All right.

That said, let's continue, and if you remember last time, we

ended up looking at this thing I called square roots bi.

This was using something called a bisection method, which is

related to something called binary search, which we'll see

lots more of later, to find square roots.

And the basic idea was that we had some sort of a line, and we

knew the answer was somewhere between this point

and this point.

The line is totally ordered.

And what that means, is that anything here is smaller

than anything to its right.

So the integers are totally ordered, the reals are totally

ordered, lots of things are, the rationals are

totally ordered.

And that idea was, we make a guess in the middle, we test it

so this is kind of a guess and check, and if the answer was

too big, then we knew that we should be looking over here.

If it was too small, we knew we should be looking over here,

and then we would repeat.

So this is very similar, this is a kind of recursive thinking

we talked about earlier, where we take our problem and we

make it smaller, we solve a smaller problem, et cetera.

All right.

So now, we've got it, I've got the code up for you.

I want you to notice the specifications to start.

We're assuming that x is greater than or equal to 0, and

epsilon is strictly greater than 0, and we're going to

return some value y such that y squared is within epsilon of x.

I'd last time talked about the two assert statements.

In some sense, strictly speaking they shouldn't be

necessary, because the fact that my specification starts

with an assumption, says, hey you, who might call square

root, make sure that the things you call me with

obey the assumption.

On the other hand, as I said, never trust a programmer

to do the right thing, so we're going to check it.

And just in case the assumptions are not true,

we're just going to stop dead in our tracks.

All right.

Then we're going to set low to-- low and high, and we're

going to perform exactly the process I talked about.

And along the way, I'm keeping track of how many iterations,

at the end I'll print how many iterations I took, before

I return the final guess.

All right, let's test it.

So one of the things I want you to observe here, is that

instead of sitting there and typing away a bunch of test

cases, I took the trouble to write a function, called

test bi in this case.

All right, so what that's doing, is it's taking the

things I would normally type, and putting them in a function,

which I can then call.

Why is that better than typing them?

Why was it worth creating a function to do this?

Pardon?

STUDENT:: [INAUDIBLE]

PROFESSOR JOHN GUTTAG: Then I can I can use it again

and again and again.

Exactly.

By putting it in a function, if I find a bug and I change my

program, I can just run the function again.

The beauty of this is, it keeps me from getting lazy, and not

only testing my program and the thing that found the bug,

but in all the things that used to work.

We'll talk more about this later, but it often happens

that when you change your program to solve one problem,

you break it, and things that used to work don't work.

And so what you want to do, and again we'll come back to this

later in the term, is something called regression testing.

This has nothing to do with linear regression.

And that's basically trying to make sure our program has not

regressed, as to say, gone backwards in how well it works.

And so we always test it on everything.

All right?

So I've created this function, let's give it a shot

and see what happens.

We'll run test bi.

Whoops!

All right, well let's look at our answers.

I first tested it on the square root of

4, and in one iteration it found

2.

I like that answer.

I then tested it on the square root of

9, and as I mentioned last time, I didn't find

3.

I was not crushed.

You know, I was not really disappointed, it found

something close enough to

3 that I'm happy.

All right.

I tried it on

2, I surely didn't expect a precise and exact answer to

that, but I got something, and if you square this, you'll

find the answer kept pretty darn close to

2.

I then tried it on 0.25 One quarter.

And what happened was not what I wanted.

As you'll see, it crashed.

It didn't really crash, it found an assert statement.

So if you look at the bottom of the function, you'll see that,

in fact, I checked for that.

I assert the counter is less than or equal to 0.

I'm checking that I didn't leave my program because

I didn't find an answer.

Well, this is a good thing, it's better than my program

running forever, but it's a bad thing because I don't have

it the square root of 0.25.

What went wrong here?

Well, let's think about it for a second.

You look like-- someone looks like they're dying

to give an answer.

No, you just scratching your head?

All right.

Remember, I said when we do a bisection method, we're

assuming the answer lies somewhere between the lower

bound and the upper bound.

Well, what is the square root of a quarter?

It is a half.

Well, what-- where did I tell my program to

look for an answer?

Between 0 and x.

So the problem was, the answer was over here somewhere, and so

I'm never going to find it cleverly searching in

this region, right?

So the basic idea was fine, but I failed to satisfy the initial

condition that the answer had to be between the lower

bound and the upper bound.

Right?

And why did I do that?

Because I forgot what happens when you look at fractions.

So what should I do?

Actually I lied, by the way, when I said the answer

was over there.

Where was the answer?

Somebody?

It was over here.

Because the square root of a quarter is not smaller than a

quarter, it's bigger than a quarter.

Right?

A half is strictly greater than a quarter.

So it wasn't on the region.

So how-- what's the fix?

Should be a pretty simple fix, in fact we should be able

to do it on the fly, here.

What should I change?

Do I need to change the lower bound?

Is the square root ever going to be less than 0?

Doesn't need to be, so, what should I do about

the upper bound here?

Oh, I could cheat and make, OK, the upper bound a half, but

that wouldn't be very honest.

What would be a good thing to do here?

Pardon?

I could square x, but maybe I should just do something

pretty simple here.

Suppose-- whoops.

Suppose I make it the max of x and 1.

Then if I'm looking for the square root of something

less than 1, I know it will be in my region, right?

All right, let's save this, and run it and see what happens.

Sure enough, it worked and, did we get-- we got the

right answer, 0.5 All right?

And by the way, I checked all of my previous ones,

and they work too.

All right.

Any questions about bisection search?

One of the things I want you to notice here is the number

iterations is certainly not constant.

Yeah, when I will looked at

4, it was a nice number like 1,

9 looked like it took me 18,

2 took me 14, if we try some big numbers it

might take even longer.

These numbers are small, but sometimes when we look at

really harder problems, we got ourselves in a position where

we do care about the number of iterations, and we care

about something called the speed of convergence.

Bisection methods were known to the ancient Greeks, and it is

believed by many, even to the Babylonians.

And as I mentioned last time, this was the state of the

art until the 17th century.

At which point, things got better.

So, let's think about it, and let's think about what we're

actually doing when we solve this.

When we look for something like the square root of x, what

we're really doing, is solving an equation.

We're looking at the equation f of guess equals the

guess squared minus x.

Right, that's what that is equal to, and we're trying

to solve the equation that f of guess equals 0.

Looking for the root of this equation.

So if we looked at it pictorially, what we've got

here is, we're looking at f of x, I've plotted it here, and

we're asking where it crosses the x axis.

Sorry for the overloading of the word x.

And I'm looking here at 16.

Square root of 16, and my plot basically shows it crosses at

4 and-- well, I think that's minus 4.

The perspective is tricky-- and so we're trying

to find the roots.

Now Isaac Newton and/or Joseph Raphson figured out how to do

this kind of thing for all differentiable functions.

Don't worry about what that means.

The basic idea is, you take a guess, and you -- whoops

-- and you find the tangent of that guess.

So let's say I guessed

3.

I look for the tangent of the curve at

3.

All right, so I've got the tangent, and then my next guess

is going to be where the tangent crosses the x axis.

So instead of dividing it in half, I'm using a different

method to find the next guess.

The utility of this relies upon the observation that, most of

the time-- and I want to emphasize this, most of the

time, that implies not all of the time-- the tangent line is

a good approximation to the curve for values

near the solution.

And therefore, the x intercept of the tangent will be closer

to the right answer than the current guess.

Is that always true, by the way?

Show me a place where that's not true, where the tangent

line will be really bad.

Yeah.

Suppose I choose it right down there, I guess 0.

Well, the tangent there will not even have an x intercept.

So I'm really going to be dead in the water.

This is the sort of thing that people who do

numerical programming worry about all the time.

And there are a lot of a little tricks they use to deal with

that, they'll perturb it a little bit, things like that.

You should not, at this point, be worrying about those things.

This method, interestingly enough, is actually the method

used in most hand calculators.

So if you've got a calculator that has a square root button,

it's actually in the calculator running Newton's method.