Close

Structure and extrapolations

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/27/2021 at 02:450 Comments

The last log 17. First image is a huge step forward because the 2D visualisation is not just cool-looking but also very information-rich. I will try to organise this new knowledge here, compare with what I knew or guesstimated before, and see where I can go from there.

We have seen that depending on the width parameter, different behaviours appear and not all are desirable. I'll only focus on the "interesting" ones, with widths= 3, 4, 10, 16... And from the little I have seen, I'll consider that their respective structures are identical, or at least obey to the same heuristics.

I expected something along the diagonal. There had to be something there to explain why the orbits had a 2^n + 2^m states, where m seemed related to n for various bit widths. Moreover, the very definition of the Fibonacci sequence says that Y gets the value of X after one step so X > Y, creating a sort of diagonal (with a slope of φ ?) ... But then, you have the wrap-around and carry, and when you keep swapping X and Y, you're simply oscillating around the diagonal line so some sort of symmetric structure had to happen.

Now, let's look at one small scale "model" of the kind of version that interests us, here with WIDTH=4 hence a size of 16. The coordinates are a bit unusual but you'll get used to it, and it's more a practical choice than guided by a theoretical constraint.

So you have a "raster scan" type of coordinates, with 2^WIDTH points horizontally, and 2^(WIDTH+1) vertically because the case of CARRY=1 must also be shown. The new 0 just appears in the middle of the rectangle, made of two squares...

The colour red shows the states belonging to the first orbit (going through 1,0,0) and the colour green show the second orbit. The darker colours correspond to the real orbits, while the brighter ones in the middle are the beginning of trajectories that directly lead to the corresponding orbit.

There are so many things to notice in this picture !

From there, we can expect these heuristics to work for different widths, as observed in smaller versions, if we are looking for an "ideal" configuration:

Given that the complementarity is expected in the ideal case, the first rule is enough to verify that one configuration is ideal. So there is no "mapping" to do, no memory to allocate, only an orbit to ride to count its length.

For WIDTH=16, that makes 2³¹ iterations, which takes approximately 1 second on a recent CPU. The number of states quadruples with each incrementation of WIDTH, so the running times would be :

17   4s
18   16
19   1 min
20   4
21   16
22   1h
23   4h
24   16h
25   3 days

And this can not run in parallel !

The search for even larger ideal cases is important, as any new lucky find would provide far longer periods for RNGs, better use of the entropy in the 32-bit registers, stronger protection against alterations... A wonderful find would be 31 because it would enable the use of the "sign bit" of a signed integer, instead of the carry flag, to compare instead of using the carry bit.

I can make small tries by adapting the existing code but this would not be practical after WIDTH=21. Which widths sound like good candidates ? Of course a "bad" version will terminate early but I need more hints to select the larger candidates. So I turn to OEIS:

https://oeis.org/search?q=3,4,10,16

So I guess I have to run the CPU for a night and get more data before I can make an informed decision for more candidates.

If I get a longer list of "good numbers", I can refine my search for the appropriate existing theory that might be underlying.

Discussions