Re: 64-bit KISS RNGs

64-bit KISS RNGs

Consistent with the Keep It Simple Stupid (KISS) principle,
I have previously suggested 32-bit KISS Random Number
Generators (RNGs) that seem to have been frequently adopted.

Having had requests for 64-bit KISSes, and now that
64-bit integers are becoming more available, I will
describe here a 64-bit KISS RNG, with comments on
implementation for various languages, speed, periods
and performance after extensive tests of randomness.

This 64-bit KISS RNG has three components, each nearly
good enough to serve alone. The components are:
Multiply-With-Carry (MWC), period (2^121+2^63-1)
Xorshift (XSH), period 2^64-1
Congruential (CNG), period 2^64

Compact C and Fortran listings are given below. They
can be cut, pasted, compiled and run to see if, after
100 million calls, results agree with that provided
by theory, assuming the default seeds.

Users may want to put the content in other forms, and,
for general use, provide means to set the 250 seed bits
required in the variables x,y,z (64 bits) and c (58 bits)
that have been given default values in the test versions.

The C version uses #define macros to enumerate the few
instructions that MWC, XSH and CNG require. The KISS
macro adds MWC+XSH+CNG mod 2^64, so that KISS can be
inserted at any place in a C program where a random 64-bit
integer is required.
Fortran's requirement that integers be signed makes the
necessary code more complicated, hence a function KISS().

C version; test by invoking macro KISS 100 million times
-----------------------------------------------------------------
#include <stdio.h>

static unsigned long long
x=1234567890987654321ULL,c=123456123456123456ULL,
y=362436362436362436ULL,z=1066149217761810ULL,t;

#define MWC (t=(x<<58)+c, c=(x>>6), x+=t, c+=(x<t), x)
#define XSH ( y^=(y<<13), y^=(y>>17), y^=(y<<43) )
#define CNG ( z=6906969069LL*z+1234567 )
#define KISS (MWC+XSH+CNG)

int main(void)
{int i;
 for(i=0;i<100000000;i++) t=KISS;
 (t==1666297717051644203ULL) ?
 printf("100 million uses of KISS OK"):
 printf("Fail");
}

---------------------------------------------------------------
Fortran version; test by calling KISS() 100 million times
---------------------------------------------------------------
program testkiss
implicit integer*8(a-z)
do i=1,100000000; t=KISS(); end do
if(t.eq.1666297717051644203_8) then
print*,"100 million calls to KISS() OK"
else; print*,"Fail"
end if; end

function KISS()
implicit integer*8(a-z)
data x,y,z,c /1234567890987654321_8, 362436362436362436_8,&
1066149217761810_8, 123456123456123456_8/
save x,y,z,c
 m(x,k)=ieor(x,ishft(x,k)) !statement function
 s(x)=ishft(x,-63) !statement function
t=ishft(x,58)+c
if(s(x).eq.s(t)) then; c=ishft(x,-6)+s(x)
     else; c=ishft(x,-6)+1-s(x+t); endif
x=t+x
y=m(m(m(y,13_8),-17_8),43_8)
z=6906969069_8*z+1234567
KISS=x+y+z
return; end
---------------------------------------------------------------

Output from using the macro KISS or the function KISS() is
MWC+XSH+CNG mod 2^64.

CNG is easily implemented on machines with 64-bit integers,
as arithmetic is automatically mod 2^64, whether integers
are considered signed or unsigned. The CNG statement is
   z=6906969069*z+1234567.
When I established the lattice structure of congruential
generators in the 60's, a search produced 69069 as an easy-
to-remember multiplier with nearly cubic lattices in 2,3,4,5-
space, so I tried concatenating, using 6906969069 as
my first test multiplier. Remarkably---a seemingly one in many
hundreds chance---it turned out to also have excellent lattice
structure in 2,3,4,5-space, so that's the one chosen.
(I doubt if lattice structure of CNG has much influence on the
composite 64-bit KISS produced via MWC+XSH+CNG mod 2^64.)

XSH, the Xorshift component, described in
    www.jstatsoft.org/v08/i14/paper
uses three invocations of an integer "xor"ed with a shifted
version of itself.
The XSH component used for this KISS is, in C notation:
  y^=(y<<13); y^=(y>>17); y^=(y<<43)
with Fortran equivalents y=ieor(y,ishft(y,13)), etc., although
this can be effected by a Fortran statement function:
    f(y,k)=ieor(y,ishft(y,k))
    y=f(f(f(y,13),-17),43)
As with lattice structure, choice of the triple 13,-17,43 is
probably of no particular importance; any one of the 275 full-
period triples listed in the above article is likely to provide
a satisfactory component XSH for the composite MWC+XSH+CNG.

The choice of multiplier 'a' for the multiply-with-carry (MWC)
component of KISS is not so easily made. In effect, a multiply-
with-carry sequence has a current value x and current "carry" c,
and from each given x,c a new x,c pair is constructed by forming
 t=a*x+c, then x=t mod b=2^64 and c=floor(t/b).
This is easily implemented for 32-bit computers that permit
forming a*t+c in 64 bits, from which the new x is the bottom and
the new c the top 32-bits.

When a,x and c are 64-bits, not many computers seem to have an easy
way to form t=a*x+c in 128 bits, then extract the top and bottom
64-bit segments. For that reason, special choices for 'a' are
needed among those that satisfy the general requirement that
p=a*b-1 is a prime for which b=2^64 has order (p-1)/2.

My choice---and the only one of this form---is a=2^58+1. Then the
top 64 bits of an imagined 128-bit t=a*x+c may be obtained as
(using C notation) (x>>6)+ 1 or 0, depending
on whether the 64-bit parts of (x<<58)+c+x cause an overflow.
Since (x<<58)+c cannot itself cause overflow (c will always be <a),
we get the carry as c=(x>>6) plus overflow from (x<<58)+x.

This is easily done in C with unsigned integers, using a different
kind of 't': t=(x<<58)+c; c=(x>>6); x=t+x; c=c+(x<t);
For Fortran and others that permit only signed integers, more work
is needed.
Equivalent mod 2^64 versions of t=(x<<58)+c and c=(x>>6) are easy,
and if s(x) represents (x>>63) in C or ishft(x,-66) in Fortran,
then for signed integers, the new carry c comes from the rule
if s(x) equals s(t) then c=(x>>6)+s(x) else c=(x>>6)+1-s(x+t)

Speed:
A C version of this KISS RNG takes 18 nanosecs for each
64-bit random number on my desktop (Vista) PC, thus
producing KISSes at a rate exceeding 55 million per second.
Fortran or other integers-must-be-signed compilers might get
"only" around 40 million per second.

Setting seeds:
Use of KISS or KISS() as a general 64-bit RNG requires specifying
3*64+58=250 bits for seeds, 64 bits each for x,y,z and 58 for c,
resulting in a composite sequence with period around 2^250.
The actual period is
 (2^250+2^192+2^64-2^186-2^129)/6 ~= 2^(247.42) or 10^(74.48).
We "lose" 1+1.58=2.58 bits from maximum possible period, one bit
because b=2^64, a square, cannot be a primitive root of p=ab-1,
so the best possible order for b is (p-1)/2.
The periods of MWC and XSH have gcd 3=2^1.58, so another 1.58
bits are "lost" from the best possible period we could expect
from 250 seed bits.

Some users may think 250 seed bits are an unreasonable requirement.
A good seeding procedure might be to assume the default seed
values then let the user choose none, one, two,..., or all
of x,y,z, and c to be reseeded.

Tests:
Latest tests in The Diehard Battery, available at
  http://i.cs.hku.hk/~diehard/
were applied extensively. Those tests that specifically required
32-bit integers were applied to the leftmost 32 bits
(e,g, KISS>>32;), then to the middle 32-bits ((KISS<<16)>>32;)
then to the rightmost 32 bits, ( (KISS<<32)>>32).
There were no extremes in the more than 700 p-values returned
by the tests, nor indeed for similar tests applied to just two of the
KISS components: MWC+XSH, then MWC+CNG, then XSH+CNG.

The simplicity, speed, period around 2^250 and performance on
tests of randomness---as well as ability to produce exactly
the same 64-bit patterns, whether considered signed or unsigned
integers---make this 64-bit KISS well worth considering for
adoption or adaption to languages other than C or Fortran,
as has been done for 32-bit KISSes.

George Marsaglia