Today I faced a problem: how to generate a pseudo-random permutation of numbers in range [0,2^128), such that each number appears
exactly once. An obvious solution is to initialize an array
A[i]=i and then shuffle elements with repeated calls to
random(). However, that would use a large amount of memory, which is not acceptable in this particular case.
So I remembered a bit of algebra that I learned long time ago at the university. It's about
cyclic groups. Consider the sequence
k*a0 % M for k = 0, 1, .... In my case
M=2^128. This sequence generates
all numbers less than
M exactly once, provided that
a0 and
M are relatively prime. Shortly,
a0 is a
generator of an additive cyclic group where the set of elements are natural numbers in the range
G=[0,2^128), and the operation is addition modulo
M.
The code is even simpler (pseudo-C):
a = 0;
do {
/* use a in some way */
a += a0;
if(a > M) a -= M;
} while(a);
When
a becomes 0 again, the whole group of
M elements has been generated, so the loop exits. In other words,
a has cycled through all elements in
G exactly once. This is also connected with pseudo-random number generators. I'm not interested in the exact statistical properties of generated numbers; the only requirement is that consecutive numbers are "far enough" apart (which I define by chosing an appropriate constant
a0).
Tags:
algebra random numbers
