Close

A more convenient definition of arcs

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 11/28/2021 at 01:470 Comments

The last log ends on a fundamental question about the arcs and their dual/complementary nature. I wonder if one part of the difficulty comes from the initial arbitrary decision to define an arc as a sequence that starts and ends at Y=0, because the complementary becomes Y=MASK, so there are 2 tests.

This could be simplified with the condition X=Y because the diagonal is a special case: it is possible with both C=1 and C=0. The 2 exceptions are of course X=Y=C=0 and X=Y=MASK when C=1. This makes the loop stop 2× more often but still doesn't solve the problem, and I have already tested that 2 tests instead of 1 doesn't slow the loop down. Let's add to this that the condition X=Y is the next step to the condition Y=0 so we're back to the initial definition (though the value of C is ignored because Y=0 only happens when C=1, while X=Y is the only case with C with either value)

The real question is: what to do when an arc crosses its complementary arc, and how to detect it.

Another more fundamental question is "what direction" does the complementary orbit go, compared to its reference orbit ? I suppose it's the reverse direction because of the central symmetry. This could help speed up things as well because "going backwards" is possible but slower. Oh wait, it was already covered in the log Some more theory 7 months ago. The answer is no: both orbits "go" in the same direction, so computing one orbit (and arc) is the same as computing its complementary. See the following video

The code runs there: http://ygdes.com/~whygee/PEAC/a2_04.html

Do ALL arcs cross their complementary first, or can they finish sometimes without crossing theirs complementary ?

According to http://ygdes.com/~whygee/PEAC/a2_05.html, this is mixed.

For w4, the ratio of blue vs green is quite dramatic and it would certainly be more balanced for larger configurations. Indeed, for w10, look at http://ygdes.com/~whygee/PEAC/a2_06.html and see the ratio getting better, at 532/493.

In the context of a parallel, multithreaded scan, there is the possibility that an arc started, finds a complementary crossing and this crossing has already been started by another thread, so the first thread should be stopped anyway. This also makes it a bit more complex to pre-allocate a set of initial X to a thread, to be queued in advance to prevent stalls. But it sounds possible...

Discussions