(random-integer n)
によって {0, ..., n-1} の乱数整数を生成し、
(random-real)
によって 0 から 1 の乱数実数を生成する。
これらの乱数値を生成するための実装の詳細は適切でないかも知れないが、
十分にランダムであるように見えればよい。
乱数ソースが乱数ビットを生成するための基盤があれば、 それを利用して別種の乱数ジェネレータを派生させることができる。 最も重要なのは、 様々な分布を持つ浮動小数点数や、ランダムな離散構造、たとえば、 順列 (premutation) やグラフを生成することである。 このような応用は無数にあるため、この SRFI では扱わない。 言い換えると、 この SRFI はランダムな あらゆる種類のランダムなオブジェクトを生成するための方法を定めるのではなく、 ランダムなビット列を移植性があり、柔軟性があり、信頼性があり、かつ、 効率性がある形で定めることである。
この設計は、 離散構造、数値シミュレーション、暗号プロトコルなど、 数多くのアプリケーションにおける乱数の多様な使われ方をカバーできるように、 十分に柔軟であることを設計目標としている。 同時に、インターフェイスを単純にすることで、 予想できない使われ方にも対応できるようにしている。 しかし、すべての用途に万能な乱数ジェネレータを設計することは不可能なので、 様々なアプリケーションにおける様々な要求に対して、 いくらかの妥協を行っている。
厳密にいえばこの仕様の一部ではないが、 この設計では高品質と高効率に重点をおいている。 疑似乱数ジェネレータはまだ大きく進歩している最中なので、 参照実装に使用したアルゴリズムは、仮のものであることをお断りしておく。
(random-integer n) -> xdefault-random-source が次に生成する
{0, ..., n-1} の範囲の整数である。
この手続きを何度呼び出してもその結果は独立であり
{0, ..., n-1} の範囲に一様に分布しているように見える。
引数 n は正整数でなければならない。
正整数でなければエラーが発生する。
(random-real) -> xdefault-random-source が次に生成する
0 < x < 1 の範囲の実数である。
この手続きを何度呼び出してもその結果は独立であり、
一様に分しているように見える。
戻り値の型および量子化は実装依存である。
詳細は random-source-make-reals を参照せよ。
default-random-source
random-source-make-integers と
random-source-make-reals を用いて
random-integer と
random-real
を派生させた乱数ソースである。
default-random-source 変数に代入を行っても、
random や random-real
は変化しないことに注意せよ。
また、この変数に新しい値を代入しないことを強く推奨する。
(make-random-source) -> smake-random-source で作成された乱数ソースは、
疑似乱数ジェネレータにより生成される乱数ビットの決定論的ストリームである。
(make-random-source) により作成される乱数ソースは、
後述の手続きにより状態を変更されない限り、
常に同じ値のストリームを生成する。
(random-source? obj) -> bool(random-source-state-ref s) -> state(random-source-state-set! s state)
random-source-state-set! の引数に指定するだけである。
しかし、このオブジェクトは外部表現可能でなければならない。
(random-source-randomize! s)
(random-source-pseudo-randomize! s i j)
random-source-randomize! とは異なり、
この手続きは完全に決定論的である。
(random-source-make-integers s) -> randアプリケーションが同じ乱数ソース s の複数のジェネレータを取得する場合、 このいずれのジェネレータも s の状態を更新する。 したがって、これらのジェネレータは状態を共有しているので、 互いに同じ乱数整数を生成することはない。 このことは、１つの乱数ソースから派生された複数のジェネレータにも当てはまる。 並列処理をサポートする処理系では、 ジェネレータの状態が正しく更新されることを保証しなければならない。
(random-source-make-reals s) -> rand(random-source-make-reals s unit) -> randオプション引数の unit は、 手続き rand により生成される数値の型と量子化を指定する。 unit は 0 < unit < 1 の数値でなければならない。 rand により生成される数値は、 unit 引数と同じ数値型であり、 最大でも unit の間隔を持つ。 rand は x*unit という形式の数値を生成すると考えればよい。 ここで x は {1, ..., floor(1/unit)-1} の範囲の乱数整数である。 しかし、実際にこのように数値を生成する必要はないし、 rand の実際の分解能は unit よりもずっと高くてよい。 unit を指定しない場合は、 適度に小さい値がデフォルトとして使われる (このデフォルト値は効率的な数値フォーマットにおける仮数の幅に関係するだろう)。
random-integer と
random-real を１つの関数にまとめないのですか？random-integer と random-real
により提供される機能である。
それに加えて、これらの機能があれば、ユーザーが単純な
modulo 計算により乱数範囲を変更するという落とし穴に落ちなくて済む。
この方法により乱数範囲を変更すると、乱数の品質は大きく劣化するのである。
このインターフェイス設計は、次の３つのプロトタイプ アプリケーションに基づいている。
random-integer は呼び出しごとに範囲を定める引数 n を取る。
この手続きの実装では、範囲が即値整数であれば、値のボクシング/アンボクシングを回避すべきである。
float や double
の型によって異なるインスタンスが有り得るだろう。
したがって、random-real はパラメータを受け取らないが、
手続き random-source-make-reals によって適切に設定された
random-real 手続きを作成できるように設計している。
random-real の戻り値から 0 と 1 が除外されているのはなぜですか？random-real が x = 0 と x = 1
を返さないのは、
(log x) や
(log (- 1 x))
を計算するときに数値演算例外を起こさないようにするためである。
以上の理由から、私はまず George Marsaglia の COMBO ジェネレータを提案した。 このジェネレータは、32 ビットの乗法遅延 Fibonacci ジェネレータと、 16 ビットのキャリー乗算ジェネレータを組み合わせたものである。 COMBO ジェネレータは Marsaglia の DIEHARD 検査をすべてパスしており、2^60 のオーダーの周期を持つ。
改善案として、Brad Lucier は Pierre L'Ecuyer の MRG32k3a ジェネレータを提案している。 このジェネレータは、２つの３次再帰ジェネレータを組み合わせたものであり、 その２つともが 54 ビット算術内に収まるというものである。 MRG32k3a ジェネレータも DIEHARD 検査をパスしており、 それに加えて、好ましいスペクトル特性を持ち、2^191 というオーダーの周期を持つ。 実を言うと、多重再帰ジェネレータ (MRG: Multiple Recursive Generator) は、 COMBO ジェネレータのような特殊な構成のジェネレータよりも、 理論的により良く解析されている。 これらの理由から、ここでは MRG32k3a ジェネレータを実装することにした。 十分な仮数幅を持つ浮動小数点演算により実装された場合、 このジェネレータは非常に高速である。
多くのアプリケーションにとっては性能が重要であるため、 実際のジェネレータをネイティブコードで実装したいと思うかもしれない。 そこで、参考までに、バックボーンとなるジェネレータを異なる３つの方法で実装した。 下記のコードを参照してほしい。
後で解説する参照実装では、
エクスポートされた手続きを持つレコード型を定義する。
ジェネレータの実際の状態は、
make-random-source の束縛時の環境に格納される。
この実装方法には、レコード型の速度が遅い場合でも (遅い必要はないが)、
状態へのアクセスが高速であるという利点がある。
random-source-randomize! である。
この手続きは現実のエントロピー源にアクセスする必要があるからである。
エントロピー源の手ごろな選択肢としては、 システム クロックを使う方法がある。 この方法は John David Stone (下記の参考文献を参照) が推奨している。 この方法はほとんどのアプリケーションでは十分良い選択肢ではあるが、 セキュリティ関連のプログラムでは使うことができない。 Scheme で時刻を取得するには、 SRFI-19 を使えばよい。
参照実装では、コードの比較的大部分が、
MRG32k3a ジェネレータのより高度な機能を扱っている。
特に random-source-pseudo-randomize! がそうである。
このコードは Pierre L'Ecuyer 自身による
MRG32k3a ジェネレータの実装から影響を受けている。
Another part of this generic code deals with changing the range and quantization of the random numbers and with error checking to detect common mistakes and abuses.
(random-integer 2) を x 回計算可能であること、
1 秒間に (random-real) を y 回計算可能であることを意味している。
実装は：
integer のみを用いた実装。
この実装は性能よりも移植性を重視している。
(30000 ints/s, 3000/s reals/s)
(double) 算術を用いた実装。
このジェネレータは、
C/Scheme インターフェイス
を介して Scheme 48 で利用可能である。
このジェネレータの性能は良好である。
(160000 ints/s, 180000 reals/s)
flonum と 54 ビット integer を用いた実装。
このコードは Brad Lucier が SRFI 議論アーカイブに
投稿した
プログラムを参考にしている。
このジェネレータは、コンパイル時の性能は良好である。
(インタープリタ実行時の性能 5000 ints/s, 25000/s reals/s ,
コンパイル後の性能は 200000 ints/s, 400000/s reals/s である。
後述の謝辞を参照せよ。)
vector で表現している。
この実装では、まず、乱数ソース s を
n 次の順列を生成する手続きに変換する手続き
random-source-make-permutations
を定義している。
次に、デフォルトの乱数ソースに対してこの手続きを適用し、
すぐに順列を生成できる手続きを定義している。
手続き (random-permutation n)
は n 次のランダム順列を生成する。
(define (random-source-make-permutations s)
(let ((rand (random-source-make-integers s)))
(lambda (n)
(let ((x (make-vector n 0)))
(do ((i 0 (+ i 1)))
((= i n))
(vector-set! x i i))
(do ((k n (- k 1)))
((= k 1) x)
(let* ((i (- k 1))
(j (rand k))
(xi (vector-ref x i))
(xj (vector-ref x j)))
(vector-set! x i xj)
(vector-set! x j xi)))))))
(define random-permutation
(random-source-make-permutations default-random-source))
random-source-make-reals にオプション引数を渡すかということにある。
(define (random-source-make-exponentials s . unit)
(let ((rand (apply random-source-make-reals s unit)))
(lambda (mu)
(- (* mu (log (rand)))))))
(define random-exponential
(random-source-make-exponentials default-random-source))
ここで定義しているインターフェイスの技術的な難しさは、
polar method が計算のたびに２つの結果を生成することに関係している。
ここでは１つめ結果のみを返し、２つめの結果は記録しておいて、
次回の手続き呼び出し時に返すようにしている。
したがって、 random-source-state-set! (あるいは状態を変更する他の手続き)
は必ずしもすぐには random-normal の出力に影響しない！
(define (random-source-make-normals s . unit)
(let ((rand (apply random-source-make-reals s unit))
(next #f))
(lambda (mu sigma)
(if next
(let ((result next))
(set! next #f)
(+ mu (* sigma result)))
(let loop ()
(let* ((v1 (- (* 2 (rand)) 1))
(v2 (- (* 2 (rand)) 1))
(s (+ (* v1 v1) (* v2 v2))))
(if (>= s 1)
(loop)
(let ((scale (sqrt (/ (* -2 (log s)) s))))
(set! next (* scale v2))
(+ mu (* sigma scale v1))))))))))
(define random-normal
(random-source-make-normals default-random-source))
random flo:random-unit *random-state* make-random-state
random-state?
http://www.swiss.ai.mit.edu/projects/scheme/documentation/scheme_5.html#SEC53
(A mechanism to run a fixed unspecified generator.)
random *random-state* copy-random-state seed->random-state
make-random-state random:uniform random:exp random:normal-vector!
random-hollow-sphere! random:solid-sphere!
http://swiss.csail.mit.edu/~jaffer/slib_5.html#SEC108
(RC-4 を使用している)
make-random make-random-vector
(Scheme48 の内部手続き、固定長 28 ビット ジェネレータ)
random random-seed current-pseudo-random-generator
make-pseudo-random-generator pseudo-random-generator?
http://download.plt-scheme.org/doc/200alpha1/html/mzscheme/mzscheme-Z-H-3.html#%_idx_144
(ジェネレータを実行する仕組みとジェネレータを交換する仕組みについて)
rand の例は乱数ジェネレータを定義するための教科書的な方法を示している)
Copyright (C) Sebastian Egner (2002). All Rights Reserved.
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.