Close

Theorizing again

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 07/28/2021 at 05:060 Comments

While I try to build up some serious and massive computing capabilities with FPGA and Raspberry Pis, old questions still remain and although I don't have a complete Maths education, I do have what I'll call "heuristics" that indicate some serious hypotheses.

Let's start with the whale in the pond: knowing how to get N+1 from N with the iteration formula, and vice versa, how come I can't directly get N+2, N+3 and by extension N+x directly ? After all the formula is linear and could be handled with a modulo. This is just some modular arithmetic, right? But the carry changes everything. My conjecture is that there is no formula that provides N+x directly (for large x), or at least with a significant saving in computation quantity and complexity. And this is why, ladies and gentlemen, I keep iterating "the long way", cycle by cycle. It may not be the definitive, best and fastest method in theory, but it's simple, stable and gets you there in a somewhat deterministic time.

Let's go back to the basics: the Pisano period. With a modulo 2n, we know the period is 1.5×2n. We also know how to get the Fibonacci's Nth number, so let's just compute it, apply the modulo and call it a day. The Nth Pisano number can be calculated for any N with a fixed number of operations.

However, PEAC uses the carry, which in itself is not easy to predict or put in a formula. And every time C=1, the next cycle will compute the Pisano series but with modulo 2n-1! About half of the steps of each orbit will be in some Mersenne world and "pseudorandomly" switches back and forth between moduli. Which explains why there is this duplication of states on the diagonal.

Another way of visualising this is by looking at the discrete vector space of Pisano. The wraparound rule is simple: on overflow, the trajectory exits on the right and returns on the same line on the left. There is one main orbit that scans only a limited number of states, but many, many more orbits exist. What PEAC does is simply add a little twist to the wraparound rule: return on the left but on the line below. In the good cases, this shift "connects" arcs belonging to different, independent orbits. In a more topological way, we could describe the Pisano world as torus, while the PEAC world as a twisted torus, something like Moebius' strip.

Now, how come only certain sizes connect all the sub-orbits while most don't? I don't have the answer (yet) but the above should give you a taste of why PEAC is something way beyond the already puzzling Pisano cycles: the seemingly random switch of moduli makes it impossible to use a deterministic linear formula or even algorithm.

Discussions