Video 2-2: The Word-RAM Model

0:02 Before we get to the um question of comparing the running time as functions of n, let's talk about what running time really is before before comparing things. And what ultimately this is about is the machine that we run on. I said I don't want to assume Pentium 4 or uh Core i7 or whatever uh car- whatever architecture you want to pick. I want something that's on a higher level of abstraction. What would that be?

0:35 To also make you a bit um aware of the pitfalls there, uh here's an innocent question. Um I have two numbers, integers, and I'm adding those up. That's a simple algorithmic task. Uh maybe the the example here is for two concrete numbers, but of course, as an algorithm, this should be two general numbers, and I want a general recipe to add these up. Of course, you've all learned in primary school how to do that, and computers by and large do the same thing, except that they do it in binary. So, if you have two input numbers that are d digits long, how long does it take?

2:04 >> It will depend a bit on how much you you've programmed and how much you've programmed in certain languages of what your typical experience there is.

2:12 Uh maybe also informally you ask who has thought about this question before. In a way we we use addition all the time. Wouldn't it be useful to know how long it takes like a such a fundamental operation and then everything else builds on top of that.

2:41 Anyone still busy thinking typing? Otherwise, let me let me share what people sent. If I can hit the button. So, we have varying opinions. In particular, um a lot of people seem seem to say constant time is correct. But then also uh scaling with D of some form. And the thing is you're all correct. Or you're both correct. Mhm. It really just depends on well, your assumption about the model that you run on, the machine you run on. So, two things to unpack here. The first is if we want to analyze algorithms, we usually don't care about how it does on inputs of size five. You can always tweak things a bit or store a a table with the answers. We care about what happens when you make the inputs bigger and bigger. That's when algorithm algorithmic design really becomes important.

3:43 So, that means I'm trying to make the inputs infinitely big if I think this towards the end, all the way through. But no current computer is really infinite and will ever be. The best I can imagine is a is a machine that whenever it gets too small for my input, I'm able to enlarge it. Say, there's a magic button I click and then the machine doubles, makes everything double twice as big. Even then, I have to think about what that means for my machine. And this is what this chapter gets at. We usually experience when we program that numbers that are small enough, 64 bits or maybe a bit more these days, you can add those up in a single processor cycle, nanosecond scale.

4:30 A couple of um Uh what's a nanosecond? Millions, billions per second. A lot of a lot of additions. But, this stops being true when the numbers have more than 64 bits or say say a few thousand bits. Now, Python um does something clever under the hood, which all algorithms teachers hate because it makes it hard to see. In Python, if numbers get too big, it just swaps out the implementation and suddenly addition is no longer constant time, but is indeed proportional to the number of digits. As you've done in in primary school, you go from the last digits, least significant digit, add those two up, maybe there's a carry, next two, add that up. So, you produce digit after digit and you take essentially time proportional to the number of digits. Same for a computer. How do we reconcile these two things? On one hand, in practice, if numbers aren't humongous, we experience constant time independent of how many of these numbers we have.

5:34 On the other hand, it is not true if the numbers get bigger. So, the the right way to think about this is that both of these things are true and that the number of bits that a computer can work with in constant time is a function of the input size. Let me say that again. The machine grows with its input, and also the number of bits it can work on in one step grows with the input. Hopefully with the kind of we need everything to scale to infinity, it's a bit less unintuitive than this otherwise sounds. But this is really the the only way to solve or reconcile these two worlds. So, abstractly speaking, a machine model fixes um what algorithms are possible, namely uh by giving some specific programming language in which you can express yourself. I'll show you an example soon. And it tells you how much things cost, and there it might make this distinction if you can add two numbers, it may depend on how big the numbers are how fast that is.

6:37 And there the goals for these models are a bit conflicting. We would like these to be as detailed as possible for predicting actual running times. On the other hand, they should be uh not too close to hardware to still be valid next year. And ideally also simple so that you can analyze them. There's maybe one of these these things where you can have to pick pick any two, but may not be possible to do all of them at the same time. Um the concrete one I want to suggest, uh which is the standard one in the algorithms literature. If you read primary research articles, this will be the standard assumption, even if it's maybe made tacitly. That's the random access machine, or more specifically the word RAM, where you uh operate on words of memory. Uh what does that machine look like? Uh you have some infinite collection of memory. This is conceptually say say not infinite, but unbounded. You can make it as big as you want.

7:42 Um, these are numbers, so these are one long array mem. Each of these cells can contain a number. And the numbers are uh from a specific range. From these you have many. But you cannot directly work with them. You can only load and store them into a small set of registers that are close to your actual processor.

8:12 So, you might picture four. And here you can talk, and otherwise you can only load something into here or write something out. And this is your CPU that works only with the registers and controls the whole process. So, unbounded memory, as much space as you need, but fixed constant number of registers to work with.

8:39 And these memory cells and registers can contain an integer from a specific range. And then maybe a number with W bits. And we'll always choose this so that roughly W is logarithmic in the input size. Which means if your input consists of n numbers and of so those memory cells, then your word size should be big enough to store an index into this input. That's where this log n comes from. Because you can represent two to the W different memory cells in one such word, and we want that to be roughly the input size. You can say more about why this is a reasonable convention, but that's the standard assumption. It may sound a little crazy, but on log n bit integers, we assume that you can add those up in constant time. Any more bits, you pay proportional to the number of bits. Or proportional to the number of words, uh I should rather say. You can operate with in W bits at a time in parallel.

