Subtitles section Play video Print subtitles ANNOUNCER: Open content is provided under a creative 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.