🚀 go-pugleaf

On Sun, 25 Oct 1998 12:00:43 -0500, "Christian Duffett" <IWM@BAKA.COM>
wrote:

>I need to create an array which has all different integers.  I need this to
>not be of N squared efficiency.  Any ideas ?

This doesn't really have anything to do with C or C++, but...

The straightforward approach is to simply use a linear congruential
generator function; see Knuth's "The Art of Computer Programming,
volume 2:  Seminumerical Algorithms".

These functions generate a sequence of pseudorandom numbers, and for
suitably chosen coefficients, the sequence is guaranteed not to repeat
any number until all generated numbers have been returned once.  That
is, for instance, if the range of output integers is 0 to 65535, then
each such integer will be output exactly once before any such integer
comes out twice.

The functions are of the form:  I(j+1) = ((aI(j) + c) mod m), where
I(j) is the j'th random result (or the seed, the first time), and
I(j+1) is the following random result.  a is the multiplier, c is the
increment, and m is the modulus.  m is chosen for convenience's sake,
and is typically 2^32 or a similar machine-word-size-related value.

a and c must be carefully chosen to achieve the desired
non-repetitiveness property.

As with any computerized "random" number generator, you must make a
tradeoff between ease of computation and "greater randomness".  Linear
congruential generators are very common in runtime libraries, but are
not really all that random.  Usually, though, you don't really care
about this defect for normal purposes.