JavaScript での乱数生成の基礎

JavaScript での乱数生成の基礎

(明らかに)乱数を生成できることは、数学、統計学、科学、技術、ゲームの多くの分野にとって不可欠な要件です。

12min read

(明らかに)乱数を生成できることは、数学、統計学、科学、技術、ゲームの多くの分野にとって不可欠な要件です。

例えば、ランダム化比較試験の参加者をグループに割り当てたり、コンピューターゲームのアウトプットを決定したり、他の方法では解決困難な問題に対するおおよその解決策を見つけたりするために使用できます。私は、完全に扱いやすい統計問題に対する解決策を確認するためにも、乱数を頻繁に使用します。ここでは取り上げませんが、暗号化乱数発生器はセキュリティ上使用できます。

Types of Random Number Generator

少なくともこの記事では、乱数コレクションには 3 つのカテゴリがあると考えることができます。

  • “True” random numbers;
  • Pseudorandom numbers;
  • Quasirandom sequences.

真の(またはハードウェアの)乱数発生器(TRNG)は、本質的にランダムであると考えられている現実世界の物理プロセスを使用して、数値のストリームを作成します。例えば、放射線源からの崩壊イベントはランダムで互いに相関しないため、大気中のノイズも利用することができます。

TRNGは、多くの場合、多くの目的にとって実用的または便利ではない(または必要ではない)わけではありません。はるかに一般的な代替手段は、コンピューターアルゴリズムを使用して、ある間隔でランダムに分布しているように見える数値のストリームを作成することです。これらのアルゴリズムは本当に予測不可能ではないため、疑似乱数ジェネレーター (PRNG) と呼ばれます。

最後に、準乱数列は、何らかの方法でサンプル空間を代表することを目的とした数値の有限の集合です。たとえば、シーケンスの平均は、母集団の既知の平均と同じ (または非常に類似している) 場合があります。準ランダム数列は興味深く、役立つ場合がありますが、この記事では焦点を当てていないため、これ以上説明しません。

The Standard Uniform Distribution

一般に、疑似乱数発生器からの多数の値の出力は、0 から 1 の範囲をカバーする標準一様分布(SUD) を近似することを目的としています。ただし、エンドポイントのいずれかまたは両方が含まれるかどうかには、いくつかのバリエーションがあります。連続分布の数学の概念的な世界では、[0,1] の間の一様分布 (0 と 1 を含む) と (0,1) の間の一様分布 (0 と 1 を除く) との間には基本的に違いはありません。浮動小数点数の現実の世界では、0 から 1 までの可能な値の数が有限しかないため、違いは現実のものであり、問題になる可能性があります。たとえば、生成された数値を自然対数関数Math.log内で使用したい場合があります。

別の分布の乱数を生成することは、通常、SUD PRNGから1つ以上の数値を使用して、関心のある分布から適切な値を生成する「だけ」の問題です。目的の最終配布に応じて、これには 1 行のコードが含まれる場合もあれば、非常に複雑なものが含まれる場合があります。この記事の残りの部分では、SUD PRNGからの番号の生成について引き続き説明します。

Period

有用なPRNGは、長い周期を持つ必要があります。つまり、それ自体を繰り返さずに多数の数値を出力できなければなりません。たとえば、1982年のWichmann Hill PRNG(これについては後で詳しく説明します)の周期は約7兆個ですが、非常に人気のあるMersenne Twister PRNGの周期は2 19937-1個の数値です。前者は現代の基準ではかなり短いと考えられています。

​Math.randomの何が問題になっていますか?

JavaScript の組み込みMath.randomを定期的に使用しても問題ありません。ただし、出力が再現できないという大きな制限があります。Math.randomを利用するコードを何度も実行すると、毎回異なる結果が得られます。多くの場合、それは実際には問題ではありません。実際、多くの場合(おそらくほとんどの場合)、それはまさにあなたが望むものになります。予測不可能性(少なくとも人間が座って出力を見つめている人にとっては)は、まさに必要なものです。しかし、時には同じ結果を見たいこともあります。

JavaScript から少し離れて、公開したい作品のシミュレーション実験を実行することを検討してください。おそらく、C++、Java、Rなどを使用していますか?結果を再現可能にしたい。これらの言語(および他の多くの言語)は、PRNGの初期状態を「シード」する方法を提供します。何らかの方法でシードを設定すると、同じ「ランダムな」数字のシーケンスが得られます。Math.random さんシードも必要で、自分で設定する方法はありません。ザ仕様対してMath.random さんまた、かなりオープンエンドであり、出力が範囲 [0,1] でほぼ均一である限り、ブラウザーベンダーは「実装に依存するアルゴリズム」を使用できます。

個人的な観点からは、データと概念の両方を伝達するためのブラウザベースのインタラクティブなデータ視覚化の大ファンです。これにはシミュレーションが含まれる場合があります。ブラウザで実用的なことには限界がありますが、Web Workers がお手伝いします。シミュレーションでは、乱数が必要になることがよくあります。乱数が再現可能でない場合、シミュレーションの条件を再実行することはできません。他にも、繰り返し可能なアニメーションなど、さまざまなユースケースがあり、JavaScriptはもはやブラウザのプログラミング言語だけではありません。

