From: buers AT gmx DOT de (Dieter Buerssner)
Newsgroups: comp.os.msdos.djgpp
Subject: Re: Random Numbers
Date: 9 Mar 2000 16:40:57 GMT
Lines: 92
Message-ID: <8a8k6o$3b0gj$1@fu-berlin.de>
References: <8a6fpg$gjg$1 AT news8 DOT svr DOT pol DOT co DOT uk> <8a896n$3aa3v$1 AT fu-berlin DOT de> <oqcfcssnqon6pl043ebse4ba1d34tlktth AT 4ax DOT com>
NNTP-Posting-Host: pec-2-241.tnt2.s2.uunet.de (149.225.2.241)
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Trace: fu-berlin.de 952620057 3506707 149.225.2.241 (16 [17104])
X-Posting-Agent: Hamster/1.3.13.0
User-Agent: Xnews/03.02.04
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Reply-To: djgpp AT delorie DOT com

Damian Yerrick wrote:

>What free, fast PRNG would you suggest?  URL?

I do not know what you exactly mean by free. I think most RNGs
are free in some sense. The algorithms are publicated in some
journals, and you can implement them.

Some RNGs that pass all the diehard tests and all my private
tests are KISS, ULTRA, Multiply with carry, Mersenne Twister,
combined linear congruential generators with prime moduli, ...
(But they are probably not suited for cryptographic applications.)

I do not have URL's handy, but you may try a web search for
George Marsaglia (+diehard), Pierre L'Ecuyer, Mersenne Twister.

I append an example, that is only a few lines of code.
BSD random() like setstate() and getstate() are straight forward
to implement.

Let me know, if you find anything, that is not portable or wrong.

Regards,
Dieter

/* Description by George Marsaglia, slightly edited */

/*
RNG KISS.  The acronym KISS means
             Keep It Simple Stupid
and the idea is to use simple, fast, individually promising
generators to get a composite that will be fast, easy to code
have a very long period and pass all the tests put to it.
The three components of KISS are
             x(n)=a*x(n-1)+1 mod 2^32
             y(n)=y(n-1)(I+L^13)(I+R^17)(I+L^5),
             z(n)=2*z(n-1)+z(n-2) +carry mod 2^32
[DB: The x's are a linear congruential generator]
The y's are a shift register sequence on 32bit binary vectors
period 2^32-1; see the description in executing makesupr.exe.
The z's are a simple multiply-with-carry sequence with period
2^63+2^32-1.  The period of KISS is thus
     2^32*(2^32-1)*(2^63+2^32-1) > 2^127
KISS is particularly well suited for assembler programming,
where it takes about 200 nanosecs with a Pentium 120.
[DB comment, it is also very well suited for C programming,
this comments seems to refer to fortran, on AMD K6-2 this implementation
uses less than 40 cycles when compiled with gcc]
  It seems to pass all tests and is highly recommended  for
 speed and simplicity (for generators with that long a period)
*/

/* state variables */
static unsigned long kiss_x=0x12345678UL,
                     kiss_y=0x87654321UL,
                     kiss_z=0x43218765UL,
                     kiss_w=0x12344321UL,
                     kiss_carry=0;

/* Returns random number between 0 and 0xffffffffUL.
   Translated from fortran source of George Marsaglia.
   The & 2^32 - 1 are for implementations where
   ULONG_MAX > 2^32 - 1, they should be optimized away when not
   needed by any reasonable compiler */

unsigned long kiss_rand(void)
{
  unsigned long k, m;
  kiss_x = ((kiss_x * 69069UL + 1) & 0xffffffffUL);
  kiss_y ^= ((kiss_y << 13) & 0xffffffffUL);
  kiss_y ^= kiss_y >> 17;
  kiss_y ^= ((kiss_y << 5) & 0xffffffffUL);
  k = (kiss_z >> 2) + (kiss_w >> 3) + (kiss_carry >> 2);
  m = ((kiss_w + kiss_w + kiss_z + kiss_carry) & 0xffffffffUL);
  kiss_z = kiss_w;
  kiss_w = m;
  kiss_carry = k >> 30;
  return (kiss_x + kiss_y + kiss_w) & 0xffffffffUL;
}

/* seed function, fancier interfaces are easily implemented */
void seed_kiss_rand(unsigned long s)
{
  kiss_x=0x12345678UL;
  kiss_y=0x87654321UL;
  kiss_z=0x43218765UL;
  kiss_w=0x12344321UL;
  kiss_carry=0;
  s &= 0xffffffffUL:
  if (s != 0)
    kiss_x = s;
}