擬似乱数の他分野拡張
仰々しいタイトルだけど、やってることは単純
まずはさらっと線形合同法の復習
S[n+1] = (A * S[n] + B) mod M
という形をしているY=aX+bみたいなもの
Y=aX+bと同じく右辺のX( S[n] )に値を入れれば左辺のY( S[n+1] )が求まる
Y=aX+bとの違いは右辺を計算した後にMで割った余りを計算結果にするところ
この計算を何度も繰り返して出てきた結果を並べたものはランダムっぽく見えるので乱数列として使われていて、
線形合同法は擬似乱数列を作って出力できるので擬似乱数生成器と呼ばれている
乱数講座のスライドでも説明したけれど、線形合同法にはいくつか重要な性質があって
・現在の値がわかれば次の値がわかる
・周期性をもつ
・現在の値から前の値もわかる(ことがある)
などなど
で、この性質を利用して他のものに応用できないか、というのがこの記事の目的
例えば、カードマジックへの応用
カードマジックの中にはメモライズド・デックと言って、あらかじめ52枚のカードの配列を全て暗記しておいて演技を行うものがある
線形合同法で得られた数字とカードの種類を対応させておけば、あるカードの前後のカードを計算で求めることができるし、
線形合同法で作られた配列は周期性があるから、演技前にカットを行っても前後の値の関係性は変わらない
これを実現するには周期が52となるA,B,Mの組み合わせを探す必要がある
最も簡単なのはM=52で最大周期となるA,Bを見つけることだけど、M=52で最大周期をとるAの条件が
・A-1が4の倍数
・A-1が2と13の倍数
・AがM未満
を全て満たすこととなって
A=1になってしまう
このときのカードの並びは赤黒が連続して並ぶか交互に並ぶかとなってランダムには見えなくなるので使えない
そこで、M=53,B=0という条件を設定し0を不動点にして最大周期M-1=52を得ることを考える
A=27を設定すると
1→27→40→20→…4→2→1
となって周期52のループが完成する
数字からカードへの変換については、4で割った商に1を足したものを数字にして4で割った余りを各スートに対応させればこの数列は
♣A→♥7→♠10→♠5→♦3→♣2→…のようにランダムな並びになる
次の値の計算について数字を27倍するのは暗算では難しいので別の方法を考えると、実はこの数列
偶数なら2で割る
奇数なら53を足して2で割る
という作業で次の数字が求まるようになっている!!!11そこから決めた
S[n+1] = 27 * S[n] mod 53
の逆関数を考えると
S[n-1] = 2 * S[n] mod 53
が得られ、前の値は現在の値を2倍したものになっていることがわかる
ということで線形合同法はカードマジックへの拡張可能性があると思ったのだけど
メモライズド・デックについてあまり詳しくないので、もしかしたらもう既にある考えなのかもしれない
上から何枚目とか
数字どうしがいくつ離れているかとか
単純な計算でできないものかと少し考えてみたけどoupoさんの記事
線形合同法であるseedが0からいくつ進めたものかを得る - oupoの日記
はMが2のべき乗でないと厳しそうだしで難しそう
なにかいい方法あればコメントでも
と言っていたら早速oupoさんがやってくれた
線形合同法であるseedが0からいくつ進めたものかを得る その3 - oupoの日記
これで解決…?
今回の線形合同法は最大周期じゃないので使えないとのこと
擬似乱数の他分野拡張というテーマはなかなか面白いテーマだと思うのでみなさんも考えてみましょう
思いついたら何でもコメントしてください