Questions tagged [pseudo-random-generators]

Questions about algorithms that deterministically generate sequences of numbers that have stochastic properties of random sequences.

Filter by
Sorted by
Tagged with
38
votes
7answers
4k views

Can PRNGs be used to magically compress stuff?

This idea occurred to me as a kid learning to program and on first encountering PRNG's. I still don't know how realistic it is, but now there's stack exchange. Here's a 14 year-old's scheme for an ...
39
votes
3answers
14k views

Why is the Mersenne Twister regarded as good?

The Mersenne Twister is widely regarded as good. Heck, the CPython source says that it "is one of the most extensively tested generators in existence." But what does this mean? When asked to list ...
60
votes
6answers
8k views

Why do we not combine random number generators?

There are many applications where a pseudo random number generator is used. So people implement one that they think is great only to find later that it's flawed. Something like this happened with ...
12
votes
3answers
1k views

PRNG for generating numbers with n set bits exactly

I'm currently writing some code to generate binary data. I specifically need to generate 64-bit numbers with a given number of set bits; more precisely, the procedure should take some $0 < n < ...
9
votes
4answers
900 views

What is a good algorithm for generating random DFAs?

I am generating random DFAs to test a DFA reduction algorithm on them. The algorithm that I'm using right now is as follows: for each state $q$, for each symbol in the alphabet $c$, add $\delta (q, c)...
2
votes
3answers
1k views

Feedback polynomial of 7-bit Linear Feedback Shift Register

My friend gave me a question to solve. The question he asked me was: the following sequence has been generated by a 7-bit linear feedback shift register. He asked me to find the feedback polynomial. I ...
1
vote
2answers
300 views

Pseudo random, unqiue integer numbers in a given range

I need an algorithm that gives me integer numbers with the following features: Numbers must be in a given range $[n..m]$; Numbers must be returned in pseudo-random order (random at visual inspection ...
13
votes
1answer
2k views

Choosing taps for Linear Feedback Shift Register

I am confused about how taps are chosen for Linear Feedback Shift Registers. I have a diagram which shows a LFSR with connection polynomial $C(X) = X^5 + X^2 + 1$. The five stages are labelled: $R4, ...
7
votes
1answer
264 views

Recover PRNG description from consecutive outputs

Given the outputs of the pseudorandom numbers generator how can one determine the type (e.g. Linear Feedback Shift Register), Multiply-With-Carry, Linear Congruential Generator etc.) and recover the ...
5
votes
1answer
278 views

What's relation between Kolmogorov complexity and pseudorandomness?

In a comment on this question, @Kaveh wondered whether the questioner really wanted to ask "is there a relation between strings with high Kolmogorov complexity and pseudorandomness?" This is not the ...
6
votes
1answer
3k views

Period of a pseudo-random sequence generated using an LFSR

I was trying to generate maximal length pseudo random sequence using an linear feedback shift register (LFSR). I have read from many sources that the length of the pseudo random sequence generated ...
4
votes
1answer
166 views

Existence of suitable pseudo-random number generators to derandomize BPP to P

I am struggling to understand how the known oracle, and conditional derandomization results connecting $BPP$ and $P$, relate to each other. My understanding is that if there is a suitably strong ...
3
votes
1answer
255 views

Perfect random number generation using normal numbers

This paper describes a computable normal number. One property of normal numbers is that, written in binary, the $i^{th}$ bit is equally likely to be 0 or 1 (in the sense that as $n$ gets large, the ...
1
vote
1answer
247 views

Periods of an LFSR with characteristic polynomial that is a product of primitive polynomials

I want to find the minimal period of any state of an LFSR (except the initial state of all zeroes) whose characteristic polynomial is the product of two primitive polynomials. In particular, $f(x),g(...