Close

More orbits !

A project log for PEAC Pisano with End-Around Carry algorithm

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

yann-guidon-ygdesYann Guidon / YGDES 04/25/2021 at 03:073 Comments

It seems that the Pisano-Carry configuration needs more theoretical analysis and exploration. In fact, it needs a whole theory, because I can't find any. So I'm starting to map all the state spaces for register widths <= 16. I might find something interesting to help explore further...

First, let's see the size of the primary orbits.

Width     states       length    ratio(%)
3            128           35     27.34
4            512          135     26.36
5           2048           84      0.41
6           8192          693      8.45
7          32768         1170      3.57
8         131072          115      0.08
9         524288         2600      0.49
10       2097152       524799     25.02
11       8388608      1046076     12.47
12      33554432      2062103      6.14
13     134217728       413028      0.3
14     536870912     66448450     12.37
15    2147483648       204484      0.001
16    8589934592   2147516415     25.0003

So it seems that the width of 16 bits is a magical value, a very very lucky one !

Another good candidate would be the width 10, with one orbit that is 2¹⁹+2⁹-1.

Less interesting candidates are 11 and 14.

The rest looks not promising at all.

It seems that the secondary orbits don't all start at the same index so let's further explore with orbits.c...

Width     states   orbit lengths  orbits joins  2nd index
3            128           2x 35     2     2x28      7,0,0
4            512          2x 135     2    2x120      3,0,0
5           2048         4,42,84    16
6           8192          6x 693     6   673,670
7          32768      10 to 1170    26
8         131072             115  too many
9         524288    130,200,2600   114
10       2097152          524799     2   2x523776    3,0,0
11       8388608  197 to 1046076     8
12      33554432   29 to 2062103    14
13     134217728  206514, 413028  too many
14     536870912  50 to 66448450     8
15    2147483648          204484   too many
16    8589934592      2147516415     2               3,0,0

So all the sizes do not behave like the others... Width 8 looks like a lost cause. 3, 4 and 10 look like scale models of the 16 version.

Note : for ALL the cases so far, points outside of the existing orbits lead to another orbit, there is no "trajectory" longer than 1 step.

UPDATE 20210913

New computations yielded some more precise results.

bit        orbit  orbit
Width Size count  lengths
 1     2     1     2
 2     4     2     9
 3     8     2     35
 4    16     2     135
 5    32    16     4,42,84
 6    64     6     693
 7   128    26     10 18 39 90 234 390 1170
 8   256   572?    115
 9   512   114     4,130,200,2600
10  1024     2     524799
11  2048     8     1046076,5844,179
12  4096    14     29,71107,2062103
13  8192   196     4, 206514, 413028
14 16384     8     50, 1328969, 66448450
15 32768  5251?    204484
16 65536     2     2147516415

.

Discussions

Yann Guidon / YGDES wrote 04/25/2021 at 04:34 point

Who has a 64GB PC with 1 or 2h of CPU time ?

  Are you sure? yes | no

Thomas wrote 04/25/2021 at 05:45 point

You need someone with access to machines-to-be-tested in a data centre. Just two years back I could have run a test on a machine with 32 cores and 768GB RAM...

Just a hunch: maybe a HLL can help?

https://en.wikipedia.org/wiki/HyperLogLog 

  Are you sure? yes | no

Yann Guidon / YGDES wrote 04/25/2021 at 16:58 point

with 768GB, I could go up to ...

8GB : 16 bits
32GB : 17
128 : 18
512: 19 bits

However such a size makes storage and transmission *hard*.

There is the possibility to use only 2 bits instead of 1 byte per state but then I will miss extra info such as the number of orbits.

I've slept on it and came to some heuristics to get the orbit structure without mapping the whole orbits in RAM, trading RAM for CPU time, and only recording states on the Y=0 column, like I did earlier.

Looking at HLL...

I'm not sure I get it but it is a different class of algo to learn :-)

It doesn't seem to be useful in my case but I'll keep it in mind.

Thanks @Thomas  !

  Are you sure? yes | no