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.