Video 1-2: §1.2 The RAM model

0:00 Intro

0:02 now for the model of the machine we'll have to spend a little more time on a little detour and look at how how we can represent the computers we actually have but also abstract them to something that is common to all of them okay so this is the delicate part we want to try to keep a model that's abstract enough so that we can analyze it but still capture what is the essence of the computers we can build or that we you can buy and the ram model the random access machine model is

0:45 the consensus model of this uh to this state and to motivate this um let's do this this little question and the question is quite simple right it's a computer so it should be able to add numbers but how long does it actually take to add two numbers

0:46 RAM model

0:59 Adding numbers

1:49 i was the question that sparks discussions now i should have paid attention where we had before we had 57 votes on the last question 47 on the first maybe we can get a few more people

2:23 so you're you're quite right in a sense the question is ill post but that's only for those who thought about the right uh the right model um let me lock it now and uh i would say there's there's different answers that all make sense uh okay no idea what you're talking about is correct too but

2:53 that's basically correct because i know you're coming from very different backgrounds there's definitely two things that you can say that both make sense and they seem to completely contradict each other you can say constant time which is true if you have integers that fit into one word as one of you said today's computers usually have 64-bit words uh most of them have uh and so if you have an integer that's that fits into 64 bits then you can add those two in uh well roughly one clock cycle is probably not quite true but there's there's pipelining going on and there's in a constant number of clock cycles for sure and maybe the definition of what exactly is a clock cycle is a little a little less clear with the uh complicated architectures but that is that is correct uh if it fits into one word um if the number is vastly bigger as for example in the case of some crypto cryptography some crypto applications like rsa where you need really really big integers uh then it's rather proportional to the number of digits in a sense it could be even worse if you for some stupid reason decided you want to represent your numbers as unary so the number of you you represent them

4:22 just with a sequence of ones and the number of ones is as long as the number you want to represent then the answer would be exponential in d no one does that so it doesn't really make sense to put it up but yeah there's there's different answers to this um and they they all kind of make sense so how can we possibly have two answers when uh they contradict each other so the reason is that we need to somehow let our model know how big the integers are right

5:01 The machine model

5:06 let's let's go back one step the machine model itself what does it do it it not only tells you how things are computed but in a sense it also dictates what our algorithms or what programs for this machine look like and so that's essentially defining what are algorithms for this model

5:28 it can usually describe how these are written down and then you can allow something like pseudocode to abstract from that but you you could in a sense work directly on the language of the machine so the machine model also describes the programming language in a way the lowest level at least and it usually defines a cost model this is a little more subtle but if you think about it's quite clear the machine has some way of executing code and that implies there's some time it takes to execute code and that depends on how the machine operates so the machine model also defines what is running time

6:10 i've talked about this trade-off before we want it to be detailed so that it captures what's going on in certain machines that we want to use in applications at the end of the day but we wanted to unify what we have where these machines differ and ideally should also be simple enough so that we can mathematically analyze it and the the real answer is there's there's more than one model that try to strike a different balance between these and we'll try to stay to stick to one that's closer on the simplicity side that makes it easier to analyze it but sometimes misses out some things i'll point point out some of these when we get there

6:50 The RAM model

6:54 and so without further ado here is the model that's the the random access machine and i want to briefly uh go through what it what it looks like again we won't really build on this at this level of detail but i want to make sure you you know about it because this this question about how long does it take to add two integers it is very cleanly answered in the word ram model and in any other model i've seen before it was still kind of fudgy and and not quite well defined so we assume we have uh an unlimited memory which is essentially one big array so you can say there's a first cell zero of cell first second and so on and you can you can use as much memory as you want uh you will have in a way to pay for it but there's no fixed limit now this seems a weird model right we can't really build an infinite machine but we do care what we do have in machines is the option to extend them as you go so you can think of whenever you run out of memory you you order more memory and attach it to the machine that's still not really infinite but this is also not what it says it says

8:06 it's unlimited which means there's no fixed limit that's not the same as infinite right from the start we'll have registers these are just variables that can store an integer and we'll have a fixed number of those i don't want to put a a specific limit on those because it's often convenient in a program to assume you have a few more if you need a few more you can think of it as around 100 or so in in current cpus it will be convenient to say we can we can borrow a few more if we want but it should not depend on the input size that's the important part it's fixed now what can these registers and the cells in the memory store they each store a w bit integer so that's that's the important part it's not just any integer it's an integer of a certain size with a certain number of bits and the w itself is a parameter of the model that you have to kind of specify for the machine to make sense uh we'll assume that these are just positive integers but you can you can redefine things in your program to pretend they're also negative so this is this is the basic model and then you can make your program work with it

