**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

## No comments:

Post a Comment