meditationatae

Just another WordPress.com site

Clean vetted C program for Collatz total stopping time records (Updated)

So, I’m now advancing by 10 steps at a time by looking at the 10 least significant bits of an iterate `k’ of the starting number `n’. This is explained in some papers on verifying Collatz (look-up table method).

My look-up table is in two parts, two files of 1024 medium-sized integers, one per residue class modulo 1024, or 2^10.

I’m posting the source code here. It is faster, and gives the stopping-time to within ~= 10 iterates.

#define MAX 10000000000000000
#define MOD 1099511627776

#include <stdio.h>
#include <math.h>

int main(void)
{
long long n;
long long y[3];
long long newy1, y1rem, newy0, z0, z1, rem0;
long long newy2, y2rem, z2, rem1;
int index;
long long dd[1024];
long long ff[1024];
int steps;
double rec;
double ratio;
int j;
FILE *in1;
FILE *in2;
in1 = fopen(“/home/david/collatz/subproblem/SEPT/sept22a/ddfile”, “r”);
in2 = fopen(“/home/david/collatz/subproblem/SEPT/sept22a/fffile”, “r”);
for(j=0; j<1024; j++)
{
fscanf(in1, “%lld”, &dd[j]);
}
for(j=0; j<1024; j++)
{
fscanf(in2, “%lld”, &ff[j]);
}

fclose(in1);
fclose(in2);
rec = (double) 30;

for(n= 3743559067775 ; n< MAX; n=n+32)
{
y[0] = n;
y[1] = 0;
y[2] = 0;
steps = 0;

while(y[0]>2 || y[1]>0 || y[2]>0 )
{
index = (int) (y[0]%1024) ;

newy2 = y[2]/1024;
y2rem = y[2]%1024;
newy1 = y2rem*MOD + y[1];
y1rem = newy1%1024;
newy1 = newy1/1024;
newy0 = y1rem*MOD + y[0];
newy0 = newy0/1024;
z0 = newy0*dd[index];
newy0 = z0%MOD;

rem0 = z0/MOD;
z1 = newy1*dd[index] + rem0;
newy1 = z1%MOD;

rem1 = z1/MOD;
z2 = newy2*dd[index] + rem1;
newy2 = z2;

newy0 = newy0 + ff[index];
rem0 = newy0/MOD;
y[0] = newy0%MOD;

newy1 = newy1 + rem0;
rem1 = newy1/MOD;
y[1] = newy1%MOD;

newy2 = newy2 + rem1;
y[2] = newy2;

steps = steps + 10;
}
ratio = ((double)steps)/log((double)n);

if(ratio > rec)
{
printf(“%lld %d total steps, ratio is: %.12lf\n”, n, steps, ratio);
}
}

return 0;
}

[david@localhost sept22a]$ time ./totsptopTime93dd40mask.out
3743559068799 970 total steps, ratio is: 33.504820564191
4025611967935 880 total steps, ratio is: 30.320050817536
4163503537119 900 total steps, ratio is: 30.973200644718
4215658462911 880 total steps, ratio is: 30.271938068264
4313591831647 890 total steps, ratio is: 30.591769900798
4670866929823 880 total steps, ratio is: 30.165534251763
4733589547487 880 total steps, ratio is: 30.151747316281
4807218842719 880 total steps, ratio is: 30.135809942138
4947238968319 900 total steps, ratio is: 30.790441169684

Advertisements

Written by meditationatae

September 23, 2014 at 6:45 am

Posted in History

3 Responses

Subscribe to comments with RSS.

  1. Post scriptum: if you have ideas for improving speed, I’d be grateful to know. Also, I can post the two 1024-long arrays of small-sized integers, if anyone is interstested.

    meditationatae

    September 23, 2014 at 7:15 am

  2. Come to think of it, MOD is a power of 2. This means that number (mod MOD) and floor(number/MOD), etc. could probably be done more efficiently with the C language bitshift operators, which look something like >> and << .

    meditationatae

    September 23, 2014 at 7:33 am

    • It took me maybe 30 minutes to 1 hour, but I finished the C bitshift and “masking” with bitwise And (say) 1023 ; in C, num&1023 gives: number with last 10 bits of `num’, i.e. num modulo 1024 .

      The new program has been validated by the old one, the one without bit-wise C operators. The old program was stopped.

      That’s the update for now.

      ——————————————————————————————————————————-

      Memo-selfie:

      [david@localhost sept22a]$ pwd

      /home/david/collatz/subproblem/SEPT/sept22a

      [david@localhost sept22a]$ ls -l

      -rwxrwxr-x. 1 david david 7888 Sep 23 06:45 a.out <———————————— executable
      -rw-rw-r–. 1 david david 1945 Sep 23 02:44 backup_totsptopTime93dd40mask.c

      -rw-rw-r–. 1 david david 3841 Sep 22 19:47 ddfile } one of two files with 1024 small ints
      -rw-rw-r–. 1 david david 3588 Sep 22 19:47 fffile } ibidem.

      -rw-rw-r–. 1 david david 2466 Sep 23 11:39 Summary_sep23_11h39am_01a.txt <—— verification
      // compared to standard, old, program.

      -rw-rw-r–. 1 david david 1945 Sep 22 19:49 totsptopTime93dd40mask.c
      -rwxrwxr-x. 1 david david 8079 Sep 22 19:50 totsptopTime93dd40mask.out
      -rw-rw-r–. 1 david david 2069 Sep 23 06:02 totsptopTime93gg41mask.c
      -rw-rw-r–. 1 david david 2004 Sep 23 06:11 totsptopTime97jj42mask.c

      -rw-rw-r–. 1 david david 2067 Sep 23 06:44 totsptopTime98mm52Bmask.c <————- source code
      for executable `a.out' .

      meditationatae

      September 23, 2014 at 4:38 pm


Comments are closed.

%d bloggers like this: