## Subtitles section Play video

• ANNOUNCER: Open content is provided under a creative

• Your support will help MIT OpenCourseWare continue to

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

• 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 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

• 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

• 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

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

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