0

I am working on developing a PRNG which transforms bits of source entropy into integers which are uniform over the range [1, N], where N is any integer greater than one.

This is exactly what randint_genmax from GNU Coreutils does.

I want to investigate the efficacy of different implementations of such a function with respect to the quality of the randomness and the expected number of bits of entropy required per call.

The problem is that I don't know how exactly I will measure "quality of randomness" in this context. I could use dieharder on the PRNG that generates the input entropy, but I have no similar methods for testing the randomness of the output.

I have looked into chi-squared tests and I thought about simulating deck shuffles and tallying the resulting permutations of the first eight or so cards. But that's just one test I could perform. I worry that it would not be comprehensive enough.

Are there existing test suites or well-known methods that I could use to run these randomness tests?

EDIT: This question is not the same because it is too general -- I need a set of tests for random integers in ranges such as [1, 7], but suites such as Dieharder operate on 32 bit integers.

The references in the answer to this question look useful, but I would like to save time by finding existing implementations somewhere.

amoeba
  • 93,463
  • 28
  • 275
  • 317
mikebolt
  • 101
  • 1
  • 2
    See https://crypto.stackexchange.com/questions/19676/how-do-you-test-randomness and https://crypto.stackexchange.com/questions/394/what-tests-can-i-do-to-ensure-my-prng-is-working-correctly – Tim Dec 19 '15 at 22:16
  • 4
    Possible duplicate of [Testing random variate generation algorithms](http://stats.stackexchange.com/questions/30/testing-random-variate-generation-algorithms) – Tim Dec 19 '15 at 22:17
  • 1
    I find the OP's clarification as to why this is not a duplicate to be convincing. – Silverfish Dec 20 '15 at 11:22
  • @Silverfish The reason Diehard/er and its cousins use 32 bit integers is because it's universally applicable to *any* PRNG. One tests a PRNG by using it to generate bits or sequences of bits and then testing those binary sequences. – whuber Dec 20 '15 at 14:13
  • @whuber Indeed, but I think that your comment may actually represent a substantive *answer* to the OP's concerns. The fact that this problem can be transformed to the situation in the proposed duplicate, but the details of that transformation are not obvious to the OP, suggests the thread merits an answer rather than a simple "closed as duplicate". – Silverfish Dec 20 '15 at 14:44
  • @Silver I agree that this is evidence the thread should stay open. I don't think I have given a substantive answer, though: that would require explaining *how* arbitrary discrete PRNGs can be used to generate binary sequences that are useful for testing them. – whuber Dec 20 '15 at 17:21
  • Curiously, generating bits from the resulting sequences is essentially the inverse of the problem I am trying to solve in the first place. Because of this, I don't think that converting back to bits in order to test the efficacy of the conversion algorithm (PRNG) would be wise. At that point I would essentially be testing the original source randomness. However, I suppose that if I proved some properties of my algorithm then I wouldn't need to worry about performing statistical experiments to validate it. That wouldn't answer this question but it would solve my problem. – mikebolt Dec 20 '15 at 21:22
  • You don't have to invert your procedure: there are plenty of different ways to convert a sequence of random integers into a sequence of random bits! Which way(s) to choose may require some understanding of what your procedure does, so that you can tailor the test to find likely sources of nonrandomness in the output. – whuber Feb 20 '17 at 23:55
  • Thanks. I ended up researching this problem in detail, and I realize now that my original question is sort of invalid. If your conversion algorithm (bits to arbitrary ranges or vice-versa) preserves randomness, then there's no need for an empirical test.For those interested, look up "Interval algorithm for random number generation" by Hao and Hoshi. It is basically a modified version of interval coding, and it preserves entropy. – mikebolt Feb 25 '17 at 02:53

0 Answers0