如何证明一随机数生成器优于另一种？ [英] How to Prove one Random Number Generator is Better Than Another?

问题描述

你怎么证明一个RNG比另一种更好呢？

How do you prove that one RNG is better than another?

我并不是在运行方面，但熵生成，而量 - 这也卷在周期性（低周期=低熵）的概念

I don't mean in terms of runtime, but rather the amount of entropy "generated" - which also rolls in the notion of periodicity (low period = low entropy).

能否RNG予以证明最优？或者，这是一个无法得到的目标是什么？通过优化，我的意思是任何顺序等可能与独立于过去或未来的结果。

Can a RNG be provable optimal? Or is this an unobtainable goal? By optimal, I mean any sequence is equally likely and independent of past or future results.

我感兴趣的算法，而不是宇宙背景采样装置或物理随机性其他来源（是随机的或只是复杂？）

I'm interested in algorithms, not cosmic background sampling devices or other sources of physical "randomness" (is it random or just complex?)

推荐答案

旧标准进行测试使用的是顽固分子的测试。 http://en.wikipedia.org/wiki/Diehard_tests 这已被取代由NIST测试这DKnight指出： http://csrc.nist.gov/groups/ ST /工具/ RNG / index.html的。积重难返wiki文章为您提供了一种被看的东西的一个很好的概述。 NIST的位将需要更多的挖掘。

The old standard for testing used to be the "Diehard tests." http://en.wikipedia.org/wiki/Diehard_tests This has been superceded by the NIST tests that DKnight pointed out: http://csrc.nist.gov/groups/ST/toolkit/rng/index.html. The Diehard wiki article gives you a good overview of the kind of things that are looked at. The NIST bit will take a bit more digging.

当你的状态是，没有伪RNG（算法）可以证明最优的。它们都具有种子值和依赖于输入，以产生一个值。如果您知道种子的状态，你知道下一个值。作为一个例子，看看 http://en.wikipedia.org/wiki/Mersenne_twister 。我主要是喜欢它，因为真棒的名字，但文章做得很好解释PRNG的信条。

As you state it, no pseudo RNG (algorithm) can be proven optimal. They all have a seed value and are dependent on the input to generate a value. If you know the seed and the state, you know the next value. As an example, check out http://en.wikipedia.org/wiki/Mersenne_twister. I like it mostly because of the awesome name, but the article does a good job explaining the tenets of a PRNG.

这篇关于如何证明一随机数生成器优于另一种？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！