



S1: let me ask a question. (xx) operate the power. is that readable? [SU-M: no ] [SS: yeah ] with the lights off you can read it... that's okay? i can make it a little bigger too. it's much better if it's green on black or yellow on black, but at the moment i can't find where they've hidden the uh colors so i won't uh, waste time on that... but i do wanna do some stuff on there so, okay um little bigger... is that doable? <P :06> who's tried to compile code on maize? just one two... lemme show you an interesting error. um, you know when you compile code you get all these crazy error messages and you look at them and you say what the hell does that mean. um, they actually all say something most of them are even understandable if you look at them for long enough. <P :06> uh <P :06> (xx) <P :06> big mistake never use Windows N-T. <P :07> still can't see (xx) <P :09> don't move, (Daniel) <P :09> okay. close enough. um <P :09>
SU-M: the font's too big. 
S1: yeah but if the font's s- smaller then you can't read it easily. okay this'll do. <P :13> okay so here's some interesting C codes. uh trust me they work. let's compile them. <P :09> now watch it'll work and i'll be embarrassed. it's supposed to break. <P :05> fast isn't it? [SU-M: (work) ] okay here we go. and we get this funky error message which says... <READING> C-C prime-dot-C line twelve error seventeen-oh-five function prototypes are an ANSI feature. </READING> okay and several people have sent me messages and several people have seen this in the labs. and, i- what the hell's it saying? anybody have a guess? it's actually telling you something. 
SU-M: uh you got something (xx)
S1: that wasn't much of a guess. <READING> are an ANSI feature. </READING> and i keep talking about how C is this family of languages and there's traditional C and ANSI-C and objective C and all these different things called C. this compiler is telling you that it is not an ANSI-C compiler. it turns out that on a lot of the CAEN not all, but a lot, of the CAEN, um, Hewlett Packard workstations the default compiler is not an ANSI-C compiler. which means you hand it our codes which are written in ANSI-C and it gives you little error messages. this is, a common problem. Visual Studio will give you some of the same problems if it thinks your code is something other than ANSI-C, it sometimes tries to guess, it'll give you mysterious error messages your code will be perfect. and it will be yelling at you that it's not right. okay? a lot of compilers have that problem. th- there're are all these different, slightly different versions of things, and the people who wrote this compiler, or the people who installed it by default didn't think you would want to write ANSI-C they're fools, because no one should use anything other than ANSI-C anymore, but no matter. it can be fixed. <P :09> this compiler, you can tell it, to use ANSI-C with this little minus capital-A little-A thingy, called a flag. okay? um, that's true of all the compilers you deal with. you may get on a Sun sometime, Sun is pretty_ the Sun workstations are pretty standard (xx) you get the ANSI-C compiler, but you may get on a Sun workstation, and run your code and it gives you an error message and you're sure there's no error. okay? Suns, just two years ago by default wouldn't compile ANSI-C you had to tell them specially, compile ANSI-C for me. so, the point is these, slight differences among versions of the language, do impact us in a practical way. the various compilers make different assumptions about uh, um, what you want it to do. they're very presumptuous. okay. so i wanted to address that since uh some of you had experienced it. <P :06> now we'll turn the lights back on and talk about loops. okay. so this is what i wanna talk about today. loops. we talked about loops a little bit when we talked about just algorithms in general without looking at computer code, we talked about algorithms we talked about, ways of_ we talked about the idea of writing down steps of instructions which will then be executed by a machine. carried out by a machine to, solve some interesting problem. and we mentioned sometimes you wanna loop. you wanna repeat something over and over. subject to some control. so these are used to repeat a set of instructions over and over. and we'll sort of call out three particular kinds of loop. and i'll list them now and then we'll describe them in in a bit of uh of detail, there's something called a while loop. and by the way, you'll find words in_ you'll uh_ i'm gonna use words while do-while for you'll find these words in C. but i'm not talking about C i'm talking about, algorithms in general. okay the while loop is a, a fairly standard construct, in, developing algorithms. as is something called a for loop as is something called a do-while. the names vary a little bit, but the ideas of what they do are the same. what the while loop lets us do is, execute a bunch of code over and over as long as some condition is true. so it executes some code over and over as long as some condition is true. at the top of the loop. okay? and i'll fill in what that means a little bit in a minute. what's a condition? well we already know what conditions are we've seen conditions when talking about branching constructs. if X is less than Y that's a condition do-while. this is exactly the same as a while loop except the condition is is checked, at the bottom of the loop. so it executes some some code, over and over as long as some condition is true. at the bottom of the loop. it's basically the only way they differ. one of them is checking something at the top and i'll show you what top means but it's, the top of the loop, the other is checking at the bottom. is at the bottom, of the loop. then there's a thing frequently called a for loop or a counting loop and what the for loop does is it repeats, a chunk of code over and over, a specified number of times. so it repeats a block. that's an ugly M this does not exhaust all the different kinds of loops there are because everybody comes along and he says, oh you know i use_ i organize my loops this way all the time i think i'll, sort of make that a new structure. for example when we look at Matlab Matlab has something called a for loop, but it's really like what most languages call a for-each loop. but we'll see that in the fullness of time. for the moment, if i can say that, for the moment think about for loops as, loops that simply repeat something a specified number of times. let's look at a, a while loop... here's what while loops look like. not what C while loops look like just what the idea of a while loop looks like. we have some condition and while it's true, i execute some block of code, called the loop body. we loosely refer to this as the top of the loop, sort of right above the loop body and this is the bottom of the loop. what this thing does is, i come into this loop this is a step to execute, this is a, a task to do, i check some condition. and that can depend on, quantities that i've just calculated these are_ this condition, isn't determined, a priori it's determined as the program runs. i come into this loop i check the condition. if it's true, i do this work whatever it is. (okay and) i come down to the bottom of the loop, i come back to the top of the loop, and i check the condition again. and if it's true i do this. do this work. i get to the bottom of the loop i come back to the top and i check this condition again and if it's true, i do this. so i keep doing this over and over, until eventually i do this i come to the bottom of the loop, come back up here and the condition is false. then i don't do this i'm just done with this whole... construct and i go on to whatever my next instruction is in my algorithm. so i keep executing this loop (xx) as long as the condition is true, at the top of the loop. doesn't matter if the, condition becomes false in the middle of the loop, i only check it at the top. that sometimes leads to some confusion. only check right here at the top, doesn't matter what it does in the middle... such a beast easily leads to the dreaded endless loop. i could very easily, have some condition like while one is equal to one do this. then, i just do this forever. because one is never not equal to one, so, my condition's always true i just stay here forever. my program never exits uh, in the old days that sucked up your C-P-U allocation and and you uh crashed and burned and, it was real money. these days your computer just sits there and people... loosely say things like it's locked up, well it's not locked up it's just, doing that over and over. computers love to do things over and over. so i'll put a little arrow here, just sort of, saying those those semantics again... this body is executed over and over. until the condition is false at the top. i don't know what word that is but s- it's interesting. <SS LAUGH> if that condition is always true this loop runs forever. a condition that's always true is for example one equals one, or lots of others. it's very easy to, trap yourself. (you have) you have to watch for that very carefully. the loop will run forever, unless, maybe i can have an escape hatch. a very, a very useful thing to have in loops and something that that, most languages provide, um, is a way to jump out of the middle of this loop. and this is called breaking out of the loop. cuz we break out of the middle of the loop. somehow. and frequently we want to write code that does that i'll show you a sample of a code that does that. and so the general picture is i do this as long as this condition is true, but i might have an escape hatch in here in the middle someplace, where i might wanna say boy things are all bollixed up let's quit out of_ let's quit this it's not working and i might have someway to jump out. we'll see in C there's a statement called break, that does exactly that... let's write an algorithm with a while loop. i'm gonna write an algorithm to check primeness of a number. is primeness a word...? well i guess it's_ i guess it is a word cuz it's being tape recorded and it'll be put out in this big uh compendium and everything so primeness is now a word. it's my word so i can spell it any way i damn well please. <SS LAUGH> i'm gonna have a number i'm gonna call it, let me be consistent here i have a number i'm going to call it num ooh how original. i'm gonna check the primeness of num. sounds like the title of a science fiction novel. um... how am i gonna do this? i'm gonna write an algorithm to do this. i'm gonna first deal with the special case... if num is one, it's prime. okay and i'll be done, and i'll stop. if num is not one i'm gonna do something else down here. so otherwise num is not one. what i'm gonna do, it's not the slickest thing to do when testing for primeness but, it works and it will illustrate the idea, i'm just gonna take every possible divisor. from num minus one, num minus two, all the way down to one, gonna call these D, and i'm gonna see if i can divide this number by, that divisor. if i can divide, num, by a divisor, and that divisor is not one, then the number is not prime cuz i just divided it by something. so let me set this up, D will be my divisor, i'll let it start, at num minus one, i don't wanna check num because i know num is divisible by num... um, so i'll start one less, and then i'll do a while loop. while, num is not divided by D, okay so there's my condition, while the number is not divisible by my divisor, check the next divisor, and i'll simply do that by saying, go down by one. <P :07> so i'll come in here, let's give a an example, say num is ten, i'll come in here i'll say my first divisor is nine... is ten divisible by nine? no... so num is not divisible by nine so do this go on down to the next divisor eight. okay? is ten divisible by eight? no, go on down. eventually, it'll have counted down to is ten divisible by five? you betcha. so i'll have, i'll've come in i'll set D to five come to the top of the loop and i'll check this condition. is ten divisible by five? yes. okay? so the condition's not true num's not divisible by D and i'll fall out of the loop. i'll be done. once i'm done, i just wanna find out what D is. if D is one, lemme not write it that way, lest it confuse with C syntax, then num was prime. otherwise it's not. if D is not one then D is bigger than one and, it's not prime. oh i'll squeeze it in here. otherwise not prime... the reason i'm guaranteed that this loop will finish is i know everything's divisible by one. eventually this divisor will be one, we'll have walked all the way down to one then i'll get out of this loop because num is divisible by one. so i don't have i don't have any concern about the endless loop, and when i'm done i can_ i actually have two interesting pieces of information. i know if this num is prime or not and i actually know its largest divisor. cuz i fall out of this loop soon as i find a divisor of num. so let's look at the lovely C code to do that there we go (wonder if i) (xx) see if this is readable, otherwise (xx) this looks okay. okay here's some C code to do this... and now i've gone from my algorithm to C code and that means i have to deal with all of the, annoying details you have to deal with, when you're writing, real code, so, i have to, include header files like S-T-D-I-O-dot-H i have to declare a main function i have to do all this garbage which only exists for the computer and not for my algorithm... i print out using print-F i ask the code to uh_ the code asks for a positive number, uses scan-F to get that number <P :05> scan-F percent-I ampersand num, so i read in a number right there, if the number's negative or zero, code stops, okay? that's sort of all just details of getting information in. here's where the real algorithm starts there's the special case. if one equals num, print out that it's prime and we're done. <P :10> here's the rest of it <P :06> oh look i don't have a laser but i have a red crayon <SS LAUGH> initialize the divisors first set D to num minus one, and then here's the while loop. this is C's version of the while loop this is how you express the while loop in C. while parens, condition, then a block of code between an opening bracket and a closing bracket. inside that is the loop body which is just D equals D minus one. the condition says, num percent D not equal to zero. well num percent D that's the divisor of number num divided by D, if that's zero they divided each other, and i wanna stop. if that's not zero, there's a remainder, D_ num is not divisible by D and i keep going. once i'm done, i have this if that i have down here. if D is bigger than one, print-F, uh such and such is not prime, and i actually also print out D, because it's the largest divisor. of that number. so that's interesting. if D is uh, equal to one, then i'm in the else clause down here and i print out that the number is prime. <P :21> compile this beast <P :05> notice... you've got Visual Studio you've got the command-line version of Visual Studio which you called C-out, showed you C-C at the beginning of the class, on some of the machines. my compiler was called E-G-C-S which is pronounced eggs, the guy in the back of the room won't like that. um, there are lots of C compilers they're all made by different people but they all do the same thing. okay i've compiled my program i can run it. it asks for, a positive integer, i give it minus two. so it doesn't do anything. it looked and it saw i gave it minus two and it's_ didn't uh_ refused to check its primeness. let's give it an interesting number twenty-three, checks if it's prime it says it is prime. okay well everybody knew that. but how about one thousand two hundred and three? well it's not prime it's divisible by four hundred and one as everyone could immediately see. <SS LAUGH> okay. okay so the point is the code works it does what i say, it doesn't do_ it doesn't wor- i don't know that it works because i ran it on a couple of cases and it came out right. i know that it works cuz i've looked at this algorithm and i've thought about it. and i'm sure that that algorithm, will find primes... i don't care how many times i run a test through this code, i'll never be sure. but if i look at that algorithm carefully i can be sure about it. <P :07> and it's a nice usable while loop. so once again, i have this piece of code, not a complicated piece of code in this case, but it could be as complicated as you want i can put anything in there. piece of code that i wanted to be executed as long as a condition was true. lemme show you another code with a much more complicated thing inside this while loop. okay? and and i'm really excited by prime numbers today, so i'm gonna show you another prime number code. <P :08> this one i think it should do (xx) the code i just showed you, um, it asks for a number, you give it the number, it checks if it's prime, if it's prime it says yes if it's not prime it says no, and then it ends. well maybe i'd like to check a lot of numbers for primeness. what i would like to do then, is write a code that looks like this. <P :10> <COMPUTER COMPANY WEBSITE ON OVERHEAD> by the way i do not get any money for these shameless advertisements sorry about that. sorry that i don't get money and sorry that i'm exposing you to shameless advertisements... <P :06> here's the way this code is gonna look, now this code in some sense is is is less pure as an algorithm cuz really what i wanna deal with is some, issues of interacting with the person. i wanna write a code that looks like this. i want this one to, keep asking for input, until the uh, human running the thing inputs garbage. so i'm gonna write a code that looks like this now. get num from human. that's an interesting phrase. um while num is positive, check to see if it's prime lemme actually number the steps inside here just so you can see them distinctly. and then after you've done that, get another number. it's gotten another num from the human, and it checks if it's positive or not. if it is, checks if it's prime, and asks for another number. and just keeps going. what makes this loop stop? the human types in something that's not positive or else is gibberish. so we get out of this loop when, the number that comes in from the human is not positive... now... this is a few lines of C code involving some scan-Fs and print-Fs, i didn't write them out in detail here cuz i don't care about those details when i'm thinking about my algorithm. same with this these are pretty much the same lines. this is interesting what goes here? that. right there. the whole thing. essentially as is... now, i'm not gonna write it in here, because that would obscure this if i had all that detail written right here, it would be harder for me to look at this and be sure it's right. now it's not too bad it's not really very many lines, but here is a task all of its own, and i really don't need to think about how this task occurs, while i'm, describing this task. i just need to know_ somehow i need, a way to check if a number's prime or not. okay? i want to think that way i want to separate, problems that can be separated, the human mind is finite and i can't think about everything at once. neither can you. <P :07> let's plunge ourselves into darkness once again, and look at this new code called prime loop. or prime loops or something like that. <P :20> okay all the standard garbage include standard I-O start main somehow declare some variables num and D, then print-F input a positive integer negative to quit in in large red letters. it scans that in. now notice what i'm doing. this is a C detail not an algorithm detail but it's an important one... scan-F percent-I address of num so i ask, the uh machine to read input from the keyboard, and try and interpret it as an integer. if it succeeds... scan-F will return one. so i can check, did scan-F equal one or not? if it did i'm okay but if it didn't, the user typed gobbledygook. okay? what i do in that case right here is i set num to minus one. because that'll force the rest of the code to quit. so i check whether scan-F worked or not. that's pretty important when you_ when a human is typing input into the machine. cuz humans sometimes make mistakes... then... below that, here's this big while loop. it's this loop. it's just this loop. while num is bigger than zero, now i threw in some bells and whistles, print out some information and stuff but it's really just this loop, while num is bigger than zero, and then, all of a sudden we see this task. check if the number's prime or not and it looks exactly like this. check the special case of num equals one. set D to num minus one. do this while loop while w- while num percent D is not zero. reduce D by one throughout_ through that loop. when i fall out of the bottom of that loop, i know if uh the number's prime or not, and i print out that answer. so i've literally, cut and pasted the C code that i wrote for this, and stuck it right into this step. <P :07> once i know if the number is prime or not it's time to get a new number. <P :05> if one is not equal to scan-F then scan-F tries to get a number from the keyboard. if scan-F succeeds it returns one cuz it read one number, nothing happens here, i'm at the end of the outer while loop, i go back up, make sure the number that came in is positive, find out if it's prime, get another number, end of the outer while loop, go on up, check the number's positive and so on. on the other hand if scan-F failed here, cuz somehow someone typed gobbledygook, i execute a statement called break. i said we could have an escape, a little escape hatch from inside a loop, and here's an example of it. that's why i wrote it this way, just to show an example of break, if scan-F didn't get a good number, we should just quit. what this break does is jump out of the enclosing while. so it jumps out of this loop, and we're done we execute the statements that follow which just print quitting, and finish up... couple of things one, i have a while loop inside a while loop. i can have while loops inside while loops inside while loops. i can put loops inside each other. that's frequently very useful, for a lot of things we do it is, crucial. you can't do a lot of, very interesting things without putting loops inside loops. all i've done here is, put, this loop, inside that loop. second was the fact that once i had this, i made sure it worked i knew it worked, i could pretty much, chuck it right in here, and i knew that any errors i had with this code would be due to this other stuff, not this. i trusted this step. this step was right. oh let me run that code, so let me once again plunge us into darkness <P :05> cuz i especially want to show you what happens when i input garbage. what i'm talking about. okay input a positive integer. alright, uh twenty-three's good, says it_ is it prime it checks, okay i- it did this. it did this it did this it told me that it's prime, and now it's down here. and i give it another number. hundred and twenty-seven, boy i'm good at picking primes aren't i? it got a number, went up to the top the number was positive so it checked if it's prime or not, and told me. and now it's sitting down here again waiting for another number. hundred and twenty-three, it's not prime... i input a hundred and twenty-three we went up here it's positive it checks if it's prime or not, it says oh oh i'm s- uh, a hundred and twenty-three is not prime it's divisible by forty-one. now if i put in say minus thirty_ twenty-three it quits. okay because it's set up, the following way. it just read minus twenty-three, it went up here, asked is minus twenty-three positive no, so don't do the loop body just jump down we're done with this step do whatever comes next. <P :06> let's run it again, i'm very curious about uh ten thousand two hundred and thirty-four, darn, it's not prime, asking for a positive integer. now, what prevents me from typing this? A-W-F semicolon oids, okay which i type all the time, nothing prevents me from typing that, and nothing prevents that from getting sucked in to this step right here. get num from human. that's done with that scan-F. but the scan-F easily looks at, A-W-F semicolon oids and says, you are not a number. and so that, scan-F does not return one it did not read a number, and i hit that break statement. i jump out of this loop, right here, and go on to the next step. okay? very important to check your_ the return from that scan-F. if i hadn't checked the return from that scan-F, this code would actually enter an infinite loop and run forever. i'd lose all control. okay? yeah. 
S2: what if you write uh one hundred and seven A B C (xx)
S1: tell me what you want?
S2: one hundred and seven A B C.
S1: one hundred and seven A B C that's actually a good question. what's it gonna do? <UNINTELLIGIBLE ANSWERS SS> no it's not gonna quit it's gonna find this number. it's gonna ignore this junk, but when it_ when scan-F starts looking for a number i told it to look for a number it just looks for digits until it sees something that's not a digit, and then it says okay that was the number, and it'll ignore this. it'll do a hundred and seven. okay?
S3: what if it was, one-oh-A-seven?
S1: i'm sorry?
S3: one-oh-A-seven?
S1: hang on on that one cuz it did something interesting. okay i told you it would do a hundred and seven and it did, hundred and seven is prime, and then it said input a positive integer where was it it was right here, and then suddenly it quit i didn't type anything. (xx) again. hundred and... make it exactly the same hundred and seven A B C. i will hit enter once, it'll tell you a hundred and seven is prime and quit. what did it do? well it saw tho- the digits one zero seven, then it saw something that wasn't a digit but took a hundred and seven as a number, everything was cool, then it went back to read more information. well that A B C doesn't disappear. that A B C was w- sitting there waiting to be read in. it started trying to read a number, immediately got A and it said, this isn't a number, can't read a number. and it stops. okay...? sorry yours was 
S3: one-oh-A-seven
S1: one-oh-capital-A-seven. any predictions? <UNINTELLIGIBLE ANSWERS SS> ten is not prime and stop. because it's gonna read this number, s- it looks at this oh that's a digit cool, that's a digit cool, that's not a digit that must be the number, ten, then that A doesn't go away it still sitting there waiting to be read. so right here i read ten, it's positive i check that it's prime it's not, right here i then, try and get more input, and it actually reads that A, and says, this is not a number, quits. okay? yeah.
S4: can we go back to the C code (issue) (xx) [S1: sure ] the um, scan-F thing i don't quite understand how that's working. [S1: this is_ ] how is i mean 
S1: we need two of these that's what we need. here's the deal... scan-F <P :05> some of this is detail that that uh, a li- i'm gonna give you a little detail that we're gonna talk about again later, um cuz some of this is detail about the way, C, ANSI-C is structured to treat data coming in. we have this scan-F... oops i turned the lights up too bright you can't see sorry... let's try this is that readable? the i- the idea behind these lights was we could use the blackboard on the edges and still read that i don't know if it worked. the code comes to this point scan-F percent-I address of number. what that makes it do is it starts reading every key i press. okay like one two three A B C. scan-F has been told cuz i told it look for a number. look for an integer. well that's part of an integer that's part of an integer that's part of an integer, this is not. so it stops reading data, after it's read that, and it's got a hundred and twenty-three. but i pressed those keys. that data is still sitting there waiting to go into the code. has to do with the way C actually is structured to treat data coming in it just has these, characters flying in at it... okay? so, it knew to stop reading the number cuz it saw an A but it's still waiting because maybe the next thing you're gonna do is ask for a character. ask for a letter. in this code the next thing we do is, we go around the loop, and we hit this again. so i've told it to look for an integer, the next thing coming in is the A that i already typed. and nothing is forgotten nothing is thrown away. it reads the A and it says that's not the start of an integer. i'm being given garbage. so scan-F fails it reads nothing. it does not put any information, in the place where this variable stores its bit pattern, doesn't read anything doesn't put anything there. instead this function returns a value, of zer- of um, zero. i really should check that but it doesn't return one that's the important thing. it's either zero or minus one i forget.
S5: what if you type a space, between one of those?
S1: hang on a second. um, so the point is that scan-F returns a value and this whole bit of text right here, scan-F double-quote percent-I comma ampersand num close-parens that whole thing evaluates to, zero cuz it didn't read anything. one is not equal to zero. that's a true statement so, i get out. something bad happened. <P :06> you nee- you may need to go and actually play with this code and look at it a little to see this. <STUDENTS GETTING UP TO LEAVE> lemme answer this guy's question.
S1: i was just asked what if i do this one twenty-three space A B C. any predictions? <UNINTELLIGIBLE ANSWERS SS> what? [SU-M: put in another (xx) ] whoa whoa whoa whoa whoa. silence silence. what? put in another [SU: (xx) ] oh after the space? [SS: yeah ] oh okay that's good. <P :05> seven space five. tells me they're both prime. okay? it read the seven, it saw the space it knows that's not part of a number so it got seven, it came around the loop, tried to read another number, the five was already sitting there. there's actually nothing very magical about pressing that return key. oh there was a hand up over here. 
S6: do a decimal. 
S1: what? 
S6: try a decimal. 
S1: alright. one last test for those who wanna stay. <P :05> uh how about ten point two. it gets to ten, it sees the period, the period is not part of an integer, stops scanning the ten, got the ten, comes around again, trying to read an integer it sees a period. period is not part of an integer it quits. 
<STUDENTS LEAVE SS> 
{END OF TRANSCRIPT}

