良い xorshift、悪い xorshift

| ← back |
| home |

長周期の擬似乱数生成手法とメルセンヌ・ツイスタの無駄知識（？）の紹介は別のページにあります．　簡易な長周期擬似乱数の合成手法　知らなくても不都合は無いメルセンヌ・ツイスタの知識

オマケとしてページ末尾で32bit/64bit xorshift向けのレジスタ初期値（seed）生成プログラムをご紹介しています．
オマケのオマケとして擬似乱数の初期値としてtime()関数で得られる値（カウントアップするUTCの経過秒数）を用いる場合に、値を置換・攪拌・ランダム化する処理もご紹介しています． . . . .

2025.3.6　time() 関数と RDTSC (ReaD Time Stamp Counter) 命令を併用した初期値生成プログラム rdtsc.c を少し手直ししました．

特性の良い xorshift のパラメータ (a, b, c)
視覚的に xorshift の特性の違いが分かるサンプル・プログラム 

/' (c) 2021, 2005 cepstrum.co.jp '/
' FreeBASIC GUI program
' >fbc -s gui 
'--------------------------------------------------------------------------
' xorshift random number generator 

function uint_xorshift(a as uinteger, b as uinteger, c as uinteger) as uinteger<32>
  static r as uinteger<32> = &Hffffffff

  r=r xor (r shl a)
  r=r xor (r shr b)
  r=r xor (r shl c)
  return r
end function

'--------------------------------------------------------------------------

dim x   as uinteger
dim y   as uinteger
dim a   as uinteger = 3
dim b   as uinteger = 13
dim c   as uinteger = 7
dim sft as uinteger = 9

screenres 1024, 1024

while inkey$<>"";
wend
sleep 300

while inkey$="";
  x=(uint_xorshift(a, b, c) shr sft) mod 1024
  y=(uint_xorshift(a, b, c) shr sft) mod 1024
  line (x, y)-(x, y), (uint_xorshift(a, b, c) shr sft) mod 64
wend
メルセンヌ・ツイスタ（MT19937）が大きすぎて使えないというのなら、TinyMTを使えば良いのに
40年前の論文の指摘
『良いパラメータ』の意味
M系列信号の常識・M系列信号を使っている人の常識
32bit/64bit xorshift向けのレジスタ初期値（seed）生成プログラム 

/* (c) 2023 cepstrum.co.jp */

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

//-----------------------------------------------------------------
// M-sequence generater, return value = 0/1

unsigned mseq16bit(unsigned seed) {
  static uint16_t reg16bit=0x5a5a;
  uint16_t        msb;
  unsigned char   b0, b2, b3, b5;

  if (seed!=0) reg16bit=seed&0xffff;    // change seed value

  b0=reg16bit&0x1;
  b2=(reg16bit>>2)&0x1;
  b3=(reg16bit>>3)&0x1;
  b5=(reg16bit>>5)&0x1;
  msb=(b0^b2^b3^b5)&0x1;
  reg16bit=(reg16bit>>1)&0x7fff;
  reg16bit=reg16bit|(msb<<15);
  return msb;
}

//-----------------------------------------------------------------
// generate 32bit seed (register initial value) for 32bit xorshift

uint32_t gen32bit_seed(unsigned mseq_seed) {
  uint32_t seed;
  unsigned i;

  mseq16bit(mseq_seed);    // set M-sequence seed
  seed=0;
  for (i=0; i<16; i=i+1) mseq16bit(0);
  for (i=0; i<16; i=i+1) seed=(seed<<1)|mseq16bit(0);
  for (i=0; i<16; i=i+1) mseq16bit(0);
  for (i=0; i<16; i=i+1) seed=(seed<<1)|mseq16bit(0);
  return seed;
}

//-----------------------------------------------------------------
// generate 64bit seed (register initial value) for 64bit xorshift

