Jan Kończak

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
===== Assignment 1 =====

**Deadline: May 31st.**



[[https://en.wikipedia.org/wiki/Collatz_conjecture|Collatz conjecture]] is an
open mathematical problem.
\\
It boils down to a question whether the following procedure will terminate for
any value of ''x'': 
<code c>
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
  }
}
</code>

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


~~META:
language = en
~~
Jan Kończak

User Tools

Site Tools

Page Tools
