7

I need some good pseudo random number generator that can be computed like a pure function from its previous output without any state hiding. Under "good" I mean:

  1. I must be able to parametrize generator in such way that running it for 2^n iterations with any parameters (or with some large subset of them) should cover all or almost all values between 0 and 2^n - 1, where n is the number of bits in output value.

  2. Combined generator output of n + p bits must cover all or almost all values between 0 and 2^(n + p) - 1 if I run it for 2^n iterations for every possible combination of its parameters, where p is the number of bits in parameters.

For example, LCG can be computed like a pure function and it can meet first condition, but it can not meet second one. Say, we have 32-bit LCG, m = 2^32 and it is constant, our p = 64 (two 32-bit parameters a and c), n + p = 96, so we must peek data by three ints from output to meet second condition. Unfortunately, condition can not be meet because of strictly alternating sequence of odd and even ints in output. To overcome this, hidden state must be introduced, but that makes function not pure and breaks first condition (long hidden period).

EDIT: Strictly speaking, I want family of functions parametrized by p bits and with full state of n bits, each generating all possible binary strings of p + n bits in unique "randomish" way, not just continuously incrementing (p + n)-bit int. Parametrization required to select that unique way.

Am I wanting too much?

actual
  • 2,370
  • 1
  • 21
  • 32
  • You want a random number generator to generate an almost distinct sequence? –  May 20 '10 at 16:44
  • @Moron, yes. Generator should be able to generate all or almost all possible distinct bit sequences of predefined length L in multiple runs with different parameters doing no more than 2^n iterations for each run, where n < L <= n + p. – actual May 20 '10 at 17:26
  • 2
    If you expect k distinct numbers in k calls, it is not random at all. For e.g. I can always predict the last one! Or did I misunderstand? –  May 20 '10 at 17:42
  • @Moron, all pseudo random number generators are not random at all, they are deterministic. I'm just looking for PRNGs with the properties described above. – actual May 20 '10 at 17:58
  • 2
    Good luck finding them. 'good' PRNGs are random enough to not have this property, btw. –  May 20 '10 at 18:05
  • 1
    @Moron, any PRNG is endless repeating sequence, just because its state have finite size. If you have state of K bits the period of that repeating sequence can not be longer than 2^K. PRNGs you think are good just showing you few bits of real hidden state. You can not produce information from nothing. – actual May 20 '10 at 18:31
  • @actual: Have you heard of the birthday paradox? –  May 20 '10 at 19:10
  • 1
    @Moron, okay, if you have state of 8 bits you can generate at most 256 different values and the period of your PRNG can not be longer than 256. At this point you must decide what you want, to generate 256 different values in this period of 256 values or to sacrifice one or many of them to fulfill birthday paradox. In the second case your "good" PRNG will never generate some numbers, 13 for example, that will be the lucky PRNG. – actual May 20 '10 at 19:38
  • 1
    Why should a PRNG even have a 'period'? All the finiteness of the possible values says that once you generate 257 numbers, you are bound to have duplicates. If a PRNG has a period, then it is not a 'good' PRNG as you can predict the whole sequence! –  May 20 '10 at 20:27
  • @Moron, and we start it again. Period exists because of finite state and deterministic algorithm. For example, if you have state of 1 bit (bool), depending on the initial value you can only generate two changing sequences: 0101(01) and 1010(10), each with period of 2. To generate twice as more you should extend the state by one bit, that will also double the period. You can not avoid periods no mater how big your state is. – actual May 21 '10 at 04:06
  • @actual. Perhaps we are talking two different things. Say I had a 'PRNG' which returned the digits of pi... Anyway, please forgive me if I don't respond to further comments. I do hope you find something that you can use. –  May 21 '10 at 04:15
  • Moron is right in that if your state has n bits, you can't let your PRNG run up to anywhere near 2^n iterations or it isn't very 'R' (even 2^(n/2) iterations is pushing it). If you wanted to generate random permutations, then maybe the story changes. – Keith Randall May 21 '10 at 04:23
  • @Moron, we are talking about same thing, but you concentrating on partial visible state (returning values) while I concentrating on full hidden state. In case of Pi, you should somehow store current position within Pi digits (state of your calculation) between calls to generator. Since Pi never ends, infinitely growing amount of memory required to store that information related to position. – actual May 21 '10 at 04:44
  • @Keith, what if I want permutations? Strictly speaking, I want family of functions parametrized by p bits and with state of n bits, each generating all permutation of p + n bits in unique "randomish" way, not just continuously incrementing (p + n)-bit int. Parametrization required to select that unique way. – actual May 21 '10 at 05:05

2 Answers2

2

You can use any block cipher, with a fixed key. To generate the next number, decrypt the current one, increment it, and re-encrypt it. Because block ciphers are 1:1, they'll necessarily iterate through every number in the output domain before repeating.

Nick Johnson
  • 100,655
  • 16
  • 128
  • 198
  • Interesting idea, but too slow for my application. Any way, thanks. – actual May 21 '10 at 03:27
  • Hmm... maybe not so slow. How do you think will it work, if I will generate key of width p, not n + p, and start XORing it with data of n + p width. Will it generate all combinations of n + p width? – actual May 21 '10 at 03:42
  • Depends where you get the data. Broadly speaking, that probably won't generate a permutation. – Nick Johnson May 21 '10 at 17:46
1

Try LFSR
All you need is list of primitive polynomials.
Period of generating finite field this way, generates field of size 2^n-1. But you can generalise this procedure to generate anything whit period of k^n-1.

I have not seen this implemented, but all you have to implement is shifting numbers by small number s>n where gcd(s,2^n-1) == 1. gcd stands for greatest common divisor

Luka Rahne
  • 10,336
  • 3
  • 34
  • 56
  • As I understand, there is subset of combined values containing zeros that can not be generated. – actual May 21 '10 at 03:34
  • That is true. You should manualy add support for zeroes if you need it and just jump from predefined value for instance 0x001 to 0x000 and than back to next value of 0x001. – Luka Rahne May 21 '10 at 07:42