自作CPUをテーマにしている学生さんと話していたときに、何か独自命令を実装してみようよという話になり、身近なところで乱数生成命令はどうかいな？という話になりました。
ちなみに私は計算機工学は専門外です。
研究室としては成果が出ませんのでいいことではないのですが、就職する子であれば僕が専門外でも自分の興味の持てるテーマを積極的に考えてやってもらってきました。
で、調べてみると、インテルもそうした命令を実装したというエントリーを見つけました。全く的はずれな目標ではなさそう。
そのエントリーを読むと、/dev/randomという疑似デバイスがあるとか。
Wikipediaによると、以下のような実装になっているそうで。
デバイスドライバその他の情報源から集めた環境ノイズを利用して、真の乱数性を得るのが目的である。
情報理論を専門にしている先生と共同研究をしたこともあり（といっても私は理論本体はさらっと勉強した程度）、興味がムクムクと。
ランダムさを評価するためdieharderというツールがあるそうで。macOSの/dev/randomをcatすると使えそう。
Robert G. Brown's General Tools Page
ちょっとやってみました。
dieharderをbrewでいれたあと、以下のコマンドをターミナルに打ち込みます。ちなみに-g 200は標準入力から乱数を受け取ることを意味しています。-aは乱数の全てのテストを実行することを指定しています。使い方はこちらを参考にしました。
cat /dev/random | dieharder -g 200 -a
実行結果は以下でした。
#=============================================================================#
# dieharder version 3.31.1 Copyright 2003 Robert G. Brown #
#=============================================================================#
rng_name |rands/second| Seed |
stdin_input_raw| 7.50e+06 | 209043854|
#=============================================================================#
test_name |ntup| tsamples |psamples| p-value |Assessment
#=============================================================================#
diehard_birthdays| 0| 100| 100|0.84010314| PASSED
diehard_operm5| 0| 1000000| 100|0.88184702| PASSED
diehard_rank_32x32| 0| 40000| 100|0.80116887| PASSED
diehard_rank_6x8| 0| 100000| 100|0.32797592| PASSED
diehard_bitstream| 0| 2097152| 100|0.71336935| PASSED
diehard_opso| 0| 2097152| 100|0.32036284| PASSED
diehard_oqso| 0| 2097152| 100|0.56588344| PASSED
diehard_dna| 0| 2097152| 100|0.16104878| PASSED
diehard_count_1s_str| 0| 256000| 100|0.02587503| PASSED
diehard_count_1s_byt| 0| 256000| 100|0.99975997| WEAK
diehard_parking_lot| 0| 12000| 100|0.76205443| PASSED
diehard_2dsphere| 2| 8000| 100|0.35372258| PASSED
diehard_3dsphere| 3| 4000| 100|0.52628048| PASSED
diehard_squeeze| 0| 100000| 100|0.99795234| WEAK
diehard_sums| 0| 100| 100|0.10828469| PASSED
diehard_runs| 0| 100000| 100|0.22786568| PASSED
diehard_runs| 0| 100000| 100|0.73520191| PASSED
diehard_craps| 0| 200000| 100|0.99817327| WEAK
diehard_craps| 0| 200000| 100|0.53775024| PASSED
marsaglia_tsang_gcd| 0| 10000000| 100|0.96242186| PASSED
marsaglia_tsang_gcd| 0| 10000000| 100|0.49693013| PASSED
sts_monobit| 1| 100000| 100|0.97466667| PASSED
sts_runs| 2| 100000| 100|0.23166568| PASSED
sts_serial| 1| 100000| 100|0.34808416| PASSED
sts_serial| 2| 100000| 100|0.99265438| PASSED
sts_serial| 3| 100000| 100|0.51311140| PASSED
sts_serial| 3| 100000| 100|0.53917861| PASSED
sts_serial| 4| 100000| 100|0.69049546| PASSED
sts_serial| 4| 100000| 100|0.99828593| WEAK
sts_serial| 5| 100000| 100|0.90872696| PASSED
sts_serial| 5| 100000| 100|0.87589480| PASSED
sts_serial| 6| 100000| 100|0.85664976| PASSED
sts_serial| 6| 100000| 100|0.76773811| PASSED
sts_serial| 7| 100000| 100|0.88820883| PASSED
sts_serial| 7| 100000| 100|0.90635794| PASSED
sts_serial| 8| 100000| 100|0.25447163| PASSED
sts_serial| 8| 100000| 100|0.34641270| PASSED
sts_serial| 9| 100000| 100|0.84809016| PASSED
sts_serial| 9| 100000| 100|0.54602730| PASSED
sts_serial| 10| 100000| 100|0.38435104| PASSED
sts_serial| 10| 100000| 100|0.31579546| PASSED
sts_serial| 11| 100000| 100|0.70558193| PASSED
sts_serial| 11| 100000| 100|0.11063842| PASSED
sts_serial| 12| 100000| 100|0.63108657| PASSED
sts_serial| 12| 100000| 100|0.46233543| PASSED
sts_serial| 13| 100000| 100|0.32157881| PASSED
sts_serial| 13| 100000| 100|0.65954542| PASSED
sts_serial| 14| 100000| 100|0.96746596| PASSED
sts_serial| 14| 100000| 100|0.77409273| PASSED
sts_serial| 15| 100000| 100|0.89417935| PASSED
sts_serial| 15| 100000| 100|0.86407150| PASSED
sts_serial| 16| 100000| 100|0.89478924| PASSED
sts_serial| 16| 100000| 100|0.67017732| PASSED
rgb_bitdist| 1| 100000| 100|0.18252442| PASSED
rgb_bitdist| 2| 100000| 100|0.19992269| PASSED
rgb_bitdist| 3| 100000| 100|0.80715854| PASSED
rgb_bitdist| 4| 100000| 100|0.78238484| PASSED
rgb_bitdist| 5| 100000| 100|0.98778718| PASSED
rgb_bitdist| 6| 100000| 100|0.55393736| PASSED
rgb_bitdist| 7| 100000| 100|0.24144382| PASSED
rgb_bitdist| 8| 100000| 100|0.22933685| PASSED
rgb_bitdist| 9| 100000| 100|0.44936032| PASSED
rgb_bitdist| 10| 100000| 100|0.47427858| PASSED
rgb_bitdist| 11| 100000| 100|0.48019771| PASSED
rgb_bitdist| 12| 100000| 100|0.32258149| PASSED
rgb_minimum_distance| 2| 10000| 1000|0.35669936| PASSED
rgb_minimum_distance| 3| 10000| 1000|0.32627779| PASSED
rgb_minimum_distance| 4| 10000| 1000|0.25836237| PASSED
rgb_minimum_distance| 5| 10000| 1000|0.36578020| PASSED
rgb_permutations| 2| 100000| 100|0.84772302| PASSED
rgb_permutations| 3| 100000| 100|0.60586989| PASSED
rgb_permutations| 4| 100000| 100|0.03945497| PASSED
rgb_permutations| 5| 100000| 100|0.36162649| PASSED
rgb_lagged_sum| 0| 1000000| 100|0.90713644| PASSED
rgb_lagged_sum| 1| 1000000| 100|0.69476062| PASSED
rgb_lagged_sum| 2| 1000000| 100|0.55459730| PASSED
rgb_lagged_sum| 3| 1000000| 100|0.61342206| PASSED
rgb_lagged_sum| 4| 1000000| 100|0.16390450| PASSED
rgb_lagged_sum| 5| 1000000| 100|0.20790596| PASSED
rgb_lagged_sum| 6| 1000000| 100|0.52135294| PASSED
rgb_lagged_sum| 7| 1000000| 100|0.40424151| PASSED
rgb_lagged_sum| 8| 1000000| 100|0.17133571| PASSED
rgb_lagged_sum| 9| 1000000| 100|0.16488017| PASSED
rgb_lagged_sum| 10| 1000000| 100|0.04872171| PASSED
rgb_lagged_sum| 11| 1000000| 100|0.14221327| PASSED
rgb_lagged_sum| 12| 1000000| 100|0.73422080| PASSED
rgb_lagged_sum| 13| 1000000| 100|0.52321745| PASSED
rgb_lagged_sum| 14| 1000000| 100|0.92157772| PASSED
rgb_lagged_sum| 15| 1000000| 100|0.46483494| PASSED
rgb_lagged_sum| 16| 1000000| 100|0.77249270| PASSED
rgb_lagged_sum| 17| 1000000| 100|0.90706117| PASSED
rgb_lagged_sum| 18| 1000000| 100|0.07863041| PASSED
rgb_lagged_sum| 19| 1000000| 100|0.57804548| PASSED
rgb_lagged_sum| 20| 1000000| 100|0.62148226| PASSED
rgb_lagged_sum| 21| 1000000| 100|0.43169864| PASSED
rgb_lagged_sum| 22| 1000000| 100|0.55355207| PASSED
rgb_lagged_sum| 23| 1000000| 100|0.37528172| PASSED
rgb_lagged_sum| 24| 1000000| 100|0.89652958| PASSED
rgb_lagged_sum| 25| 1000000| 100|0.56031126| PASSED
rgb_lagged_sum| 26| 1000000| 100|0.06051842| PASSED
rgb_lagged_sum| 27| 1000000| 100|0.48204716| PASSED
rgb_lagged_sum| 28| 1000000| 100|0.78433150| PASSED
rgb_lagged_sum| 29| 1000000| 100|0.46256405| PASSED
rgb_lagged_sum| 30| 1000000| 100|0.65675002| PASSED
rgb_lagged_sum| 31| 1000000| 100|0.40871416| PASSED
rgb_lagged_sum| 32| 1000000| 100|0.63328571| PASSED
rgb_kstest_test| 0| 10000| 1000|0.04705398| PASSED
dab_bytedistrib| 0| 51200000| 1|0.29698159| PASSED
dab_dct| 256| 50000| 1|0.97199683| PASSED
Preparing to run test 207. ntuple = 0
dab_filltree| 32| 15000000| 1|0.06271944| PASSED
dab_filltree| 32| 15000000| 1|0.08685594| PASSED
Preparing to run test 208. ntuple = 0
dab_filltree2| 0| 5000000| 1|0.07147807| PASSED
dab_filltree2| 1| 5000000| 1|0.74653162| PASSED
Preparing to run test 209. ntuple = 0
dab_monobit2| 12| 65000000| 1|0.86530447| PASSED あまり深い興味はないので、とりあえずPASSEDが並んでいることから、様々なランダムさが基準を満たしているのかな。。。と思います＜テキトウですいません。
で、本題のProcessingでの可視化。
まず、ヒストグラムを描いてみることにしました。/dev/randomから１バイトずつ読み取り、そのデータをfreqという２次元配列にぶっこみます。普通に走らせ続けると画面からすぐにオーバーフローしそうだったので平均値を差し引くことで中央に稜線？を書くような感じにしました。ばらつきが小さければそれぞれの値（０−２５５）の頻度が大きくなっても中央付近に線が１本描かれるだけになるはずです。
import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; FileInputStream fs; InputStreamReader isr; int freq[][]; int gen = 0; void setup() { size(256, 256); clearFreq(); try { fs = new FileInputStream("/dev/random"); } catch (IOException e) { e.printStackTrace(); } frameRate(3000); } void clearFreq() { freq = new int [2][256]; } int getRandomNumber() { int data = 0; try { data = fs.read(); } catch (IOException e) { e.printStackTrace(); } return (data & 0xff); } void draw() { freq[0][(int)random(256)]++; freq[1][getRandomNumber()]++; if (++gen % 1000 != 0) return; fill(255); background(0); text(gen, 0, 20); // if (gen % 1000 == 0) clearFreq(); noFill(); for (int i = 0; i < 2; i++) { if (i == 0) stroke(255, 0, 0); else stroke(0, 255, 0); beginShape(); int y_base = avg(freq[i]); for (int j = 0; j < 256; j++) { vertex(j, height / 2 + y_base - freq[i][j]); //if (freq[i][j] > height) clearFreq(); } endShape(); } } int avg(int[] v) { int sum = 0; for (int i = 0; i < v.length; i++) { sum += v[i]; } return sum / v.length; }
１００万回繰り返した（１００万バイトを取り出して、それぞれのバイト値の頻度を集計した）結果は以下の通りです。縦横２５６ピクセルのウィンドウです。ちなみに赤線がProcessingのrandomメソッドで、緑線が/dev/randomでした。
発生頻度に２５６回程度の差があるように見えますが１００万回の試行に対してなので。。。ほぼ均一と言えるような気はします。でも、randomメソッドの分布もいい感じですね。。。あまり差がありません。実は両方とも同じ仕組みで動いていたりして。。。ちょっとそこまでは追っていません。
分布はほぼ一様として、順列に法則性があるのかないのか？
dieharderじゃないですが、ランダムさを測る指標があるのでしょうけど。。。ま、思いつくところで。
ランダムウォークさせてみました。１バイトなので３６０度を２５６等分して。。。移動した経路がどうなるか？
コードは以下です。
ベタですが、前述のプログラムように実行速度がなかなか出なかったので、なるべく参照する深さを減らしたつもりですが。。。あまり効きませんでした。
import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; FileInputStream fs; InputStreamReader isr; final int BUFF_SIZE = 1000; int gen = 0; float p1x, p1y; float p2x, p2y; float p1x_[] = new float [BUFF_SIZE]; float p1y_[] = new float [BUFF_SIZE]; float p2x_[] = new float [BUFF_SIZE]; float p2y_[] = new float [BUFF_SIZE]; float tbl_x[] = new float [256]; float tbl_y[] = new float [256]; void setup() { fullScreen(); try { fs = new FileInputStream("/dev/random"); } catch (IOException e) { e.printStackTrace(); } p1x = p2x = width / 2.0; p1y = p2y = height / 2.0; makeTbl(); frameRate(3000); background(0); } void makeTbl() { for (int i = 0; i < 256; i++) { tbl_x[i] = cos(TWO_PI / 255 * i); tbl_y[i] = sin(TWO_PI / 255 * i); } } int getRandomNumber() { int data = 0; try { data = fs.read(); } catch (IOException e) { e.printStackTrace(); } return (data & 0xff); } void draw() { int th = (int)random(256); int th2 = getRandomNumber(); int g = gen++ % BUFF_SIZE; p1x += tbl_x[th]; p1y += tbl_y[th]; p1x_[g] = p1x; p1y_[g] = p1y; p2x += tbl_x[th2]; p2y += tbl_y[th2]; p2x_[g] = p2x; p2y_[g] = p2y; if (g != BUFF_SIZE - 1) return; noStroke(); fill(0); rect(0, 0, width, 30); fill(255); text(gen, 0, 20); beginShape(POINTS); stroke(255, 0, 0); for (int i = 0; i < BUFF_SIZE; i++) { vertex(p1x_[i], p1y_[i]); } stroke(0, 255, 0); for (int i = 0; i < BUFF_SIZE; i++) { vertex(p2x_[i], p2y_[i]); } endShape(); }
とりあえず１５万回（歩）試行させた経路が以下です（なお、以下の画像は1920x1200ピクセルで、１歩の最大値は１ピクセルです）。上記と同じく、赤線がProcessingのrandomメソッド。緑線が/dev/randomです。
緑の方が方向性を持ってるような気がしますが。。。プログラムコードの誤りのような気もします。
大きな差があるようには思えませんでした。
/dev/randomは遅いとかで。。。であればrandomメソッドで十分じゃないかな。。。という結論です。
とりあえず。
ああ。。。また脱線してしまった。やることやらなきゃ。
