龍虎氏の記事に対するコメント。
続いてようやく第三回の乱数生成アルゴリズム。なんと2000年代に入ってから開発されたという・・最新やん！
このアルゴリズム、Xorshiftは実はかなり以前、このブログでも扱っている。
改めて紹介しよう。
と言うか、実は2000年代の末期にツイッターとかでも流行ってたアルゴリズムだ。
これが出てくるまで、「高精度の乱数アルゴリズム」は、R(※1)やPythonで採用されてる、日本製のメルセンヌ・ツイスタがある意味一強だったんだ。メルセンヌ・ツイスタでなければ乱数に非ず、って程の人気と信頼度の高さだった。
ところが、高精度な疑似乱数生成器であるメルセンヌ・ツイスタなんだけど、計算量やメモリの使用量が結構デカい。特にWebブラウザ上で動かすには結構困るわけだ。
そんな中、確か最初はGoogleだったと思うんだけど、Chromeに搭載した疑似乱数発生器がこのXorshiftで、そのせいで一躍有名になったわけだ。
引数を関数内で破壊的に使うので&mutと。
そう、Lispや関数型言語の経験から、Rustでもmutを使う際には「ホントにそうしなきゃアカンの?」と自問すべきだ・・・残念ながらやっぱC出身者がユーザーに多い故、「Cのロジックで書く = mutしまくり」ってのは良く起こる。
は～ん・・値が違う場合だけ束縛するってことか。結局同じなんだから構わず束縛したらエエのでは？と思うのだが。それとも真偽値が入るのか？そんなことも無いだろうしなぁ・・
ここはちと注釈が必要かも。
龍虎氏が考えてるように、「論理学的な意味では」その通り、だ。
> (xor 11 #f)
11
> (xor #f 22)
22
> (xor 11 22)
#f
> (xor #f #f)
#f
一方、ここで言ってる「排他的論理和」と言うのは、Racketで言うと次のような事だ。
> (bitwise-xor 1 5)
4
ちょっとパッと見、意味が分からないかもしんない。いや、これは「ビット演算」で、各ビット毎に排他的論理和を取る、って意味なんだよ。
;; 100000001;; 500000101;; 各ビット毎に排他的論理和を取る00000100 -> 4
1が真、0が偽で、「どちらかのみが真」の時が真、他が全部偽なのが排他的論理和、ってヤツなんで両者0のビットは0、両者1のビットも0、どっちか片方だけが1の時に1になる、ってわけ。
いずれにせよ、同じ桁の各ビットを比較していって・・・ってのがビット演算上での排他的論理和なんだ。
ビットシフトの数が素数だったのが気になって質問。別に意味は無かったのか・・
うん、これ、原論文チラッと見ても、「素数にして下さい」とは特に書いてないんだよね(笑)。
(条件として記述されてるのは一回目の左シフトは三回目の左シフトより数を小さくせよ、としかない)
後は時間の取得に関するメソッドがあるんだけど・・なんか日本語では検索してもロクな情報が出てこなかったし、欲しいとも思わないので今回は良いや。
あ〜、これは、だな・・・・・・。
上にも書いたけど、疑似乱数列ってのは単なる数列で「規則性がある」。
よってXorshiftだろうと線形合同法だろうと、はたまたメルセンヌ・ツイスタだろうと、「毎回同じシード(初期値)を与えると」同じ数列を生成するのだよ・・・・・・。
っつーことは、規則が同じでも起動する毎に別のシードを与えれば見た目違った疑似乱数列になる・・・・・・。
じゃあ、どうシードを変えるのよ?っつーと、一番簡単なのは「起動した時の現在の時間」を与えれば簡単だよな、って話になる・・・いわゆるUNIX時ってのは、エポック時間(1970年1月1日午前0時0分0秒)からの経過秒数で、増える一方だから「同一の時間」っつーのがあり得ないわけだ。
これを利用する為に「時間を取得してる」わけだ。
ちなみに、Schemeの仕様書には実は乱数はない。と言うのも「時間」が仕様上無い、からだ(笑)。
従って、各Scheme実装の乱数は実装者がサービスで入れてる、ってこった(笑)。
さて、Rustでmut(破壊的変更)を避けてXorshiftを実装しようとするとこのようになる。
Xorshift本体自体を関数型プログラミングするのはさして難しくない。Rustでもラムダ式が使えるので、ラムダ式を詰め込んだ配列を利用して書く事が出来る・・・でもどうしてもRacketなんかと比べるとイマイチで記述量が減る、ってカンジではないんだよな(苦笑)。
;; Racketの場合(define (xorshift seed)
(foldl (lambda (x acc)
(bitwise-xor acc (arithmetic-shift acc x))) seed '(13 -7 17)))
Pythonもそうなんだけど、結局、ビットシフトやら排他的論理和は「演算子」だと言う辺りで、ぶっちゃけ「足を引っ張られてる」カンジだ。Lispの「徹底した前置記法」は一般には嫌われるが、一方、「ルールが絶対変わらん」ってのが記述量削減に役立ってる。「演算子」による「中置記法」ってのは言っちゃえば「途中で記述ルールが変更になる」に等しい。よって色々纏めて書く分には一貫した前置記法の方が有利、なんだ。
ただ、それでもXorshift自体はラクに書ける。
逆にムズいのは、むしろ「300個の乱数を表示」の方だ。特にfoldの部分だ。
ここは「シード列」と言えるモノを生成してんだけど・・・・・・。
そもそも、Rustには基本的に「可変長のリスト」みてぇなモノがない。いや、一応可変長配列(ベクタ)ってのがあるにはあるんだが・・・。
いやまぁ、それでもRustは及第点なんだよ。Javaとかだと初期値に整数しか取れない、とか、reduceの機能は随分と「劣ったモノ」なんだ。型変換もメンドイし。
上の部分は要は「更新されていくseed列を生成する」コードなんだけど、Racketなんかに比べると同じ事をしてるのに、明らかに記述がメンドい。
(foldl (lambda (x v)
(cons (xorshift (car v)) v))
`(,seed) (range 300))
そしてシード列に対して(順番が逆になるんで)反転し、サイコロを振った結果になるようにマッピングし、改めてfor_eachで出力しないといけない。
ん〜〜・・・・・・。
この辺、結局関数型プログラミングで書けなくはないけど、特に短くもならんのであまり嬉しくない、ってのがホントのトコかな(笑)。Racketのコードに比べるとあまりにも複雑に見える。
この辺のmain関数内での出力は、悔しいけど破壊的変更を辞さず、フツーにルーピングして出力した方がコーディング的にはラクかな、ってのが正直なトコでした(笑)。
クソ(笑)。
S言語そのものは、AT&Tで開発された為、思いっきり同じ出自のC言語に近い構文になっている。
そしてRが採用している「言語」はS言語方言、となる(しばしばR言語と呼ばれる・・・正確じゃないが)。
ただし、R実装自体は、内部的にはSchemeに極めて近いらしい。
※2: 疑似乱数列とは実は単なる数列だ・・・従って「規則性」があり「周期」が存在する。延々と生成するといつの間にか「同じパターンが出現する」。
よって「良い疑似乱数」とは、人が気づきづらい「長い周期」の数列の事となる・・・任意の範囲をサンプリングすると、充分乱数として「使える」と言うわけだ。
一方、C言語実装なんかでは、仕様で要求されているわけではないが、線形合同法が良く使われていて、これはあまり品質が良くない疑似乱数発生器となる。
例えばRacketで
;; シードは8で300個の乱数列を生成(するつもり)
(foldl (lambda (y x)
(modulo (+ (* 13 (car x)) 5) 24)) '(8) (range 300))
等としてみれば分かるが(逆順の乱数列を返す事に留意)、線形合同法だと結果、
8、13、6、11、4、9、2、7、0、5、22、3、20、1、18、23、16、21、14、19、12、17、10、15
と言う24個の数の並びが１パターンで、以降は全部このパターンで埋め尽くされる。
「短い周期で予想が付く」と言うのはあまり良い乱数列ではないわけだ。
