Even more orbits !

A project log for Pisano-carry Checksum algorithm

Add X to Y and Y to X, says the song. And carry on.

Yann Guidon / YGDESYann Guidon / YGDES 04/27/2021 at 05:110 Comments

With a new smaller program orbit_count.c, I try to check the length of the first orbit for widths larger than 16.

Remember what we have found previously : for the configuration to be "good", the first orbit must have at least 2^(width*2 -1) different states, or > 25% of all possible states.

The first 4 are disappointing:

22 and 23 might be interesting... I have no idea how long they'll run but it's good to have 4 cores on the laptop, so I can run 2 heavy tasks while writing this comfortably. However I can only run about 30G iterations per core per minute and w22 might run about 8800G (4h and half) and w23 about 35000G iterations (17h)...


Later :


Stay tuned. But so far I have not found another "good configuration". I'd love if Width=32 was good but for now there is no reasonable way to prove this except with the brute-force approach.

20210507 : computations started on 20210427 and now I must reboot my computer. Fortunately I have saved here some checkpoint values but I have no program that accepts them. Sigh.


OK it was  pretty straight-forward! I made orbit_resume.c  so I could resume the computations. Log on !


Note: the search runs on a i7-2620M CPU@ 2.70GHz (with boost speed claimed at 3.4GHz, only 3.2G if 2 cores are active). OK this is already 10 years old but the cache is 4MB and the speed is better than the i5 of the same generation.

Now the question is : how does Intel share the integer pipelines with its "hyperthreading" ?



Aaaand that's it for 27 ! After 291 hours, I got this:

Step 545082889469952 : X=55724991, Y=71769679, C=1 
Step 545151608946688 : X=34558478, Y=102388704, C=1 
Step 545220328423424 : X=31287111, Y=119884834, C=1 
Step 545289047900160 : X=86600095, Y=126472141, C=1 
Step 545357767376896 : X=131220743, Y=127310596, C=0 
Step 545426486853632 : X=61045646, Y=97472749, C=1 
Step 545495206330368 : X=103373142, Y=130537106, C=1 
Step 545563925807104 : X=60260964, Y=42478582, C=0 
Step 545632645283840 : X=78002777, Y=50383733, C=0 
Step 545701364760576 : X=60031805, Y=54709728, C=0 
Step 545770084237312 : X=53286963, Y=47886241, C=0 
Step 545838803714048 : X=14925605, Y=3740871, C=0 

Orbit length: 545.890.867.990.899

The end.
457702.88user 44.28system 283:27:08elapsed 44%CPU (0avgtext+0avgdata 1376maxresident)k
0inputs+0outputs (0major+57minor)pagefaults 0swaps

So the first orbit is only 6% of the desired length...