memorandums

日々のメモです。

/dev/randomをProcessingで可視化してみた件

自作CPUをテーマにしている学生さんと話していたときに、何か独自命令を実装してみようよという話になり、身近なところで乱数生成命令はどうかいな?という話になりました。

ちなみに私は計算機工学は専門外です。

研究室としては成果が出ませんのでいいことではないのですが、就職する子であれば僕が専門外でも自分の興味の持てるテーマを積極的に考えてやってもらってきました。

で、調べてみると、インテルもそうした命令を実装したというエントリーを見つけました。全く的はずれな目標ではなさそう。

本の虫: ハードウェア乱数生成器は信頼できるか

そのエントリーを読むと、/dev/randomという疑似デバイスがあるとか。

Wikipediaによると、以下のような実装になっているそうで。

デバイスドライバその他の情報源から集めた環境ノイズを利用して、真の乱数性を得るのが目的である。

/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から1バイトずつ読み取り、そのデータをfreqという2次元配列にぶっこみます。普通に走らせ続けると画面からすぐにオーバーフローしそうだったので平均値を差し引くことで中央に稜線?を書くような感じにしました。ばらつきが小さければそれぞれの値(0−255)の頻度が大きくなっても中央付近に線が1本描かれるだけになるはずです。

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;
}

100万回繰り返した(100万バイトを取り出して、それぞれのバイト値の頻度を集計した)結果は以下の通りです。縦横256ピクセルのウィンドウです。ちなみに赤線がProcessingのrandomメソッドで、緑線が/dev/randomでした。

f:id:ke_takahashi:20181112184544p:plain

発生頻度に256回程度の差があるように見えますが100万回の試行に対してなので。。。ほぼ均一と言えるような気はします。でも、randomメソッドの分布もいい感じですね。。。あまり差がありません。実は両方とも同じ仕組みで動いていたりして。。。ちょっとそこまでは追っていません。

分布はほぼ一様として、順列に法則性があるのかないのか?

dieharderじゃないですが、ランダムさを測る指標があるのでしょうけど。。。ま、思いつくところで。

ランダムウォークさせてみました。1バイトなので360度を256等分して。。。移動した経路がどうなるか?

コードは以下です。

ベタですが、前述のプログラムように実行速度がなかなか出なかったので、なるべく参照する深さを減らしたつもりですが。。。あまり効きませんでした。

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();
}

とりあえず15万回(歩)試行させた経路が以下です(なお、以下の画像は1920x1200ピクセルで、1歩の最大値は1ピクセルです)。上記と同じく、赤線がProcessingのrandomメソッド。緑線が/dev/randomです。

f:id:ke_takahashi:20181112201657p:plain

緑の方が方向性を持ってるような気がしますが。。。プログラムコードの誤りのような気もします。

大きな差があるようには思えませんでした。

/dev/randomは遅いとかで。。。であればrandomメソッドで十分じゃないかな。。。という結論です。

とりあえず。

ああ。。。また脱線してしまった。やることやらなきゃ。