User Tools

Site Tools


Sidebar


Start


Teaching:

Feedback


os_cp:assignments

This is an old revision of the document!


Assignment 1

Deadline: May 31st.

Collatz conjecture is an open mathematical problem.
It boils down to a question whether the following procedure will terminate for any value of x:

typedef uint64_t natural_number;
void collatz(natural_number x) {
  while (x != 1) {                 // until you reach 1,
    if (x % 2)                     // if the number is odd,
      x = 3 * x + 1;               // multiply it by three and add one,
    else                           // else, if the number is even,
      x /= 2;                      // divide it by two
  }
}

For instance, collatz(3) will go through the following numbers:
      3→10→5→16→8→4→2→1
so it needs 7 steps to reach 1 from 3.
Notice that 32 needs only 5 steps, but 27 needs 111 steps.

Your assignment is to write a computer program that will take as an argument an integer MAX_STEPS and will run until it finds five smallest numbers that need S steps to go down to 1 for every integer S lesser than MAX_STEPS and larger than 10.

The program must be written so that it can be:

  • run multiple times in parallel,
  • stopped and started at will.

So, the program must use shared memory to store the results and disseminate the numbers to test among running processes.
Obviously, the results must be correct.

If the program is restarted with MAX_STEPS greater than for the first time, it shall print an error.

There is one strict performance requirement: several instances of the program must compute faster than a single-threaded brute-force program doing the same job.


Assignment 2

TBA

os_cp/assignments.1683675912.txt.gz · Last modified: 2023/05/10 01:45 by jkonczak