問題のあるPRNG

これまで、一様分布 PRNG のしくみについては読み飛ばしてきました。それはすべてブラックボックスのようなものでした:関数を1回以上呼び出し、場合によってはシードを設定すると、いくつかの疑似乱数が出てくるのです。問題は、優れたPRNGを作成するのが難しいことです。このトピックに関する何千もの論文と複数の方法があります。そして、私よりもこのトピックについてはるかに詳しい人々が物事を間違えているように見える複数の例があります。例えば。。。

RANDU

RANDUは、1950年代にIBMが開発した「線形合同発電機」(LCG)です。LCG は、次の形式の回帰関係を使用して、新しい疑似乱数を生成します。

RANDUの場合、cは0、aは65,539、mは2 31です。cが 0 であるため、RANDU は "乗算合同ジェネレータ" (MCG) と呼ばれる LCG のサブセットのメンバーです。0 から 1 の範囲の数値を取得するには (Math.randomの代わりとして望ましいように)、RANDU の漸化関係の結果をmで割るだけです。JavaScript の実装 (絶対に使用しないでください) は、次のようになります。

var randu = function(seed){

   "use strict";
   
   if(!isFinite(seed)){
      throw new Error("Seed not a finite number");
   }
		   
   var x = Math.round(seed);
   var a = 65539;
   var m = Math.pow(2, 31);

   if(x<1 || x≥m){
      throw new Error("Seed out of bounds");
   }

   return function(){
      x = (a*x)%m;
      return x/m;
   };
    
};

RANDUの回帰関係によって生成される値のパリティは変化しません。つまり、奇数シードはxの奇数値のみを生じさせ、偶数シードはxの偶数値のみを生じさせます。これは必ずしも望ましい特性ではありませんが、より大きな問題があります。

LCGの周期は最大でmですが、RANDUの場合はそれよりもはるかに短く、シードのパリティに依存します。奇数種子の場合は5億3,600万個を超えますが、偶数種子の場合は16,384個にもなります。

