Tecniques to improve quality of RNGs

58 views
Skip to first unread message

lodi...@gmail.com

unread,
Jul 21, 2020, 6:15:30 AM7/21/20
to prng
I have a general question. 
Take for example xoroshiro128**. What is the best way to "provably" increase its quality?
For example, which of these options is expected to work best:

1. Output only the highest 32 bits [speed decreased by 2].
2. Skip every second generated 64bit number (ie update the internal state twice before outputting) [speed decreased by 2].
3. Instantiate and separately initialise two generators, then xadd the output of generator 1 and the reversed output of generator 2 [speed decreased by 2, memory increased by 2].
4. Instantiate two generators. The output of the first is used (with padding/doubling...) to initialise the second generator, whose output is returned to the user [speed decreased by 2, memory increased by 2]. 
5. other schemes?

I understand you'd probably be better off using a different generator. However sometimes one already has a trusted generator and would like to double check results with something which is definitely better without having to implement anything radically new (a 2x performance hit -- or even higher -- is acceptable to me for such cases, especially if the base generator is already very fast).

Lorenzo

Sebastiano Vigna

unread,
Jul 21, 2020, 9:32:41 AM7/21/20
to pr...@googlegroups.com


> On 21 Jul 2020, at 12:15, lodi...@gmail.com wrote:
>
> I have a general question.
> Take for example xoroshiro128**. What is the best way to "provably" increase its quality?
> For example, which of these options is expected to work best:
>
> 1. Output only the highest 32 bits [speed decreased by 2].
> 2. Skip every second generated 64bit number (ie update the internal state twice before outputting) [speed decreased by 2].
> 3. Instantiate and separately initialise two generators, then xadd the output of generator 1 and the reversed output of generator 2 [speed decreased by 2, memory increased by 2].
> 4. Instantiate two generators. The output of the first is used (with padding/doubling...) to initialise the second generator, whose output is returned to the user [speed decreased by 2, memory increased by 2].
> 5. other schemes?
>

I think none of these techniques give you something "provable".

Ciao,

seba

lodi...@gmail.com

unread,
Jul 24, 2020, 6:08:54 AM7/24/20
to prng
Ok, fair enough. 
What if we lower the requirement to "probably increase its quality"? 
Can't we say anything even at this level of confidence? Techniques similar to those mentioned have been used in the past (eg by ran3 in numerical recipes, by kiss generator by Marsaglia and (decimation) by the ranlux generator), even if (usually) they have no formal justification.
Any comment is welcome,

Lorenzo

On Tuesday, 21 July 2020 15:32:41 UTC+2, Sebastiano Vigna wrote:

[...]

Sebastiano Vigna

unread,
Jul 24, 2020, 7:24:46 AM7/24/20
to pr...@googlegroups.com
Exactly: no formal justification.

If you want to improve quality, I'd improve the underlying engine or the scrambler. That gives you some possibility of getting evidence.
--
Sent from my Android device with K-9 Mail. Please excuse my brevity.

Sebastiano Vigna

unread,
Jul 24, 2020, 7:27:10 AM7/24/20
to pr...@googlegroups.com
BTW, you might get some evidence by iterating twice, in the sense that you can compute the associated linear transformation and analyze it (characteristic polynomial, etc.).
Reply all
Reply to author
Forward
0 new messages