32 bit version of xorshift*

[Dannii Willis]

Hi,

I want to implement a PRNG and xorshift has caught my eye. To be honest most of the debates on generators are over my head, but I can get some of the flaws with particular algorithms. I skimmed Panneton and L'Ecuyer's paper and figure that if xorshift* can avoid the flaws of xorshift for just one multiplication then why not use it?

Unfortunately the language I'm using is only 32 bit. I could implement the 64 bit algorithm manually but I really don't want to. So a couple of questions:

1. How do you choose the multiplier?

2. How do you choose which triple to use? Or does it not matter?

3. And just to clarify, because the function cycles through all numbers in the range, all seeds are equally good to start with? (Except 0 of course)

Thanks in advance!

-Dannii

[marc.b....@gmail.com]

I attempted this by simply choosing one from "Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure". Perhaps my choice of base XorShift variant and final multiplier were bad but it performed worse than a 32-bit XorWow. The former consistently fails one SmallCrush test "BirthdaySpacings" and the latter consistently passes SmallCrush. (Disclaimer: my testing methodology is likely to be flawed).

[marc.b....@gmail.com]

Actually let's back up. What's your use-case?

[marc.b....@gmail.com]

> I have no particular use case in mind. We use PRNGs all over...
Sorry for the confusion..my question was intended for the OP.

[Dannii Willis]

A roguelike game for the 32bit Glulx virtual machine. The VM has a random opcode but it's not implemented consistently, so we need our own PRNG generator for it to work across platforms.

[marc.b....@gmail.com]

So you're basically just going to be rolling dice and only a small number of them to generate a result. Long period is not important and statistical quality (other than really really bad) isn't important either. You probably could just use a power-of-two LCG and call it a day. Choose one from "Tables of...". Or you could use a 32-bit XorShift if you're not going to generating results by inspecting the bits.

[marc.b....@gmail.com]

Taking a peek at the new paper brought my mind back to this.

Although attempting to use either method doesn't seem to increase stat. quality to that of an xorshift + integer Weyl, using either does significantly increase stat quality without doubling the state space. So from a practical standpoint the decrease a memory motion might be a win for some use-cases. The specific combos I tried with minimal TestU01 result summaries:

https://gist.github.com/Marc-B-Reynolds/0b5f1db5ad7a3e453596

[marc.b....@gmail.com]

Dannii Willis asked in e-mail if the (13,17,5) I was using was a typo and should be (13,17,15). I checked the original paper and can't find that triple in the table and I also check the L'Ecuyer/Panneton review paper which does mention a typo in the original but for a different pair. So I assumed I'd made a mistake (and I changed the gist but not the results of minimal testing). I then reskimmed the two paper and the both talk specifically about (13,17,5). So is it a full-period triple or not?

[marc.b....@gmail.com]

Nevermind: I'm an idiot. abc=(5,17,13) right in the table so the original version I put up was full-period. Reverting the gist.

[Dannii Willis]

So the order doesn't matter? I guess that makes sense, they're both being shifted the same directly. Sorry then!

On 13 August 2014 17:37, <marc.b....@gmail.com> wrote:

Nevermind: I'm an idiot. abc=(5,17,13) right in the table so the original version I put up was full-period.  Reverting the gist.

--
You received this message because you are subscribed to a topic in the Google Groups "prng" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/prng/rajh-G5WvG0/unsubscribe.
To unsubscribe from this group and all its topics, send an email to prng+uns...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Dannii Willis]

I found several mentions of it being a typo, but I think they're all actually by the one guy: https://issues.dlang.org/show_bug.cgi?id=10550#c2 (see comments 2, 3, 9)

On 13 August 2014 17:25, <marc.b....@gmail.com> wrote:

Dannii Willis asked in e-mail if the (13,17,5) I was using was a typo and should be (13,17,15).  I checked the original paper and can't find that triple in the table and I also check the L'Ecuyer/Panneton review paper which does mention a typo in the original but for a different pair.  So I assumed I'd made a mistake (and I changed the gist but not the results of minimal testing).  I then reskimmed the two paper and the both talk specifically about (13,17,5).  So is it a full-period triple or not?

[marc.b....@gmail.com]

There are 8 combinations that each triple can be used. See 'On the Xorshift Random Number Generators' Proposition 4.4 on page 6.

[jayanth...@gmail.com]

Hi Dannii,

           Did you got the efficient solution for 32-bit xorshift* algorithm. if so, can you post the multiplier and triple you have used.

Thanks,

Jayanth.

[Chris Rutz]

On Thursday, April 23, 2020 at 9:42:45 AM UTC-4, jayanth...@gmail.com wrote:

Hi Dannii,

           Did you got the efficient solution for 32-bit xorshift* algorithm. if so, can you post the multiplier and triple you have used.

Old posts, so not sure if you would get any other response...

Xorshift32 is getting somewhat dated, but is simple to understand and implement. Paired with any multiplier and triples, it will still suffer some issues with its LSBs.

That being said, there is no good reason I can think of to not use Marsaglia's recommended triple that was mentioned above: 13,17,5.

If I had to pick a multiplier, I believe L'Ecuyer was referenced already above, so his recommendation might be 2891336453.

Cheers

Chris