偶数シードを気にしない別の理由があります: ジェネレーターのランダム性を評価するための一般的で簡単な方法の 1 つは、連続する値のペアを散布図としてプロットすることです。優れたPRNGは、1 x 1 の正方形をかなり均等に埋める必要があります。10,000個の乱数、5,000ポイント、1のシードがあれば、すべてが合理的に見えます。("x" は、10,000 個の乱数の (0 インデックス付き) 配列の偶数インデックス位置の値を指すと考えることができます。それはインデックス0、2、4、6です...9,996, 9,998.散布図上のポイントは、次の奇数指数(1、3、5、7...9,997, 9999) "y" 値。

RANDUが生成した5000ペアの番号は1のシード

いくつかの偶数種子では、私たちはかなり異なる何かをしています。以下は、シード32,768の散布図です。

いくつかの偶数種子では、私たちはかなり異なる何かをしています。以下は、シード32,768の散布図です。

明らかに、イーブンシードの場合、ポイントが不足しているだけではありません。場合によっては、隣接する値の間に明確な関係があります。

上記のrandu関数を適応させて、シードも拒否し、適切なエラーメッセージを表示するのは簡単です。残念ながら、オッズシードも構造を示しています。これを確認するには、連続する乱数の3連符を見て、散布図のアイデアを3次元に拡張する必要があります。3D散布図は、多くの場合、かなり役に立たないものです。RANDUデータは、このルールの例外のようなものを提供します。(ここで、"x" 値のインデックスは 0、3、6、9...9,993、9,996、「y」値のインデックスは1、4、7、10です...9,994, 9997 で、"z" 値のインデックスは 2, 5, 8, 11...9,995, 9,998.)

3,333 個の RANDU トリプレットが 1 のシードを使用して数値を生成しました

箱をほぼ均等に埋めるのではなく、数字の三つ子はすべて、種に関係なく、15の平面の1つに横たわっています。(実際には、偶数のシード32,768の場合、これよりも悪いです。これをMath.randomの結果と比較できます（これにはChromeを使用しました）その違いは歴然としています。

Math.randomが生成した3,333個の3連星の数値

3D散布図の一般的な問題の1つは、プロット内の構造の可視性が視野角に依存する可能性があることです。特定の角度から見ると、RANDUプロットの構造は隠されます。これできたの場合Math.random さん.この問題を解決するために、PRNG(および必要に応じて1つ以上のシード)を選択し、結果を視覚化できるインタラクティブバージョンを作成しました。WebGLの.このデモは、ここで見つけましたまた、乱数のボックスは(マウスを使用して)回転させて、さまざまな角度から見ることができます。私はまだ使用時に構造の明らかな兆候を見つけていませんMath.random さん複数のブラウザ(デスクトップではChrome、Firefox、Maxthon、IE、Edge、Opera、iOSではSafari)に対応しています。

3次元以上の格子構造の出現はすべてのMCGに存在しますが、RANDUでは特に悪いです。それは1960年代から知られています。それにもかかわらず、RANDUは1970年代にまだ使用されており、その時代のシミュレーション結果の一部は、おそらく懐疑的に見るべきです。

秀でる

PRNGの問題は1960年代と70年代に限定されていたのかどうか疑問に思われるかもしれませんか?この質問に対する簡単な答えは「いいえ」です。古い乱数発生器に対する批判の後、MicrosoftはExcel 2003のWichmann–Hill PRNGに変更しました。WHジェネレータ(1982年に最初に公開)は、3つのMCGを組み合わせて、単一のMCGの欠点のいくつか(比較的短い周期や、隣接する値のグループを見るときに見られる格子平面と超平面など)を克服します。WH の簡単な JavaScript 実装は、次のようになります。

var wh = function(seeds){
  
   "use strict";

   if(seeds.length<3){
      throw new Error("Not enough seeds");
   }

   var xA = Math.round(seeds[0]);
   var aA = 171;
   var mA = 30269;

   var xB = Math.round(seeds[1]);
   var aB = 172;
   var mB = 30307;

   var xC = Math.round(seeds[2]);
   var aC = 170;
   var mC = 30323;
   
   if(!isFinite(xA) || !isFinite(xB) || !isFinite(xC)){
      throw new Error("Seed not a finite number");
   }

   if(Math.min(xA,xB,xC)<1 || xA≥mA || xB≥mB || xC≥mC){
      throw new Error("Seed out of bounds");
   }  

   return function(){
      xA = (aA*xA)%mA;
      xB = (aB*xB)%mB;
      xC = (aC*xC)%mC;
      return (xA/mA + xB/mB + xC/mC) % 1;
   };
	  
};

ここでも、隣接する値のセットを2次元または3次元でプロットするときに構造を探すことができます。

1、2、3 のシードを持つ WH 生成番号の 5000 ペア
WH で生成された数値の 3,333 個のトリプレット (シード 1、2、3)

これは明らかに、優れた乱数発生器があるかどうかを述べるには不十分ですが、上記のプロットは少なくとも合理的に見えます。(上記のWebGL デモで 3 次元ボックスをチェックすることもできます。ただし、ExcelのRAND関数のWHアルゴリズムの元の実装では、負の数が吐き出されることがありました。

WHアルゴリズムは、PRNGのより近代的で厳格なテストの数に失敗しており、Microsoftは人気のある(しかしより複雑な) Mersenne Twisterアルゴリズムの使用に移行したようです。

V8

先ほど、Chrome のMath.randomの実装からの出力を使用して、乱数の 3 連符の分布を 3 次元の散布図としてプロットしたときにどのように見えるかを示しました。しかし、Chrome の JavaScript エンジンである V8 で使用されていたアルゴリズムに欠陥があることが最近明らかになりました。具体的には、この長いが有益な記事で説明されているように、同じ「ランダムな」文字列を本来よりもはるかに高い頻度で再現しました。V8開発者は使用するアルゴリズムをすぐに変更し、この問題はバージョン49以降のChromeで修正されたようです。

Speed

JavaScript PRNGを「自分で育てる」前に考慮すべきもう1つの考慮事項は、速度です。Math.randomは高度に最適化されていると期待する必要があります。たとえば、いくつかのブラウザを使用した非常に大まかなテストでは、Math.randomは上記の単純な WH 実装よりも 100,000 個の乱数を生成するのに ~3 倍速いことが示されました。そうは言っても、私たちはまだ数十ミリ秒のオーダーについて話しているので(少なくとも私のラップトップのChromeとFirefoxでは)、多数の乱数が必要な場合でも、これはボトルネックにならないかもしれません。もちろん、より優れた統計的特性を持つより複雑なPRNGは、遅くなる可能性があります。

結論

ここの表面にはほとんど触れていません。私はいくつかの単純なPRNGだけを見て、それらがまだ問題になる可能性があることを示しました。PRNGにははるかに複雑なアルゴリズムがあり、中には多数の非常に厳しい統計テストに合格したものもあります。また、これらのいくつかはすでにオープンソースのJavaScript実装を持っています。

再現性が必要ない場合は、Math.randomが乱数のニーズすべてに対応できるかもしれません。いずれにせよ、乱数ジェネレーターの信頼性がサイトの機能にとって重要である場合は、関連するチェックを実行する必要があります。Math.randomの場合、JavaScript 仕様ではベンダーが使用しなければならない特定のアルゴリズムが指定されていないため、これはすべての対象ブラウザーをチェックインすることを意味します。

Web アプリ用の JavaScript HTML5 コントロールを試して、その優れたデータ視覚化機能をすぐに活用してください。今すぐ無料トライアルをダウンロードしてください。

操作方法
デモを予約