Hacker News Reader

Comment by GrantMoyer | Hacker News Reader

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

View on HN

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...)

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

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 :) )

Reply on news.ycombinator.com