Video 1-2: §1.2 The RAM model

0:03 in the next section I want you I want to show you the standard model for for computers that we use in algorithms these days that's the the random access machine and this is I I saved this for the last part because it's a bit more intricate um and it has a little a little twist to it that will come too uh and to motivate that I'd like to ask you this question um without saying too

1:30 I've had 114 people vote on the attendance code earlier I'm not looks like you're more than age let's wait until we have a 100 people voted and then 98 all right ah one more good there's the results that people voted um let me briefly discuss this a bit they're really different answers that all make sense depending on some assumptions that you

2:40 make so uh it it could be that it takes constant time to add two numbers um on on our so take in take in the concrete model I'll show you in a moment aside on on your computers that you have with you it takes constant time if the numbers

3:06 have at most 64 bits then it's quite guaranteed well almost all computers these days have 64-bit architectures uh so it fits in one word and then there's one machine instruction that adds two numbers bum done and it can do I don't know uh a few billion per second of these right uh constant for us just means it doesn't depend on the input size now that's that's a little cheating because if the numbers are big uh it it does take more time and so the uh algorithmically more sensible answer is C if the numbers keep growing then it will be time proportional to the length of the numbers in

3:53 bits so I would say this is um more more correct right but if you write if you write a program that always just uses numbers with the most 64 bits the first answer is is what you'll see and uh okay the last uh is is of course correct but we'll try to fix

4:23 that U maybe a quick comment why is it proportional to D well you do the primary school method you start with the last digit you add those two digits up there may be a carry digit so you have three digits in The Next Step but that's all so you add these three then you get the next digit so in each step you get one digit of the uh result produced and you have D digits in total to to process maybe it's D plus one in the end uh but that should be it all

4:53 right so the Machine model is really important uh because it it determines how algorithms look like it tells you what algorithm are possible and in what kind of language they are expressed and it also defines usually what the cost of an execution is and because it defines all these things there's a there's a few trade-offs that are that are tricky in general to get right it should be detailed and powerful enough to reflect what current machines can do for example what I just said if you have numbers with at most 64 bits it's very fast to add them whereas if you have much longer numbers it takes more time somehow the model should reflect that uh it should also be abstract enough to not change every year otherwise gone our our Eternal truths uh but then also we would like it to be simple enough to analyze it mathematically so the the second this this first point and the last Point are in clear opposition so sometimes uh you may need a compromise and can't get all

6:01 three uh here's the solution that algorithms research has essentially settled on H it's a bit of a mouthful but don't get uh don't get intimidated it's just trying to Define all that a computer can do in one slide and so it has to uh go through a few different things uh there's a book which is listed on the module page so little digression little aside um you know the module has a module website which is linked on canvas but is living outside of canvas on my on my personal website uh it the module page has sub pages for all the units and unit one has the slides from today will have the videos from today after some point and also has a list of further reading and sources at the bottom and there you'll find a link to this book it's in the library in some form um most books you can borrow from the library in in electronic form which is probably most convenient but they also have some print copies so the definition here is in in much more detail described in this book but I'll try to give you the the short version our computers the random access machines at least have one big array of memory it's essentially unlimited you can use as much as you need I'll comment

7:21 on that in a second why that uh sounds a bit weird right but why that might be okay that's memory where you can store uh data but to work with the data you have to copy it to registers and there you have a fixed number and that number is not usually very important so I'm I'm generous I allow you to tell me how many you want but it should be somewhat reasonable maybe a few hundred at most definitely independent of the input size so you have to you have to write a program that fixes the number of registers without knowing how big the input is that you work

8:05 gone uh the memory cells themselves they can each contain a number and that number is an integer with W bits and that's where things get a bit uh a bit tricky in a way we have this second parameter W that is part of the Machine model so you have to tell um how large that is and most current computers have essentially 64 4 um not too long ago it was 32 if you're if you're strict then many of the computers actually have more than 64 because they have these s IMD instructions single instruction multiple data where you can work on longer words up to 265 at least uh maybe some graphic cards even more and they split this it's treated as a vector where you can do Vector Vise operations so in a way even 64 is uh playing it playing it safe but to come back to the formal model each memory cell contains a number with W bits so that's an integer between 0 and 2 to the wus one and now the clue is that this word size is allowed to depend on the input size that's a really weird concept the machine grows with the input and a typical assumption is that by and large W is logarithmic in the input

