Skip to content

ex1

Jump to bottom
ajd98 edited this page Apr 10, 2018 · 20 revisions

Exercise 1: C variables and functions

Like many programming languages, C enables the programmer to include variables, which can represent arbitrary values, and functions, which encapsulate some specific task. The C programming language is specific about the data type of each variable including the return type of a function and the types of a function's parameters. The data type of a variable must be declared before using the variable. Variable declarations consist of the type of the variable, followed by the name of the variable. For example, the follow creates a variable named my_variable of type int (an integer):

int my_variable;

Optionally, the value of the variable may be set when the variable is declared. Both of the following are valid C:

int a;
a = 5;
int a = 5;

If desired, multiple variables may be declared on a single line:

int a, b, c;

Just as the type of a variable must be declared, so must the type of the return value and parameters of a function be declared:

int
my_func(int a, int b, int c) 
{
  return a + b*c;
}

The above code indicates that the function takes three integer arguments and returns an integer.

Data types

C includes a number of built-in data types. The exact definition of each data type may depend on the architecture of the computer and implementation of the compiler; feel free to read the ISO/IEC C standards if you are curious. Take care when choosing a data type that it will behave as you expect. With this caveat in mind, the following table gives some rough rules for common data types:

Data type description
int Signed 16-bit integer (or greater), which can hold values between -215+1 and 215-1 (-32767 and 32767)
char An integer type that can contain the basic character set; typically 8 bits or larger
float A floating point number. Typically 32 bits.
double A floating point number, able to represent at least as many value as float. Typically 64 bits.
void An "empty" data type

A variable of one data type may be converted to another data type by casting, for example as follows:

int a = 1;
float b;
b = (float) a;

Loops and Conditionals

C enables the programmer to include multiple types of loops, including the for-loop, the while-loop, and the do...while-loop.

for-loop

For-loops may be used to iterate over a series of values. The for-loop has the following syntax:

for (initialization; condition; increment) {
   statements;
}

Here, initialization, condition, and increment should be replaced with relevant values. For example, we could compute the sum of the first 100 integers:

int i;
int n = 100; // The number of times to go through the loop
int sum = 0;
for (i=0;i<n;i++) {
  sum += i;
}
printf("%d\n", sum);

while-loop

The while-loop continues to run as long as a specified condition is true. In contrast to the for-loop, it is more commonly used when the number of iterations is not known in advance. The while-loop has the following syntax:

while (condition) {
  statements;
}

For example, we could use a while loop to compute the first power of two that is greater than 1000:

#include <math.h>
#include <stdio.h>

int
main (void)
{
  int exponent = 0;
  while (pow(2,exponent) <= 1000) {
    exponent++;
  }
  printf("%d\n", exponent);
}

do...while-loop

The do...while-loop is a variation on the while-loop in which the code inside the loop is always executed at least once. The syntax for a do...while-loop is as follows:

do {
  statements;
} while (condition);

