Welcome to this unit, in which we are going to continue the discussion of mathematical operations that we began in the previous unit. In the previous unit, we discussed the dramatical difference between linear runtime, which we normally don't like, and logarithmic runtime, which we normally love. And that is because it is bounded, and it is always rather small, irrespective of the size of the input. And using this observation here, we have shown two different multiplication algorithms. The first one was naive, and it had a linear runtime, this was the algorithm in which we did multiplication by repetitive addition. And the other algorithm was much more clever and faster and it ran, if you recall, in logarithmic runtime. And to put it in practical terms, the runtime of the better algorithm depended on the number of the digits of the input, which is always a small number like 32 or 64 or 128. Depending on the size of the data type that you are handling. And in this unit, we'll continue in the same spirit. And talk about some other mathematical operations using this dual presentation of a naive algorithm leading to a better one. So let's start with division. Well, here is how division comes to play in Jack programs. You can write either something like x = something divided by something, or if you want, you could make a direct call to the divide function of the math class. Both syntax forms are acceptable, but of course, the first one is more desirable because it's more readable. And yet, if you do the first one, as you know, the compiler eventually is going to reduce it to a function call. So I just wanted to point this out as an interesting observation. So, here is a naive way to implement divide, and basically we're going to count how many times we can subtract y from x before we get a remainder which is strictly less than y. For example, what is 20 divided by 6? Well, 20 minus 6 is 14, we subtracted it once, and then 15 minus 6 is 8. We subtracted it another time, and then 8 minus 6 is 2. We subtracted there 3 times, and 2 is less than 6, so we are done. So the answer is, I'm sorry, the answer is 3 with a remainder of 2, that's the algorithm. And as you see, the algorithm's runtime depends on the size of x. And if N is the largest number that you can represent, or that it can be asked to divide, then the runtime will be proportional to N. And you see it, because if you look at the y loop, you realize that the number of iterations that you have to do depends on the magnitude of x. And that's bad news, because not only the runtime here is very large, it's also potentially very large, it's also unpredictable. In some inputs you will get the answer right away, or in other inputs the algorithm will run millions or billions of times, that's not a good situation. So fortunately, we have a much better algorithm which is based on long division. So what is 175 divided by 3? Well, as we learned in, sometimes in elementary school, we go through this cryptic procedure here, and we get the result. Now, most people don't enjoy seeing long division, and they don't enjoy it, I think, because as children, they were taught to go through the motions of long division without bothering to understand what is going on. Teachers, many times, don't understand it themselves, and that's why people begin to develop math phobia. So what I'd like to do next is, first of all, explain to you why this algorithm works, and in the process of explaining it, I will also illustrate that this is actually a darn good algorithm. So here's our division exercise or division example, 175 divided by 3. So here is how I'm going to do it. Consider the following question, what is the largest number x out of 100, 90, 80, all the way down to 10 so that 3x is no greater than 175? Well, we start with 100, so 100 times 3 is 300, it's too large. Let's skip the 90 and go to the 80, 80 times 3 is 240, too large. Skip the 70 and go to the 60, 60 times 3 is 180, too large. 50 times 3 is 150, bingo, we got it. So 50 is the answer to this question. And so, we write 50 up there in the result slot. And we note that the answer must be at least 50. And if you don't see it, notice that basically what we did here is accelerated subtraction. We have managed to subtract 3 from 175, 50 times. But we are not done yet, right? We haven't yet exhausted the 175. And we still have some more work to do. How much more work we have to do? Well, we multiply 50 by 3, we get 150. And we see that there is still a remainder of 25 that has to be divided by 3. And so now, we have to subtract 3 from 25 so many times, until we get the right answer. So here's the next question. What is the largest number x out of 9, 8, 7, all the way down to 1, so that 3x is no greater than 25? Well, 9 times 3 is 27, it's greater, not good. 8 times 3 is 24, bingo, we got it. So we conclude that the answer must be at least 50 plus 8, right? We subtracted 50 before, now, we subtracted 3, 50 times before. Now we subtracted 3 another 8 times, and we have a remainder, which we compute up there, of 1. So we still have to divide the remainder, 1, by 3. But 1 is less than 3, so we are done. And the answer is 58 with a remainder of 1. So as you see, we got the answer very fast, as fast as we can, actually. And the beauty of this algorithm, in addition to its simplicity, is that the runtime of this algorithm is proportional to the number of digits that we have in the input, which is log N On base two. If we divide binary numbers and log n on base ten, if we divide decimal numbers. So that's a great result. And to sum up what we did with these two algorithms, let's take another quick look at them again. Here we have repetitive subtraction, and here we have the long division algorithm. The run time of repetitive subtraction depends on the input's size, which can be huge. And the run time of the long division depends on the number of digits of the input, which is never too big. And if you're not convinced, take a look at this example here. And this happens all the time with computers that we have to divide and subtract, divide or multiply huge numbers. For example in graphical operations. And the run time of the naive algorithm in this case will be something along this number here. Which is the number of times that you can subtract 3 from the astronomical number that you see here. And the running time of the long division algorithm is going to be 27. Which is the number of digits in the input. So you see the incredible efficiency of long division. And so that's what I had to say about these two algorithms. And the next thing that I'd like to show you is yet another division algorithm, which is the division algorithm that we're going to use in our own operating system. So once again, we have to divide x by y, and the algorithm that we're going to use in our operating system is the following one. It's a recursive algorithm. It may take a few minutes to understand what is going on here, but basically, this algorithm is based on the following insight. Suppose we want to divide 100 by 7. Well, I don't know what's the answer, but I do know that the answer is twice as much as 50 divided by 7. Now what is 50 divided by 7? I don't know, but it must be twice as much as 25 divided by 7. And you got the picture. So you see that in just a few Drilling steps, I get the right answer. And it turns out that the running time of this recursive algorithm is log of m, which once again is as good as it gets in these algorithm. We cannot hope to get anything better than that. And the beauty of this algorithm is that it involves only addition and subtraction operations, which are the same, they're all addition. And therefore versions of this algorithm can be implemented very efficiently in either software or hardware. So that's the algorithm that we requested to implement in the division function of our math class in the Jack operating system. All right, so we discussed multiplication and division. And we presented highly efficient algorithms, which are once again, as good as it gets almost, barring some asympotically possible improvements, which we won't worry about. And the next function that I'd like to discuss is square root, the last one. So here's square root and how can we compute square root efficiently? Well, square root is actually an example of a very large and highly practical family of functions that have two highly attractive features. First of all, the inverse of square root can be easily computed. It is simply x times x. And we know how to compute multiplication efficiently. So that's one attractive property. The second attractive property is that square root is monotonically increasing. It never does something like this, it always goes up together with x, together with the input. Now, based on these two properties, we can conclude that square roots can be computed using a binary search algorithm. And the binary search algorithm has a running time which is logarithmic. So once again, we are back in the cozy place of logarithmic running times and we are very happy and pleased. And this is the algorithm that we are going to use in our operating system. I don't want to dwell on it, because quite frankly, this is not a course about algorithms. But if you want, you can stop the tape and indulge in understanding how it works. And that's how we're going to implement square roots. And once again, it is a highly efficient algorithm. So to recap, we talked about the multiplication, division, square root, the remaining functions are so trivial, that I don't want to waste our time at discussing them and I trust that you will be able to handle them quite easily. So moving along, I do want to talk about some implementation notes which are important, because mathematical operations always have some potential problems that have to be dealt with. So here's our multiplication, algorithm, silver code. And there are three issues which we haven't discussed. First of all, how do we multiply signed numbers? Not necessarily negative, but numbers that have signs. How to handle overflow, if we get it, and how to implement the operation i'th bit of i of y, which is required somewhere in the algorithm. So we'll deal with each of these questions separately. Handling negative numbers, or mixed numbers. Well it turns out, if you inspect this algorithm, it turns out that if the inputs are represented using two's complement, the algorithm works just fine. It will always give you the right answer. You can try to prove it, you can try to play with an example, or you can just believe us. There's no need to handle signed numbers in any particular way. Okay, what about overflow? Well, if you look at the algorithm, you will see at least another two places where you can get overflow sum becomes sum plus shiftedX and shiftedX becomes shiftedX plus shiftedX. So what should we do about overflow? Well, it turns out once again, that the algorithm always returns the correct answer modulo 2 to the 16th, which means that maybe it will not give you all the digits of the correct answer, but the digits that it will give you will be the right ones. And normally, we don't have overflow, so for us this result is good enough. Finally, we have this condition here which is somewhat challenging. We have to extract The ith rate of some 16-bit value, which we'll call y in this algorithm. So how do we do it? How can we extract, let's say the 5th grade of 1001100011, 16-bit value, how should we do it? Well, we suggest to encapsulate this extraction, this operation in Boolean function that we call bit. It has two arguments. The first argument is the 16-bit value that we want to operate on. And the second one is the index that we want to extract. And this function normally can be implemented very efficiently using bit shifting operations, which some languages like Java has and yet Jack does not feature bit-wise operations. And therefore, we need some workaround, and what we proposed is to create an array, a fixed array, to create it once and for all when we start the computer. And this array will hold the 16 values, 2 raised to the power of i. Where I go from 0 to 15 and we can build these array as follows, we recommend that it will be a static array, we call it, you can call it whatever you want, but that's a I think a pretty good name, 2 to the i. So we can declare it statically at the class level of meth and we can use meth in it to actually build it and populate it with values. Once you have this array in place, if you think about it a little bit you will see that it can use this array In order to implement the bit function quite easily. And once again, I want to reiterate, we build this array only once when we start up the operating system. And this actually is quite typical to operating systems. When they start running, there's an in it stage in which the operating system builds all sorts of data structures, that it is going to use throughout its execution. Many different classes can use these data structures. In this example, the math class is going to use it quite extensively. So that's multiplication. Moving along, I'd like to say a few words about division. Here, we have the following issues. First of all, once again, how do we handle signed numbers, x and y. What should we do if asked to divide 151 by -17? Well, here is what we recommend. You can divide the absolute values of the inputs and then set the results as needed. So you have four possibilities. And you can handle it quite easily. What about overflow? Well, y can certainly overflow in this recursive computation. Because we multiply it by 2. And sometimes we add 1. So it can become fairly large and right now, the algorithm is completely oblivious of the size of y. So we suggest that we monitor the y and in general, when you have a twos complement number which grows, positive number that grows When it becomes negative that's the point where there is overflow. And so, we can add this condition instead of saying y greater than x as we have in the algorithm we can say if y is greater than x or y is less than 0 then we return 0, and for us, this is a good enough way to handle overflow. What about square root? Well, with square root we have also a potential overflow. It can happen right here. And how should we handle it? Well, once again we can play with the conditions and instead of using the condition that you see in the algorithm we recommend that you add another cross list condition. And this will once again handle the overflow properly. So these are our implementation notes of these three functions. And this completes the implementation of our math class, because once again the remaining functions abs min and max are trivial, and we don't want to spend time talking about them. I trust that you will know how to implement them yourself. So with that, we are done implementing our first OS class, the math class. And in the next unit, we'll talk about memory management.
