Random/LFSR on P2

15960626465

Comments

  • 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.
    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>
  • evanhevanh Posts: 5,906
    edited October 11 Vote Up0Vote Down
    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.

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

    Money is a placeholder for cooperation
  • PublisonPublison Posts: 10,474
    edited October 11 Vote Up0Vote Down
    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.

    Infernal Machine
  • evanhevanh Posts: 5,906
    edited October 11 Vote Up0Vote Down
    The little gear in the corner is there but the edit button doesn't pop out from it when clicked on, no.
    Money is a placeholder for cooperation
  • 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.
    Infernal Machine
  • 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.
    Formerly known as TonyB
  • TonyB_TonyB_ Posts: 1,005
    edited October 11 Vote Up0Vote Down
    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.
    Formerly known as TonyB
  • PublisonPublison Posts: 10,474
    edited October 11 Vote Up0Vote Down
    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.
    Infernal Machine
  • 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
    
    Formerly known as TonyB
  • TonyB_TonyB_ Posts: 1,005
    edited October 11 Vote Up0Vote Down
    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
    Formerly known as TonyB
  • PublisonPublison Posts: 10,474
    edited October 11 Vote Up0Vote Down
    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
    Infernal Machine
  • Publison, when I insert an image into a post, it puts three or four copies in a row.
  • PublisonPublison Posts: 10,474
    edited October 11 Vote Up0Vote Down
    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.
    Infernal Machine
  • 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.
    Infernal Machine
  • 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: 1,005
    edited October 11 Vote Up0Vote Down
    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.
    Formerly known as TonyB
  • 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.
    Infernal Machine
  • OK. Try it again.
    Infernal Machine
  • Publison wrote: »
    OK. Try it again.

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

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

    Yes
    Infernal Machine
  • 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
    Formerly known as TonyB
  • 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 ...
    Money is a placeholder for cooperation
  • Heater.Heater. Posts: 21,205
    edited October 11 Vote Up0Vote Down
    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.
  • 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?

  • :)
    Money is a placeholder for cooperation
  • evanhevanh Posts: 5,906
    edited October 11 Vote Up0Vote Down
    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.

    Money is a placeholder for cooperation
  • TonyB_TonyB_ Posts: 1,005
    edited October 11 Vote Up0Vote Down
    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
    
    Formerly known as TonyB
  • 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.