Video 1-2: §1.2 The RAM model

0:00 <Untitled Chapter 1>

0:05 now we roughly know how to model data um in the next subsection i want to introduce you to the standard model for computers that's used in in today's algorithms and data structures research and before i want to dive into that i want you to tell me a little bit what you think about this question you're given two d digit integers say it's written in decimal like in the example and you try to sum them

0:09 The Standard Model for Computers

0:42 what is the running time that you need for that and prepare my get my act together for showing you the result well let's see i want okay 25 people well you can see the results anyway because i forgot to take this

1:49 um okay sorry for this i might as well show the results um we have a clear majority for constant time and we have a few votes for the other things and a few people are confused what i'm actually asking which is fine we'll we'll come to this and i haven't introduced a lot of these things in particular what does it mean to be logarithmic in d etc um okay i'll just i'll just keep it going um

2:29 the uh the nice thing about this question is it's kind of a trick question and uh there is several answers i mean i accepted the last one is correct because we haven't talked about some of it but really uh it's both answer three and answer one which are um correct and uh the reason for that is it depends on on your model really um the cost of adding integers that's a very a very detailed question and what does that mean i guess what most of you um had in mind when they ticked constant time is if i go to java i have to int variables and x equals this 45 235 and in y is 91 342 and then i write x plus y and that's one instruction in the cpu um it's a couple of cycles depending on the arithmetic logical unit but whatever it is it is a constant time operation if the things

2:57 The Cost of Adding Integers

3:45 if the numbers fit into an int so these days it's usually 64-bit numbers it would work for these two for sure it would work for a good deal larger numbers too some some computers have uh wider words operations 128 bits but uh if it does not fit into an end um then the running time is actually proportional to d

4:20 so informally if these if the number of digits okay this is decimal digits uh i shouldn't say this so if if the number of bits whatever that is is much bigger than 64. um then the best thing we can do is in java there's something called um

4:40 Big Integer

4:43 big integer so there's a library function that you can use to compute with arbitrarily big integers and it's fairly slow if you add two numbers you will have to spend time proportional to d if you multiply them it's even slower depending on the exact algorithm it might be up to d squared so both is correct it depends on the model so we should talk about the model uh what is a machine model more generally um it tells you what a machine can do and that mo also tells you what algorithms are what is possible for an algorithm what what can that be it tells you how they are described so every model comes with a sort of a programming language you'll see an example in a second it's fairly low level usually you don't want to work in it but you can build compilers for it if you want and the the third important part that the machine model specifies is how costly is a certain execution how long does it take to execute a certain algorithm or a certain yeah piece of piece of code in in this model now we would like machine models to be on one side to be very detailed and powerful to reflect what happens in actual machines today

5:10 What Is a Machine Model

6:01 but at the same time they should be abstract enough so that they they survive the pentium 4 again this idea they they capture what's common to those architecture as opposed to representing just what a single one does and they should be simple enough to analyze and here i mean understandable by a human with some mathematical education at least that's the goals and the machine models that are used they strike a certain balance they're different models some are more detailed some are more abstract we'll work on a fairly abstract model to keep the analysis simpler and more advanced algorithms classes could dig a little deeper into the into the more powerful models the more detailed models but we'll also touch a little bit on that with the parallel algorithms

7:02 okay so uh without further ado this is our machine model the random access machine i'll describe that briefly to you there's a book with more details we won't really program in this this is background information for you to make sense of this question that i asked before what does it mean to add up to integers how costly is that the answer is it depends and it depends on the the details of of this model so let's let's go through this a random access machine has one one long array if you like of memory so it has unlimited memory it's not restricted but of course if you wanted to build such a machine it always has a certain a certain amount of memory but um think about this as whenever you need more memory you just add more memory to the machine you stop the machine for a year you build new ram and you add it to the machine so uh unlimited memory and you can't really directly work with the memory what you have instead is registers that's similar to actual cpus and their numbers is bounded we don't care so much how many registers there are but it should be a fixed fixed number that does not depend on the size of the

8:27 inputs so it's not possible to store the entire input just in the registers because if you make the input sufficiently big you will run out of registers that's the idea

8:40 now what can you do with these memory cells and registers that's the that's the crucial part so um this just should be read and memorized carefully um they all store w bit integers so this machine can only work with integers and it's actually natural numbers so it can only work with integers in that range between 0 and 2 to the w minus 1. now you might object how on earth should i use such a machine to build a web server build whatever all the sophisticated how should i build something that streams video to youtube well i mean all our computers are actually like this um they uh they have binary memory they have a few more types of of words they can have integers or signed unsigned integers and maybe floating point but when it comes down to the core level of memory it's it's just a long array of bits maybe broken up into bytes um but you can simulate everything you can do with an actual computer on this ram machine it's a little inconvenient to program it point taken apart from that it's fully general it's as general as a computer can be now w is called the word size or the the width width or word size and that's a parameter that's current

