無作為無作為の作成.ランダム

JavaScriptでは、使用する乱数を作成することができますMath.random() . しかし、我々はこの関数なしでブラウザで独自のランダムな値を作成したい場合はどうですか?
The ECMAScript Language Specification の要件を定義するMath.random() :

Returns a Number value with positive sign, greater than or equal to 0 but less than 1, chosen randomly or pseudo randomly with approximately uniform distribution over that range, using an implementation-dependent algorithm or strategy. This function takes no arguments.

Each Math.random function created for distinct realms must produce a distinct sequence of values from successive calls.

世代数

数ジェネレータの例を示します.それはclosure 内部状態を維持し、初期シード値を基に数字のシーケンスを作成します.ここでは、種子は固定され、常に0 .

Math.random = (function () {
  let seed = 0
  return function () {
    seed += 1
    return seed
  }
})()

// We can iterate through the sequence
Math.random() // 1
Math.random() // 2
Math.random() // 3

擬似乱数発生器(PRNG)も同様に動作する.PRNGは内部の状態を維持して、新しい乱数が要求されるたびに、その状態に数学を適用します.種子は手動または自動です.にGo programming language , あなたはシードmath/rand あなた自身.ブラウザでMath.random オペレーティングシステム(OS)からのフードの下でランダムなデータを要求するシードとして使用します.
prngsは決定論的である.同じ種は常に同じ数の数を生成します.しばしば、決定論的結果が好ましい.たとえば、ネットワーク上で話をすることなく、すべてのクライアント上で同じランダムイベントを生成します.または再現可能なパフォーマンスベンチマーク.
ハッシュ関数を使用してprngを作成できます.インspinning-balls , Chromeのベンチマークの一つに、この例があります.

// v8/benchmarks/spinning-balls/v.js

// To make the benchmark results predictable, we replace Math.random
// with a 100% deterministic alternative.
Math.random = (function () {
  var seed = 49734321
  return function () {
    // Robert Jenkins' 32 bit integer hash function.
    seed = seed & 0xffffffff
    seed = (seed + 0x7ed55d16 + (seed << 12)) & 0xffffffff
    seed = (seed ^ 0xc761c23c ^ (seed >>> 19)) & 0xffffffff
    seed = (seed + 0x165667b1 + (seed << 5)) & 0xffffffff
    seed = ((seed + 0xd3a2646c) ^ (seed << 9)) & 0xffffffff
    seed = (seed + 0xfd7046c5 + (seed << 3)) & 0xffffffff
    seed = (seed ^ 0xb55a4f09 ^ (seed >>> 16)) & 0xffffffff
    return (seed & 0xfffffff) / 0x10000000
  }
})()

我々の数ジェネレータのように、次の乱数を計算しながら、それは内部状態を変更します.この状態変化により、次の呼は異なる番号を生成することができる.

擬似乱数発生器について

PRNGの中で最もよく知られているタイプの一つはlinear congruential generator (lcg)これは、やや怖い名前にもかかわらず、多くの行のコードを必要としません.
@ brycは例を示します、そしてa warning :

Commonly called a Linear congruential generator (LCG), but in this case, more correctly called a Multiplicative congruential generator (MCG) or Lehmer RNG. It has a state and period of 2^31-1. It's blazingly fast in JavaScript (likely the fastest), but its quality is quite poor.

function LCG(a) {
  return function () {
    a = Math.imul(48271, a) | 0 % 2147483647
    return (a & 2147483647) / 2147483648
  }
}

(これが初めてだMath.imul() — 提供するC-like 32-bit multiplication のいずれか)
@ brycのコメントは「この品質はかなり貧しい」という意味ですか?よく、特定の偶数の種子を与えられた場合、最後のステップ(除算)が除去されるとき、このアルゴリズムはパターンを持っています.

// https://gist.github.com/blixt/f17b47c62508be59987b#gistcomment-2792771

// @bryc:
// "Looking at the output without the division, and in hexadecimal, the
// first bits are always the same. This shows a clear pattern in the
// first 8 bits of the output: 1000 000, and it happens each time,
// infinitely. This is mostly caused by using an even seed."
const LCG = (s) => (_) => (s = Math.imul(48271, s) >>> 0)
const nxt = LCG(3816034944)
for (let i = 0; i < 9; i++) {
  console.log(nxt().toString(16))
}

/* Outputs:
4b6c5580 <-- notice the last two digits
b04dc280 <--
9645a580
16717280
d974f580
5c9f2280
9a3a4580
f196d280
b5d59580 */

があるmany ランダム性の品質をテストする方法これらのテストの方法論と結果のいくつかは、素人によって理解することができます.一つDiehard battery of tests クラップスの200000ゲームをプレイし、勝利の分布を見て、各ゲームをスローします.
LCGSのテストもありますspectral test は、2つ以上の次元でシーケンスをプロットします.以下の例では、hyperplanes それはスペクトルテストを測定します.