uint64_t gen64bit_seed(unsigned mseq_seed) {
  uint64_t seed;
  unsigned i;

  mseq16bit(mseq_seed);    // set M-sequence seed
  seed=0;
  for (i=0; i<16; i=i+1) mseq16bit(0);
  for (i=0; i<16; i=i+1) seed=(seed<<1)|mseq16bit(0);
  for (i=0; i<16; i=i+1) mseq16bit(0);
  for (i=0; i<16; i=i+1) seed=(seed<<1)|mseq16bit(0);
  for (i=0; i<16; i=i+1) mseq16bit(0);
  for (i=0; i<16; i=i+1) seed=(seed<<1)|mseq16bit(0);
  for (i=0; i<16; i=i+1) mseq16bit(0);
  for (i=0; i<16; i=i+1) seed=(seed<<1)|mseq16bit(0);
  return seed;
}

//-----------------------------------------------------------------
// test gen32bit_seed() function

int main() {
  int i;
  int iteration=20;

  for (i=0; i<iteration; i=i+1) printf("A %3i %#010x\n", i, gen32bit_seed(0));

  for (i=0; i<iteration; i=i+1) printf("B %3i %#010x\n", i, gen32bit_seed(i+1));

  gen32bit_seed(123456);  // set new M-sequence seed
  for (i=0; i<iteration; i=i+1) printf("C %3i %#010x\n", i, gen32bit_seed(0));

  gen32bit_seed(time(NULL)&0xffff);  // set new M-sequence seed
  for (i=0; i<iteration; i=i+1) printf("D %3i %#010x\n", i, gen32bit_seed(0));

  /*
  for (i=0; i<iteration; i=i+1) printf("a %3i %10u\n", i, gen32bit_seed(0));

  for (i=0; i<iteration; i=i+1) printf("b %3i %10u\n", i, gen32bit_seed(i+1));

  gen32bit_seed(123456);  // set new M-sequence seed
  for (i=0; i<iteration; i=i+1) printf("c %3i %10u\n", i, gen32bit_seed(0));

  gen32bit_seed(time(NULL)&0xffff);  // set new M-sequence seed
  for (i=0; i<iteration; i=i+1) printf("d %3i %10u\n", i, gen32bit_seed(0));
  */
}



A   0 0x07e002b6     B   0 0x045113d3     C   0 0x62c6e599     D   0 0x0de90ead
A   1 0xbad8c213     B   1 0x822889e9     C   1 0x7b9844fd     D   1 0xf2856c55
A   2 0x535dc645     B   2 0x86799a3a     C   2 0x87cb24d6     D   2 0xd13e75bc
A   3 0x4f9219fe     B   3 0x45455727     C   3 0x08375b24     D   3 0x677b22ba
A   4 0x071adb05     B   4 0x411444f4     C   4 0x64cd2e6b     D   4 0x980b3692
A   5 0x7c50eef1     B   5 0xc76ddece     C   5 0xfd68d0c5     D   5 0x62615ac4
A   6 0xf4c69145     B   6 0xc33ccd1d     C   6 0xf3c72124     D   6 0xaaba4791
A   7 0x8329dc05     B   7 0x26f33840     C   7 0xd0dc9a24     D   7 0x396173d3
A   8 0x14309aa3     B   8 0x22a22b93     C   8 0x41cf1321     D   8 0xeea227e5
A   9 0x2b1a36ed     B   9 0xa4dbb1a9     C   9 0xdfb20298     D   9 0x6a0754c5
A  10 0xaa94f6ce     B  10 0xa08aa27a     C  10 0xd867da15     D  10 0x7a7baf34
A  11 0x2167f0f3     B  11 0x63b66f67     C  11 0x551c33f6     D  11 0x86d83c82
A  12 0x1b112949     B  12 0x67e77cb4     C  12 0x52cbe3d8     D  12 0xbdd97272
A  13 0x90211f37     B  13 0xe19ee68e     C  13 0x90fe59a4     D  13 0x00a88064
A  14 0xf8da28df     B  14 0xe5cff55d     C  14 0x7386b332     D  14 0x1a6d907c
A  15 0xdb1bc05b     B  15 0x13791c20     C  15 0x0d7454f2     D  15 0xf3b2ef70
A  16 0x786e5c43     B  16 0x17280ff3     C  16 0xdf4bd7d9     D  16 0x0ea3c22a
A  17 0x0b74b17f     B  17 0x915195c9     C  17 0x76068ca7     D  17 0x80bd5240
A  18 0x0c6977ce     B  18 0x9500861a     C  18 0xe47f4312     D  18 0xcaf31694
A  19 0x864d4450     B  19 0x563c4b07     C  19 0xfcd45541     D  19 0x14efdc30



