4 ms·

Xorshift is really cool because of how simple it is to comprehend and implement despite how well it works as a PRNG. The initial paper describing it, "Xorshift

Xorshift is really cool because of how simple it is to comprehend and implement despite how well it works as a PRNG. The initial paper describing it, "Xorshift RNGs"[1], is surprisingly short and approachable, and I encourage anyone with any interest to read through it. [1]: https://www.jstatsoft.org/article/download/v008i14/916 https://www.jstatsoft.org/article/download/v008i14/916

pavel_lishin 2y ago
It doesn't seem to work well for smaller sizes when shifting left by 1. I'm sitting in a waiting room, playing with this on paper with four-digit binary numbers, and so far it seems to rapidly fall into a loop of 1,3,5,15,1... edit: they all fall into their own loops. I forget the term for it, but the pattern is, unless I've made an arithmetic mistake (likely!): 1,3,5,15,1... 2,6,10,14,2... 4,12,4... 7,9,11,(1,3,5,15,1...) 8,8... 14,7,9,11,(1,3,5,15,1...)
- GrantMoyer 2y ago
  Note that you need to use 3 shifts. All the triplets of shifts listed in the paper should generate sequences with period 2^32-1 or 2^64-1 depending on the state size, because the tables were generated with that constraint. For example the first triplet for a 32 bit state corresponds to the algortihm: def advance_state(state): state ^= state << 1 state ^= state >> 3 state ^= state << 10 return state
  - pavel_lishin 2y ago
    I should really have read the whole paper, but it's hard to read a PDF on my phone :/ I also definitely wasn't up for working with 8-digit binary numbers on my graph paper. What I consider may be weird, but it's not that weird :P (But I did do a little reading about LFSRs, and I wonder if the amount the numbers are shifted by is related to the stuff about arithmetic fields & groups & such... maybe I'll look into it later, but statistically speaking, probably not :) )

4 ms·

Xorshift is really cool because of how simple it is to comprehend and implement despite how well it works as a PRNG. The initial paper describing it, "Xorshift

by GrantMoyer 2y ago

pavel_lishin 2y ago
It doesn't seem to work well for smaller sizes when shifting left by 1. I'm sitting in a waiting room, playing with this on paper with four-digit binary numbers, and so far it seems to rapidly fall into a loop of 1,3,5,15,1... edit: they all fall into their own loops. I forget the term for it, but the pattern is, unless I've made an arithmetic mistake (likely!): 1,3,5,15,1... 2,6,10,14,2... 4,12,4... 7,9,11,(1,3,5,15,1...) 8,8... 14,7,9,11,(1,3,5,15,1...)
- GrantMoyer 2y ago
  Note that you need to use 3 shifts. All the triplets of shifts listed in the paper should generate sequences with period 2^32-1 or 2^64-1 depending on the state size, because the tables were generated with that constraint. For example the first triplet for a 32 bit state corresponds to the algortihm: def advance_state(state): state ^= state << 1 state ^= state >> 3 state ^= state << 10 return state
  - pavel_lishin 2y ago
    I should really have read the whole paper, but it's hard to read a PDF on my phone :/ I also definitely wasn't up for working with 8-digit binary numbers on my graph paper. What I consider may be weird, but it's not that weird :P (But I did do a little reading about LFSRs, and I wonder if the amount the numbers are shifted by is related to the stuff about arithmetic fields & groups & such... maybe I'll look into it later, but statistically speaking, probably not :) )