Mail Archives: djgpp/2000/03/09/14:10:32
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;
}
- Raw text -