46
votes
Why do we not combine random number generators?
Sure, you can combine PRNGs like this, if you want, assuming they are seeded independently. However, it will be slower and it probably won't solve the most pressing problems that people have.
In ...
D.W.♦
- 156k
39
votes
Accepted
Is there a PRNG that visits every number exactly once, in a non-trivial bitspace, without repetition, without large memory usage, before it cycles?
Sure. Pick a block cipher (i.e., pseudorandom permutation), $E_K$, and a random key for it, $K$. Let $x_i=E_K(i)$. Then this has the properties you are looking for.
Short explanation:
As the block ...
D.W.♦
- 156k
28
votes
Accepted
Simulating a probability of 1 of 2^N with less than N random bits
Wow, great question! Let me try to explain the resolution. It'll take three distinct steps.
The first thing to note is that the entropy is focused more on the average number of bits needed per draw,...
D.W.♦
- 156k
23
votes
Why is the Mersenne Twister regarded as good?
The initial Mersenne-Twister (MT) was regarded as good for some years, until it was found out to be pretty bad with the more advanced TestU01 BigCrush tests and better PRNGs.
This page lists the ...
- 457
20
votes
Why is the Mersenne Twister regarded as good?
I am the Editor who accepted the MT paper in ACM TOMS back in 1998 and I am also the designer of TestU01. I do not use MT, but mostly MRG32k3a, MRG31k3p, and LRSR113. To know more about these, about ...
- 201
20
votes
Is there a PRNG that visits every number exactly once, in a non-trivial bitspace, without repetition, without large memory usage, before it cycles?
A linear-feedback shift register (LFSR) is a terrible PRNG(*),
but (with correct selection of feedback taps) it seems to meet all your qualifications.
A LFSR can run extremely fast -- faster than ...
- 886
18
votes
Why do we not combine random number generators?
In fact, something of a breakthrough has just been announced by doing precisely this.
University of Texas computer science professor David Zuckerman and PhD student Eshan Chattopadhyay found that a "...
- 827
12
votes
Accepted
PRNG for generating numbers with n set bits exactly
What you need is a random number between 0 and ${ 64 \choose n } - 1$. The problem then is to turn this into the bit pattern.
This is known as enumerative coding, and it's one of the oldest deployed ...
- 21.7k
11
votes
Accepted
Why is the Mersenne Twister regarded as good?
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 ...
- 228
11
votes
Is there a PRNG that visits every number exactly once, in a non-trivial bitspace, without repetition, without large memory usage, before it cycles?
The period of a PRNG is how many random numbers you can generate before the sequence starts to repeat. If you don't mind using lower-quality PRNG algorithms, some classic ones (which fell out of ...
- 841
10
votes
Accepted
Recover PRNG description from consecutive outputs
There's no single method to determine the type of the PRNG. Indeed, for a cryptographic-strength PRNG you can't distinguish its output from truly random, so you can't determine the type of such PRNGs ...
D.W.♦
- 156k
9
votes
Why is the Mersenne Twister regarded as good?
Somewhat like sorting algorithms in this regard, there is no "one size fits all" PRNG. Different ones are used for different purposes and there is a wide variety of design criteria and uses. It is ...
- 11k
9
votes
Accepted
What makes a pseudorandom generator, a high quality one?
There are several criteria for the quality of a PRNG:
How fast it is. This includes how fast it is to setup it, and how fast it is to produce a single bit (amortized).
How difficult it is to guess ...
- 275k
8
votes
Accepted
Why do we not combine random number generators?
IIRC (and this is from memory), the 1955 Rand bestseller A Million Random Digits did something like this. Before computers were cheap, people picked random numbers out of this book.
The authors ...
- 104
8
votes
Why do we not combine random number generators?
Suppose that $X_1,\ldots,X_n$ is a pseudorandom binary sequence. That is, each $X_i$ is a random variable supported on $\{0,1\}$, and the variables $X_1,\ldots,X_n$ are not necessarily independent. We ...
- 275k
7
votes
Accepted
Feedback polynomial of 7-bit Linear Feedback Shift Register
The feedback polynomial is $x^7 + x^6 + x^5 + x^1 + 1$ and can be computed using the Berlekamp-Massey algorithm.
- 186
7
votes
Accepted
One way recurrence O(N)->O(1)
There are two answers: one that solves your problem, and one that answers your question. I'll start with the first. One way to make sure that previous states cannot be backtracked from generated ...
- 4,282
6
votes
Are all pseudo-random number generators ultimately periodic?
Simple example of pseudo-random sequence that is not periodic:
concatenate together the binary representations of all positive integers, in order:
...
- 209
6
votes
Accepted
What's relation between Kolmogorov complexity and pseudorandomness?
The standard notion of pseudorandomness is about a process. You can say that the process (the pseudorandom generator) is pseudorandom, or not. The notion of pseudorandomness of a single string is ...
D.W.♦
- 156k
6
votes
PRNG for a gaussian distribution?
You can generate any distribution by using a standard PRNG to choose $X$ uniformly from the interval $[0,1]$ and then returning $F^{-1}(X)$, where $F$ is the cumulative distribution function of ...
- 81.4k
5
votes
Accepted
What does it mean to fool a function?
Let's start with some background. The context is derandomization:
Given a randomized algorithm, is there an equivalent deterministic algorithm?
Let's consider a randomized algorithm for some ...
- 275k
5
votes
Why do we not combine random number generators?
I'll give this a shot, since I'm sufficiently disturbed by the advice given in some of the other answers.
Let $\vec{X},\vec{Y}$ be infinite bit sequences generated by two RNGs (not necessarily PRNGs ...
- 209
5
votes
Feedback polynomial of 7-bit Linear Feedback Shift Register
There is a comprehensive and excellent answer in this earlier “Cryptanalysis of Linear Feedback Shift Registers” question. Alternatively, if you know the order of the recurrence is $n$, you can solve ...
- 582
5
votes
Accepted
How good (or bad) is my makeshift PRNG?
There is no such test. All automated tests for examining the randomness of a PRNG have limitations. If you read some papers in the literature that propose PRNGs, you might notice that they do more ...
D.W.♦
- 156k
5
votes
Accepted
What are the advantages of using PRNG over TRNG?
It's an apples and oranges comparison.
When you want something to be truly random, you must use a TRNG. Examples include a lottery, or a secret/private key in cryptography.
When you want something ...
- 519
4
votes
Introductory Book on Pseudo-Random Number Generation
The book Random numbers and computers by Ronald T. Kneusel, recently published by Springer, contains pseudorandom number generation algorithms, evaluation techniques, and code examples in C and Python....
- 3,252
4
votes
Could PRNGs make use of more internal state?
Because, for any practical purpose, a PRNG with sufficiently, but finitely many states is indistinguishable from one with infinitely many. Mersenne Twister has a period of $2^{19937} - 1$, [insert ...
- 13.2k
4
votes
Is there a way to incrementally degrade the quality of a PRNG?
There are many possible ways to degrade its output, but here is one simple choice:
Think of your PRNG as outputting a sequence of bits. For a good PRNG, each bit would be uniformly distributed (...
D.W.♦
- 156k
4
votes
One way recurrence O(N)->O(1)
(A follow up to the accepted answer, to some degree...)
Using a hash function in this way is somewhat equivalent to fast forwarding a pseudorandom number generator.
A linear congruential generator (...
- 203
4
votes
Accepted
Recover NLFSR description from given output
Normally we evaluate PRNGs under the model where the source code is available and fully known, and where the output is a deterministic function of the seed. This leaves multiple possibilities for how ...
D.W.♦
- 156k
Only top scored, non community-wiki answers of a minimum length are eligible