Shop OBEX P1 Docs P2 Docs Learn Events
Random/LFSR on P2 - Page 61 — Parallax Forums

Random/LFSR on P2

1585961636492

Comments

  • evanhevanh Posts: 16,007
    edited 2018-10-10 18:37
    And aperture size 8 of SmallCrush reports:
  • TonyB_TonyB_ Posts: 2,190
    edited 2018-10-10 18:56
    evanh wrote: »
    Here's all the Practrand gridding data. I haven't made any spreadsheet.

    Something suspect though: Full period repeat is 64 KB so Practrand should be maxing out at 128 KB, but there is plenty of 512 KB!

    Thanks for these results, Evan.

    We've had a few impossible scores before, but not in such profusion! 1 bit samples included. Would it be better to clamp the scores to the maximum possible when calculating grid totals?
    evanh wrote: »
    And aperture size 8 of SmallCrush reports:

    SmallCrush results aren't very good, so no point trying Crush.
  • evanhevanh Posts: 16,007
    edited 2018-10-10 19:04
    TonyB_ wrote: »
    Would it be better to clamp the scores to the maximum possible when calculating grid totals?

    Probably should just look at the size 8 apertures ... I'll redo the grid tables this way ...
  • evanhevanh Posts: 16,007
    built with aperture sizes 4 and 8:
  • Heater.Heater. Posts: 21,230
    The only reason I asked about how the P2 xor??? algorithm differed from any published algorithm is that sometimes it is useful to be able to run the same code with the same seeds on different machines and get the same results. Just for software testing for example.

    Just now the whole situation confuses me because I just read that the P2 PRNG should be seeded by some real randomness at boot up. So even if you know the algorithm you don't know where it starts. Or is there a way to seed it how you like?
  • evanhevanh Posts: 16,007
    Heater,
    That's the free-running Xoroshiro128**. Because it never stops iterating it would be tricky to even map it even if it always started at the same seed.

  • evanhevanh Posts: 16,007
    Here's my Xoroshiro source code that is used for all the testing: It's not very tidy. I'll do a hard coded clean looking XORO32 as well.
  • evanhevanh Posts: 16,007
    edited 2018-10-10 19:45
    C source for simulation of XORO32 instruction. Oops, missing the first iteration ... hmm, the testing code calls nextxoro() twice to simulate XORO32.
  • evanhevanh Posts: 16,007
    Here's said testing code. Double iteration caried out at line 60:
    		random64 = rotr( (drnword_t)nextxoro() | ((drnword_t)nextxoro() << ACCUM_SIZE), SAMPLE_POSITION );
    
  • evanhevanh Posts: 16,007
    Here's the basic Xoroshiro32++ cleaned up and set for [13 5 10 9]:
    #include <stdint.h>
    
    #define  ACCUM_SIZE  16
    #define  CONSTANT_A  13
    #define  CONSTANT_B  5
    #define  CONSTANT_C  10
    #define  CONSTANT_D  9
    
    typedef  uint16_t  rngword_t;
    
    
    static inline rngword_t  rotl( rngword_t value, int shift )  {
    	return (value << shift) | (value >> (ACCUM_SIZE - shift));
    }
    
    
    // Seed the state array.  Seed MUST not be all zero.
    static rngword_t  s[2] = {1, 0};
    
    
    static rngword_t  nextxoro( void )
    {
    	rngword_t  s0 = s[0];
    	rngword_t  s1 = s[1];
    	rngword_t  result = s0 + s1;  // output hash (scrambler) for Xoroshiro+
    //New addition from authors:  Rotation and second summing
    	result = rotl( result, CONSTANT_D ) + s0;
    
    	s1 ^= s0;
    	s[0] = rotl( s0, CONSTANT_A ) ^ s1 ^ (s1 << CONSTANT_B);
    	s[1] = rotl( s1, CONSTANT_C );
    
    	return( result );
    }
    
  • TonyB_TonyB_ Posts: 2,190
    edited 2018-10-10 21:37
    xoroshiro16++ pair distribution results, top 20 combined ranking:
    #a,  b,  c,  d, prank, zrank, nzrank, prank+zrank+nzrank
     2,  6,  7,  2,    5,    6,    2,    1
     5,  5,  2,  2,   10,    1,    6,    2
     5,  6,  2,  2,    3,    2,   14,    3
     7,  6,  2,  4,    7,    8,   11,    4
     6,  7,  5,  6,    6,    7,   21,    5
     2,  6,  3,  1,   11,    9,   15,    6
     3,  6,  2,  4,    4,   20,   16,    7
     3,  6,  2,  3,   18,    3,   19,    8
     7,  6,  2,  5,   15,   23,    7,    9
     2,  6,  5,  4,    2,    5,   43,   10
     4,  7,  3,  3,   23,   27,    8,   11
     5,  7,  6,  7,   16,   17,   26,   12
     2,  5,  5,  2,   21,   30,   10,   13
     4,  7,  3,  2,   39,   15,    9,   14
     3,  7,  4,  1,   24,   21,   20,   15
     5,  5,  2,  4,   14,   29,   23,   16
     5,  7,  6,  4,   28,   10,   28,   17
     2,  6,  7,  3,   13,   44,   18,   18
     3,  6,  2,  1,   33,   37,    5,   19
     5,  5,  2,  5,   12,   26,   39,   20
    
  • Heater.Heater. Posts: 21,230
    evanh
    That's the free-running Xoroshiro128**. Because it never stops iterating it would be tricky to even map it even if it always started at the same seed.
    
    I see. Sounds good.

    Is it also possible to use that Xoroshiro128** hardware with ones own known seed? Or do we have to revert back to using a known PRNG algorithm in our software?
  • evanhevanh Posts: 16,007
    You can certainly load seed data into the free-running generator but don't count on that being an exact seeding state. Only 32 bits (1/4 the state bits) I think and while it is already running.
  • Heater. wrote: »
    evanh
    That's the free-running Xoroshiro128**. Because it never stops iterating it would be tricky to even map it even if it always started at the same seed.
    
    I see. Sounds good.

    Is it also possible to use that Xoroshiro128** hardware with ones own known seed? Or do we have to revert back to using a known PRNG algorithm in our software?

    No and no, use XORO32. :) Do you not trust this instruction? It uses the published xoroshiro++ algorithm.

    It is possible to seed xoroshiro128** only partially.

  • evanh wrote: »
    TonyB_ wrote: »
    Would it be better to clamp the scores to the maximum possible when calculating grid totals?

    Probably should just look at the size 8 apertures ... I'll redo the grid tables this way ...

    Are impossible scores still there?
  • evanhevanh Posts: 16,007
    edited 2018-10-10 20:59
    Heater. wrote: »
    Or do we have to revert back to using a known PRNG algorithm in our software?

    The ** scrambler has that invertible issue that drew a tongue lashing from Melissa. I'm thinking that's not a big concern with the free-running nature here, but if you are wanting to work with a controllable software version of Xoroshiro or Xoshiro without that weakness then I'd go for the ++ scrambler we're using in XORO32.
  • evanhevanh Posts: 16,007
    TonyB_ wrote: »
    evanh wrote: »
    TonyB_ wrote: »
    Would it be better to clamp the scores to the maximum possible when calculating grid totals?

    Probably should just look at the size 8 apertures ... I'll redo the grid tables this way ...

    Are impossible scores still there?

    Nothing higher than 128 KB. [2 6 7 2] is an average good PR grid score, similar to how XORO32 measured up.

  • evanhevanh Posts: 16,007
    To do a Xoroshiro128++ would probably need Dave and Seba to conjuror up the four constants. Although, if Tony is really on to something with this distribution scoring, then that should indicate that the first three constants don't change from the original Xoroshiro128+.
  • TonyB_TonyB_ Posts: 2,190
    edited 2018-10-10 22:17
    evanh wrote: »
    To do a Xoroshiro128++ would probably need Dave and Seba to conjuror up the four constants. Although, if Tony is really on to something with this distribution scoring, then that should indicate that the first three constants don't change from the original Xoroshiro128+.

    Strictly speaking, it should be "pair distribution" not just "distribution" as my tests only apply to pairs of successive outputs.

    I doubt anyone will ever use xoroshiro128++ now the ** scrambler exists. Quote below is copied from a PM just before a bug fix let us change from xoroshiro128+ to xoroshiro128**.

    {s1,s0} = 128-bit state
    PRN = 64-bit output
    TonyB_ wrote:
    Due to extra pipelining, I think xoroshiro128** would need more logic than xoroshiro128+, but less than xoroshiro128++.

    xoroshiro128+
    PRN  := s0 + s1
    

    xoroshiro128++
    PRN = ((s0 + s1) rotl d) + s0	thus
    
    PRNa := s0 + s1
    s0a  := s0
    PRN  := (PRNa rotl d) + s0a
    

    xoroshiro128**
    PRN = ((s0 * 5) rotl 7) * 9	thus
    
    PRNa := (s0 << 2) + s0
    PRN  := ((PRNa rotl 7) << 3) + (PRNa rotl 7)
    

    Logic comparison

    xoroshiro128+
    1 * 64-bit register
    1 * 64-bit adder

    xoroshiro128++
    3 * 64-bit register
    2 * 64-bit adder

    xoroshiro128**
    2 * 64-bit register
    1 * 62-bit adder (PRNa)
    1 * 61-bit adder (PRN)
  • Heater.Heater. Posts: 21,230
    TonyB_
    No and no, use XORO32. :) Do you not trust this instruction? It uses the published xoroshiro++ algorithm.
    It's not a question of trust.

    If I have a program using XO??? whatever algorithm that I can seed and run and get reproducible results on my PC. Can I then run the same program on the P2 using the XO??? whatever instruction and get the same results?

    This may be a picky, quibbly question that nobody cares about. I'd just like to know how it works.






  • Heater. wrote: »
    TonyB_
    No and no, use XORO32. :) Do you not trust this instruction? It uses the published xoroshiro++ algorithm.
    It's not a question of trust.

    If I have a program using XO??? whatever algorithm that I can seed and run and get reproducible results on my PC. Can I then run the same program on the P2 using the XO??? whatever instruction and get the same results?

    This may be a picky, quibbly question that nobody cares about. I'd just like to know how it works.


    If you rely on the free-running generator then the answer is no.
    If you rely on the XORO32 instruction then the answer is yes.
  • Heater.Heater. Posts: 21,230
    Thank you AJL. All sounds good.

  • TonyB_TonyB_ Posts: 2,190
    edited 2018-10-10 22:39
    Heater. wrote: »
    TonyB_
    No and no, use XORO32. :) Do you not trust this instruction? It uses the published xoroshiro++ algorithm.
    It's not a question of trust.

    If I have a program using XO??? whatever algorithm that I can seed and run and get reproducible results on my PC. Can I then run the same program on the P2 using the XO??? whatever instruction and get the same results?

    This may be a picky, quibbly question that nobody cares about. I'd just like to know how it works.

    Heater.

    Here is the thread I created for important xoroshiro announcements:
    http://forums.parallax.com/discussion/168188/xoroshiro-random-number-generator
    Sadly I can't seem to edit it now.

    The pseudo-code for the xoroshiro32++ algorithm as used in XORO32 is at the end of the first post. XORO32 does a double-iteration, with the first output in the low word and the second in the high. [a,b,c,d] is now [13,5,10,9] and there are test outputs here:
    http://forums.parallax.com/discussion/comment/1447884/#Comment_1447884
  • As far as I understand we have one free running xoroshiro128++, seeded at bootup from something variable I did not understand. But the goal here is to have a non repeatable random sequence.

    Then we have a seed-able and thus repeatable xoroshiro32 (per COG?).

    But maybe I am completely wrong here, has happened before,

    Mike
  • msrobots wrote: »
    As far as I understand we have one free running xoroshiro128++, seeded at bootup from something variable I did not understand. But the goal here is to have a non repeatable random sequence.

    Then we have a seed-able and thus repeatable xoroshiro32 (per COG?).

    But maybe I am completely wrong here, has happened before,

    Mike

    The XORO32 instruction in each cog is independent of any other cog. There could be dozens of different XORO32 instances running in the same cog at the same time, hundreds even!
  • 60+ forum pages of research, implementation and testing just for the PRNG functions. Truly an impressive effort from you guys! I hope this makes some ripples amongst the RND() aficionados. :thumb:
  • My thoughts too. They have put real polish on this feature. Spoiling future P2 users with very solid grade PRNG generation, in the box!

  • evanhevanh Posts: 16,007
    TonyB_ wrote: »
    I doubt anyone will ever use xoroshiro128++ now the ** scrambler exists.

    The way Melissa sounded, no one should ever start using the ** scrambler. It's not hard to see the flaw - There is only one variable contributor to invert back to uncover the much weaker engine.
  • evanhevanh Posts: 16,007
    TonyB_ wrote: »
    Here is the thread I created for important xoroshiro announcements:
    http://forums.parallax.com/discussion/168188/xoroshiro-random-number-generator
    Sadly I can't seem to edit it now.

    Ask Publison to unlock it for you. It will be a new automatic locking feature to prevent necro'ing.

  • I am unclear on that point.

    For crypto / security related things, that one flaw being unfavorable makes some sense.

    But, for the other purposes, like improving DAC effective resolution by adding noise, what we have in the P2 now is robust, yes?

    Or, no?

Sign In or Register to comment.