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

Random/LFSR on P2

1596062646592

Comments

  • cgraceycgracey Posts: 14,133
    Yes, good PRNG in hardware is going to enable new ideas.
  • All part of the playground.

    Man, I am having a hard time waiting for the Parallax boards... :D

    And notice the interest. Remember way back when we all talked about, "build something cool and they will come?" We are here, and it appears they will.
  • evanhevanh Posts: 15,126
    edited 2018-10-11 04:08
    potatohead wrote: »
    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?

    Possibly. I brushed it off as too security oriented at first too.

    But if the random numbers are sequentially sourced for use in a large data set for statistics I suspect then there is a case for what Melissa is on about.

    Yeah, I'm okay with it in the Prop2 for I/O applications. Particularly the free-running generator as it is much harder to end up with sequential numbers.

  • evanhevanh Posts: 15,126
    TonyB_ wrote: »
    msrobots wrote: »
    Then we have a seed-able and thus repeatable xoroshiro32 (per COG?).

    There could be dozens of different XORO32 instances running in the same cog at the same time, hundreds even!

    This is a notable point. XORO32, as just another cog instruction, uses any cogram for its state store. A mere 32 bits, hence the name. So you, the programmer, can mess with or reseed as you like.

  • PublisonPublison Posts: 12,366
    edited 2018-10-11 08:54
    No and no, use XORO32. :) Do you not trust this instruction? It uses the published xoroshiro++ algorithm.

    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.


    Do you mean there is not an "Edit" button? I show the thread is open and I can edit.

  • evanhevanh Posts: 15,126
    edited 2018-10-11 08:58
    The little gear in the corner is there but the edit button doesn't pop out from it when clicked on, no.
  • evanh wrote: »
    The little gear in the corner is there but the edit button doesn't pop out from it when clicked on, no.

    I'll see what I can do.
  • Publison wrote: »
    No and no, use XORO32. :) Do you not trust this instruction? It uses the published xoroshiro++ algorithm.

    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.


    Do you mean there is not an "Edit" button? I show the thread is open and I can edit.

    The edit box is blank. I can edit more recent posts.
  • TonyB_TonyB_ Posts: 2,108
    edited 2018-10-11 10:44
    The post I cannot edit has a strange number. It's not 14xxxxx.
    http://forums.parallax.com/discussion/168188/xoroshiro-random-number-generator

    EDIT:
    I can edit newer and older posts with numbers 14xxxxx.
  • PublisonPublison Posts: 12,366
    edited 2018-10-11 10:55
    TonyB_ wrote: »
    The post I cannot edit has a strange number. It's not 14xxxxx.
    http://forums.parallax.com/discussion/168188/xoroshiro-random-number-generator

    EDIT:
    I can edit newer and older posts with numbers 14xxxxx.

    Try it again. I just opened and closed an edit without changing anything.
  • evanh wrote: »
    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.

    The reason for mentioning xoroshiro16 again is that someone asked on the prng forum yesterday for a 16-bit state xoroshiro-style generator. Evan, which candidate(s) would you recommend?

    [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
    
  • TonyB_TonyB_ Posts: 2,108
    edited 2018-10-11 11:20
    Publison wrote: »
    TonyB_ wrote: »
    The post I cannot edit has a strange number. It's not 14xxxxx.
    http://forums.parallax.com/discussion/168188/xoroshiro-random-number-generator

    EDIT:
    I can edit newer and older posts with numbers 14xxxxx.

    Try it again. I just opened and closed an edit without changing anything.

    Thanks for helping. Edit box still empty but here's how I edited the post:

    1. Click Quote
    2. Copy quoted text into blank edit box
    3. Delete quote and /quote
    4. Click Save Comment
  • PublisonPublison Posts: 12,366
    edited 2018-10-11 11:27
    TonyB_ wrote: »
    Publison wrote: »
    TonyB_ wrote: »
    The post I cannot edit has a strange number. It's not 14xxxxx.
    http://forums.parallax.com/discussion/168188/xoroshiro-random-number-generator

    EDIT:
    I can edit newer and older posts with numbers 14xxxxx.

    Try it again. I just opened and closed an edit without changing anything.

    Thanks for helping. Edit box still empty but here's how I edited the post:

    1. Click Quote
    2. Copy quoted text into blank edit box
    3. Delete quote and /quote
    4. Click Save Comment
    Sounds good for now.

    I do not have permissions to dig any deeper. I'll have to get Parallax to look at it. Probably something to do with the last Forum Upgrade
  • cgraceycgracey Posts: 14,133
    Publison, when I insert an image into a post, it puts three or four copies in a row.
  • PublisonPublison Posts: 12,366
    edited 2018-10-11 11:30
    cgracey wrote: »
    Publison, when I insert an image into a post, it puts three or four copies in a row.

    That has been reported a few days ago. I'll recheck.
  • cgracey wrote: »
    Publison, when I insert an image into a post, it puts three or four copies in a row.

    I "Attached" a picture yesterday, and it only showed up once.
  • cgraceycgracey Posts: 14,133
    Publison wrote: »
    cgracey wrote: »
    Publison, when I insert an image into a post, it puts three or four copies in a row.

    I "Attached" a picture yesterday, and it only showed up once.

    I think it varies.
  • TonyB_TonyB_ Posts: 2,108
    edited 2018-10-11 12:14
    Publison wrote: »
    TonyB_ wrote: »
    Publison wrote: »
    TonyB_ wrote: »
    The post I cannot edit has a strange number. It's not 14xxxxx.
    http://forums.parallax.com/discussion/168188/xoroshiro-random-number-generator

    EDIT:
    I can edit newer and older posts with numbers 14xxxxx.

    Try it again. I just opened and closed an edit without changing anything.

    Thanks for helping. Edit box still empty but here's how I edited the post:

    1. Click Quote
    2. Copy quoted text into blank edit box
    3. Delete quote and /quote
    4. Click Save Comment
    Sounds good for now.

    I do not have permissions to dig any deeper. I'll have to get Parallax to look at it. Probably something to do with the last Forum Upgrade

    My method doesn't work. It adds a new post to the end of the thread. I edited the first post again and another post was added to the end. I didn't check the whole thread the first time and didn't notice what it did.
  • TonyB_ wrote: »
    Publison wrote: »
    TonyB_ wrote: »
    Publison wrote: »
    TonyB_ wrote: »
    The post I cannot edit has a strange number. It's not 14xxxxx.
    http://forums.parallax.com/discussion/168188/xoroshiro-random-number-generator

    EDIT:
    I can edit newer and older posts with numbers 14xxxxx.

    Try it again. I just opened and closed an edit without changing anything.

    Thanks for helping. Edit box still empty but here's how I edited the post:

    1. Click Quote
    2. Copy quoted text into blank edit box
    3. Delete quote and /quote
    4. Click Save Comment
    Sounds good for now.

    I do not have permissions to dig any deeper. I'll have to get Parallax to look at it. Probably something to do with the last Forum Upgrade

    My method doesn't work. It adds a new post to the end of the thread. I edited the first post again and another post was added to the end. I didn't check the whole thread the first time and didn't notice what it did.

    I'll try closing the thread and re-open it to see if it gets reset.
  • OK. Try it again.
  • Publison wrote: »
    OK. Try it again.

    Can you delete a post if it adds one to the end again?
  • TonyB_ wrote: »
    Publison wrote: »
    OK. Try it again.

    Can you delete a post if it adds one to the end again?

    Yes
  • Publison wrote: »
    TonyB_ wrote: »
    Publison wrote: »
    OK. Try it again.

    Can you delete a post if it adds one to the end again?

    Yes

    Still no good. Please delete this post
    http://forums.parallax.com/discussion/comment/1448914/#Comment_1448914
  • evanhevanh Posts: 15,126
    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 ...
  • Heater.Heater. Posts: 21,230
    edited 2018-10-11 17:35
    evanh,

    Continuing from the xoro announcements thread.... Thanks for the C source earlier. My C++ class now looks like this:
    class Xoroshiro32PlusPlus
    {
      const uint16_t a = 13;
      const uint16_t b = 5;
      const uint16_t c = 10;
      const uint16_t d = 9;
    
      static inline uint16_t rol(uint16_t x, uint16_t bits) noexcept
      {
        return (x << bits) | (x >> ((sizeof(uint16_t) * 8) - bits));
      }
    
      uint16_t s0;
      uint16_t s1;
    
    public:
      explicit Xoroshiro32PlusPlus(uint16_t s0 = 1, uint16_t s1 = 0) noexcept
        : s0(s0), s1(s1)
      {
      }
    
      inline uint16_t operator()() noexcept
      {
        uint16_t result = rol(s0 + s1, d) + s0;
    
        s1 ^= s0;
        s0 = rol(s0, a ) ^ s1 ^ (s1 << b);
        s1 = rol(s1, c);
    
        return result;
      }
    };
    

    With results:
    0201
    6269
    ae16
    12a2
    4ae8
    d719
    0c52
    984b
    1df1
    743c
    dba0
    bcc6
    34c9
    746c
    3643
    07ff
    bbc0
    
    Which now matches TonyB_'s on the other thread.

    Next up... a version in SpinalHDL.
  • Heater.Heater. Posts: 21,230
    OK, the penny dropped. The "32" refers to the number of state bits not the width of the output.

    Now I wonder why do this? Isn't the cycle length now down to 4 billion?

  • evanhevanh Posts: 15,126
    :)
  • evanhevanh Posts: 15,126
    edited 2018-10-11 18:01
    The reason for such a small state space is Chip wanted to fit it in a single cogram register. Keeps it simple and fast instruction. No independent hardware needed.

    EDIT: And it allowed Tony and myself to realistically do our experimenting directly with the target candidates.

  • TonyB_TonyB_ Posts: 2,108
    edited 2018-10-11 20:51
    Heater. wrote: »
    OK, the penny dropped. The "32" refers to the number of state bits not the width of the output.

    Now I wonder why do this? Isn't the cycle length now down to 4 billion?

    From confused to disgusted? :)

    You could try xoroshiro64++ [26,9,13,17].

    The paper mentions the xoroshiro64 [26,9,13] engine and the +, * and ** scramblers. + is not good enough and ++ would be a much better alternative if there are no multipliers available. In an email to me Seba suggested 15 or 17 for the ++ rotation, i.e. half the output width +/- 1.

    EDIT:
    First 16 outputs for xoroshiro64++ [26,9,13,17] when seed = 1 {s1 = 0, s0 = 1}
    PRN calculated at start of algorithm before new state generated
    00020001
    48020A01
    81662931
    CD2B5253
    D3E6CBE6
    CD5AF43D
    860AA4BA
    B7BEA7FB
    63DCAFF3
    762D74C9
    3E7D7E8F
    E10E0616
    5788242D
    D8ECE2A3
    7A242FAB
    ADD23D97
    
  • Heater.Heater. Posts: 21,230
    No, not disgusted. A teeny, tiny bit disappointed at the cycle length but otherwise happy I have something that does what the P2 does as a reference. I hope!

    I'll have to read that paper again...

Sign In or Register to comment.