For this lab, you will modify a CPU program so that a portion of it runs on the GPU instead. The program tests something known as the Collatz conjecture which states:
Take any natural number $n$. If $n$ is even, divide it by 2. If $n$ is odd, multiply it by 3 and add 1. If you repeat this process long enough, $n$ will eventually be equal to 1.
This conjecture has never been proven, but a counter-example has never been found. Different numbers take a different amount of steps to reach 1, but they always do.
The following program tries the Collatz conjecture on all numbers up to 50,000. It then prints the one which took the largest number of steps to reach 1.
#include <stdio.h>
#include <stdlib.h>
#define N 50000
/* run the collatz conjecture and return the number of steps */
unsigned long collatz(unsigned long x) {
unsigned long step = 0;
/* do the iterative process */
while (x != 1) {
if ((x % 2) == 0) {
x = x / 2;
} else {
x = 3 * x + 1;
}
step++;
}
return step;
}
int main() {
/* store the number of steps for each number up to N */
unsigned long steps[N];
/* run the collatz conjecture on all N items */
unsigned long i;
for (i = 0; i < N; i++) {
steps[i] = collatz(i + 1);
}
/* find the largest */
unsigned int largest = steps[0], largest_i = 0;
for (i = 1; i < N; i++) {
if (steps[i] > largest) {
largest = steps[i];
largest_i = i;
}
}
/* report results */
printf("The longest collatz chain up to %d is %d with %d steps.\n",
N, largest_i + 1, largest);
return 0;
}
You should modify this program so that the collatz function is run on multiple values in parallel on the GPU.
$ wget "http://ianfinlayson.net/class/cpsc425/labs/collatz.c"
When you're finished, submit the source code to Canvas.
Copyright © 2024 Ian Finlayson | Licensed under a Attribution-NonCommercial 4.0 International License.