Xorshift

解説/アルゴリズム

乱数で取得する値の並びがまったく同じになるように調整できると便利なときがある。たとえば、デバッグ時やなにかのリプレイを行うようなときなど。

そのような乱数列を生み出すために、乱数を利用する前に前もって渡しておく値のことをシードと呼び、シード毎に固定の乱数列が生成される。

Math.random() ではシードが指定できないので、代わりに Xorshift(32bit) という生成アルゴリズムを利用する。

Xorshift(32bit) は 1 以上 4294967295 以下の整数値全てを重複なくバラバラに出力するアルゴリズムになる。

順番	生成される値
仮にこの位置を 1 番目だとする	3337163801
2 番目	1763869612
3 番目	330629095
...
4294967293 番目	447601850
4294967294 番目	2254653639
4294967295 番目	12346
4294967296 番目(1 番目)	3337163801
4294967297 番目(2 番目)	1763869612
4294967298 番目(3 番目)	330629095

バラバラといっても内部の計算式に乱数が使われているわけではないので、ローテーション自体は固定のものになる。

たとえば、 3337163801 の後に生成される値は必ず 1763869612 になる。

内部では前回生成した値を保持しているが、それを外部から初期値として指定できるようにすると、それはそのままシード値になる。

下記で掲載しているコードでは Math.random と同じように 0 以上 1 未満の値が返却されるように正規化している。

コード例

// 2^32 - 1
const max = 0xffffffff;

export type XorShift = {
  seed: number;
};

export function init(seed?: number) {
  const xs: XorShift = { seed: 0 };

  // 引数がなければシード値をランダムに選ぶ
  if (seed === undefined) {
    xs.seed = Math.floor(Math.random() * max) + 1;
  } else {
    setSeed(xs, seed);
  }

  // この時点で初期値(seed)が1以上MAX以下の値になるように調整されている

  return xs;
}

// シード値の指定(0 <= seed < MAX)
export function setSeed(xs: XorShift, seed: number): void {
  // 整数にする
  seed = Math.floor(seed);
  if (!(0 <= seed && seed < max)) {
    throw new Error(
      `シード値の範囲は0以上${max}未満の値でなければいけません。`
    );
  }
  xs.seed = seed + 1;
}

// 0以上1未満の値を返す
export function getValue(xs: XorShift): number {
  next(xs);

  // 上限値が1未満になる、の実装のため、seed/MAX=1になるような計算はスキップする
  if (xs.seed === max) {
    next(xs);
  }

  // 下限値が0になるように分子分母ともに1を引いて割合を求める
  return (xs.seed - 1) / (max - 1);
}

// 次に生成される値を計算
function next(xs: XorShift): void {
  xs.seed = xs.seed ^ (xs.seed << 13);
  xs.seed = xs.seed ^ (xs.seed >>> 17);
  xs.seed = xs.seed ^ (xs.seed << 5);
  xs.seed = xs.seed >>> 0; // 33bit番目以上の情報は捨てる
}

import { init, getValue } from "./xorshift";

const a = init(12345);
console.log(getValue(a)); // 0.7769939958942095
console.log(getValue(a)); // 0.4106828970418698
console.log(getValue(a)); // 0.07698058480256265

const b = init(12345);
console.log(getValue(b)); // 0.7769939958942095
console.log(getValue(b)); // 0.4106828970418698
console.log(getValue(b)); // 0.07698058480256265

Xorshift(32bit) をベースとしたシード値が指定できる疑似乱数生成クラス。

コンストラクタにはシード値を指定する。シード値の範囲は 0 以上 4294967295(0xFFFFFFFF) 未満。

getValueは 0 以上 1 未満の値を返却する。

ソースコード

xorshift.ts / app.ts

内部で利用しているアルゴリズム

擬似乱数, 床関数, 正規化