mseq_seed  gen32bit_seed(mseq_seed)
-----------------------------------
0x0001     0x045113d3
0x0002     0x822889e9
0x0004     0x45455727
0x0008     0x26f33840
0x0010     0x13791c20
0x0020     0x8ded9dc3
0x0040     0x46f64ee1
0x0080     0xa37ba770
0x0100     0x51bdd3b8
0x0200     0x28dee9dc
0x0400     0x146ff4ee
0x0800     0x8a377a77
0x1000     0x451b3d3b
0x2000     0x228d9e9d
0x4000     0x11464f4e
0x8000     0x08a327a7
time()関数で得た値のランダム化（その１）　：　S-boxを用いた攪拌 

/* generate 32bit seed value of random number generator */
/* from time() and AES S-box conversion                 */
/* (c) 2025 cepstrum.co.jp                              */

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//-------------------------------------------------------------------

unsigned aes_sbox[256]={           // AES S-box table
  0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,
  0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0,
  0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15,
  0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75,
  0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84,
  0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf,
  0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8,
  0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2,
  0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73,
  0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb,
  0xe0, 0e32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79,
  0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08,
  0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a,
  0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e,
  0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf,
  0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16
};

//-------------------------------------------------------------------
// apply S-box conversion to 32bit data

unsigned sbox_conv(unsigned x) {
  unsigned y=0;

  y=y|(aes_sbox[(x>> 0)&0xff]<< 0);
  y=y|(aes_sbox[(x>> 8)&0xff]<< 8);
  y=y|(aes_sbox[(x>>16)&0xff]<<16);
  y=y|(aes_sbox[(x>>24)&0xff]<<24);
  return y;
}

//-------------------------------------------------------------------
// apply double S-box conversion to 32bit data

unsigned sbox_double_conv(unsigned x) {
  unsigned y;
  unsigned p, q;

  // 1st S-box conversion
  p=sbox_conv(x);
  // shuffle (bit reverse like block shuffle)
  q=0;
  q=q|( p     &0x0000000f);
  q=q|((p>>12)&0x000000f0);
  q=q|( p     &0x00000f00);
  q=q|((p>>12)&0x0000f000);
  q=q|((p<<12)&0x000f0000);
  q=q|( p     &0x00f00000);
  q=q|((p<<12)&0x0f000000);
  q=q|( p     &0xf0000000);
  // 2nd S-box conversion
  y=sbox_conv(q);
  return y;
}

//-------------------------------------------------------------------

int main() {
  unsigned           seed1, seed2;
  unsigned long long lu=0;                   // unsigned 64bit
  unsigned long long zlu;                    // unsigned 64bit

  while(1) {                                 // forever loop (don't stop)
    do {
      zlu=lu;                                // save last time value
      lu=time(NULL);                         // read UTC time value
    } while (zlu==lu);                       // wait untile time change
    seed1=sbox_conv(lu&0xffffffff);          // S-box conversion
    seed2=sbox_double_conv(lu&0xffffffff);   // double S-box conversion
    printf("time=%10u seed1=%10u(0x%08X) seed2=%10u(0x%08X)\n", lu&0xffffffff, seed1, seed1, seed2, seed2);
  }

}


.....

