Help us understand the problem. What is going on with this article?

Xorshiftなどの擬似乱数をプロットして比較してみた

Xorshift で得られた乱数が適度にばらけているか視覚的に確認するため、平面に分布をプロットしました。

比較のためアルゴリズムが選べるようにしましたが、残念ながら違いは感じられませんでした。

See the Pen Xorshift32 by 七誌 (@7shi) on CodePen.

この記事には Haskell 版があります。

実装

Xorshift は実装が簡単な割に良好な擬似乱数を生成します。

JavaScript で実装します。

const UINT32_MAX_NEXT = 2 ** 32;
let getSeed = () => Math.floor(Math.random() * (UINT32_MAX_NEXT - 1)) + 1;
let getNext = (() => {
  let s = Uint32Array.of(getSeed());
  return seed => {
    if (seed) s[0] = seed;
    s[0] ^= s[0] << 13;
    s[0] ^= s[0] >> 17;
    s[0] ^= s[0] << 5;
    return s[0];
  };
})();
  • 型付きで演算するため 1 要素の TypedArray を使用しました。
  • 引数でシード値が指定できるようにしました。指定しなければ保持していた値を使います。初期値は JavaScript 組み込みの乱数から得ます。

Math.random と同じ使い方ができるように、結果を 0 以上 1 未満の浮動小数点数に変換します。

let getFloat = u32 => u32 / UINT32_MAX_NEXT;
let rand = seed => getFloat(getNext(seed));

Math.random

Math.random ではシード値が指定できません。

実装側で乱数生成アルゴリズムの初期シードを選択し、ユーザーが初期シードを選択、またはリセットすることは出来ません。

シード値が必要な場合に Xorshift は手軽な代替手段となるでしょう。

線形合同法

従来用いられていた単純なアルゴリズムです。

Stephen K. Park と Keith W. Miller が、彼らのサーベイ中で「最低基準」として示したもので、より良い選択肢が無いのならば、自作などせずにこれを使うべしというもの。

X_{n+1}=\left(48,271\times X_{n}\right)\ {\bmod {\ }}(2^{31}-1)

4. comp.lang.c FAQ list · Question 13.15 ただしソースコードでは乗数が 16807 になっているので注意すること。48271 を使ったほうが(もしかしたら計算がわずかに重くなるかもしれないが)少し良い乱数列になる。ソースコード中のその数の部分を書き換えるだけでよい。

これを JavaScript に移植しました。シード値の扱いは Xorshift の getNext に合わせています。

let [PMgetSeed, PMrand, PMrandF] = (() => {
  const a = 48271;
  const m = 2147483647;
  const q = Math.floor(m / a);
  const r = m % a;
  let PMgetSeed = () => Math.floor(Math.random() * (m - 1)) + 1;
  let s = Int32Array.of(PMgetSeed(), 0, 0, 0);
  let PMrand = seed => {
    if (seed) s[0] = seed;
    s[1] = s[0] / q;
    s[2] = s[0] % q;
    s[3] = a * s[2] - r * s[1];
    s[0] = s[3] > 0 ? s[3] : s[3] + m;
    return s[0];
  };
  let PMrandF = seed => PMrand(seed) / m;
  return [PMgetSeed, PMrand, PMrandF];
})();

Web Crypto API

MDN には次のように言及があります。

Math.random() の提供する乱数は、暗号に使用可能な安全性を備えていません。セキュリティに関連する目的では使用しないでください。代わりに Web Crypto API(より正確にはwindow.crypto.getRandomValues() メソッド)を使用してください。

こちらも比較に使ってみました。

let cryptoRand = (() => {
  let buf = new Uint32Array(1);
  return () => getFloat(window.crypto.getRandomValues(buf)[0]);
})();

プロット

Canvas にサイズ 1×1 の長方形を描くことで点を打ちます。最初の 20 個の乱数は値を表示します。

function test() {
  result.innerHTML = "";
  let ctx = canvas.getContext("2d");
  let w = canvas.width;
  let h = canvas.height;
  ctx.fillStyle = "white";
  ctx.fillRect(0, 0, w, h);
  ctx.fillStyle = "black";
  let count = parseInt(dots.value);
  let rnd = select.selectedOptions[0].function;
  for (let i = 0; i < count; i++) {
    let rx = rnd(), ry = rnd();
    if (i < 10) { log(rx); log(ry); }
    x = Math.floor(rx * w);
    y = Math.floor(ry * h);
    ctx.fillRect(x, y, 1, 1);
  }
}

この種のプロットについて Wikipedia に言及があります。

線形合同法一般の欠点に、多次元で規則的に分布するという性質がある。線形合同法による乱数列$r _ 0$, $r _ 1$, $r _ 2$, $r _ 3$, ... から($r _ 0$, $r _ 1$), ($r _ 1$, $r _ 2$), ($r _ 2$, $r _ 3$), ... のように順番に割り当ててプロットすると、それが疎になるのはしょうがないのだが(例として、全部で10000個しかない点を、10000x10000 の矩形にプロットすることになるのだから、稠密にはなりえない)、一定の間隔の平面上に点が並んでしまうのが問題である。

今回のプロットは 100×100 と小さかったため、目で見て分かるほどには表面化しませんでした。

参考

出力の log() は次の実装を使っています。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした