Close
0%
0%

PEAC Pisano with End-Around Carry algorithm

Add X to Y and Y to X, says the song. And carry on.

Similar projects worth following
A purely additive, non-cryptographic, fast and minimalistic checksum/PRNG/scrambler.

The sweet spot is a 32-bit checksum with a pair of 16-bit registers,
- very small, using only ADD,
- without the flaws of Adler32 and Fletcher, yet the same size and complexity,
- as good as CRC32, which it may replace when the memory footprint is critical
- can't be 0-crashed
- very easy to implement in digital circuits as well as microcontrollers,
- suitable for the detection of trivial corruption in network packets or files.
- not patented
- "as is", inappropriate for cryptography (though could inspire someone)

If you wonder why, just click and read the log.

For the what, check Definitions as well as PEAC vs LFSR for a comparison.

The original algo/project name was "Fibonacci checksum" but it later appeared that it was not the most accurate choice because Leonardo Pisano (the real name of Fibonacci) is the name associated to the periodicity of the sequence under modulo. All I did was add the tiny detail of "end-around carry", or "1-complement addition", which changed everything.

 
-o-O-0-O-o-
 

As for how I came to this system...

In 2012, Piano Magic released their album "Life Has Not Finished with Me Yet". One song contains a weird repeating pattern...

Glen Johnson's lyrics are often cryptic and more evocative than objective, but any geek's mind would cling on this mantra at the end:

"Add X to Y and Y to X"

This is really weird but... Why ? What's the point in this obscure "song" with no precise theme or clear subject ? And what does it do ? This last question is the most easily answered : just follow the damned algorithm.

C'est parti...

X=1, Y=0
Y+=X => 0+1=1
X+=Y => 1+1=2
Y+=X => 1+2=3
X+=Y => 2+3=5
Y+=X => 3+5=8
X+=Y => 5+8=13
X+=Y => 8+13=21
Y+=X => 13+21=34
X+=Y => 21+34=55
...

No need to go further, most of you should have recognised http://oeis.org/A000045, the famous Fibonacci sequence.

This gave me a compelling idea to modify the old Fletcher & Adler algorithms, keeping their very low footprint and minimalistic computational complexity. Both of these well known algos use a pair of values and have a similar structure. The trick is that rearranging the data dependency graph provides the equivalent of a minimalistic polynomial checksum, because the result is fed back on itself, in a more robust way than Fletcher's algo.

At first glance, this new checksum loop's body becomes something like :

Y += ( X ^ datum[i  ] );
X += ( Y ^ datum[i+1] );
i+=2;

This loop body is totally trivial to unroll. As trivial is the design of the corresponding digital circuit. This early version seemed to contain the whole checksum entropy in the last computed value but now X and Y are part of the signature. And the really important enhancement is the use of the carry!

For superscalar 32 bits CPUs, the following code seems to work well though the missing carry hardware (and/or lack of language support) requires more instructions to emulate:

t = X + Y + C;    Y = X + data;
C = t >> 16;      X = t & 0xFFFF;

A more efficient variation exists which does not use a temporary variable:

C += X + Y;
Y = X + data;
X = C & MASK;
C = C >> WIDTH;

In this worst case, without support of a carry flag, that's 5 basic operations (not counting memory loads) that fit in 4 registers and 3 cycles, to process 2 bytes. Not too bad. I'll let you deal with alignment. But is it really safe or safer?

The following logs will show how the idea evolves and the performance increases, through discussions about carry wrap-around, register widths, scheduling, avalanche, parallelism, orbits, structure, and escaping black holes...

 
-o-O-0-O-o-
 

Logs:
1. The variable
2. Datapath
3. Adler32 weakness
4. Easy circuit
5. Periodicity
6. A promising 32-bit checksum
7. Progress
8. Why
9. Orbital mechanics
10. Orbits, trajectories and that damned carry bit
11. Two hairy orbits
12. How to deal with black holes
13. Anteriority
14. Moonlighting as a PRNG
15. A new name
16. More orbits !
17. First image
18. Structure and extrapolations
19. Even more orbits !
20. Start and stop
21. Some theory
22. Some more theory
23. Even more theory.
24. A little enhancement
25. sdrawkcab gnioG
26. Further theorising
27. What is it ?
28. A bigger enhancement
29. Going both ways
30. Can you add states ?
31. Please, GCC !
32. _|_||_||_|______|______|____|_|___|_________|||_|__
33. Carry on with GCC
34. A good compromise
35. The new non-masking algorithm
36. Add or XOR ?
37. A 32/64-bit version
38. Closing the trajectories
39. Stats about missed crossings
40. Application : Displace LFSR...

Read more »

gPEAC.2-131540.txt.gz

List of maximal and perfect orbits, from 2 to 131540.

gzip - 101.30 kB - 04/05/2022 at 02:03

Download

moduli_02.c

like moduli_01.c but can handle larger data, for m>65K

x-csrc - 1.17 kB - 01/29/2022 at 21:36

Download

mods.log

1880 first results with maximal or double-maximal orbit lengths

x-log - 40.00 kB - 01/29/2022 at 20:36

Download

moduli_01.c

check orbit length for non-power-of-two moduli

x-csrc - 1.14 kB - 01/29/2022 at 20:36

Download

fusion_20220109.tgz

contains dump7ck, pscan_10 and fusion, good enough to test up to w26.

x-compressed-tar - 7.13 kB - 01/09/2022 at 13:34

Download

View all 55 files

  • Currently in (French) kiosks

    Yann Guidon / YGDES7 days ago 0 comments

    I wrote a 16-page article about the dark art of checksumming and it is still in kiosks in France ! Here is the link to the editor's site :

    https://connect.ed-diamond.com/gnu-linux-magazine/glmf-259/l-interminable-quete-du-parfait-petit-checksum-analyse-comparee

    The article should become "free to read online" in mid-2023. It builds upon many of the subjects and data covered in this project and expands from there, I'd dare to say it's a "must read" if you're French and want to use/implement some checksum code. I'll see if I can make a short version in English somehow.

  • Draft

    Yann Guidon / YGDES09/12/2022 at 17:37 0 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 Marsiglia'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 :

    • the 16-bit wide version is an alternative to CRC32,
    • the 26-bit wide is a simple PRNG with more than 2^52 distinct states,
    • the 4 and 10-bit versions can be line scramblers/descramblers for serial communications for example.

    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. 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...

    Read more »

  • Do you speak (insert programming language name here) ?

    Yann Guidon / YGDES09/12/2022 at 00:09 0 comments

    My latest article is published and it's a killer !

    https://connect.ed-diamond.com/gnu-linux-magazine/glmf-259/l-interminable-quete-du-parfait-petit-checksum-analyse-comparee

    It will be fully open around mid-2023. It packs a thorough analysis of existing checksums to deduce/develop the structure and the theory of PEAC checksums. A must-read for anyone who understands French and wants to develop or implement their own checksum!

    So I looked around and found that PEAC was picked up by https://en.wikibooks.org/wiki/Algorithm_Implementation/Checksums. I'd like to contribute a coding example but so far I have only coded it in C, asm and JS. Who wants to make other versions of the checksum in Python, Perl, Pascal, ...Psomethingelse ?

    DavidCary, if you read this, here's a first snippet to add to the PEAC page:

    // PEAC16x2 algorithm, not unrolled.
    // Good practice : Pad the end of the buffer
    // with 2 words (can be 0) to increase mixing.
    
    #include <stdint.h>
    
    uint32_t  PEAC16x2(int len, uint16_t *src) {
      uint16_t X=0xABCD;
      uint32_t Y=0x4567,
        C=len;  // add the size of the buffer to the checksum
    
      while (len > 0) {
        C += X;
        len--;
        C += Y;
        Y  = X + *src;
        X  = C & 0xFFFF;
        C >>= 16;
        src++;
      }
      // return 32 bits
      return X | (Y << 16);
    } 

    The JavaScript version is almost identical, if we modify the declaration, the data types and the array indexing.

    // PEAC16x2 algorithm, not unrolled, in JS.
    
    function PEAC16x2(len, src) {
      var X=0xABCD,
        Y=0x4567,
        C=len,
        i=0;
    
      while (len > 0) {
        C += X + Y;
        len--;
        Y  = X + src[i++];
        X  = C & 0xFFFF;
        C >>= 16;
      }
      return X | (Y << 16);
    }

    What's next ?

  • New scanner record format

    Yann Guidon / YGDES08/18/2022 at 21:43 0 comments

    So lately I started tinkering with #YAMS and things started to get weird because the most important place where I would need a good sorting algo would be here, to manage the merging of the trajectories to rebuild the whole orbit(s). Previously I used the traditional sort utility which implies a specific type of encoding. See
    94. New packing: p7k
    95. New packing at work

    But if I have my own sorting infrastructure, not only I can simplify/compact the records, but I could also exploit some parallelism here and there, eventually avoiding sort completely.

    For now the goal is to reach w32 and this determines the format:

    1. uint32_t Xstart : range from 0 to 0xFFFFFFFF
    2. uint32_t Xend: range from 0 to 0xFFFFFFFF
    3. uint32_t Arcs: range from 1 to 0xFFFFFFFF
    4. uint64_t Len: range from 1 to 0xFFFFFFFFFFFFFFFD
    5. uint8_t Parity flag : 0 or 1

    Total : 21 bytes per record, down from 26, so the final log for w32 would be about 90GB. The last byte has very little entropy but it is required to check that w26 is perfect, not just maximal.

    Maybe the record could be reduced a bit by using variable-sized Arcs and Len fields, because they are pretty low at the start and increase in size with each pass of fusion. Xstart and Xend remain fixed (to ease sorting). I'm fine with variable-sized records because random access is not required here.

    Arcs ranges from 1 to 4 bytes (2 bits), Len from 1 to 8 bytes (3 bits) so there would be 1 bit left in a byte to signal the parity flag. So the minimum size of a record would be 11 bytes. The 2 remaining bits could help reduce the size further: with 3 bits, one can encode either the number of bytes, or a direct value from 1 to 4.

    The fusion program should be able to perform the sorts only, so partial logs can be preprocessed for fusion. The input processing would likely be decoupled from the output processing (usint pthread ?) to keep the whole program fast, despite all the I/O stalls. The sum of all the lengths should always be computed, to catch any flaw during processing.

    Edit :

    For w32, the Len field should be capable to hold more than 64 bits... so 4 bits are required to encode more than 4 bytes, because the orbit could be perfect...

  • Related ideas

    Yann Guidon / YGDES07/02/2022 at 10:54 0 comments

    Veritasium just uploaded a new video.

    And apart from the funny subject in itself, it contains a few related and pertinent ideas.

    First : it calculates the probability for any permutation to create a "loop", or "orbit", of length one half (or more) of the total number of items. So this is a first hint to find the distribution of "maximal" or "perfect" orbits, except that generalised PEAC are not random.

    Second : adding an offset to the items' coordinates changes the topology of the loops/orbits. And this is exactly what the carry does in PEAC.

  • Funnels and dead ends

    Yann Guidon / YGDES06/15/2022 at 09:00 0 comments

    I have not progressed much lately on this front but I just finished writing a new article, due for publication next month probably.

    In there, I develop a little new theory derived from Bob Jenkin's funnel principle, but applied to the dataflow graph of the checksums.

    a) is obviously the very flawed checksum algorithm.

    b) is the Fletcher algo, not quite there.

    c) is PEAC which differs from Fletcher by a very little rewiring of a feedback operand...

    How come the Fibonacci structure is not the de facto standard ?

  • Line scrambling with PEAC

    Yann Guidon / YGDES04/24/2022 at 11:51 0 comments

    One significant application for binary PEAC is for scrambling data over a serial link. LFSRs are the traditional candidates because, well, what else ? But their shortcomings are quickly prominent.

    State of the art with LFSR

    I'll let you browse Wikipedia for the references and definitions but here are the major purposes of a line scrambler :

    • Avoid long runs of 0s or 1s to ensure clock recovery
    • Spread the spectrum of the bitstream to ensure EMC compliance
    • Ensure "DC balance" (equal average number of 0s and 1s) to prevent saturation of magnetics coupling
    • Eventually allow the insertion of signaling symbols (such as in the 8B10B) for line management or flow control
    • Eventually transform binary symbols to other bases (ternary, quinary) for PAM3, PAM4, PAM5 physical encoding...
    • Eventually add a tiny bit of redundancy to provide crude FEC

    LSFR-based systems are used almost everywhere and are well characterised. Their ability to "crash" however is not as well covered but an example was given by Wikipedia where an old transmission protocol used a 7-tap LFSR that was trivial to attack: just transmit all possible sequences of the LFSR output, so that one (or more) packets would be all (or mostly) 0 (or 1) and the receiver can't recover the clock, leading to a loss of synchronisation and a failure of the link.

      The run length statistics may get worse if the data consists of specifically chosen patterns, instead of being random. An earlier scrambler used in Packet over SONET/SDH (RFC 1619 (1994)) had a short polynomial with only 7 bits of internal state which allowed a malicious attacker to create a Denial-of-service attack by transmitting patterns in all 27−1 states, one of which was guaranteed to de-synchronize the clock recovery circuits. This vulnerability was kept secret until the scrambler length was increased to 43 bits (RFC 2615 (1999)) making it impossible for a malicious attacker to jam the system with a short sequence. (64b/66b_encoding#Run_length)

    Modern links use 64B66B (that is : raw copy of the data and add a couple of signaling bits) followed by a 58-tap LFSR. The "clock crash" attack becomes practically impossible but then you have to deal with the possibility of sequences of 57 identical bits. From what I have gathered, another smaller LFSR or encoder is used again to further ensure DC balance. At this point the designers bet on the statistical properties of the data and channel to "push" the probability of an "adverse condition" to the "extremely unlikely" domain but it's still not impossible. Apparently, low encoding overhead seems to be more important to push the bit-per-symbol ratio.

      "The scrambler cannot guarantee that output data will never have a long run-length of 0s or all 1s, or other undesirable properties in communications, but does allow strong statistical bounds to be put on the probability of such events. Practical designs will choose system parameters such that a bit-error due to long run-lengths is vanishingly unlikely." (64b/66b encoding)

    Of course, LFSRs must run at the bit/line speed so a 10Gbps link requires a 10GHz LFSR. Same if you want to reach 40 Gbps and there, the available technology requires a parallel LFSR implementation, meaning that the poly is extremely sparse to allow operation at a low-enough ratio. With the IEEE proposal x58+x19+1, there are 19 layers of XOR to implement before the circuits becomes too complex, but basically this limits the slowdown to 1/19. For a 1GHz logic speed, the bit speed is at most 20Gbps, and the scrambler size (and power draw) is directly linear to the slowdown.

    One thing I was surprised to not find is a detection that the LFSR got stuck or "0-crashed", in order to restart it automatically. It would depend if the scrambler is additive or multiplicative but apparently, handwaving and reducing the risks down to statistics is the preferred engineering method.

    Links:

    https://en.wikipedia.org/wiki/Linear-feedback_shift_register#Scrambling

    https://en.wikipedia.org/wiki/Scrambler#Additive_(synchronous)_scramblers...

    Read more »

  • Just another hypothesis.

    Yann Guidon / YGDES04/12/2022 at 22:15 0 comments

    In a previous log (More questions on gPEAC) I evoked a hunch I had but nothing was explained. I write this log to close this gap.

    I suspect a mechanism that is somewhat similar to what I have seen with prime numbers, since I have studied algorithms (reverse sieves) to generate them. The common hints are

    • a density that follows a logarithmic probability (to be determined for PEAC)
    • Something to do with numbers moduli a prime number (2, 5 are identified)
    • there are exclusion rules that have one exception, which is the very first occurrence.

    From there it is possible to imagine a similar algorithm to detect which moduli are not going to give a perfect orbit.

    I should try the sieve with other prime numbers, as already suggested in another log.

  • Definitions

    Yann Guidon / YGDES04/12/2022 at 17:23 0 comments

    See also log 81. PEAC vs LFSR.

    _____________________________________

    General definition

    As the name says, PEAC is a Pisano sequence with the added twist of "End-Around Carry", where the sum is post-incremented when an overflow (or wrap around) occurred.

    The sequence is performed by simple iterations using 2 variables and only one parameter: the modulus (written m). Depending on this modulus, there can be one, two or more cyclic sequences, or "orbits":

    • When there is one orbit, which is the ideal case, the system is called "perfect" and its period is m² + m - 2.
    • When there are two orbits, which is still "good enough" for most cases, the system is called "maximal" (for historical reasons) and each of the symmetrical orbits has a period of ((m² + m) / 2 ) -1.
    • The other cases have not been named.

    There are a total of m² + m states but we don't usually count the degenerate states ("stuck points") at (0, 0) and (m-1, m-1). These values are avoided in PRNG mode but the scrambler and the checksum configurations are immune.

    The +m accounts for 2 cases where X=Y, so if only X or Y is looked at, its sequence of values has all the possible values from 0 to m-1, with a 1/2 bias for those limit values.

    Note: just like a LFSR, it is a purely linear iterative function that is reversible and can be unwound with a strategy similar to the Berlekamp-Massey algorithm.

    Binary PEAC

    For practical reasons, the first PEAC sub-family that has been studied has a width parameter w such that m = 2w.

    • widths w=3, 4, 10 and 16 are maximal, they have 2 complementary orbits.
    • widths 2 and 26 are perfect (26 still needs a computational proof though, but it is not a priority)

    This binary PEAC has a very straight-forward and efficient implementation in hardware and software, making it a sweet spot for PRNG, checsum and (de)scrambler. However it has poor mixing.

    Generalised PEAC

    Any other modulus is possible, and gPEAC are all the other moduli that are not a power of two. The operations are slightly less convenient for HW implementation but the high-level code is still quite simple and this uncovers some of the mathematical elements required for its analysis.

    With a higher "bit density" (just like with LFSR with "dense polynomials"), they have better mixing properties and might become an element for hashing functions.

    Here are 2 sub-families where we can tune the biases for a specific application (here: binary words). Other applications and constraints may lead to the creation of other sub-families. Note that the modulus should still be carefully chosen and the "spectrum" of valid values is sparse.

    Sqrt(2) moduli

    Sqrt(2) is an irrational value with a "good enough" bit density that can be easily scaled, making it appropriate for basic hashes. The other interesting property is that when the modulus is squared, the product is a power of two, suitable for a binary representation with the least bias. This makes it appropriate for indexing hash tables with dynamic size, where the MSB are masked off (or discarded).

    This type of moduli is under investigation at this time.

    Adjusted moduli

    A "perfect" modulus m has a period of m² + m - 2.  The extra m-2 can be a nuisance so a modulus of the form 2w- 2w-1 could absorb most of the bias and boost the mixing. This is only a speculation for now.

  • More questions on gPEAC

    Yann Guidon / YGDES04/05/2022 at 02:27 0 comments

    I just uploaded the file gPEAC.2-131540.txt.gz which contains the results of a long scanning campaign in early February.

    From 2 to 131540, there are 13646 maximal and/or perfect sizes, among them 3858 are perfect.

    I should plot the density vs value, and the gaps, or histograms thereof...

    One very interesting and unexpected find (already noted at wow.) is that :

    • Maximal (semi-perfect) systems have a modulus ending with the decimal digits 0, 1, 3, 4, 5, 6, or 9.
    • Perfect systems have a modulus ending with the decimal digits 0, 4, 6, or 8.

    Weren't we looking for some sort of pattern ? Well, there could be one and I included it in the latest scanner's code: scanning stops if the last digit is either 2 or 7 (with the exceptions of size=2).

    There is a blind spot however: the scan only cared for 2 cases but we would need the whole data, including the length and count of all the orbits, in order to "predict" if a given modulus is promising (at least we can eliminate some candidates.

    Let's review the actual moduli of the binary PEAC

     1 2 perfect (a noted outlier and exception)
     2 4 maximal
     3 8 maximal
     4 16 maximal
     5 32
     6 64
     7 128
     8 256
     9 512 (impossible)
    10 1024 maximal
    11 2049
    12 4096
    13 8192 (impossible)
    14 16384
    15 32768
    16 65536 maximal
    17 131072 (impossible)
    18 262144
    19 524288
    20 1048576
    21 2097152 (impossible)
    22 4194308
    23 8388608
    24 16777216
    25 33554432 (impossible)
    26 67108864 perfect ?
    

    From there we can know which powers of 2 to skip:

    27 134217728
    28 268435456
    29 536870912 (impossible)
    30 1073741824
    31 2147483648
    32 4294967296
    33 8589934592 (impossible)
    34 17179869184
    etc.
    

    Better : this can help with finding better candidates for the hash moduli.

    sqrt(2^33) = 92681
    sqrt(2^35) = 185363
    sqrt(2^37) = 370727 (impossible)
    sqrt(2^39) = 741455
    sqrt(2^41) = 1482910 maybe perfect
    sqrt(2^43) = 2965820 maybe perfect
    sqrt(2^45) = 5931641
    sqrt(2^47) = 11863283
    sqrt(2^49) = 23726566 maybe perfect
    sqrt(2^51) = 47453132 (impossible)
    sqrt(2^53) = 94906265
    sqrt(2^55) = 189812531
    sqrt(2^57) = 379625062 (impossible)
    sqrt(2^59) = 759250124 maybe perfect
    sqrt(2^61) = 1518500249
    sqrt(2^63) = 3037000499
    sqrt(2^65) = 6074000999
    sqrt(2^67) = 12148001999
    sqrt(2^69) = 24296003999
    sqrt(2^71) = 48592007999
    sqrt(2^73) = 97184015999
    sqrt(2^75) = 194368031998 maybe perfect
    sqrt(2^77) = 388736063996 maybe perfect
    sqrt(2^79) = 777472127993
    sqrt(2^81) = 1554944255987 (impossible)
    etc.
    

    But this is for now purely observational and 2^3=8 is an exception to the semi-perfect rule. I'm sure I miss something.

    So not only should I recompute these numbers completely, but also plot them to BMP and count the number of orbits, like I did for the videos.

    I should also examine the existing list with other bases (not just base 10, but prime bases, so maybe there is another link with Galois Fields ?) and understand why 2 and 7 are exceptions (note: they are 5 apart, mod 10)

    This is really so strange... I suspect some prime-number tricky business here.

View all 132 project logs

Enjoy this project?

Share

Discussions

Yann Guidon / YGDES wrote 09/21/2022 at 17:14 point

https://www.youtube.com/watch?v=EWgts6EiJA0 has some relevant ideas here and there :-)

  Are you sure? yes | no

Yann Guidon / YGDES wrote 07/28/2022 at 16:03 point

TODO : check the distribution and periodicity of each rank of bit to show they don't exhibit the flaws of https://en.wikipedia.org/wiki/Linear_congruential_generator#m_a_power_of_2,_c_=_0

  Are you sure? yes | no

Yann Guidon / YGDES wrote 04/08/2022 at 11:41 point

https://en.wikipedia.org/wiki/Cyclic_code

It seems that PEAC is a cyclic code (in a loose way because it's not using Galois fields but still interesting)

  Are you sure? yes | no

Ezra Wolf wrote 01/21/2022 at 23:18 point

Wow !

  Are you sure? yes | no

Yann Guidon / YGDES wrote 01/26/2022 at 05:27 point

Hi Ezra, feel free to elaborate :-)

  Are you sure? yes | no

Yann Guidon / YGDES wrote 01/17/2022 at 08:49 point

Correction to some of my statements here and there (and my videos) : φ is not transcendental but an irrational number that is a solution to the quadratic equation x² − x − 1 = 0. Mea culpa, but at least I learned something from one of the Bogdanoff brothers' countless errors and confusions :-D

  Are you sure? yes | no

Yann Guidon / YGDES wrote 01/14/2022 at 16:55 point

Oh my !

https://en.wikichip.org/wiki/x86/adx

Now, THAT's a hack :-)

And I can see how it could increase the speed of some algorithms, even this one...

  Are you sure? yes | no

Tim wrote 01/14/2022 at 19:44 point

On ever other architecture, yes. On x86 is does not add notably to the entropy :)

  Are you sure? yes | no

Yann Guidon / YGDES wrote 01/15/2022 at 12:04 point

  Are you sure? yes | no

Yann Guidon / YGDES wrote 10/23/2021 at 21:33 point

Interesting !

https://research.nccgroup.com/2021/10/15/cracking-random-number-generators-using-machine-learning-part-1-xorshift128/

https://research.nccgroup.com/2021/10/18/cracking-random-number-generators-using-machine-learning-part-2-mersenne-twister/

  Are you sure? yes | no

[deleted]

[this comment has been deleted]

Yann Guidon / YGDES wrote 10/13/2021 at 14:39 point

so far, half a year and 50£.

  Are you sure? yes | no

Yann Guidon / YGDES wrote 09/14/2021 at 04:16 point

George Marsaglia and Arif Zaman got quite a lot figured out in 1991:
https://projecteuclid.org/download/pdf_1/euclid.aoap/1177005878

Why didn't this catch up, but they focus on extremely large sequences with tens of registers of lag, and didn't look enough at just a pair of registers. They also didn't look at the link with checksums.

  Are you sure? yes | no

Yann Guidon / YGDES wrote 09/08/2021 at 07:28 point

Funny !

https://en.wikipedia.org/wiki/Lagged_Fibonacci_generator

Toward a universal random number generator, G.Marsaglia, A.Zaman

  Are you sure? yes | no

Yann Guidon / YGDES wrote 08/05/2021 at 23:24 point

https://www.researchgate.net/profile/Michael_Greenwald/publication/3334567_Performance_of_checksums_and_CRCs_over_real_data/links/53f4b15f0cf2888a749113c5/Performance-of-checksums-and-CRCs-over-real-data.pdf

"In practice, TCP trailer sums outperform even Fletcher header sums."

Ouch.

  Are you sure? yes | no

Yann Guidon / YGDES wrote 08/08/2021 at 00:51 point

"Ones complement (with EAC) Fletcher, however, has a weakness that sometimes offsets its probabilistic advantage: since bytes containing either 255 or 0 are considered identical by the checksum, certain common pathological cases cause total failure of Fletcher-255."

Re-ouch.

  Are you sure? yes | no

Yann Guidon / YGDES wrote 08/05/2021 at 23:09 point

http://users-tima.imag.fr/cdsi/guyot/Cours/Oparithm/english/Modulo.htm and others say that special adders exist to compute mod 2^n-1.

But this is not necessary because the carry is explicitly integrated in the next cycle.

  Are you sure? yes | no

Yann Guidon / YGDES wrote 08/05/2021 at 22:20 point

https://www.cs.auckland.ac.nz/compsci314s1t/resources/Checksums.pdf  is a nice beginner-level overview of error detection basics. Polynomial checks are mentioned, as well as 1s complement / end-around-carry and Fletcher is well explained but no sight of Fibonacci.

  Are you sure? yes | no

Yann Guidon / YGDES wrote 05/24/2021 at 03:52 point

Oh, nice !

https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html#Integer-Overflow-Builtins

  Are you sure? yes | no

Similar Projects

Does this project spark your interest?

Become a member to follow this project and never miss any updates