Random/LFSR on P2

15961636465

Comments

  • evanhevanh Posts: 5,906
    edited October 10 Vote Up0Vote Down
    And aperture size 8 of SmallCrush reports:
    Money is a placeholder for cooperation
  • TonyB_TonyB_ Posts: 1,005
    edited October 10 Vote Up0Vote Down
    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.
    Formerly known as TonyB
  • evanhevanh Posts: 5,906
    edited October 10 Vote Up0Vote Down
    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 ...
    Money is a placeholder for cooperation
  • built with aperture sizes 4 and 8:
    Money is a placeholder for cooperation
  • 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?
  • 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.

    Money is a placeholder for cooperation
  • 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.
    Money is a placeholder for cooperation
  • evanhevanh Posts: 5,906
    edited October 10 Vote Up0Vote Down
    C source for simulation of XORO32 instruction. Oops, missing the first iteration ... hmm, the testing code calls nextxoro() twice to simulate XORO32.
    Money is a placeholder for cooperation
  • Here's said testing code. Double iteration caried out at line 60:
    		random64 = rotr( (drnword_t)nextxoro() | ((drnword_t)nextxoro() << ACCUM_SIZE), SAMPLE_POSITION );
    
    Money is a placeholder for cooperation
  • 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 );
    }
    
    Money is a placeholder for cooperation
  • TonyB_TonyB_ Posts: 1,005
    edited October 10 Vote Up0Vote Down
    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
    
    Formerly known as TonyB
  • 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?
  • 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.
    Money is a placeholder for cooperation
  • 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.

    Formerly known as TonyB
  • 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?
    Formerly known as TonyB
  • evanhevanh Posts: 5,906
    edited October 10 Vote Up0Vote Down
    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.
    Money is a placeholder for cooperation
  • 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.

    Money is a placeholder for cooperation
  • 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+.
    Money is a placeholder for cooperation
  • TonyB_TonyB_ Posts: 1,005
    edited October 10 Vote Up0Vote Down
    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)
    Formerly known as TonyB
  • 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.
  • Thank you AJL. All sounds good.

  • TonyB_TonyB_ Posts: 1,005
    edited October 10 Vote Up0Vote Down
    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
    Formerly known as TonyB
  • 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
    I am just another Code Monkey.
    A determined coder can write COBOL programs in any language. -- Author unknown.
    Press any key to continue, any other key to quit

    The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this post are to be interpreted as described in RFC 2119.
  • 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!
    Formerly known as TonyB
  • 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:
    Propeller ASC- Use your Arduino shields with the Propeller.
    Propeller DNA- A Propeller Platform compatible proto board.
  • My thoughts too. They have put real polish on this feature. Spoiling future P2 users with very solid grade PRNG generation, in the box!

    Do not taunt Happy Fun Ball! @opengeekorg ---> Be Excellent To One Another SKYPE = acuity_doug
    Parallax colors simplified: https://forums.parallax.com/discussion/123709/commented-graphics-demo-spin<br>
  • 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.
    Money is a placeholder for cooperation
  • 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.

    Money is a placeholder for cooperation
  • 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?

    Do not taunt Happy Fun Ball! @opengeekorg ---> Be Excellent To One Another SKYPE = acuity_doug
    Parallax colors simplified: https://forums.parallax.com/discussion/123709/commented-graphics-demo-spin<br>
Sign In or Register to comment.