[Delphi][小ネタ] XorShift

はじめに

９日に引き続き乱数の話です。
今回はアルゴリズムの話で、XorShift についてです。

XorShift とは

Wikipedia によると

Xorshiftは疑似乱数列生成法の1つである。
George Marsagliaが2003年に提案した。
演算が排他的論理和とビットシフトのみであるため高速であるなどの特徴がある。

とのことで、メルセンヌ・ツイスタとかより非常に高速なのに、周期もそこそこ長くて使い勝手が良い乱数生成法です。

実装

Delphi での実装はこんな感じ

function XorShift: UInt32;
begin
  // FA は初期化されている必要がある
  FA := FA xor (FA shl 13);
  FA := FA xor (FA shr 17);
  FA := FA xor (FA shl 5);
  Result := FA;
end;

今回、これも Unit 化しました。

Unit 化

unit PK.Math.XorShift;

interface

implementation

uses
  System.SysUtils;

type
  TXorShift = record
  private class var
    FA: UInt32;
  private
    class procedure Init; static;
  public
    class procedure SetSeed(ANewSeed: UInt64); static;
    class function Execute: UInt32; static;
  end;

{ TXorShift }

class function TXorShift.Execute: UInt32;
begin
  FA := FA xor (FA shl 13);
  FA := FA xor (FA shr 17);
  FA := FA xor (FA shl 5);
  Result := FA;
end;

class procedure TXorShift.Init;
begin
  FA := Round(Frac(Now) * 24 * 60 * 60 * 1000) mod 1000;;
  Random32Proc := Execute;
  RandomizeProc := SetSeed;
end;

class procedure TXorShift.SetSeed(ANewSeed: UInt64);
begin
  DefaultRandomize(ANewSeed);
  FA := RandSeed;
end;

initialization
  TXorShift.Init;

end.

ここで新たな RandomizeProc 変数が出てきました。
これは Randomize 関数を呼んだ時に、こちらで指定した関数が呼ばれるようにする物です。
XorShift は初期化が必要なので、これを使って初期化できます。
Randomize を呼ぶと、時刻を元にした値がやってきます。

ここでは、それを DefaultRandomize 関数に渡して、初期化を代行させています。
DefaultRandomize では RandSeed 変数にシード値を入れてくれるため、それを使って FA メンバ変数を初期化しています。

サンプル

前回と同じサンプルを動かしてみました。

結果はこうなりました。

0 949
1 1036
2 973
3 1047
4 1006
5 1024
6 991
7 989
8 987
9 999

まとめ

XorShift は性能と高速さを併せ持っているので通常の乱数を使う場面であれば、ほぼ万能と言えます。
暗号論的強度はない（次の数字が予測可能である）ため、その用途には CNG Random が向いています。

ちなみにシード値を指定できるタイプの乱数生成では、同じシード値からは必ず同じ乱数列が生成されます。
その性質のため、ゲーム等で役に立ちます。
たとえば、ぷよぷよで２人プレイの場合、２人に同じぷよが降ってくる必要がありますが、同じシード値を持った乱数生成関数があれば、容易に実現できるのです。