Hacktoberfest 2026: le issue che i maintainer hanno segnato per ottobre, aperte e adatte ai principianti. Sfoglia le issue Hacktoberfest

Incorrect information about PRNG quality

Aperta
#168 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
5/5
Tempo stimato
Più di una settimana
Idoneità per principianti
35/100
Tipo di issue
Documentazione
Chiarezza
Da chiarire
Stato di attività
Attiva
Stack tecnologico
cpp
Ambito
documentation

Direzione di ricerca

Start with doc/generators.qbk and review the cited literature and reproduced results for the claims about cycle length, uniformity, and simulation suitability. Determine which generator descriptions require correction and whether the proposed stream-cipher additions are within scope; done means the documentation accurately reflects the supported evidence and agreed recommendations.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

The next manual part contains an incorrect information about quality of some generators:

https://github.com/boostorg/random/blob/develop/doc/generators.qbk

It is said that "The cycle length is a rough estimate of the quality of the generator", but it is incorrect at least for additive lagged Fibonacci generators with two lags. They do fail such basic uniformity checks (comparable to Kolmogorov-Smirnov or chi-square tests by importance) as some modifications of gap test or birthday spacings test. The failure of birthday spacings test for them is described in TAOCP vol. 2 (3rd edition) and also by G.Marsaglia (https://www.jstatsoft.org/article/view/v007i03) and TestU01 authors (https://doi.org/10.1145/1268776.1268777). Such kind of defects also can cause biases in Monte-Carlo simulations (https://doi.org/10.1103/PhysRevLett.69.3382, https://doi.org/10.1142/S0129183196000235).

I've managed to reproduce some of that failures. Moreover, a modification of gap test taken from gjrand can easily detect flaws even in additive lagged Fibonacci generators with huge lags (https://github.com/alvoskov/SmokeRand/blob/main/docs/results.md).

I think that these lagged Fibonacci generators should be described as flawed and unsuitable for any simulations (or may be even as "toy generators for writing TETRIS" or "don't pass basic tests for uniformity"). The same approach probably should be applied to generators with periods shorter than 2^60: basic tests for production ready PRNG uniformity require around 10^13 values anyway. The library already has some fast and descent generators such as MT19937, Taus88, MIXMAX, xoroshiro. But some other generators with relatively large period such as rand48, ecuyer1988 are also flawed.

P.S. I've noticed that the PRNG collection includes only "bithack" type generators but not stream ciphers such as AES-CTR, ChaCha, ThreeFish-CTR or LEA-CTR. They are not only much faster than LCG such as RANLUX but also very suitable for parallelism.

Lingua principale
C++
Stelle
42
Fork
76
Merge medio
3g 22h
PR unite (30g)
6

Guida per i contributori

Nessuna guida per i contributori indicizzata per questo repository

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di boostorg/random

Tutte le issue di boostorg/random

Issue simili

Altre issue su C++

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.