PRNGは最終的にシーケンスを繰り返す.この文脈では、周期はサイクルが繰り返されるまでの長さである.単純なPRNGMulberry32 その期間は40億円と低いMersenne Twister 期間がある2^19,937 - 1 . 2015年にはV 8チームsaid その実装Math.random() というアルゴリズムを使うxorshift128+ の期間2^128 - 1 . その導入はthis diff .
PRNGが最終的に繰り返されるならば、あなたは我々がなぜそれを繰り返し呼ぶかについて疑問に思うかもしれません.なぜ最初の数を使用しないし、新しい種子で内部状態をリセット?この問題は、種がどこかに由来する必要があるということです.我々がより多くのランダムなデータのためにOSに尋ねることを続けるならば、呼び出しがブロックするかもしれないという可能性があります(OSが生成されるより多くのランダムさを待ちます)、そして、我々のプログラムは失速します.

必要なエントロピー

それで、あなたはPRNGとwindow.Math.random . あなたはあなたのユーザーにそれを出荷しました、そして、最初に、誰でも幸せであるようです.
でも待って!あなたはその種について忘れました.そして今、あなたのユーザーは、彼らが得る乱数のシーケンスについて不平を言っている.彼らの顧客のページ負荷が毎回同じです.すべてのソフトウェアは予測可能です.その結果、彼らが構築したWebゲームはビートに簡単です.
シダプルワreminds us :

Entropy is the measurement of uncertainty or disorder in a system. Good entropy comes from the surrounding environment which is unpredictable and chaotic.

必要に応じて、ブラウザの安全な乱数の生成はCrypto.getRandomValues() からWeb Cryptography API . プラットフォーム特有の乱数関数、Unix/dev/urandom デバイス、またはランダムまたは擬似乱数データの他のソース."
Linuxsource この擬似乱数データがどこから来るかを示唆します.

Sources of randomness from the environment include inter-keyboard timings, inter-interrupt timings from some interrupts, and other events which are both (a) non-deterministic and (b) hard for an outside observer to measure.

また、使用するハードウェアデバイスもありますquantum mechanical physical randomness .
あなたは多くを見つけることができますprominent examples 間違ったタイプ(または十分でない)エントロピーが使用されたので、発生した乱数発生器攻撃の.曇りfamously エントロピー源として溶岩ランプを使用我々は安全なアルゴリズムを作成しようとしていないので、時間のようなエントロピーの予測可能なソースは素晴らしいです.
私たちはDate.now() 我々の種子状態.これは、すべてのミリ秒ごとに異なるランダムシーケンスを取得することを意味します.私たちはまたperformance.now() を返します.time origin .
ブラウザでエントロピーを得る他の方法

crypto.getRandomValues , crypto キージェネレーション、または似ている

マウス/タッチイベントambient light events , マイク/ウェブカメラのノイズ

GeoLocation API、Bluetooth API、または類似(必要なアクセス許可、ページロードでは動作しません)

WebGL/ビデオパフォーマンス

大部分のAPIlisted here

ここでは私たちの遅い(ネイティブコードではないので)と不安定です(私はそれをテストしていないので)交換Math.random() . また、prngsにはシード状態(例えば素数、128ビット)の要件があることに注意してください.我々のアルゴリズムはseed recommendations XoShio家族のために.

// https://github.com/bryc/code/blob/master/jshash/PRNGs.md
// xoshiro128+ (128-bit state generator in 32-bit)
Math.random = (function xoshiro128p() {
  // Using the same value for each seed is _screamingly_ wrong
  // but this is 'good enough' for a toy function.
  let a = Date.now(),
    b = Date.now(),
    c = Date.now(),
    d = Date.now()
  return function () {
    let t = b << 9,
      r = a + d
    c = c ^ a
    d = d ^ b
    b = b ^ c
    a = a ^ d
    c = c ^ t
    d = (d << 11) | (d >>> 21)
    return (r >>> 0) / 4294967296
  }
})()

Math.random() // 0.5351827056147158
Math.random() // 0.2675913528073579

だから、使命達成？

悲しいことに、それは完全にECMAScript準拠の置換を作成することは不可能ですMath.random() 仕様は連続した呼び出しから値のはっきりした系列を生産する「異なった領域」を必要とするのでレルムは、大まかに異なる環境(例えば、異なるウィンドウまたは異なる)を意味するWebWorker ). 私たちのバージョンは、この保証を行うことはできませんこの領域の外に到達することはできません.
しかし、提案されているRealms API . そのようなAPIが増加しているrealm IDのような何かへのアクセスを提供するのは、考えられないです.
ありがとうJN~commonswiki スペクトルテストの3 D GIFについて
参加300 +人々は私にサインアップnewsletter コードとどのようにそれを書く!
私は技術についてつぶやきます.