Close

Draft

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 09/12/2022 at 17:370 Comments

Quite a lot of my research used Wikipedia and it's likely that one day, PEAC will have its own page, so what should it contain? I've been collecting my thoughts lately and here is a first incomplete draft.


PEAC (algorithm)

PEAC is a modified Pisano sequence generator that uses ones' complement addition to handle overflows. Unlike the original Pisano algorithm, each time a sum exceeds the modulus value, the result is also incremented by one.

It is the smallest possible configuration of Marsaglia's Lagged Fibonacci PRNG "add-with-carry" algorithm and only certain moduli give a maximum length sequence. It is also comparable to a Linear Congruential Generator with no multiplier and conditional increment, but with two variables instead of one, following the Fibonacci additive structure.

When the modulus is a power of two, it is an alternative to GF(2) Galois fields in some applications :

Non-power-of-two, or generalised PEAC, have better mixing properties and could be used as part of a hashing algorithm, though they have basic inherent biases.

The maximal possible length period (or orbit) for a given modulus m is m^2  + m - 2 because the states all-0 and all-1 are degenerate but are never reached (when properly initialised). Binary PEAC of widths 3, 4, 10 and 16 bits have 2 symmetrical orbits of half this length and are useful in practice: the checksum built from the 16-bit PEAC wraps around after 2147516415 iterations over 16-bit words, or more than 4Gi bytes.

The naive iteration algorithm of Pisano sequences is:

t = X
X = X+Y
if X >= modulus then
   X = X-modulus
Y = t

The conditional subtraction of the modulus amounts to a modulo operation. The properties of the generated sequence is well studied and understood but practically useless. When the modulus is a power of two, the orbit length is only 1.5 times the modulus.

Instead, the PEAC algorithm performs

X = X + 1 - modulus

The conditional +1 ideally comes from the carry flag that is set in a processor's ALU if the sum in X overflows in a power-of-two configuration, making the process almost free.

PEAC shares only a few properties with Galois fields, mainly that only certain sizes provide useful characteristics, and maximal length sequences can be considered as a permutation of a monotonic sequence (because almost all values appear, and only once).

PEAC is defined by two numbers plus a carry flag in some configurations, which allows the generation of the value 0, unlike LFSRs based on Galois fields. The maximal length of a sequence follows a different rule, m^2+m-2, whereas LFSR only go to m-1.

Applications

As PEAC is not a field, it does not feature operations provided by Galois fields for example, such as addition and multiplication of two values or states. The only available operations are next and previous since the iteration is reversible, as it has only one result made from reversible operations. This forces a complete enumeration of all intermediate states when one requires the distance (number of steps or iterations) between two states. This can be viewed as a feature or a handicap depending on the context, for example PEAC can't directly replace Galois Fields for Error Correcting Codes (as used by BCH and Reed-Solomon codes) But there are at least 3 other applications where PEAC is an interesting alternative to Galois Fields:

PRNG

PEAC can be considered as the smallest possible Lagged Fibonacci PRNG with "add with carry" configuration. As such it features much shorter orbits but they are easier to study computationally and theoretically, as the only operation is one addition per word. This is barely more complex than a comparable LFSR while the latter only provides one bit per cycle.

A 26-bit PEAC can generate a sequence of 2^52+2^26-2 (  26-bit words with very few resources and may be an alternative to a similarly-sized LFSR (or bank thereof such as Mersenne Twisters) when throughput is required.

The study of the properties of this minimalist configuration helps determine the properties of the following derived configurations.

...


(to be continued)

I know the page can't be added because it lacks external references, but the latest French article is meant to help.

Discussions