Re: KISS4691, a potentially top-ranked RNG.

[Thad Smith <ThadSmith@acm.org>]

On 4/27/2011 6:14 PM, robin wrote:
> "Uno"<merrilljensen@q.com>  wrote in message news:8bfh28Fve1U1@mid.individual.net...
> | robin wrote:
> |>  "jacob navia"<jacob@spamsink.net>  wrote in message news:i2fir2$op4$1@speranza.aioe.org...
> |>
> |>  | This doesn't work with systems that have unsigned long as a 64 bit quantity.
> |>  |
> |>  | I obtain:
> |>  |
> |>  |  MWC result=3740121002 ?
> |>  |             4169348530
> |>  | KISS result=2224631993 ?
> |>  |             1421918629
> |>
> |>  For a 64-bit machine (using 64-bit integer arithmetic),
> |>  you'd need to truncate each result to 32 bits.  That not
> |>  only applies to the multiplication, it also applies to addition, etc.
> |>  On a 32-bit machine, these extra bits are discarded,
> |>  but in 64-bit arithmetic, they are retained,
> |>  and unless they are similarly discarded,
> |>  you won't get the same results.
> |>  I suggest using IAND(k, 2*2147483647+1)
> |>  for the truncation.
> |>
> |>  With such modifications in the program,
> |>  it should then produce the same results on both 32-bit and
> |>  64-bit machines.

Here is a modification of the program with masking to produce correct results 
with any conforming C implementation.  It truncates where when required.  A good 
optimizer should eliminate the unneeded masking for 32-bit unsigned long.

static unsigned long xs = 521288629;
static unsigned long xcng = 362436069;
static unsigned long Q[4691];

#define M32 0xffffffff

unsigned long   MWC(void)
{
     static unsigned long c = 0;
     static unsigned long j = 4691;
     unsigned long   t;
     unsigned long   x;
     j = (j < 4690) ? j + 1 : 0;
     x = Q[j];
     t = ((x << 13) + c) & M32;
     if (t < c) {
         c = (x >> 19) + 1;
         t = (t + x) & M32;
     } else {
         t = (t + x) & M32;
         c = (x >> 19) + (t < x);
     }
     return (Q[j] = t);

}

void            initMWC(void)
{
     unsigned long   i;
     for (i = 0; i < sizeof Q / sizeof Q[0]; i++)
         Q[i] = ((xcng = 69069 * xcng + 123) + (xs = (xs ^ (xs << 13)) & M32,
                 xs ^= (xs >> 17), xs ^= (xs << 5))) & M32;

}

#ifdef UNIT_TEST

#include <stdio.h>

int             main()
{
     unsigned long   i;
     unsigned long   x;

     initMWC();

     printf("Does  MWC result=3740121002 ?\n");
     for (i = 0; i < 1000000000; i++)
         x = MWC();
     printf("%27u\n", x);

     printf("Does KISS result=2224631993 ?\n");
     for (i = 0; i < 1000000000; i++)
         x = (MWC() + (xcng = 69069 * xcng + 123) + (xs = (xs ^ (xs << 13)) & M32,
              xs ^= (xs >> 17), xs ^= (xs << 5)));
     printf("%27u\n", x);
     return 0;
}

#endif



-- 
Thad