Imprecision00:00
-
Last week, we saw in
imprecision.c
that1.0/10.0
does not in fact equal0.1
as expected. Well, actually it does equal0.1
, of course - but the computer gets it a little bit wrong. -
Computers only have a finite amount of memory, so they have to pick and choose what values they’re going to support.
-
If we only have 8 bits, we can only represent 256 values (and since we use one of those values for zero, the greatest number we can represent is 255).
-
Floating point values are stored a little differently, but the computer still only uses typically either 32 or 64 bits to store a floating point number - so it can’t possibly represent infinitely many values.
-
When we get these inaccuracies after many decimal places, we’re running up against the hardware limitations of the computer.
-
Paying attention to how numbers are stored in your code can be critical - this clip from Modern Marvels shows how disasters can result when numerical imprecision isn’t taken into account in high-precision systems.
Announcements11:57
-
Supersections this weekend; they will be filmed and streamed live for those unable to attend.
-
Problem Set 1 is live on the course website, and due next Thursday.
-
Office hours will take place Monday through Thursday this week.
C12:19
-
Let’s return to our canonical program from last time:
1#include <stdio.h> 2 3int main(void) 4{ 5 printf("hello, world"\n); 6}
-
Recall that
#include <stdio.h>
allows us to use the functions of the standard I/O library, written by other programmers in the past, and declared in a file calledstdio.h
elsewhere in our system. -
We introduced
main
last week as the analog of Scratch’s[ when [green flag] clicked ]
block. In C and several other languages, your first function must be calledmain
. We’ll explain later whatint
andvoid
are doing here. -
printf()
is a function that prints out a formatted string. It takes one or more arguments (also known as parameters or simply inputs). The first is a string - a word or phrase or even a whole essay - which you usually want to terminate with a\n
to ensure that the output ends with a newline. Subsequent arguments tellprintf
what values to fill in for any format strings (such as%f
for a floating-point number) that you included in the first string argument.-
\n
in the above is what’s known as an escape character - rather than being interpreted literally as a backslash and the letter n, it tells the compiler to do something else. In this case, that "something else" is starting a new line.
-
-
Semicolons indicate the end of statements, and curly braces delineate blocks of code (like the structures of control puzzle pieces in Scratch).
-
Volunteer Kopal acts as the
printf
function, accepting input from David (acting as thehello
program that callsprintf
) written on a piece of paper and writing the input given on the touchscreen, simulating the effect ofprintf
. -
Another volunteer, Ife, represents the
GetString
function. Kopal, asprintf
, writes "State your name" on the touchscreen. Ife then gets a name from the audience and brings it back. David stores the returned name, "Nik", in a variable calleds
(by writing it on a sheet of paper labeleds
). -
David now gives Kopal/
printf
a sheet of paper that sayshello, %s\n
and the sheet of paper containing the value ofs
. He fills in the name stored in the variables
, "Nik", in place of the placeholder%s
. -
This same model of message passing underlies all the code we write, as outputs of functions are passed as inputs to other functions and so on.
Types20:56
-
We’ve been talking mostly about strings thus far, but values in C can have a few other types:
-
char
, a single character (likea
or7
or%
), which takes up one byte, or 8 bits; uses aprintf
format code of%c
-
float
, a floating-point value (a number with a decimal point, like10.0
or3.14159
), which takes up 32 bits (four bytes);%f
-
double
, a floating-point number that takes up twice as much space as afloat
(so 64 bits/8 bytes); also%f
-
int
, an integer, also 32 bits/4 bytes, meaning that the largest integer we can represent is roughly 4 billion;%i
or%d
-
longlong
, a 64 bit integer (which can represent much larger values!); '%lld`
-
-
And from the CS50 Library, found in
cs50.h
:-
bool
, true or false -
string
, a sequence of characters
-
-
We can also use various escape sequences in
printf
format strings:-
\n
for a newline -
\t
for a tab character -
\"
to include a double-quote in the middle of aprintf
format string (since a bare double-quote would make the compiler think it had reached the end of the string!)
-
-
In the CS50 Library, we provide functions like
GetString()
,GetInt()
,GetFloat()
,GetLongLong()
and so on, that let you get input of a specific type from the user. These functions include error checking to prevent the user from providing invalid input.
Conditions26:41
-
Conditions have the following structure:
if (condition) { // do this }
-
The
//
in line 3 marks a comment, English words directed at yourself or other readers of your code. Lines starting with//
(or multi-line blocks beginning with/*
and ending with*/
) tell the compiler not to look for actual instructions here. -
There can also be two exclusive branches:
if (condition) { // do this } else { // do that }
-
Or three:
if (condition) { // do this } else if (condition) { // do that } else { // do this other thing }
-
Boolean expressions (the conditions inside the conditional) can be combined with
&&
as "and", and||
as "or":if (condition && condition) { // do this } if (condition || condition) { // do this }
-
Switches express the same thing as certain
if
/else if
/…/else
constructs, but can be more elegant and involve fewer curly braces. They provide no additional functionality that can’t be done with regular conditionals, but can sometimes be stylistically preferable. -
You can use a switch whenever all the conditions of your conditional would be of the form
expression == value
for the same expression but different values.switch (expression) { case i: // do this break; case j: // do that break; default: // do this other thing break; }
Loops28:01
-
One type of loop in C is the
for
loop, which has the following basic structure:for (initializations; condition; updates) { // do this again and again }
-
A specific example:
for (int i = 0; i < 50; i++) { printf("%i\n", i); }
-
In this case,
int i = 0
is the initialization of the loop, telling it to start counting at zero by creating a variable calledi
and assigning it the value0
. -
i < 50
is the condition of the loop: immediately after the initialization, and at the start of every step of the loop thereafter, the condition is checked, and the code in the body of the loop will only be executed if the condition evaluates totrue
. -
i++
is the update of the loop, which will be executed after the body of the loop to move to the next step. -
We’ve put
printf("%i\n", i);
in the body of the loop, so this code will print the numbers from0
to49
(not50
, because when we update toi = 50
, the conditioni < 50
evaluates tofalse
and the body of the loop is not executed). -
The curly braces are not syntactically required if the body of the loop is only one line, but we will always use them in class (and we request that you do too!) for clarity and to prevent mistakes.
-
Integer Overflow28:01
-
Just as floating point values have limits on their precision, integers have limits on the size of values they can represent.
-
For a 32-bit integer, the maximum value is roughly 4 billion.
-
When a binary number overflows, we go from a value like this (255 stored in 8 bits):
128 64 32 16 8 4 2 1 1 1 1 1 1 1 1 1
To a value like this:
?? 128 64 32 16 8 4 2 1 1 0 0 0 0 0 0 0 0
But this is still only an 8-bit value, so there’s nowhere to put the leading 1, and instead we get:
128 64 32 16 8 4 2 1 0 0 0 0 0 0 0 0
-
We can see the effects of these limits on integers in various software:
-
In the video game Lego Star Wars, the number of coins you can collect is capped at 4 billion exactly - from which we can infer that the original developer for this game used a 32-bit integer to store the user’s number of coins.
-
In the original Civilization game, each world leader was assigned an aggressiveness score, and Gandhi was given the lowest score of 1. If a nation transitioned to democracy in the game, the leader’s aggressiveness score was decreased by 2. However, the aggressiveness scores were stored in unsigned 8-bit integers (meaning they couldn’t be negative) - so decreasing Gandhi’s aggressiveness score to -1 had the effect of looping around to 255 (so Gandhi became the most aggressive leader in the game!)
-
The Boeing 787 would lose all power after 248 days of continuous operation due to an integer overflow in the control units of its power generators (the workaround solution is to reboot the plane more often than that!)
-
Loops, continued40:44
-
Slightly different from a
for
loop, we have awhile
loop, that merely depends upon a single condition which is checked before every iteration of the loop:while (condition) { // do this again and again }
-
Similarly, in a
do-while
loop, the condition is checked after every iteration of the loop (as indicated by the syntax):do { // do this again and again } while (condition);
Variables41:25
-
As we’ve discussed, a variable in C has a particular type, which must be declared when the variable is created. Here, the first line creates a new variable of the type
int
, and the second assigns a value of0
to it. The declaration of the variable and assigning it a value can happen as far away from each other in code as you like, but for clarity it’s best to keep them close together.int counter; counter = 0;
-
A more succinct way to write the above code:
int counter = 0;
Functions and Arguments41:57
-
Functions are followed by parentheses, which contain any arguments that are being passed to the function:
string name = GetString(); printf("hello, %s\n", name);
-
In
function-0.c
, we show how to define your own function:1#include <cs50.h> 2#include <stdio.h> 3 4// prototype 5void PrintName(string name); 6 7int main(void) 8{ 9 printf("Your name: "); 10 string s = GetString(); 11 PrintName(s); 12} 13 14/** 15 * Says hello to someone by name. 16 */ 17void PrintName(string name) 18{ 19 printf("hello, %s\n", name); 20}
-
Separating out this logic in
PrintName()
is a form of abstraction, hiding the low-level implementation details of how we print the name. -
Similarly, in
function-1.c
, we can use the return value of a function:1#include <cs50.h> 2#include <stdio.h> 3 4// prototype 5int GetPositiveInt(); 6 7int main(void) 8{ 9 int n = GetPositiveInt(); 10 printf("Thanks for the %i!\n", n); 11} 12 13/** 14 * Gets a positive integer from a user. 15 */ 16int GetPositiveInt(void) 17{ 18 int n; 19 do 20 { 21 printf("Please give me a positive int: "); 22 n = GetInt(); 23 } 24 while (n < 1); 25 return n; 26}
-
The
int
inint GetPositiveInt(void)
, as well as thevoid
invoid PrintName(string name)
, indicates the return type of the function. -
PrintName()
doesn’t return anything (it just prints a name to the screen, which is a side effect), so its return type isvoid
. -
GetPositiveInt()
returns anint
- the first positive integer value the user enters - using thereturn
command. Any non-void function must have a return value (if you don’t have areturn
command, your return value is assumed to be0
, for reasons we’ll discuss later in the course). -
In
return.c
, we have another example of returning a value from a function:1#include <stdio.h> 2 3// function prototype 4int cube(int a); 5 6int main(void) 7{ 8 int x = 2; 9 printf("x is now %i\n", x); 10 printf("Cubing...\n"); 11 x = cube(x); 12 printf("Cubed!\n"); 13 printf("x is now %i\n", x); 14} 15 16/** 17 * Cubes argument. 18*/ 19int cube(int n) 20{ 21 return n * n * n; 22}
-
In this case, this function both accepts an input argument (an
int
, which we’re callingn
) and outputs, or returns, a value.
Problem Set 149:18
-
On this problem set, you’ll implement in C an ASCII version of Mario’s pyramid (or a more challenging version in the hacker edition!)
-
You’ll also implement a greedy algorithm for determining the coins necessary when giving change, and investigate rates of water flow.