请输入您要查询的百科知识:

 

词条 Xoroshiro128+
释义

  1. Statistical Quality

  2. Quotations

  3. Implementations

  4. See also

  5. References

  6. External links

xoroshiro128+ (named after its operations: XOR, rotate, shift, rotate) is a pseudorandom number generator intended as a successor to xorshift+. Instead of perpetuating Marsaglia's tradition of xorshift as a basic operation, xoroshiro128+ uses a shift/rotate-based linear transformation designed by Sebastiano Vigna in collaboration with David Blackman. The result is a significant improvement in speed (well below a nanosecond per integer) and a significant improvement in statistical quality.[1]

Statistical Quality

The authors of xoroshiro128+ acknowledge that it does not pass all statistical tests, stating

It passes all tests we are aware of except for the four lower bits, which might fail linearity tests (and just those), so if low linear complexity is not considered an issue (as it is usually the case) it can be used to generate 64-bit outputs, too; moreover, this generator has a very mild Hamming-weight dependency making our test (http://prng.di.unimi.it/hwd.php) fail after 8 TB of output; we believe this slight bias cannot affect any application.[2]

These claims about not passing tests can be confirmed by running PractRand on the input, resulting in output like that shown below:

RNG_test using PractRand version 0.93RNG = RNG_stdin64, seed = 0xfac83126test set = normal, folding = standard (64 bit)rng=RNG_stdin64, seed=0xfac83126length= 128 megabytes (2^27 bytes), time= 2.1 seconds  Test Name                         Raw       Processed     Evaluation  [Low1/64]BRank(12):256(2)         R= +3748  p~=  3e-1129    FAIL !!!!!!!!    [Low1/64]BRank(12):384(1)         R= +5405  p~=  3e-1628    FAIL !!!!!!!!    ...and 146 test result(s) without anomalies

Acknowledging the weak low order bit, the authors go on to say:

We suggest to use a sign test to extract a random Boolean value[2]

Thus, programmers should prefer the highest bits (e.g., making a heads/tails by writing random_number < 0 rather than random_number & 1). It must be noted, though, that the same test is failed by the Mersenne Twister, WELL, etc., so the issue is mainly of academic concern.

As stated in the comments, the generator fails a Hamming-weight dependency test developed by Blackman and Vigna[3] after 8 TB of data. As a comparison, for some choice of parameters the Mersenne Twister at 607 bits fails the same test after less than a gigabyte of data.

Quotations

David Meister, who implemented it in Clojure, made some valuable statements:

"This is a clojure implementation of the xoroshiro128+ PRNG described at http://xoroshiro.di.unimi.it. The algorithm has been shown to be fast and produce superior statistical results to many PRNGs shipped with languages, including Java. The statistical results have been verified in both PractRand and TestU01 by the authors. xoroshiro128+ is designed to be the successor to xorshift128+, currently used in the JavaScript engines of Chrome, Firefox and Safari. Both xorshift128+ and xoroshiro128+ have a period of 2128 but xoroshiro128+ is benchmarked by the authors as 20% faster and with 20% fewer failures in BigCrush than its predecessor."[4]

Matt Gallagher, in his study on random number generators in Swift made the following conclusion:

It looks like Xoroshiro is the best general purpose algorithm currently available. Low memory (just 128 bits of storage), extremely high performance (1.2 nanoseconds per 64-bit number, after subtracting baseline overheads) and very well distributed (beating other algorithms on a range of automated tests). Mersenne Twister might still be a better choice for highly conservative projects unwilling to switch to such a new algorithm, but the current generation of statistically tested algorithms brings a baseline of assurance from the outset that previous generations lacked.[5]

Implementations

  • Original C source code implementation
  • [https://github.com/SquidPony/SquidLib/blob/master/squidlib-util/src/main/java/squidpony/squidmath/XoRoRNG.java Java Implementation]
  • [https://github.com/thedavidmeister/xoroshiro128 Clojure implementation]
  • [https://github.com/mattgallagher/CwlUtils Swift implementation] in [https://github.com/mattgallagher/CwlUtils/blob/master/CwlUtils/CwlRandom.swift this file] and comparison with other RNG's here: [https://www.cocoawithlove.com/blog/2016/05/19/random-numbers.html "Random number generators in Swift"].
  • [https://github.com/jannisteunissen/rng_fortran Fortran implementation]
  • [https://gist.github.com/kaustav-das/cf6b60638e62abb0394737f19f2fcf03 C# Implementation]

See also

  • List of Pseudorandom Number Generators
  • Pseudorandom Number Generator
  • Xorshift
  • Mersenne Twister
  • WELL

References

1. ^{{cite arXiv |last=Blackman |first=David |last2=Vigna|first2=Sebastiano|eprint=1805.01407 |title= Scrambled Linear Pseudorandom Generators|class=cs.DS |date= }}
2. ^{{Cite web|url=http://prng.di.unimi.it/xoroshiro128plus.c|title=Original C source code implementation of xoroshiro128+|last=Blackman |first=David|last2= Vigna |first2= Sebastiano|date=2018|access-date=May 4, 2018}}
3. ^{{Cite web|url=http://prng.di.unimi.it/hwd.php|title=Testing Hamming-weight dependencies|date=May 3, 2018|access-date=May 3, 2018}}
4. ^{{Cite web|url=https://github.com/thedavidmeister/xoroshiro128|title=Clojure implementation of the xoroshiro128+ PRNG described at web site xoroshiro.di.unimi.it|last=Meister|first=David|date=August 1, 2016|website=github.com|publisher=|access-date=November 2, 2016}}
5. ^{{Cite web|url=https://www.cocoawithlove.com/blog/2016/05/19/random-numbers.html|title=Random number generators in Swift|last=Gallagher|first=Matt|date=May 19, 2016|website=www.cocoawithlove.com|publisher=|access-date=November 2, 2016}}

External links

  • {{Cite web | url=http://vigna.di.unimi.it/xorshift/|title=xoshiro / xoroshiro generators and the PRNG shootout | year =2018 | first = Sebastiano | last = Vigna | access-date= 2018-05-04 }}

1 : Pseudorandom number generators

随便看

 

开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。

 

Copyright © 2023 OENC.NET All Rights Reserved
京ICP备2021023879号 更新时间:2024/11/11 1:09:39