Video 1-2: §1.2 The RAM model

0:00 Introduction

0:04 in the next subsection we'll look at our basic Machine model that we'll use for most of the module and that's the random access Machine model called the ram model for short to motivate a little bit of some of the complications I'm about to mention let's do this little question of

0:25 uh uh essentially jumping ahead of ourselves so uh this already is talking in terms of asmic asmic costs what's the cost of adding two question well we'll we'll discuss it don't spoil the questions

1:17 code so we should get at least 60 again right H and you you remember like this is It's participation marks for slido not getting it correct this might be the first question with an actual correct answer

1:30 uh so yeah let me reiterate uh it doesn't matter if you're voting for something that's not the correct in uh 59 all that counts as 60 good okay so we have votes for most of the answers right um and this is somewhat intended well maybe there's no intention to have your answer for the last one but if that's uh what it is uh that's what it

2:07 is um try to lock that now so there's uh as you may see on your devices there's a lot of a lot of correct answers uh the problem is it depends on on your model uh it's a bit of a oh religious question what do you believe about your computers uh you can argue it's constant time

2:34 yeah let me let me run through this because we we have to get through this in time but we can take it offline um so there's an argument to be made for each of these answers you can say it's constant time because you know my computer has 64-bit integers I can add those two up in in one or two cycles uh that's constant time isn't it you could also say well hold on if I give you two 20,000 digit long integers uh good luck with squeezing them in your in your fixed size integer either you have overflows and you just get garbage results or you'll have to spend more time and if you just do the the elementary school method of adding two numbers you're basically going digit by digit in one way or another carryovers and and so on so that takes time proportional to the length of the digits or the the sum uh so that's that's the answer in general okay the last one is also correct in a way but yeah uh the the point really is there's no good answer to this unless you tell me more what integers how big are they what's the machine now uh machine models are trying to put all these questions on a solid

3:42 Machine Models

3:51 ground um make make sure you can answer those definitively so a machine model has to tell you uh what algorithms are possible also because it specifies what programs are so uh it sounds like it's just the machine but it really is uh more than that um it's more influential if you want and the last bit is important um this in implicit in real machines they just run and as long as they run that's the time cost uh for our abstractly defined machines we will have to say what is cost how what what is the cost of an execution of some

4:38 program so uh we have a bit of conflicting interests here we want machine models that are as detailed and Powerful as our actual machines because we want to be realistic at the same time we want to not have one model for each computer in the room we'd like to unify that if if anyhow possible and then we'd also like to analyze it which again pushes it to the the simple Direction and well I I don't know uh I thought I'll in terms of tradeoffs I don't know if you can laugh about this so you usually can't have all three pick any two

5:17 um yeah you can be smart honest or investment banker is not not too serious but let me introduce the random access Machine model before we close for today the random access machine is basically one big array with operations on it now the fun is the array is basically as big as you need it it's not infinite but it's unbounded it's as big as you use it if you want you can think of this as whenever you need more memory you build more discs that's not quite how computers work these days uh but it's also not so far away away from it and cloud computing brought us even closer in in some ways the the problem we're H we're having at this point is we try to describe algorithms that solve remember a whole instant a whole class of problems which have an input size and the inputs can bet can get bigger and bigger and bigger so if you want a machine with an algorithm that can solve all of those will have to allow arbitrarily big inputs and that's only really possible if we also allow arbitrarily big resources in particular memory uh there there's just no way around it no fixed machine allows that uh but if you look in history how machines got bigger there's definitely

5:22 Random Access Machine

6:44 some truth to it question okay uh the question is what's the execution cost I didn't get to that yet um uh so I first want to talk briefly running out of time I think um I want to talk briefly about what programs look like on this machine and uh the cost will actually just be the number of executed primitive instructions so that's that's relatively

7:18 easy uh as I said the machine is one big array what goes in the array well integers uh but we've had this question before so you should all be asking how big are the integers and um here the catch is we'll leave that open we say they have W Bits And W is not fixed per se but can grow with the input size so a typical thing is is this that W grows with the logarithm of the input or some multiple of that uh we'll come to why that's a useful thing but if you think of one big array then log n is roughly the number of bits you need to specify one position in the array it just turns out to be both realistic and convenient to assume that one index into the into the data fits in one word the content of the memory we call a word and so w bit words means each cell in the array can store an integer of w

8:23 bits uh the operations that fill up most of the slide uh they're actually not not too complicated so you could do uh three types of things you can get a memory cell and copy its contents to one of your registers haven't talked about registers haven't I uh you have a fixed number of registers that you can actually compute with the memory is is out there and you have to get all the data into your registers then you can compute and you can write it back and here for the registers again I don't want to fix a concrete number uh so in a way you can say if if you need five more that's fine but it's a fixed constant number the number of registers does not grow with the input so you can say 100 uh that's usually enough for programs that would be right uh if you want to compute you can do this with the registers you can do the normal type of arithmetic everything is done modul 2 to the W modul the word size uh that's how computers work this is basically C style operations so you can do plus minus multiplication integer Division and you can you also do the bitwise tricks that uh languages like C Java python they all

9:34 have something like this so you can do bitwise end of the numbers treating the binary digits as individual bits uh and uh left and right shift okay they're basically multiplications so we wouldn't need those okay that's the operations you can do in the register second type of operation is load something from the memory into the register and store it back and you can do this by specifying the address with one of your registers that's an important bit that means you can do pointers and indirect addressing okay and the last bit you can do is uh ifs basically you can condition on the value of some register is the register zero if so then jump to five skip the next five instructions something like that and then the cost of an of a program run is just the number of instructions that you need it this is a super low-level kind of machine and and way to program uh there's a book that describes this in a bit more detail if you feel like this is um still having some gaps the key thing I want to point out again this is essentially programming in c or some other lowlevel language except for this weird idea that the the word size the the size of the indries you can

11:01 work on in constant time grows with the input uh we'll usually not code in exactly the Primitive instructions we'll allow ourself the kind of highle code I've shown you in the first lecture uh there's a way to map that highle code to what we've seen just on the last slide it's usually very primitive very automatic to do in fact compilers are exactly doing that so we'll we'll usually allow ourselves to be um more convenient for human readers um I think you've seen all these so we use the usual Ty kind of control flow constructions as you would use them in Python uh we allow ourselves to use variable names instead of just indices of registers and so on um and last important bit we'll do we'll count dominant operations so we'll fix some more abstract things to count instead of all primitive operations that's often

12:21 sufficient one last comment Before I Let You Go we'll have to worry about memory management so so we assume that there's some way to allocate memory and that's pretty much all you need to know about this for now so we'll ignore how this is done we'll just assume that this works for most of it you can pretend we're programming in c just that we have these variable size registers or variable size words