In this homework we’re going to show the power of functions as tools by computing inverse functions and doing the work just once, rather than having to do it for each function. What do I mean by that? The square function for squaring numbers is easy, right? We just return x times x. But if we wanted to define the square root function, that’s a lot harder. Assuming we didn’t have the exponentiation operator built in, if we wanted to define it in terms of elementary arithmetic, that’s a lot of work. Isaac Newton came up with a way to do it, but he’s Newton. For those of us who aren’t, wouldn’t it be great if instead of having to write all this code to define the square root, we could just say “sqrt” is the inverse of square and be done with it? Well, in this homework we’re going to do just that. We’re going to do it in a slightly restricted sense. We’re only going to deal with functions that are defined on the non-negative numbers and are monotonically increasing. They have to keep on going up. That way they have a defined inverse. Functions that are non monotonic don’t have a single inverse, because there’s a two-to-one mapping. Here’s my definition of inverse. I’m going to give you a simple version and then ask you to write a more efficient one. What does inverse do? It takes a function f and returns a function f_1. The way it figures out what to do is it says let’s start at zero, because we said this is the function defined on the non-negative numbers, and ask is this f(x) greater than the y that’s being passed to f_1. If it is, let’s increment x by a little bit–a little bit being delta, which here I’ve defined as 1/128, but you can define it as what you want when you’re asking for the inverse. Keep on going until we find an f(x) which is not less than y. Now x is too big. It’s greater than or equal to y, and y minus delta is too small. It’s less than y. We’re somewhere in between the two, and we want to pick the closest one. That’s what this expression does. It says we know the result is somewhere in there, and we want to choose which one is closer. How does that work? Well, we can define square. We can ask for the square root of 100. I guess I missed a step in here where I have to say that sqrt is equal to inverse(square). Now when we ask for the square root of 100 we get exactly 10.0. That’s the right answer. When we ask for the square root of 99, we get 9.95-something. That’s pretty close, although there are more accurate representations that the computer could come up with. When we ask for the square root of 100 million, we get 10,000 exactly, which is exactly the right answer. But it took a little bit too long. It took almost a second to come up with this result. I’d like it to go much faster. So that’s what I’m going to ask you to do. I want you to modify inverse so that it has a run time closer to the logarithm of the input to f_1 rather than to linear in the input to f_1. I’ll give you two hints of things to consider. One is binary search, and the other Newton’s method. So do some research on those, and then modify the definition of inverse so that when we say sqrt=inverse(square) the whole function runs faster.