xorshiftファミリ比較

概要

xorshift128, xorshift*64, xorshift+128を検証する. 32bitを返すバージョンも作成する.
検証はDieharder 3.31.1を使用する.

コード

#include <stdio.h>
typedef int s32;
typedef unsigned int u32;
typedef unsigned long long u64;


u32 xorshift128()
{
    static u32 x_ = 123459876;
    static u32 y_ = 362436069;
    static u32 z_ = 521288629;
    static u32 w_ = 88675123;
    u32 t = x_^(x_<<11);
    x_ = y_;
    y_ = z_;
    z_ = w_;
    w_ = (w_^(w_>>19)) ^ (t^(t>>8));
    return w_;
}

u64 xorshift64star()
{
    static u64 s_ = 0x8a5cd789635d2dffULL;
    static const u64 M = 2685821657736338717ULL;
    u64 s = s_;
    s_ ^= s>>12;
    s_ ^= s_<<25;
    s_ ^= s_>>27;
    return s * M;
}

u32 xorshift64star32()
{
    static u64 s_ = 0x8a5cd789635d2dffULL;
    static u64 r_ = 0;
    static s32 flag_ = 1;
    static const u64 M=2685821657736338717ULL;
    if(flag_^=1){
        return (u32)(r_>>32);
    }
    u64 s = s_;
    s_ ^= s>>12;
    s_ ^= s_<<25;
    s_ ^= s_>>27;
    r_ = s * M;
    return (u32)r_;
}

u64 xorshift128plus()
{
    static u64 s0_ = 0x8a5cd789635d2dffULL;
    static u64 s1_ = 0x121fd2155c472f96ULL;
    u64 s1 = s0_;
    const u64 s0 = s1_;
    s0_ = s0;
    s1 ^= s1<<23;
    s1_ = s1^s0^(s1>>18)^(s0>>5);
    return s1_+s0;
}

u32 xorshift128plus32()
{
    static u64 s0_ = 0x8a5cd789635d2dffULL;
    static u64 s1_ = 0x121fd2155c472f96ULL;
    static u64 r_ = 0;
    static s32 flag_ = 1;
    if(flag_^=1){
        return (u32)(r_>>32);
    }
    u64 s1 = s0_;
    const u64 s0 = s1_;
    s0_ = s0;
    s1 ^= s1<<23;
    s1_ = s1^s0^(s1>>18)^(s0>>5);
    r_ = s1_+s0;
    return (u32)r_;
}

int main(int arc, char** argv)
{
    static const u64 size = 14ULL*1024ULL*1024ULL*1024ULL;
    FILE* file = NULL;

    file = fopen("xorshift.bin", "wb");
    for(u64 i=0; i<size; i+=4){
        u32 x = xorshift128();
        fwrite(&x, sizeof(x), 1, file);
    }
    fclose(file);

    file = fopen("xorshift64star.bin", "wb");
    for(u64 i=0; i<size; i+=8){
        u64 x = xorshift64star();
        fwrite(&x, sizeof(x), 1, file);
    }
    fclose(file);

    file = fopen("xorshift64star32.bin", "wb");
    for(u64 i=0; i<size; i+=4){
        u32 x = xorshift64star32();
        fwrite(&x, sizeof(x), 1, file);
    }
    fclose(file);

    file = fopen("xorshift128plus.bin", "wb");
    for(u64 i=0; i<size; i+=8){
        u64 x = xorshift128plus();
        fwrite(&x, sizeof(x), 1, file);
    }
    fclose(file);

    file = fopen("xorshift128plus32.bin", "wb");
    for(u64 i=0; i<size; i+=4){
        u32 x = xorshift128plus32();
        fwrite(&x, sizeof(x), 1, file);
    }
    fclose(file);

    return 0;
}

結果

PASSEDではない行を抜き出した.

xorshift128

$ dieharder -a -g 201 -f xorshift.bin
#=============================================================================#
#            dieharder version 3.31.1 Copyright 2003 Robert G. Brown          #
#=============================================================================#
   rng_name    |           filename             |rands/second|
 file_input_raw|                    xorshift.bin|  8.44e+06  |
#=============================================================================#
        test_name   |ntup| tsamples |psamples|  p-value |Assessment
#=============================================================================#
          sts_serial|  12|    100000|     100|0.99913098|   WEAK
# The file file_input_raw was rewound 2 times
      rgb_lagged_sum|   9|   1000000|     100|0.99857250|   WEAK

Preparing to run test 209.  ntuple = 0
# The file file_input_raw was rewound 16 times
        dab_monobit2|  12|  65000000|       1|0.99999170|   WEAK

xorshift64*

$ dieharder -a -g 201 -f xorshift64star.bin
#=============================================================================#
#            dieharder version 3.31.1 Copyright 2003 Robert G. Brown          #
#=============================================================================#
   rng_name    |           filename             |rands/second|
 file_input_raw|              xorshift64star.bin|  8.52e+06  |
#=============================================================================#
        test_name   |ntup| tsamples |psamples|  p-value |Assessment
#=============================================================================#
        diehard_oqso|   0|   2097152|     100|0.99886404|   WEAK
       diehard_craps|   0|    200000|     100|0.99772387|   WEAK
          sts_serial|   6|    100000|     100|0.99999972|  FAILED
          sts_serial|  13|    100000|     100|0.99583499|   WEAK
# The file file_input_raw was rewound 14 times
      rgb_lagged_sum|  30|   1000000|     100|0.99834128|   WEAK

xorshift128+

$ dieharder -a -g 201 -f xorshift128plus.bin
#=============================================================================#
#            dieharder version 3.31.1 Copyright 2003 Robert G. Brown          #
#=============================================================================#
   rng_name    |           filename             |rands/second|
 file_input_raw|             xorshift128plus.bin|  8.42e+06  |
#=============================================================================#
        test_name   |ntup| tsamples |psamples|  p-value |Assessment
#=============================================================================#
# The file file_input_raw was rewound 1 times
         rgb_bitdist|  10|    100000|     100|0.99906642|   WEAK

Future Work

PCGの実装.

References

George Marsaglia, "Xorshift RNGs"
Sebastiano Vigna, "An experimental exploration of Marsaglia's xorshift generators, scrambled"
Sebastiano Vigna, "Further scramblings of Marsaglia's xorshift generators"