0
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ See crypto.stackexchange.com/questions/19676/… and crypto.stackexchange.com/questions/394/… $\endgroup$
    – Tim
    Commented Dec 19, 2015 at 22:16
  • 4
    $\begingroup$ Possible duplicate of Testing random variate generation algorithms $\endgroup$
    – Tim
    Commented Dec 19, 2015 at 22:17
  • 1
    $\begingroup$ I find the OP's clarification as to why this is not a duplicate to be convincing. $\endgroup$
    – Silverfish
    Commented Dec 20, 2015 at 11:22
  • $\begingroup$ @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. $\endgroup$
    – whuber ♦
    Commented Dec 20, 2015 at 14:13
  • $\begingroup$ @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". $\endgroup$
    – Silverfish
    Commented Dec 20, 2015 at 14:44

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.