Looping Random Number Generator

2

1

I'm not even sure if this is even possible, but I think it's worth a shot.

The Challenge

Code/conceptualize a pseudo-random number generator that has the potential to produce results evenly spaced out with similar frequencies... with a twist. The random number generator has to 'loop' back after Foo iterations to its beginning state then produce the exact same results. Foo is a variable of all positive integers.

For example, if the iterations amount is 4 and the random numbers generated after 4 iterations are {93,5,80,13}, then the next 4 iterations will produce {93,5,80,13}, as will the next 4 after that and so on.

Limitations

  1. Random numbers can't be pre-defined. For example, the algorithm can't simply iterate over {1,2,3,4,...int.MaxValue}, up to the iteration amount then go back to the first value.
  2. Similar to Limitation 1, random numbers can't be cached so a set of numbers can't be generated, saved, then repeatedly returned.
  3. Similar to Limitation 2, the random number generator can't be 'forced' back to a certain state. Beginning seed numbers and whatnot cannot be saved.
  4. The RNG can't use the number of iterations its run.

In other words, the Generator has to arrive back at its beginning state solely through consecutive calculations.

Objective

Shortest code wins!

JPtheK9

Posted 2015-05-08T06:39:14.947

Reputation: 129

Question was closed 2015-05-08T13:03:59.007

As Sp says, most random number generators necessarily loop back on themselves because they are only pseudo random and have a finite period.

– Calvin's Hobbies – 2015-05-08T06:51:19.140

Yes, but that period is a defined one in this challenge. Sorry about the confusion. Changed 'any' to 'all'. – JPtheK9 – 2015-05-08T06:52:27.540

Does "all positive integers" really mean all or just up to int.max? If the latter then could someone just take the first Foo values of their language's PRNG? (Assuming the language PRNG period is larger than int.max.) – Calvin's Hobbies – 2015-05-08T06:59:29.583

All can't be practically tested, so I'd say just up to int.max. Taking the first Foo values of a default PRNG would violate Limitation 2. The PRNG has to arrive back at its beginning state solely through consecutive calculations. – JPtheK9 – 2015-05-08T07:00:56.060

But the values wouldn't be saved per se. The prng would just be restarted. – Calvin's Hobbies – 2015-05-08T07:02:53.000

Ah, true. That would violate Limitation 3 though. – JPtheK9 – 2015-05-08T07:03:43.227

2What is the objective winning criterion? Shortest code? Fastest code (which leads to more questions)? – Kyle Kanos – 2015-05-08T11:10:10.543

If you loop an integer N with steps of 3 to infinity and then use seed(n%3)/seed(n%2)+seed(n%1) to create numbers, would this break limitation 3? – dwana – 2015-05-08T13:10:33.943

I added a new limitation to clear things up, and the winning objective. @dwana That kind of violates limitation 3 but I clarified it with a new limitation. – JPtheK9 – 2015-05-08T19:57:39.687

1I think you might want give a specific criteria for what counts as "reasonably random". Different PRNGs pass different tests, but if you specify the exact testing method then everybody can be on the same boat. – Sp3000 – 2015-05-08T20:10:27.993

The ideal would be to provide code in the question that will validate the answers, so there is no confusion over which answers are valid. Testing randomness is not easy though... – trichoplax – 2015-05-08T20:15:38.407

Could I generate random numbers for foo iterations and then use those same numbers? – ASCIIThenANSI – 2015-05-08T20:31:18.913

Answers

4

J

I think the simplest solution to this would be the slightly bendy

   p =: 0
   random =: 3 : '(p =: y | >: p) } ?. y # 0'

That is used like this:

   random 5
0.329284
   random 5
0.335644
   random 5
0.985972
   random 5
0.0583756
   random 5
0.038363
   random 5
0.329284

This can be easily modified to provide integers, just change the 0 to whatever value you want as a maximum. Alternatively, one might write the following code:

   p =: 0
   random =: 4 : '(p =: y | >: p) } ?. y # x'

Used like this:

   10 random 5
8
   10 random 5
6
   10 random 5
5
   10 random 5
4
   10 random 5
6
   10 random 5
8

How this works

This uses the J primitive ?.: the statically seeded random number generator; as opposed to ?: the dynamically seeded random number generator. This makes sure the outcome is always the same when run with the same arguments. p is just a simple array pointer here, that gets incremented with every run of the function, up to a maximum of y: the left argument. Every time this code is executed, a list of y random numbers is generated (to comply with the rules). Yes, I do realize this is very much on the edge of the phrasing of the question and that it is most likely against the spirit of the question.

ɐɔıʇǝɥʇuʎs

Posted 2015-05-08T06:39:14.947

Reputation: 4 449

2

Python

Edit

Since the approach below does not satisfy the criterion, I give an even simpler method Full Cycle, which always produces a full cycle:

def generatePeriodic(seed, period):
    x = seed
    increment = findSmallestCoPrime(period)
    while True:
        x = (x + increment) % period
        yield x

This method always yields all values from [0, period - 1] and then repeats itself. Here findSmallestCoPrime is a function that returns the smallest prime p for which gcd(p, period) = 1 holds.

Previous approach

def generate(seed):
    a = 2 * 5 * 7 + 1
    c = 1
    m = 2 * 5 * 7 * 7
    x = seed % m
    while True:
        yield x
        x = (a * x + c) % m

This is a basic Linear congruential generator, with a period m. m is in this case 490.

The restrictions are:

  1. 0 < m
  2. 0 < a < m
  3. 0 <= c < m
  4. 0 <= seed < m

Linear congruential generator has full period for all seed values if and only if:

  1. c and m are coprime,
  2. a - 1 is divisible by all prime factors of m, and
  3. a - 1 is a multiple of 4 if m is a multiple of 4.

With the following, we can choose (almost) any period m, and modify the code accordingly. We always choose c = 1, to satisfy the first point. Then we factorize m = p_1 ^ k_1 * p_2 ^ k_2 * ... * p_n ^ k_n, and we set a = p_1 * p_2 * ... * p_n + 1. So we satisfy the second point. Finally, if m % 4 == 0 we set a new value to a = 2 * (p_1 * p_2 * ... * p_k) + 1 (here note, that (p_1 * p_2 * ... * p_n) % 2 == 0). With this, we satisfy the third point (and the second point is still satisfied).

The only values of m that can not generate a Linear congruential generator are of type: m = 4 * p_1 * p_2 * ... p_n, where p_i != 2. This is because in such cases we get a = m + 1, which violates the second point of restrictions.

Nejc

Posted 2015-05-08T06:39:14.947

Reputation: 241

m, the period, should be the input parameter, not a fixed value! – Jakube – 2015-05-08T13:04:31.953

Sure, I added the description on how to do this, but will update my answer. – Nejc – 2015-05-08T13:11:55.863

Yeah, but your job is to program this stuff, so that a user don't have to do some calculations before using your program. Also you wrote: "almost any period". The OP asked for every period. – Jakube – 2015-05-08T13:15:45.843