1
$\begingroup$

Below is a Python code that calculates the periodicity of the middle-square method for a given 4 digit-numbers:

n = int(input("Please enter a four digit number: "))
already_seen = list()
while n not in already_seen:
    already_seen.append(n)
    n = int(str(n * n).zfill(8)[2:6])
    print(n)
print('periodicity = ', len(already_seen) - already_seen.index(n))

For example the seed number 9267 yield to a series that enters in a short loop of periodicity 4 [9267, …, 6100, 2100, 4100, 8100, 6100, 2100, 4100, 8100, 6100, ...]

Is there any solution to find out what numbers yield to the longest periodicity without having to simulate? If no, why isn't there a solution? Generally speaking, are there solutions to find out the periodicity of a given seed in different random number generators?

$\endgroup$
8
  • $\begingroup$ Welcome to SciComp! If I understand your question correctly, you are asking about theoretical properties of a certain random number generator, and not its implementation or use in a computational algorithm? $\endgroup$ Jul 24 '14 at 7:10
  • $\begingroup$ @ChristianClason Yes, that's correct. Is it off-topic? I didn't dare to ask my question on CSTheory.SE as this site is made for research level question and I am not not at all a computer scientist. $\endgroup$
    – Remi.b
    Jul 24 '14 at 7:23
  • $\begingroup$ In this case, I would say it is indeed off-topic. You are probably right about CSTheory -- I would rather try math.stackexchange.com (since you can use number theory to analyze RNGs) or crypto.stackexchange.com (since the analysis of RNGs, especially their periodicity, is a central topic in cryptography since that is information that can be used to break a scheme). You can flag your question and ask for migration (under "other"). $\endgroup$ Jul 24 '14 at 7:31
  • $\begingroup$ On the other hand, a question about which random number generator to use for a particular purpose in scientific computing would be on-topic. What do you need the random numbers for, and why do you care about periodicity? $\endgroup$ Jul 24 '14 at 7:33
  • 1
    $\begingroup$ @GeoffOxberry This migration to Cryptography was rejected because this isn't about a crypto RNG. (Yes, our help center could be read to imply that any RNG is on-topic. I've requested to it less misleading.) This question could fit on Computer Science, or probably even Mathematics. $\endgroup$ Jul 24 '14 at 20:46
6
$\begingroup$

To the best of my knowledge, no, but maybe other people here know the field more intimately. My knowledge comes primarily from developing Monte Carlo codes in physics.

Knuth, in volume 2 of his Art of Computer Programming, states that Metropolis, using the middle-square method on 20 bits, found 13 cycles to which the method would always degenerate, the longest of which has a period of 142. Sadly I've been unable to find the original paper, but note that he only refers to the period of the cycle, not the time it takes to reach the cycle from a given period.

More generally, most (but not all) random number generators used in numerics today have a guaranteed period, often independent of the seed. This period is however calculated differently from generator to generator. See this for a list of reasonable random number generators.

Finding the period experimentally will be very difficult for almost all modern random number generators, simply because the periods are very very long. In many cases it would take far far longer than the expected age of the universe, even if every single atom was turned into a computer to work on the problem in parallel. Just to give you an idea of how difficult it is.

Anyway, for toy random generators, remember that in order to find a cycle, you need to check if the entire state space of the generator is repeating. In the case of the middle-square method, the state and the output are the same, but this is not the case for most random number generators, and certainly not for any practical ones.

PS: The middle-square method is a really bad random number generator and should not be used for generating random numbers. Ever.

$\endgroup$

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