To understand the difference between the do...while and while-loop, consider the following code:`

int i = 0;
int j = 0;
do {
  j = 1;
} while (i > 0);
printf("%d\n", j);
int i = 0;
int j = 0;
while (i > 0) {
  j = 1;
}
printf("%d\n", j);

Whereas the first example will print 1, the second example will print 0, since the code inside the while-loop will not be executed.

If-statement

To execute code only when some condition is satisfied, use the if-statement. The if-statement has the following syntax:

if (condition) {
  statements;
}

Optionally, the if-statement may be extended by including elif and else statements:

if (condition_0) {
  statements0;
} elif (condition_1) {
  statements1;
} else {
  statements2;
}

Here, statements0 will be executed if condition_0 is true. If condition_0 is not true and condition_1 is true, then statements1 will be executed. If both condition_0 and condition_1 are false, then statements2 will be executed.

An example program

Consider the following the program, which calculates n! for a specified value of n, and prints the value to standard output.

#include <stdio.h>

// Calculate the factorial of a non-negative integer.
int
factorial (int n)
{
  int result = 1;
  int i;
  for (i=n;i>=1;i--)
  {
    result *= i;
  }
  return result;
}

// Test the factorial function
int
main (void)
{
  // test some values
  int i;
  for (i=1;i<=20;i++) {
    printf("%d! = %d\n", i, factorial(i));
  }
}

Try compiling and running the above program. You should see something like the following:

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 1932053504
14! = 1278945280
15! = 2004310016
16! = 2004189184
17! = -288522240
18! = -898433024
19! = 109641728
20! = -2102132736

The first few values look correct, but how could 17! be negative? In fact, the result for each number greater than 12 appears to be wrong.

The problem that we encountered is an overflow, meaning that the size of the result is greater than the maximum value that the int type can represent. On the machine on which this code was run, the default size for an int is 32 bits, corresponding to a maximum value of 231-1 = 2147483647, which is less than n! for n > 12. As per the C standard referenced above, when the value of an operation exceeds the maximum size of the int, the value is wrapped back around to the minimum value of the int; this is how we end up with negative results.

We can fix the overflow by using a different data type. In addition to the int, a type exists called the long int, which also stores integer values but can (typically) store larger values than the normal int. The long int is guaranteed to represent values between 231-1 and -(231-1), and it may be able to represent larger values (on my machine it represents values between 263-1 and -(263-1)). To be sure that we can represent 20!, we actually need yet another type: the long long int, which is guaranteed to represent values between -(263-1) and 263-1, a range than includes 20!. We can modify our code as follows:

#include <stdio.h>

// Calculate the factorial of a non-negative integer.
long long int
factorial (int n)
{
  long long int result = 1;
  int i;
  for (i=n;i>=1;i--)
  {
    result *= i;
  }
  return result;
}

// Test the factorial function
int
main (void)
{
  // test some values
  int i;
  for (i=1;i<=20;i++) {
    printf("%d! = %lld\n", i, factorial(i));
  }
}

Note that the data type of the factorial function changed, along with the type of result. In addition, the format specifier for printf is now %lld, indicating a long long int. Compiling and running the above code should give the following result:

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
15! = 1307674368000
16! = 20922789888000
17! = 355687428096000
18! = 6402373705728000
19! = 121645100408832000
20! = 2432902008176640000

Practice

Try the following practice problems to get used to writing C code. If you get stuck, try searching online for help (this is an invaluable skill in coding!). You can also check the ex1/answers directory for working example code.

Problem 1: sums

Write a function that calculates the sum:

1 + 1/4 + 1/9 + 1/16 + ... + 1/n2

Find the value of the sum for n=10000. What do you get if you multiply the value of this sum by 6 and take the square root? (Note that you can use the sqrt function by adding #include <math.h> to the top of your source file. When you compile with gcc, add the -lm flag to include libmath.)

Problem 2: prime numbers

Recall that an integer p>1 is called prime if for each positive integer d < p, p is not divisible by d unless d = 1 (note that 1 is not prime). Write a function is_prime that takes an int as an argument and returns 1 if the argument is prime and returns 0 otherwise. Use your function to calculate the first 10000 prime numbers and print them to the terminal.

Problem 3: The Collatz Conjecture

Lothar Collatz conjectured that starting from any positive integer n, the sequence generated as follows will eventually reach 1:

an+1 = an/2 if an is even

an+1 = 3×an+1 if an is odd.

For example, the sequence starting with 7 is:

7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, ...

Though the conjecture has been demonstrated to be true by computational means for up to very large n, a full proof remains elusive.

Write a function collatz_stopping_time that takes an integer n and computes the length of the Collatz sequence starting from n before first reaching 1. For example, collatz_stopping_time(1) should return 0, while collatz_stopping_time(4) should return 2. Use your function to show that the Collatz conjecture holds for integers n with 0 < n < 1e+6.

Extra problem

If you are curious why someone might use C rather than Python, trying solving the above problems with Python, and see how much longer the code takes to run (you can use the time command included with most *nix distributions to do so).

Clone this wiki locally