2

This will of course depend on the algorithm generating the pseudo random numbers, but what I'm wondering is whether practical, usable pseudo-random number generating algorithms exist that never repeat the same number twice until their period is up.

  • 2
    I highly doubt that this would be a desirable property or one that was designed - as it makes the end of the sequence highly predictable. Some PRNGs may have this as an unintended consequence, but I really doubt it. – Ordous Mar 23 '18 at 16:01
  • 7
    A sequence of "random" numbers that never repeats a number until all numbers are used up isn't really random, is it? The desired quality of a good PRNG is even distribution across the desired numeric range, not using all of the numbers only once. – Robert Harvey Mar 23 '18 at 16:03
  • A coinflip on such a generator would mean that even best case, 50% of flips are 100% predictable. Not very random. – nvoigt Mar 23 '18 at 16:17
  • 2
    Maybe check out shuffling algorithms. Start with a set of unique numbers then shuffle them into a random order. – KChaloux Mar 23 '18 at 16:20
  • @KChaloux Right was just going to say that would appear to be the answer for a practical, usable algorithm that never repeats the same number twice. – JimmyJames Mar 23 '18 at 16:22
3

As the accepted answer correctly notes, that would be a horrible PRNG. You want the period of the generator to be many orders of magnitude larger than the number of values it generates; your proposal is that they be equal.

But your question was not "critique this idea" but rather

does a practical, usable pseudo-random number generating algorithms exist that never repeat the same number twice until their period is up.

Sure, that's easy. Here's one:

  • Choose the period you want. Call it p.
  • Plainly the number of values that the PRNG generates must be not less than p, because otherwise by the pigeonhole principle, it repeats an output in fewer than p steps. Let's suppose that the number of possible values the PRNG generates is also p, and that it generates numbers from 0 to p-1.
  • Now our algorithm is simple. We have two seeds, which we call s and i, both between 0 and p-1. s can be anything. i must be any number coprime to p. The nth element generated by the PRNG with seeds s and i is (n * i + s) % p. That is, multiply i by n, add s, and take the remainder when that value is divided by p.
  • That gives you a sequence of incredibly crappy pseudo-random numbers that repeats with period p and never generates the same number within the period, and each number is between 0 and p-1. Enjoy.
  • Let's work an example. p=10, i=3, s=5, the sequence is 5, 8, 1, 4, 7, 0, 3, 6, 9, 2 and then it repeats.
  • Notice that the low bit of the sequence produced by this algorithm toggles on each subsequent step; that's really bad!
  • You asked if any algorithm exists, not if any good algorithm exists.

That was really crappy. Can we do better?

Basically what you're asking is "I need a random permutation of this set". There are lots of good algorithms for that. Since there are p! permutations of a set with p unique items, what you have to do is uniformly choose a number between 0 and p!-1, and then generate a permutation from that number.

Generating the random seed is your problem; I describe how to turn it in to a permutation in my lengthy series on interesting properties of permutations, which you can read here:

https://ericlippert.com/2013/04/15/producing-permutations-part-one/

3

I doubt that such a PRNG exists, since it is simply not a very good PRNG. Not only do you know something about the next number in the sequence (whereas in a PRNG the whole point is that you don't know anything about the next number), but the longer the sequence gets, the more you know!

This is just a bad PRNG.

What you are talking about seems to be more a (pseudo-)random permutation than a (pseudo-)random number sequence.

1

Good pseudorandom number generator have a large period, for example C#'s implementation is more than 2⁵⁵

Since the next integer will be taken from the set of 2³² values, there will be repetitions long before its period is up.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.