9:30 size uh a quick motivation for why that roughly is if you write down the input in an array you want to at least have a way to say I want the I bit in the input and that number I should fit in one word because that's mostly possible in computers uh the second reason is you usually want to be able to use addresses to memory in operations for example you can add up two addresses in computer uh memory and so to be able to do that they should fit in one word so this is a somewhat natural assumption but maybe it looks really weird if you see it the first

10:13 time these two things that the input is essentially unbounded and that the word size grows with the input might look really strange but if you look back historically if you don't treat this as a model for one laptop on your on your desk but for all of the computers over the history of computers it makes a little more sense the word size has kept growing over time it started with single digit number of bits and then quickly went to 32 and now we're at 64 and even going beyond that with these SD instructions and at the same time the data that the computers worked on was also growing and roughly in that relation exponential growth so don't treat it as a as a weirdness of the model that it seems to grow with the input imagine rather if you want a bigger input to be solved you have to build the machine up you have to add more memory and you have to increase the word size accordingly basically any other way to define the model gives you other paradoxes for the theory that are not nice all right so I talked a lot about what the what the memory is like um how big it is and how many bits you have in each memory

11:27 cell I will briefly talk about the instructions of the computer but that's the slightly less important part you have more leeway on this but uh to be concrete um our computers here the random access machines can do basically three different things one is they can load and store memory from uh data from memory so you can get what's in a certain cell in memory and Stor it in a register and the address is given by another register so you can use indirect addressing and you can do that for reading and writing then you can do all sorts of standard arithmetic on registers so you can add to numbers subtract multiply integer Division and integer modulo uh and you can also do the C style bitwise operations I called them C style because uh C popularized them back then but most programming languages have operators for that the same operators are used in Java and c and so on um and python has some way to express them as well so you can for example take two numbers and do the bitwise and treat the numbers of spinar binary strings and do the end of each digit and a few other related ones these won't be so relevant for this module but I wanted to list them to be uh to be

12:51 complete and the third thing you can do is uh jumps and conditional jumps in your program that's to do logic in the program so you can say jump back to line so and so and you can say only do that jump if a register is zero or something like that so here again uh you can you can compare two registers uh we don't we don't necessarily care about the the fine detail

13:21 here that's the three type of of things you can do that's very similar to most if you've done some undergrad in computer science you will probably have done some Assembly Language where you've built some you least conceptually build a processor and that's the kind of operations they support so this is very close to the Silicon uh that we actually use um but it's a bit abstracted from some details the cost in the model how long does an exe uh an a program take in this model is assuming it's exactly the number of executed instructions so again for the experts I'll I'll point out that accessing memory here is assumed to take these these kind of instructions they take constant time and they are as fast as doing arithmetic that's often not true in reality but uh as a first order approximation that's what we assume

14:20 here any questions on that model for now I know it's been a lot uh lot of info because it's very very low level I said it's it's close to a silicon style what actual processors um have as operations it's very inconvenient to write any complicated algorithm in that level of detail so we'll usually allow ourselves to do um something that's closer to python code and uh you either have SE in a compiler lecture or you have to take my word for it that it's a solve problem how to translate from this more high level description if it's precise like python down to what I've just shown you that's an automated process that's what compilers can do and they usually even even smart about it to make some optimizations along the way so we'll ignore that step for us algorithms will live at a slightly higher level uh but we'll we'll know that if if needed we can go back to this slightly lower detailed level to measure the

15:39 performance because we we allow ourselves to work with this more abstract pseudo code uh what we'll usually do is count count dominant operations so we don't count all instructions in the ram program because that would need us to write down exactly the program that we that we want to analyze um there's a famous famous theoretical computer scientist Don K Donald Donald can who has done that exactly that in his his books the art of computer programming uh maybe some of you know the book uh many many know the book but haven't haven't ever read parts of it he does exactly that he goes for all algorithms down to a level of the RAM and counts all the instructions precisely it's doable but it's painful