time=1740788990 seed1=2233802939(0x852520BB) seed2= 334582585(0x13F15339)
time=1740788991 seed1=2233802774(0x85252016) seed2= 335369137(0x13FD53B1)
time=1740788992 seed1=2233859171(0x8525FC63) seed2=1945586413(0x73F74AED)
time=1740788993 seed1=2233859196(0x8525FC7C) seed2=1942768202(0x73CC4A4A)
time=1740788994 seed1=2233859191(0x8525FC77) seed2=1942768219(0x73CC4A5B)
time=1740788995 seed1=2233859195(0x8525FC7B) seed2=1942768185(0x73CC4A39)
time=1740788996 seed1=2233859314(0x8525FCF2) seed2=1930775040(0x73154A00)
time=1740788997 seed1=2233859179(0x8525FC6B) seed2=1945586233(0x73F74A39)
time=1740788998 seed1=2233859183(0x8525FC6F) seed2=1945586383(0x73F74ACF)
time=1740788999 seed1=2233859269(0x8525FCC5) seed2=1936804604(0x73714AFC)
.....



/* generate 32bit seed value of random number generator */
/* (c) 2025 cepstrum.co.jp                              */

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//-------------------------------------------------------------------

unsigned simple_mod(unsigned x) {
  return x=x+((x%3)<<2)-((x%5)<<4)+((x%7)<<6)+((x%11)<<8)-((x%13)<<10)+((x%17)<<12)-((x%19)<<14)+((x%23)<<16);
}

//-------------------------------------------------------------------

int main() {
  unsigned           seed;
  unsigned long long lu=0;                   // unsigned 64bit
  unsigned long long zlu;                    // unsigned 64bit

  while(1) {                                 // forever loop (don't stop)
    do {
      zlu=lu;                                // save last time value
      lu=time(NULL);                         // read UTC time value
    } while (zlu==lu);                       // wait untile time change
    seed=simple_mod(lu);                     // simple conversion
    printf("time=%10u seed1=%10u(0x%08X)\n", lu&0xffffffff, seed, seed);
  }

}



.....

time=1741016530 seed1=1742030358(0x67D54616)
time=1741016531 seed1=1742394187(0x67DAD34B)
time=1741016532 seed1=1742446708(0x67DBA074)
time=1741016533 seed1=1740991913(0x67C56DA9)
time=1741016534 seed1=1741044446(0x67C63ADE)
time=1741016535 seed1=1741097047(0x67C70857)
time=1741016536 seed1=1741149132(0x67C7D3CC)
time=1741016537 seed1=1741214977(0x67C8D501)
time=1741016538 seed1=1741267498(0x67C9A22A)
time=1741016539 seed1=1741320031(0x67CA6F5F)
.....
time()関数で得た値のランダム化（その２）　：　timp stamp counterの値の併用 

.....

time=1741217650 tsc=3758225877 seed=2546475928(0x97C82398)
time=1741217650 tsc=   3720435 seed=1741995275(0x67D4BD0B)
time=1741217650 tsc= 546690075 seed=2005022079(0x7782357F)
time=1741217650 tsc=1088356141 seed=1202168036(0x47A7A0E4)
time=1741217650 tsc=1630275875 seed=1465834467(0x575EDBE3)
time=1741217651 tsc=2171753907 seed= 661779882(0x2771F5AA)
time=1741217651 tsc=2713111927 seed= 924039624(0x3713B9C8)
time=1741217651 tsc=3261178399 seed= 116919932(0x06F80E7C)
time=1741217651 tsc=3801389195 seed= 377656118(0x16829336)
time=1741217652 tsc=  48018715 seed=3869672953(0xE6A685F9)
time=1741217652 tsc= 609693231 seed=4125313123(0xF5E34863)
time=1741217652 tsc=1150902331 seed=3313790825(0xC5846F69)
time=1741217652 tsc=1694594115 seed=3578291541(0xD5486555)
time=1741217652 tsc=2235925379 seed=2775195317(0xA56A1EB5)
time=1741217653 tsc=2778729023 seed=3038304874(0xB518DA6A)
time=1741217653 tsc=3319660111 seed=2233868370(0x85262052)
time=1741217653 tsc=3866970143 seed=2499181434(0x94F67B7A)
time=1741217653 tsc= 116817159 seed=1689510390(0x64B3E1F6)
.....

内輪のジョークをネットで拡散するのは止めよう

English page is here 

| ← back | ↑top |
 
| home |