3

A recent paper by Vigna starts with an explanation of the history of Mersenne-Twister (MT), and why it has prevailed so far. The original paper about the Mersenne Twister was published by Makoto Matsumoto and Takuji Nishimura in 1997 [22]. At that time, the PRNG had several interesting properties. In particular, it was easy to build generators with a very ...


3

Amplification is equivalent to "stretch", the number of (seemingly) random bits that your algorithm generates given the truly random seed. Let $G:\{0,1\}^*\rightarrow\{0,1\}^*$ be a PRG that maps strings of length $n$ to strings of length $l(n)$, then $l(n)$ is said to be the stretch function of $G$. If $l(n)>n$ and $l$ is injective, then you ...


3

If you want just some basic ideas what you might test. The simplest test just generates a million random numbers and puts them into say 100 buckets depending on their value. Each bucket should contain about 10,000 random numbers. If not, your random number generator is off. However, just generating 1, 2, 3, 4, 5, ... will pass this test, so it's not a very ...


2

We can construct $S$ such that polynomial-time generators for $A$ exist, while no generator exists for $S^{c}$. Pick $S$ such that all strings starting with $1$ are in it, and exactly half of all strings starting with $0$ are in it. A sampler that sets the first bit of $x$ to $1$ and outputs it always generates an element in $S$, and generates exactly $\...


2

I'm not sure what's the simplest way, but you can use diagonalization. We will construct an oracle for the following problem: $$ L = \{ x : O(y) = 0 \text{ for all } |y|=|x| \}, $$ where $O$ is some oracle that we construct by diagonalization. The same oracle will also be used to solve $L$ in randomized polynomial time, but we will ensure that it doesn't ...


2

I can't argue with the second paragraph of D.W.'s answer, and D.W. is right that all tests have limitations: That's intrinsic to PRNG-testing. But TestU01 is still pretty much state of the art. You can use the NIST suite, too, which includes some tests not in TestU01, I believe. You might want to skim L'Ecuyer and Simard's paper on TestU01 and O'Neill's ...


2

Another quite elegant method is to use bisection as described in this stackoverflow answer. The idea is to keep two words, one known to have at most k bits set and one known to have at least k bits set, and use randomness to move one of these towards having exactly k bits. Here is some source code to illustrate it: word randomKBits(int k) { word min = 0;...


2

Given the same internal state, a pseudorandom number generator (PRNG) must produce the same output. PRNGs have a period: if you run one long enough, it will start repeating the same sequence. (For good PRNGs, the period is long enough that you don't have to worry about it.) For very simple PRNGs such as a simple linear congruent generator of the form new ...


2

While this looks like a programming question, the real misunderstanding is in how to use pseudorandom number generators. A pseudorandom number generator is initialized using a seed (we later expand on that). Once initialized, it can be called to output a (seemingly) infinite sequence of random bits or integers (the sequence will be periodic, but the period ...


1

Define what you mean by similar (any way you like). For a given, fixed x let the probability that a random number y is similar to x be p. Then the probability that n consecutive random numbers $y_1$ to $y_n$ are all similar to x is $p^n$. Now let the numbers x and $y_1$ to $y_n$ be numbers generated by a PRNG. Then either the probability that $y_1$ to $...


1

The likelihood of, e.g. a string "000000" should be exactly the same as every other six-bit strings, i.e. $2^{-6}$ for each. To see if a particular PRNG satisfies such properties requires either hairy math (see for example the exhaustive discussion of congruential generators in Knuth's "Seminumerical Algorithms", it has a chapter on random numbers, other ...


Only top voted, non community-wiki answers of a minimum length are eligible