/* ****************************************** 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