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

Random/LFSR on P2

1606163656692

Comments

  • Heater.Heater. Posts: 21,230
    TonyB_,

    Thanks for posting xoroshiro64++ results. I had just adapted my little class above to 64++ like so:
    class Xoroshiro64PlusPlus
    {
      const uint32_t a = 26;
      const uint32_t b = 9;
      const uint32_t c = 13;
      const uint32_t d = 17;
    
      static inline uint32_t rol(uint32_t x, uint32_t bits) noexcept
      {
        return (x << bits) | (x >> ((sizeof(x) * 8) - bits));
      }
    
      uint32_t s0;
      uint32_t s1;
    
    public:
      explicit Xoroshiro64PlusPlus(uint32_t s0 = 1, uint32_t s1 = 0) noexcept
        : s0(s0), s1(s1)
      {
      }
    
      inline uint32_t operator()() noexcept
      {
        uint32_t result = rol(s0 + s1, d) + s0;
    
        s1 ^= s0;
        s0 = rol(s0, a ) ^ s1 ^ (s1 << b);
        s1 = rol(s1, c);
    
        return result;
      }
    };
    
    And it reproduces your results like so:
    00020001
    48020a01
    81662931
    cd2b5253
    d3e6cbe6
    cd5af43d
    860aa4ba
    b7bea7fb
    63dcaff3
    762d74c9
    3e7d7e8f
    e10e0616
    5788242d
    d8ece2a3
    7a242fab
    add23d97
    

    Neat.

  • evanhevanh Posts: 15,091
    edited 2018-10-12 08:15
    evanh wrote: »
    TonyB_ wrote: »
    [2,6,7,2] is best for simulating a 16-bit PRN. Is the d = 0 binary slot for xoroshiro16+? If so, [2,6,7] is not the best for pair distributions, as shown by the worst scores:
     2,  6,  3,  0,   86,   85,   84,   84
     2,  6,  7,  1,   82,   88,   86,   85
     2,  6,  5,  0,   88,   86,   85,   86
     2,  6,  7,  0,   85,   84,   91,   87
     5,  6,  2,  0,   89,   87,   88,   88
     5,  5,  2,  0,   90,   89,   87,   89
     3,  7,  4,  0,   91,   91,   89,   90
     7,  6,  2,  0,   92,   90,   90,   91
     2,  5,  5,  0,   87,   92,   94,   92
     5,  7,  6,  0,   93,   93,   96,   93
     3,  6,  2,  0,   94,   94,   95,   94
     4,  7,  3,  0,   95,   95,   93,   95
     6,  7,  5,  0,   96,   96,   92,   96
    

    Yep, d=0 is the single summing (+) scrambler. Hmm, maybe need to verify generated number sequences like Heater is ...
    Xoroshiro16++/+
    [2 6 7 2] [2 6 7] [2 6 3]
       05       01      01
       5c       c5      4d
       59       72      82
       57       e9      25
       4a       cf      13
       4b       0a      07
       f2       aa      47
       0d       a0      8e
       2d       7f      9e
       77       3e      76
       b3       9d      d7
       47       97      83
       2f       c3      7f
       d5       84      28
       c7       8e      98
       ba       00      81
       68       94      2d
       c1       64      2d
       df       c6      db
       37       b8      92
    
  • Heater.Heater. Posts: 21,230
    Here is Xoroshiro64PlusPlus in the hardware description language SpinalHDL:
    class  Xoroshiro64PlusPlus extends Component {
      val io = new Bundle {
        val prng = out UInt(32 bits)
        val next = in Bool
      }
    
      // The PRNG state
      val s0 = Reg(UInt(32 bits)) init(1)
      val s1 = Reg(UInt(32 bits)) init(0)
    
      // Xoroshiro64PlusPlus magic numbers
      val a = 26
      val b = 9
      val c = 13
      val d = 17
    
      when(io.next) {
        s0 := s0.rotateLeft(a) ^ (s1 ^ s0) ^ ((s1 ^ s0) |<< b)
        s1 := (s1 ^ s0).rotateLeft(c)
      }
      io.prng := (s0 + s1).rotateLeft(d) + s0
    }
    
    Which compiles to the Verilog code:
    module Xoroshiro64PlusPlus (
          output [31:0] io_prng,
          input   io_next,
          input   clk,
          input   reset);
      wire [31:0] _zz_2;
      reg [31:0] s0;
      reg [31:0] s1;
      wire [31:0] _zz_1;
      assign _zz_2 = (s1 <<< 9);
      assign _zz_1 = (s0 + s1);
      assign io_prng = ({_zz_1[14 : 0],_zz_1[31 : 15]} + s0);
      always @ (posedge clk or posedge reset) begin
        if (reset) begin
          s0 <= (32'b00000000000000000000000000000001);
          s1 <= (32'b00000000000000000000000000000000);
        end else begin
          if(io_next)begin
            s0 <= (({s0[5 : 0],s0[31 : 6]} ^ (s1 ^ s0)) ^ _zz_2);
            s1 <= {s1[18 : 0],s1[31 : 19]};
          end
        end
      end
    endmodule
    
    When simulated with the Verilator it produces the same results as above.

    Of course we don't mess with Verilog or C++ when using the Verilator, we let Spinal do it all with a test harness in Spinal:
    object Xoroshiro64PlusPlusSim {
      def main(args: Array[String]) {
    
        val compiled = SimConfig.withWave.compile{
          val dut = new Xoroshiro64PlusPlus ;
          dut
        }
    
        compiled.doSim("test_Xoroshiro64PlusPlus"){dut =>
          // Fork a process to generate the reset and the clock on the dut
          dut.clockDomain.forkStimulus(period = 10)
    
          var idx = 0
          while(idx < 16){
            // Drive the dut input to enable random generation
            dut.io.next #= true
    
            // Wait a rising edge on the clock
            dut.clockDomain.waitRisingEdge()
    
            println(dut.io.prng.toLong.toHexString.padTo(8, "0").mkString)
    
            idx += 1
          }
        }
      }
    }
    
  • Heater. wrote: »
    Here is Xoroshiro64PlusPlus in the hardware description language SpinalHDL:
    class  Xoroshiro64PlusPlus extends Component {
      val io = new Bundle {
        val prng = out UInt(32 bits)
        val next = in Bool
      }
    
      // The PRNG state
      val s0 = Reg(UInt(32 bits)) init(1)
      val s1 = Reg(UInt(32 bits)) init(0)
    
      // Xoroshiro64PlusPlus magic numbers
      val a = 26
      val b = 9
      val c = 13
      val d = 17
    
      when(io.next) {
        s0 := s0.rotateLeft(a) ^ (s1 ^ s0) ^ ((s1 ^ s0) |<< b)
        s1 := (s1 ^ s0).rotateLeft(c)
      }
      io.prng := (s0 + s1).rotateLeft(d) + s0
    }
    

    Or the following?
    ...
      when(io.next) {
        s0 := s0.rotateLeft(a) ^ (s1 ^ s0) ^ ((s1 ^ s0) |<< b)
        s1 := (s1 ^ s0).rotateLeft(c)
        io.prng := (s0 + s1).rotateLeft(d) + s0
      }
    }
    
  • TonyB_TonyB_ Posts: 2,099
    edited 2018-10-13 23:51
    P2 asm version of xoroshiro64++ [a,b,c,d]
    con				' xoroshiro64 constants
    	a = 26
    	b = 9
    	c = 13
    	d = 17			' ++ only
    
    dat	org
    
    xoro64				' xoroshiro64 prng
    	xor	s1,s0
    	rol	s0,#a
    	mov	prn,s1
    	xor	s0,prn
    	shl	prn,#b
    	xor	s0,prn		' new state low
    	rol	s1,#c		' new state high
    	mov	prn,s1
    	add	prn,s0		' xoroshiro64+ prn
    	rol	prn,#d
     _ret_	add	prn,s0		' xoroshiro64++ prn
    
    s1	long	0		' state high
    s0	long	1		' state low
    prn	long	0		' pseudo-random number
    

    There are various ways of writing the routine and shortest length is 11 instructions, considerably more than the two for XORO32. Code above calculates PRN after new state iterated, which saves a register. xoroshiro64++ has period of 2^64-1 and is only really required if XORO32 period of 2^32-1 is considered to be too short.
  • Heater.Heater. Posts: 21,230
    edited 2018-10-13 23:52
    TonyB_

    No you can't do that. The idea is that the stuff inside a "when" updates state. That is to say it clocks new values into the state registers ("Reg").

    Trying to update something that is not a register in the "when" produces the error "LATCH DETECTED from the combinatorial signal". Which is a correct response because what we actually want here is a continuous assignment (Just wire connections) from the state registers to the io output bus.

    The problem is that if we could have "io.prng := ..." in the "when" clause then io.prng is not defined until io.next becomes true. Which it might never do. We can't have an output with nothing driving it!

    In the Verilog world this is known as an "inferred latch" and is a problem that can catch you out as it's easy to create inferred latches accidentally when you don't really want a register.

    In fact this is an example of a great feature of SpinalHDL, it does a much better job of catching all kind of mistakes that cause a lot of head scratching to Verilog writers.

    See here https://stackoverflow.com/questions/22459413/what-is-inferred-latch-and-how-it-is-created-when-it-is-missing-else-statement-i and here https://www.nandland.com/articles/how-to-avoid-transparent-latches-in-vhdl-and-verlog.html

  • Heater. wrote: »
    TonyB_

    No you can't do that. The idea is that the stuff inside a "when" updates state. That is to say it clocks new values into the state registers ("Reg").

    Trying to update something that is not a register in the "when" produces the error "LATCH DETECTED from the combinatorial signal". Which is a correct response because what we actually want here is a continuous assignment (Just wire connections) from the state registers to the io output bus.

    I want a registered PRN, to match the registered state.
  • Heater.Heater. Posts: 21,230
    edited 2018-10-14 06:16
    I'm not sure I follow what you mean. Currently the prng output exactly follows the current state register values via some sequential logic. It is effectively registered.

    I'll assume you mean you want the equivalent of moving the ++ scrambler to the end of the C code function.

    In that case we have to calculate the next PRNG state and scrambler output using sequential logic but only actually update the state registers in the "when" clause. Something like this:
    class  Xoroshiro64PlusPlus extends Component {
      val io = new Bundle {
        val prng = out UInt(32 bits)
        val next = in Bool
      }
    
      // The PRNG state
      val s0 = Reg(UInt(32 bits)) init(1)
      val s1 = Reg(UInt(32 bits)) init(0)
    
      // Xoroshiro64PlusPlus magic numbers
      val a = 26
      val b = 9
      val c = 13
      val d = 17
    
      // Pre-calculate the next PRNG state.
      val s0_ = s0.rotateLeft(a) ^ (s1 ^ s0) ^ ((s1 ^ s0) |<< b)
      val s1_ = (s1 ^ s0).rotateLeft(c)
    
      when(io.next) {
        // Update the PRNG state
        s0 := s0_
        s1 := s1_
      }
      io.prng := (s0_ + s1_).rotateLeft(d) + s0_
    }
    
    Note: that this does not require any new registers, it just moves the sequential logic around w.r.t the state registers we have already. I'm guessing the number of gates used is the same.

    Which produces the following result:
    48020a01
    81662931
    cd2b5253
    d3e6cbe6
    cd5af43d
    860aa4ba
    b7bea7fb
    63dcaff3
    762d74c9
    3e7d7e8f
    e10e0616
    5788242d
    d8ece2a3
    7a242fab
    add23d97
    98ef01be
    
    Same as before but missing the initial 00020001 we had.

    I like it. This does not give you your seed value back as the first random number which would not be very random now world it!
  • Heater.Heater. Posts: 21,230
    edited 2018-10-15 08:24
    Thought for the day:

    "The generation of random numbers is indeed too important to be left to chance."

    Dan Kaminsky, DEFCON 22, "Secure Random By Default".

  • evanhevanh Posts: 15,091
    edited 2018-10-15 04:59
    Funnies work better with correct spelling when the right words are used!

  • Heater.Heater. Posts: 21,230
    Well spotted. That was not misspelling or the wrong word, it was a typo :)
    I was mostly asleep when I heard that on utube last night. It's not so funny anyway but I could not resist sharing after the massively long discussions about PRNG we have had here.
  • evanhevanh Posts: 15,091
    Huh, I'd always equated typo as same as misspelling, whether by accident or not.

  • evanhevanh Posts: 15,091
    edited 2018-10-15 10:00
    For me, an example of a wrong word would be using "your" to mean "you are" and thinking you've got it right.

    BTW: I had assumed you'd copy'n'pasted the quote, rather than hand typed it.

  • Heater.Heater. Posts: 21,230
    edited 2018-10-15 11:11
    Wrong word, misspelling, typo, the results are all the same I guess.

    To me "typo" implies the writer probably has the correct word and probably knows how to spell it, they just happened to hit the wrong key. "your"/"you are", "its"/"it's", "to"/too", "due"/"do" mistakes are all over the net. Now I find I'm doing it!

    The quote is somewhere in this presentation "Secure Random by Default"



    I scribbled it down because it made me chuckle.

    The problem of getting sufficient randomness first hit me whilst working on a crypto algorithm for some mobile military gear thirty years ago. I was surprised that such a simple sounding thing was so difficult and so easy to get wrong.

  • evanhevanh Posts: 15,091
    I've never noticed anyone use "do" in place of "due". They're not even pronounced the same. Due is pronounced same as dew.

    I can understand "too" being accidentally shortened by some, and I mean some. But I'm pretty certain others don't have a clue they're doing wrong at all, particularly with "you're" vs "your".

    "its" vs "it's" is one I have trouble with. Having three meanings doens't help. Sometimes I've been typing "it's" so much, as a shortened "it is", that I add the apostrophe through repetitive habit, so that's typo then. Other times I'm actually not sure what is correct, so can be a wrong word then. I think it's called possessive when using the apostrophe. Something like that.

    I prefer apostrophes always be used on acronyms, possessive or not. It's a lot easy to read the acronym then.

  • Heater.Heater. Posts: 21,230
    I think the "do"/"due" thing is limited to some particular American accents where they begin to sound the same.
  • Heater. wrote: »
    I think the "do"/"due" thing is limited to some particular American accents where they begin to sound the same.

    Similarly, the 'moot point' vs 'mute point' confusion only makes sense in those accents.

    Of course, in some parts of the USA these words all sound the same:
    merry
    marry
    Mary
    while where I'm from they are all distinct.
  • evanh wrote: »
    I've never noticed anyone use "do" in place of "due". They're not even pronounced the same. Due is pronounced same as dew.

    I can understand "too" being accidentally shortened by some, and I mean some. But I'm pretty certain others don't have a clue they're doing wrong at all, particularly with "you're" vs "your".

    "its" vs "it's" is one I have trouble with. Having three meanings doens't help. Sometimes I've been typing "it's" so much, as a shortened "it is", that I add the apostrophe through repetitive habit, so that's typo then. Other times I'm actually not sure what is correct, so can be a wrong word then. I think it's called possessive when using the apostrophe. Something like that.

    I prefer apostrophes always be used on acronyms, possessive or not. It's a lot easy to read the acronym then.

    Its is the exception to the rule:
    Possessive : Its
    Contraction of it is : it's

    It's its own thing :-)
  • Heater.Heater. Posts: 21,230
    I just wish Americans would put the "l" back into "solder" :)
  • cgraceycgracey Posts: 14,131
    Heater. wrote: »
    I just wish Americans would put the "l" back into "solder" :)

    I wish we could put the Pb back in.
  • Heater.Heater. Posts: 21,230
    Ha, round here solder is pronounced "60/40"!
  • kwinnkwinn Posts: 8,697
    Heater. wrote: »
    Ha, round here solder is pronounced "60/40"!

    And I still have a couple of good sized spools of 63/37 on my bench.
  • Heater.Heater. Posts: 21,230
    Hmm...extra leaded!
  • Is this old news?

    “Xorshift1024*, Xorshift1024+, Xorshift128+ and Xoroshiro128+ Fail Statistical Tests for Linearity”

    https://arxiv.org/abs/1810.05313
  • evanhevanh Posts: 15,091
    KeithE wrote: »
    Is this old news?

    In short, yep.

    We've gone through a number of changes since then. The free-running shared hardware generator in the hub is using Xoroshiro128**. The XORO32 instruction in each cog is using Xoroshiro32++. You'll note neither is a single + suffix.


  • evanhevanh Posts: 15,091
    edited 2018-10-15 16:48
    Seba and Dave (The authors of the Xoroshiro/Xoshiro generator algorithms) have been hard at work to improve things. And we've even been privy to early info from them. Tony has been keeping the lines open.

  • evanhevanh Posts: 15,091
    These aren't the best of the best in quality, but the trade-off is performance and compactness in hardware.

    Quality of the XORO32 is reaching about 10% of full period. 10% may sound like a low number but trust me it is as good as you get without hitting 100%. Lower quality can quickly drop below 1%, which is about where Xoroshiro+ sits with truncated output data.

    Without truncation, Xoroshiro+ sits a long way below 0.1%. This will be what Melissa tore into.

  • kwinnkwinn Posts: 8,697
    Heater. wrote: »
    Hmm...extra leaded!

    Eutectic mixture that has the lowest melting point for a lead/tin alloy. Best choice for avoiding pad lifting when repairing old pcb's.
  • Heater.Heater. Posts: 21,230
    evanh,
    Quality of the XORO32 is reaching about 10% of full period. 10% may sound like a low number but trust me it is as good as you get without hitting 100%. Lower quality can quickly drop below 1%, which is about where Xoroshiro+ sits with truncated output data.
    Wait up a minute. XORO32 is a PRNG with 32 bits of state. Right? I thought it was common for such PRNG to have a cycle length that reached all that state space. About 4 billion in this case.

    Is it so that XORO32 only reaches 10% of it. I.e 400 million ?

    Or is it that it has a 4 billion length cycle but some obscure statistical test fails after 10%?

    Or am I misunderstanding something again?


  • evanhevanh Posts: 15,091
    Number two. Particular tests start to fail at about 400 Mega-Iteration of output collected.

Sign In or Register to comment.