16:30 so most people abstract a bit from that and count dominant operations so specific points in the program that will be proportional to the total cost if we count those here's a few things that we allow ourselves in the pseudo code um instead of just doing conditional branches we allow ourselves the usual kind of loop constructions that you would have in Python and other languages uh we use variable names instead of registers with numbers maybe that's obvious um but yeah if you work with assembly you'll have to deal with that uh and I we'll also make another assumption that I'll talk to about talk about in a second again my point about presenting this detailed model is is twofold one is I want I want to assure you that there is a level of detail that you can go down to if needed and also sometimes um answering a question for example about sorting we'll come back to that requires that you specify what model you're working on even if your programs are abstract pseudo code tell saying how fast an algorithm is might need to tell details about the model so it's kind of something that's looming in the back and we don't always uh go down down all that level but it's it's important to know how to resolve

17:57 this one last assumption that we use in our pseudo code which is a bit of a bigger thing it's again if you've done an undergrad in computer science maybe you've done a lecture on operating systems and then again you would know in detail how this works otherwise take my word for it that it's a solved problem but we'll just assume that this is already somehow done if we're if we're working on a ram like I defined it there's no such thing as structured memory memory is just this one giant array and you can use as much of it as you want we assume it's as long as you need it but there's no structure to it and it's super painful to write programs that

18:53 way sorry say it again the ram doesn't right so the question is about the the ram model and space complexity um if you want to define the used space you would you would take the furthest you access the the memory so you would assume you don't use or there's the memory that you don't ever touch doesn't need to

19:24 exist and now I have two systems one follow Ali any point where patient algorithm will cross the right so the question was about uh comparing different Al maybe I'll have to take it offline and I have to ask you about the details what we'll assume is that all algorithms are operating on the RAM and uh I guess they all R ran run on the same Ram with the same W [Music] um that can have consequences for the algorithms

20:29 um oh the input okay I didn't talk about the the details about the input so the a standard assumption is the input is initially written in the first n cells of the

20:43 memory and you can you can read and overwrite that and at the end you'll leave the output in the first few cells of memory but you can change these conventions uh that's not too essential but yeah you're right I mean there's it's already a full slide uh there's some details that I left out um I tried to leave out those where no matter how you fill them it doesn't change the model substantially but yeah uh maybe have a look at the book they they're a bit more um a bit more rigorous about that part uh because you brought up recursion recursive algorithms is another useful programming technique doesn't exist on what I defined on the ram right doesn't have any system Stacks it just knows nothing about that uh that's all something we'll assume that it exists without worrying too much about how it's done so we'll assume um that we have some sort of memory management built in so we uh we're able to just say give me a new a free piece of memory of that size that's similar to what you can do in C or you can allocate an array of a certain size with a certain type of objects uh we'll also assume that you can can allocate objects from some

22:00 objectoriented program if you have a class and you instantiate that similar to what python uh offers we'll assume that that's also handled by this operating system that's that's running on this Ram without us touching it uh if I if I talk about pointers in algorithms that's basically just a number it's an address of some memory cell and that's what it is in reality too uh but memory safe languages

22:29 uh I don't know if python is memory safe with all the C extensions probably not but uh Java is a memory safe language that that guarantees to you if you're if you have a pointer you're never going to access a piece of memory that wasn't properly allocated you don't get this uh uh buffer overflows in in that sense at least um so that sometimes they talk about references to make the distinction to a pointer that could be an arbitrary number in in memory with the algorithms we won't make that distinction pointer and reference is the same and it's just the number of the address in memory and uh yeah as I said recursive calls all operating systems have a a system stack where you can call functions recursively and so on or non- recursively we'll we'll also assume that that exists

23:25 okay as a bit of a slide for um for everyone who's seen some of this before um if not everything on that slide makes too much sense for you don't worry too much I just wanted to put this up so that those people who know about it uh know our assumptions on it