Close

More mathematics

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 01/13/2022 at 04:430 Comments

Some astute observers might still wonder why I insist on taking the "long road", with explicit computation of all terms of the series, calculating all the steps of every (semi-)arc. Well, to the best of my ability and knowledge, it is NOT possible to easily predict the length of an orbit, to name a few of the many limitations I have found. And it is important to know why, since evaluating w32 is still a huge investment in time, resources and development.

Well, PEAC is a modified Pisano cyclic series, which itself is a Fibonacci series under a given Modulo.

From there, it would be easy to predict the behaviour of a system because Fibonacci is simply an exponential derived from a series with a growth of φ. φ is irrational so there can never be a precise value. The first main problem with predicting PEAC is the uncertainty between the integer/discrete value and the irrational-based prediction.

The Binet formula gives the value of the Nth Fibonacci number. It is great when you want to calculate this but is not easily adapted when we want to find a precise, different value, given a set of pretty stringent conditions.

There would be 2 adaptations to do :

And that's quite a mess... I don't have the maths tools to solve that kind of nasty equations.

However I can do some pen&papering where I observe the behaviour of small systems. As the system size increases, estimates get harder and harder, to the point of not being easily decidable.

There are several types of questions we may want to answer:

Let's start again with the very basics: the Fibonacci series is characterised by a growth factor of φ. The rate is thus φ raised to the power of the number of steps we want to walk. So it goes roughly like this:

F(n) = φ^n

More precisely, let's look at Binet's formula:

F(n) = ( φ^n - (-φ)^n ) / √5
     = ( ((1+√5)/2)^n  - ((1-√5)/2)^n ) / √5
     = ( (1+√5)^n − (1−√5)^n ) / (√5 * 2^n)

So far, so good. It's a well known matter.
The formula has been applied to real numbers and even complex numbers.

You could try to solve for F(n)=x for example.

Going from Fibonacci to Pisano is less documented however. Given a modulo m, this would be

Pis(n,m) = F(n) mod m
              = (( φ^n - (-φ)^n ) / √5 ) mod m

https://en.wikipedia.org/wiki/Pisano_period explains the period of the corresponding sequence using "general linear group GL2(ℤn) of invertible 2 by 2 matrices in the finite ring ℤn of integers modulo n." Ouch.

Given the period p=π(m), we get :

Pis(n,m) = Pis(n+p,m)

The system is turned from a linear/exponential to a discrete cyclic series. So we can reduce the study to the range of n = 0 to p-1

But how do we get π(m) ? What is the formula ? Obviously we are concerned by computer "words", of k bits, or k'th power of 2, and there is this special case:

If m = 2^k, then π(m) = 3×2^(k–1) = (3×2^k)/2 = 3m/2

This is well explained in the Wikipedia article and easy to test.

By definition, the Pisano series start with the Fibonacci numbers, until one of them >= m. The last numbers in the sequence are also easy to compute btw. And between these extremes, this is where the headache starts.

Binet's formula is less powerful here. You can "compute" the n'th value of the series but how can you know, for example, how many times a given value appears, or where ?

For example for the Pisano series of 2^4,

How can we determine, without computing every single value sequentially, how many times one value appears, or how many steps separate 2 identical values ? No trivial transformation I can conceive of Binet's formula can directly provide this insight. Trying to turn the formula into one that answers the above questions might unleash some elliptic curves or something crazy like this.

From direct calculation, we know that the equation

  ( (1+√5)^n − (1−√5)^n ) / (√5 * 2^n) mod 16 = 2

has 4 solutions... But how do you know how many exist ?

Going from Pisano to PEAC is even more weird. The +1 changes everything, not only by its very value, but also because it appear about every other time, with no clear pattern. This totally wrecks Binet's formula which was pretty linear, even for Pisano's formula. Still, everything adds up nicely in the end... So there is a rule without formula, it's chaotic.

If the increment occurs in a "random" way (unpredictible, yet with a sufficiently spread probability), then we could use "statistics", or a stochastic approach, or approximation. However this inserts non-determinism, or an error margin, that quickly grows, and very quickly overcomes the range of possible values, so the error bar is the whole range.

If we use a PEAC of width w (> 10 maybe), and we don't know its characteristics, at least there are 2^(2w-1) (first order) individual value pairs, but only approximately 2^(w-1) occurences of a given value. This means that if we only had an error of 1 per step, the error will reach the whole range of the numbers after only of the total number of states. Which is a significantly small ratio of w32... When the error exceeds the data, there is almost no hope of recovering any useful information.

It might be easy to determine special cases, but they are of limited use as soon as we want to extend the range of validity. We can exploit the properties of the diagonal, or even play with multiples of the original series of the first numbers (which are the same as the Pisano series). However, as soon as the numbers reach or exceed the modulo, things go totally crazy, because φ has lost any meaningfulness there.

Another limiting factor is computational complexity of transcendental numbers: https://en.wikipedia.org/wiki/Square_root_of_5 says that

As of November 2019, its numerical value in decimal has been computed to at least 2,000,000,000,000 digits

But 2 trillions of digits might still not be precise enough if you want to deal with w40 or larger. This also requires a huuuuge storage (a whole rust-plater HDD) and raising this to any meaningful power will amplify any imprecision. So computing w40 sequentially might be almost as fast as short-circuiting it, though computing √5 shows quadratic convergence...

I'm trying to explore some geometric perspectives/approaches but I don't see how it would work. Time will tell.

Discussions