一人一党党

一人一人の、一人一人による、一人一人のための政治制度を!

メルセンヌ素数でxorshift疑似乱数の軽量化

とってもお手軽な割にそこそこ高速で高品質な疑似乱数生成アルゴリズム「xorshift」。
32bit版などの実装では、乱数生成一回あたりxor演算とshift演算を3組、計6回演算命令を使わねばならない。
ところが64bit版実装では、xorとshiftの組を2組しか使わずとも、2の64乗の周期が出る。
そこで、31bit版などbit数がメルセンヌ素数の場合、2組で可能か試してみた。
一般的なCPUのレジスタは32bitや64bitなど2のベキ乗なので、bit数を調整するためにand演算でbitmaskをかける必要がある。
しかしand演算はxorやshfit同様に軽い整数演算だ。
従って、xorとshiftの組を一組、すなわち整数演算を二つ減らせるなら、and演算一つ払っても整数演算ひとつ分だけ高速化できる。
メルセンス素数なら、周期は1かbit幅一杯かのどちらかなので生成パラメータが見つかる可能性が高そうだ。
しかも周期が素数なので、乱数を利用する側のプログラムの持つ周期と同期してしまう可能性が低い。
普通のxorshift疑似乱数は周期が素数ではないので、利用するプログラム側と組み合わせた周期が小さくなる場合がある。
パラメータ探索には下記のサイトのpythonスクリプトを拝借した。
Google Chromeが採用した、擬似乱数生成アルゴリズム「xorshift」の数理 – びりあるの研究ノート
https://blog.visvirial.com/articles/575
31bit版と5bit版しか試していないが、例えば31bit版だと14組も生成パラメータが見つかった。
bitmaskを即値として演算命令に格納しないと、命令節約効果が打ち消される。
下位bit側をクリアするbitmaskなら、符号拡張により即値フィールドを小さくできる。
即値フィールド制限の厳しいRISC命令では不可欠だし、制限の緩いx86でも命令長節約になる。

--- C言語コード ---
#include <stdint.h>
uint32_t xorshift31(void)
{
    static uint32_t seed = 2;
    seed = seed ^ (seed << 7);
    seed = seed ^ (seed >> 12);
    return seed = seed & (~1);
}

--- x86へのコンパイル結果 ---
00000000 <xorshift31>:
   0:   8b 15 00 00 00 00       mov    0x0,%edx
   6:   89 d0                   mov    %edx,%eax
   8:   c1 e0 07                shl    $0x7,%eax
   b:   31 c2                   xor    %eax,%edx
   d:   89 d0                   mov    %edx,%eax
   f:   c1 e8 0c                shr    $0xc,%eax
  12:   31 d0                   xor    %edx,%eax
  14:   83 e0 fe                and    $0xfffffffe,%eax
  17:   a3 00 00 00 00          mov    %eax,0x0
  1c:   c3                      ret

コンパイル結果での0x14バイト目の命令の長さは3byteしかないが、符号拡張により4byteのbitmaskをかけることができている。
x86は2オペランド命令であり、演算結果を格納するために元データを破壊するため、xorとshiftの組ごとにデータ複製のためのmov命令が余計に加わっている。
xorとshiftの組を3組用いる32bit版実装では、31bit版より2命令多く必要になるはずだ。
上記31bit版の命令数が10個なので、2命令分の増加は2割増し。
なお、左シフトのパラメータを3以下にすると、x86の場合元データを破壊しないlea命令が使え、mov命令を回避できる。
31bit版の有効なパラメータとして(3,28)があり、これを使うと命令数を9個に減らせる。