9:43 Okay. Um the operations on this machine are a bit similar to some typical assembly language if you've seen one. Uh you can read from memory and store the result in a register, or you can uh write a memory cell, take the contents of one register and and save that in memory. And where you do that in both cases, the address is another register. So, you can do indirect addressing. You can jump to a specific place.

10:16 Then, on the registers, you can do all the usual arithmetic operations, um and also bitwise operations. So, bitwise and bitwise or these these tricks. Um that's all allowed, but you only you can only do those on the registers. And these take constant time, but all the operations are in this uh small in this limited range with W-bit numbers.

10:39 And the cost of an execution is now simply the number of in instructions that you execute. So, if you wanted to add up two numbers that are more than W bits long, you need to represent them as several of so of such words or several such integers, and implement how to add them up manually. And then it will take proportional to the number of words that they take.

11:07 Okay. Oof. Uh bit of a thing. Let me show you one example of what a program here looks like. Um is maybe a bit hard to see what happens. You can simulate this if you want. Um the registers, maybe you could give more telling names. Uh here the assumption is I'm starting with a list of numbers in my memory. And then I go through this, and this indeed does some useful task. Uh but in the interest of time, let me simply give away the answer. This is a sorting algorithm. Um you can puzzle over it a bit. It's indeed uh bubble sort. And this excerpt um maybe you know these books. Uh Don Knuth Art of Computer Programming is one of the uh founding founding figures of uh this analysis of algorithms field and theoretical computer science in general. And his books have a distinctive feature. They discuss algorithms as assembly code. Which is not too far from this.

12:17 Which you is totally possible and may sometimes be rather useful. It's extremely hard to read though. So even there he first gives some more high-level description as bullet points and flow charts, but then the full detailed code.

12:39 We will not usually do that. For essentially the reason that I want I want you to learn algorithm design techniques that help you solve more more interesting algorithmic problems than sorting eventually. And we would just never get there if we do everything on this low level. Again, just as for the proofs, I want to give you the equipment that if you ever want to ever need to, you can drill down to the level of detail that we have here. And settle the questions that may that you may uh have at this point. Maybe uh you want to answer how long it takes to add up two integers. Now you know, it depends how big they are. And there's nothing wrong with both of these realms, constant time or linear in number of digits being relevant in different applications. It just depends on the details of how big the numbers are. Similar for the implementations.

13:33 For the module though, we'll work on more typical pseudo code, closer to high-level programming languages that you know, Java, Python, these things. Um I'll usually try to not give full detailed code in this module so that we can sometimes be even a bit more concise than a programming language would be. So the programs you've seen on the slide before are are very low-level. Um the typical simplifications is for one, I'm allowing the typical structured assumptions, if, for, while, and so on. And I think all of them that I'm using are are rather self-explanatory even if you've seen any programming language. Uh we'll use proper variable names and not worry about registers and memory cells usually. Uh we'll also assume that we don't have to uh figure out where we place things in memory, but rather we do something like in in Java, there's some heap that I can allocate objects on. Uh what we'll also do is as the cost measure, we're not count every single instruction, because that means we have to figure out what exactly the low-level instructions are.

14:43 Instead, we'll pick elementary operations, which is a term that people use to mean different things in different applications. What we mean here is you pick some operation that the algorithm has to do that is essentially dominating the running time. And um often this is easy to pick. Say in a sorting algorithm, it could could be the number of comparisons or the number of swaps that you do. Easy to identify in a specific uh pseudo code and sufficient for the analysis that we want to do.

15:21 So instead of this full uh low-level code, we'll write things more like here on the right. That's the pseudo code for bubble sort. That's um that corresponds to this low-level code. Um we have an outer loop that goes through the array once. Then, we have an inner loop that goes through the array once. And for two adjacent things, if they're in the wrong order, we swap them. That's maybe what you would recognize as bubble sort if you've seen it before. Hopefully, this is at least on a superficial level readable for everyone. Figuring out what the algorithm does is still not always easy. But, it's easier here than here.

16:07 and that's that's usually uh sufficient for the analysis. Last point before I let you go for today or for this week is a bit about the memory management that I already mentioned. Uh we could in theory on computers still work like this uh word RAM where you have one long piece of memory and everything else is up to your interpretation. But, then you would run a single program at a time and have no operating system. That's neither unreal neither realistic nor really useful. So, instead we'll assume the typical uh memory management of a high-level programming language. Which specifically means there's some way to tell this operating system, "Please give me a free piece of memory. A contiguous uh array of of uh entries in memory, and I don't want to worry about how to find this." There's algorithms for that. That's an operating systems class that you can take. Um here we'll just assume that this is given. In C, this would be called m alloc malloc.

17:10 Uh in Java, you just say new and then array or an object. Uh most languages have something like this. And then um what we get back from this is a pointer, a position in memory where these things live and where or where the array starts. So on the word RAM, a pointer is just an integer, so that at this position in memory something is is stored.

17:39 Second, we'll assume that we can just call recursive functions and everything just works because the operating system implements a call stack. Uh just to make you aware that all these things are not so old. Uh Fortran still doesn't have recursive functions and is still in use. Essentially around 1960, people developed these recursive calls. And only then was this introduced into programming languages and there's easily 10 years of of people working on computers that didn't have that. But thankfully we uh don't have to worry about that. So we'll just assume these things are there and ignore how the details work for this module.