/* ******************************************
Find a rolling average of the "delay" as defined here
http://www.ericr.nl/wondrous/index.html#part3
Except I define (3*n + 1)/2 as a single step,
though 4 lines can be uncommented or switched to make it 2 steps.
I will average the delays in each consecutive 2^k block of numbers
Collatz conjecture is the following...
Repeated application of following f eventually reduces any n>1 integer to 1.
f(n) = (3*n+1)/2 if n%2 = 1
f(n) = n/2 if n%2 = 0
For example, let's start at 9...
9 -> 14 -> 7 -> 11 -> 17 -> 26 -> 13 -> 20 -> 10 -> 5 -> 8 -> 4 -> 2 -> 1
You'll need a 64-bit computer with a not-ancient version of gcc
in order for __uint128_t to work. This gives a 128-bit integer!
Compile and run using something like...
gcc -O3 collatzCPUdelay.c
./a.out [log2(N)] [taskID] >> log.txt &
Numbers N to N + 2^k - 1 will be run for taskID=0,
so log2(N) >= 1.0 must be true.
The next taskID runs the next 2^k numbers.
The argument log2(N) will be converted to a double,
then 2^log2(N) will be converted to an integer.
To run many processes but only a few at a time, do something like...
seq 0 7 | parallel -P 2 ./a.out 50 |tee -a log.txt
The above example will run 8 processes (tasksID 0 to 7) at most 2 at a time.
(c) 2021 Bradley Knockel
****************************************** */
#include
#include
#include
#include
struct timeval tv1, tv2;
#define min(a,b) (((a)<(b))?(a):(b))
/*
2^k numbers will be run
k=30 will take around 3 minutes for a log2(N) just before overflow starts to happen
*/
const int k = 20;
/*
2^k2 is lookup table size for doing k2 steps at once
k2 < 37
*/
const int k2 = 15;
// Prints __uint128_t numbers since printf("%llu\n", x) doesn't work
// since "long long" is only 64-bit in gcc.
// This function works for any non-negative integer less than 128 bits.
void print128(__uint128_t n) {
char a[40] = { '\0' };
char *p = a + 39;
if (n==0) { *--p = (char)('0'); }
else { for (; n != 0; n /= 10) *--p = (char)('0' + n % 10); }
printf("%s\n", p);
fflush(stdout);
}
int main(int argc, char *argv[]) {
double log2_N = 40.0;
if(argc > 1) {
log2_N = strtod(argv[1], NULL);
}
int taskID = 0;
if(argc > 2) {
taskID = strtol(argv[2], NULL, 10);
}
const __uint128_t UINTmax = -1; // trick to get all bits to be 1
const int lenC3 = 65;
// calculate lookup table for c3, which is 3^c
__uint128_t* c3 = (__uint128_t*)malloc(lenC3*sizeof(__uint128_t));
c3[0] = 1;
for (int j=1; j