An experimental exploration of Marsaglia’s xorshift generators, scrambled 5
trixRank, MaxOft and Permutation test of BigCrush, which highlights a significant weakness
in its lower bits.
We remark that in this paper we do not pursue the search for equidistribution—the
property that all tuples of consecutive values, seen as vectors in the unit cube, are evenly
distributed, as done, for instance, by Panneton and L’Ecuyer [2005]. Brent [2010] has already
argued in detail that for long-period generators equidistribution is not particularly desirable,
as it is a property of the whole sequence produced by the generator, and in the case of
a long-period generator only a minuscule fraction of the sequence can be actually used.
Moreover, equidistribution is currently impossible to evaluate exactly for long-period non-
linear generators, and in the formulation commonly used in the literature it is known to be
biased towards the high bits [L’Ecuyer and Panneton 2005]: for instance, the WELL1024a
generator has been designed to be maximally equidistributed [Panneton et al. 2006], and
indeed it has measure of equidistribution ∆
1
= 0, but the generator obtained by reversing
its bits has ∆
1
= 366: a quite counterintuitive result, as in general we expect all bits to be
equally important.
Another problem with equidistribution is that it is intrinsically unstable, unless we restrict
its usage to the class of linear generators, only. Indeed, if we take a maximally equidistributed
sequence, no matter how long, and we flip the most significant bit of a single element of the
sequence, the new sequence will have the worst possible ∆
1
. For instance, by flipping the
most significant bit of a single chosen value out of the output of WELL1024a we can turn its
equidistribution measure to ∆
1
= 4143. But for any statistical or practical purpose the two
sequences are indistinguishable—we are modifying one bit out of 2
5
(2
1024
− 1). However, in
general this paradoxical behaviour is not a big issue, because the modified sequence can no
longer be emitted by a linear generator.
We note that since multiplication by an invertible constant induces a permutation of the
space of 64-bit values (and thus of t-tuples of such values), it preserves some of the equidis-
tribution properties of the underlying generator (this is true of any bijective scrambling
function); more details will be given in the rest of the paper.
4. RESULTS FOR xorshift64 GENERATORS
First of all, all generators fail at all seeds the MatrixRank test from TestU01’s SmallCrush
suite.
6
A score-rank plot
7
of the SmallCrush scores for all generators is shown in Figure 2.
The plot associates with abscissa x the number of generators with x or more failures. We
observe immediately that there is a wide range of quality among the generators examined.
The “bumps” in the plot corresponds to new tests failed systematically.
A closer inspection would confirm that there is just a weak correlation between scores
of algorithms conjugate by reversal, because of the bias of TestU01 towards high bits. We
thus report in Table I reports the best four generators by combined scores (i.e., adding
the scores of conjugate generators), which are the only ones failing systematically just the
MatrixRank test. The table reports also results for the generator A
0
(13, 7, 17) suggested by
Marsaglia in his original paper, claiming that it “will provide an excellent period 2
64
− 1
RNG, [. . . ] but any of the above 2200 choices is likely to do as well”. Clearly, this is not
the case: A
0
(13, 7, 17)/A
1
(13, 7, 17) ranks 655 in the combined SmallCrush ranking and fails
systematically several tests.
6
Panneton and L’Ecuyer [2005] reports that half of the generators fail this test, but the authors have chosen
to use only 32 of the 64 generated bits as output bits, in practice applying a kind of decimation to the
output of the generator.
7
Score-rank plots are the numerosity-based discrete analogous of the complementary cumulative distribution
function of scores. They give a much clearer picture than frequency dot plots when the data points are
scattered and highly variable.
剩余22页未读，继续阅读
weixin_38639872
- 粉丝: 9
- 资源: 952
我的内容管理
展开
最新资源
- 新型矿用本安直流稳压电源设计：双重保护电路
- 煤矿掘进工作面安全因素研究：结构方程模型
- 利用同位素位移探测原子内部新型力
- 钻锚机钻臂动力学仿真分析与优化
- 钻孔成像技术在巷道松动圈检测与支护设计中的应用
- 极化与非极化ep碰撞中J/ψ的Sivers与cos2φ效应：理论分析与COMPASS验证
- 新疆矿区1200m深孔钻探关键技术与实践
- 建筑行业事故预防：综合动态事故致因理论的应用
- 北斗卫星监测系统在电网塔形实时监控中的应用
- 煤层气羽状水平井数值模拟：交替隐式算法的应用
- 开放字符串T对偶与双空间坐标变换
- 煤矿瓦斯抽采半径测定新方法——瓦斯储量法
- 大倾角大采高工作面设备稳定与安全控制关键技术
- 超标违规背景下的热波动影响分析
- 中国煤矿选煤设计进展与挑战：历史、现状与未来发展
- 反演技术与RBF神经网络在移动机器人控制中的应用
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