9:32 in any way you want what can you do on this machine uh basically three types of operations you can load or store a single cell from or to a register and it's important to say here that the location in memory from which you load or to which you store a value is also taken from a registry so you can do something like indirect addressing the address where you go to is taken from another register so your program can can compute the address

10:09 then on the registers we can compute that's the actual computation going on we can add numbers and all the other arithmetic operations it's all integers so keep that in mind that something like division only makes sense in the integer sense so you round down or you take the the remainder and all arithmetic by default this is modulo 2 to the w so this is what actual machines do it's exactly taken from how how cpus work and [Music] it's not usually a problem

10:45 on top of these arithmetic operations we also allow bitwise operations i don't think we ever use this in this module but this is part of the word ram so you can do bitwise and or xor negations which allows some extra tricks sometimes

11:04 and the third type of of operations is control instructions in your program you can jump to a different location in the program and you can make that jump conditional on some register so you can ask if that register is zero jump here otherwise don't

11:26 that's all you can do the cost measure is is quite natural i guess uh it's just the number of executed instructions from these three classes and that's that's all you can do so that's quite close to what current cpus are like except for one little weird weirdness that i skipped over and that's this statement so remember n is the size of the input size of the data you want to work with and now this statement says so this this symbol is is taken to be proportional to

12:13 uh so this says the number of bits in a single word grows with the input size that's probably a weird concept so let me write this down you would think this is not really what computers do they don't somehow just double however if you look historically on different computers how the word size has increased it's not so far from this it's actually quite quite well described by this uh relation word size is roughly the logarithm of the input sizes it just happens to be maybe the other way around if you have a certain word size you can work with a certain size of data but this is not it's not automatic it's quite quite striking that this matches the historical development so the machine grows with the input only means as a model you can make the input bigger and bigger and then if you need to work with inputs of a certain size you would have to build a machine with the appropriate word length to do an algorithm properly and there's a another more intuitive reason maybe if you want think of n as the number you're given an uh your input is one big list and an array then that would can would take up n input cells so what that condition then means is you

13:53 can describe one position in this input in a single word that's the condition we want maybe that's um some some somewhat intuitive uh condition okay for now take it as the definition and in case of doubt this is what you should look at for asking the questions uh what is the actual the actual running time and so again

14:24 our our question about how much time does it take to add two integers it is proportional to d if you have d digits divided by w because you can work on on w digits in one time step so if originally your numbers were small enough so that a constant number of words can hold them addition takes constant time if they take if they're bigger if they take a linear number of words it takes linear time and so on so this model clearly answers that question without any resort to if this is the case than this and if that's the case then that in between i don't really know

15:05 Pseudocode

15:10 you can you can imagine how if you program a ram with these three types of instructions this is very very low level it almost is like an assembly code for some actual processors so this is quite inconvenient what we usually do is instead write pseudocode so that's code that's supposed to be clear enough for an average programmer to turn it into the description that the machine can understand now average programmer who knows what that is but i'll just make some some assumptions about our average programmer and we'll have to live with that

15:52 and the second simplification we'll make is instead of counting the exact number of instructions on the ram we'll count dominant operations and that's that's a bit problem specific what that means but for example it could mean the number of array excesses the idea is that the overall running time will be proportional to the number of these dominating operations and we you will have to find what that what what operation that is and again in in many applications it's quite clear what what is a suitable choice

16:30 the important thing here i want to stress this again if you have this abstract model in both cases you can go into more detail if you ever wanted that's that's the idea you should always be able to if you have pseudocode you could translate it to actual instructions on the word ram and you could instead of doing the dominant operations count the exact number of instructions on the word ram it's inconvenient it's tedious it's often not needed for getting the statement you want compare algorithms and predict how long they'll take roughly but you could that's the beauty of the the detailed models

17:16 Questions

17:21 uh before we continue with asymptotics uh questions about word ram and is everybody clear about the the d digit edition now so this might might be something i want to put on the

17:47 slides i said this before but i didn't write it down how much time does it take to add two d digit numbers on a w bid word ram does anyone remember and wants to tell me

18:27 d over w because i can work with w digits at a time and remember w is not a constant w depends on the input size so uh w can be log n if d is is uh well depends what n is but this can be anything between constant and linear in d