10:12 machines so current machines have 64-bit maybe 182 for floating point maybe even 256 but in our mathematical model we don't assume that w is a given number that's fixed we assume that w grows with the input so that's that's fairly weird it means that the machine grows with the input

10:55 sorry for the messy slide but there was a lot i wanted to fit on one slide to have it all handy and show it that's a very weird concept how should the computer grow with its with its inputs again think about this more on a historical perspective think about it as as the inputs become bigger you build bigger machines to work with these inputs if you look at what the word size w has been in historical machines this relation how much how big is the word size and how big of an input can you handle on these machines that behaved roughly like this so this is it's an abstraction of reality and it's an abstraction into infinity as we always do with these models and that's necessary but it's not as absurd as it may sound may sound if you first see it okay that was a long talk about what these word sizes mean and what the memories the memory cells and the registers can store now i should briefly comment on what you can actually do with your integers you can load something from memory into a register or you can store something from a register back into memory easy enough and i should say um yeah that's that's implicitly down here the cost of an execution is the number

12:24 of executed instructions that means each of these instructions takes constant time by assumption and such an instruction can be load or store from or to memory or it can be compute something on registers it could be the addition of two integers but careful it's modular two to the w so if there's if the two numbers together are bigger than two to the w you subtract to the w and you just wrap around if you've done an undergrad in cs you will have seen modulo arithmetic if not be aware the integers in the registers have to stay within w bits there's no way you can make them bigger and if you store if you add two times the largest number in this range that will be bigger than that range there's no way you can get this represented so what's done is is this modulo to the w uh you will talk about integer division a bit in the tutorials also just for refreshing that uh that operation of course you cannot only do addition you can also subtract or multiply or do integer division and the modulo operation again multiplication all these operations are modulo 2 to the w so you have to be careful in how to interpret them and you can do some more operations

12:55 Modulo Arithmetic

13:46 which are sometimes handy to have you can do bitwise tricks you can do the bitwise and of the bits in that number so you take the integer represented as a binary number and then you manipulate directly the individual bits we won't obsess about this too much but the ram model is not complete if you don't include those so that's why i listed them i called them c style operations because they're available in the c programming language but they're also available in java and they're usually available as machine instructions because they're really easy to do in hardware the last thing you can do is conditional unconditional jumps so i haven't talked what the program really is the program of a ram is a sequence of these instructions of these three types and uh you well that sequence has a numbering line numbers if you want and you can jump to a certain line number back or forth and that jump can be unconditional or conditional and the condition again

14:26 Conditional Unconditional Jumps

14:58 you can do using the registers so i don't know you can you can ask whether this is zero for example whether a certain register stores the value zero all right uh that's it that's all this model can do these types of operations it's fairly low levels like assembly on on an actual processor not too far away from it the only difference again is this assumption that the machine grows with the input and that's the the standard model now again so coming back to the question what's the cost of adding two d did not d did integers it depends whether they fit into a word then it's constant time or if they have to be represented as a string of these integers representing the the different parts of the number then it's proportional to the length of the numbers

15:52 all right any questions please pop them in the q a and otherwise i have one last comment to make about the the ram model it's a very low level programming model you don't really want to use in it use it to use it for for implementing algorithms or specifying algorithms so what we usually do is we we usually work with pseudo code so it's not actual code for the ram but something close to it and we'll use uh two simplifications so we write a little abstract code so humans can understand it easily and could translate it to actual ram code but we don't really write down the ram code in detail and the second simplification um is for the analysis uh counting all individual operations in a ram program only makes sense if you have the ram program whereas if you have the pseudo code only you might be able to translate it in a slightly different way so you might use here five instead of six instructions and we don't want to obsess about that difference usually so what we identify as some dominant operations we'll revisit that idea in the next unit a lot you find some operations that are dominant in the sense that they they are a constant fraction of the

17:05 Dominant Operations

17:19 overall effort and then you count those operations instead of all operations that will only um make a mistake in the in the constant term in the in a constant you'll be a constant factor away from the actual ram cost that's usually good enough for us

17:45 last piece of warning pseudocode should be so that if necessary we can actually expand it into full detail and same for the analysis if necessary we can actually expand it to the full details i've spent my msc project with doing something like that it's a lot of fun it's a lot of work you don't want to do it for every algorithm you want to do it only for the important algorithms