3

I am trying to implement an xorshift* PRNG (practically an xorshift with a multiplication step in the end) as a long term replacement of Java's Math.Random. I have been reading an article pointed out in an answer to another question, but I am confused with the magical $M_t$ values used for the multiplication.

The article comments on this number in the following way:

The goodness of the multiplier, however, is established by a figure of merit which is a normalized best distance between the hyperplanes of families covering tuples of length $t$ given by successive outputs of the generators. The length t is an additional parameter, and $M_{32}$ has the best figures of merit for $t = 32$. Clearly, if an alternative multiplier provides improvements on both t and the associated figure of merit, we have a hint that it could be chosen instead of $M_{32}$.

Lacking that possibility, what if we scramble xorshift64's output with a multiplier that has better figures of merit for a lower $t$? We thus also ran experiment with the multiplier $M_8 = 1181783497276652981$, which has a better figure of merit for $t = 8$ [L'Ecuyer 1999], and the multiplier $M_2 = 8372773778140471301$, which has a better figure of merit for $t = 2$ and was kindly provided by Richard Simard.

Seeing as the author has used different multipliers in different xorshift* implementations (different state size) I am not sure how to interpret the role of $t$ in $M_t$. Here's the article by L'Ecuyer that's referenced above.

posdef
  • 739
  • 8
  • 24

1 Answers1

2

The paper is written using three multipliers to check experimentally if the $t$ parameter has any influence on the result. For all I could see, there is no such influence. Indeed, it could be even possible that a random invertible element of $\mathbf Z/2^{64}\mathbf Z$ works as well (even if it doesn't have good spectral properties). The choice of a multiplier with good spectral properties comes from a suggestion in "Numerical Recipes".

There is no connection between $t$ and the state-space size. $t$ is an independent parameter. In the paper I try all combinations.

BTW, if you need a Java implementation is already done: http://dsiutils.di.unimi.it/

seba
  • 286
  • 2
  • 5
  • The interesting bit is that there are several possible numbers in the article by L'Ecuyer that fit the criteria, if I understand it correctly (there are several other numbers listed where 2685821657736338717 is denoted in the paper :)) – posdef Jan 30 '14 at 17:43
  • On a side note, what is the class called? I can't seem to locate it in the jar file – posdef Jan 30 '14 at 17:50
  • Yes. Experimentally, using one or another doesn't produce visible changes in the results of the test suite. http://dsiutils.di.unimi.it/docs/it/unimi/dsi/util/XorShift64StarRandom.html http://dsiutils.di.unimi.it/docs/it/unimi/dsi/util/XorShift1024StarRandom.html – seba Jan 30 '14 at 21:20