Arduinoで乱数のランダムネスを評価する方法の考察

以前書いた記事「お化け探知機「化けたん」の再発明を目指して！」シリーズでハードウエア乱数発生装置を作ってその中で乱数の「偏り」や「秩序ある目」の評価についていろいろ考えていましたが、一部の「秩序ある目」を「周期性」と読み替えてArdionoで見つける方法を思いついたので報告します。

前提

乱数はビット列としてunsigned long intに記録されており、新しい乱数ビットは<<1 により一番古い乱数ビットがシフトアウトされて一番右側に新しいビットが挿入されます。

（１）乱数の偏りについて

単純にHIGHになっているビットの数を数えて期待値を引きます。Arduinoのlong intは32ビットなのでpopcountでHIGHになっているビットの数の合計から16を引きます。

（２）周期性について

周期性があるということは同じパターンが何度も出現することを意味しているので、ビット列をシフトして合致した目の数を数えることで周期性を評価します。
例えば 01 という周期２のパターンが32ビット分続くときは
01010101010101010101010101010101
となります。

これを <<2 として2ビット分ずらしてXORすると
01010101010101010101010101010101 元のビット列
01010101010101010101010101010100 <<2
00000000000000000000000000000001 XOR
右の2ビットに用はないので >>2 してやると
000000000000000000000000000000
となり、ミスマッチがないので0が30個出現します。

一方、周期性が全くない場合にはミスマッチを意味する1の数の期待値は (32-周期)/2 となり、周期は2なので期待値は (32-2)/2 = 15 となります。
01が16回出現した上の例の場合、期待値とのずれは 0 - 15 = -15 となります。この値を周期性スコアとしてみました。

ここまでを周期1から10までのスコアを計算するプログラムに直すと以下のように書けます。
本当は順列組み合わせとかを考慮して確率計算をするともっといいのですが、今回はここまでとします。

  union {
    unsigned long int sum=0;
    unsigned char div[4];
  } data;

  union {
    unsigned long int sum=0;
    unsigned char div[4];
  } c;

void main(void){
  // 電圧の偶奇性から乱数を発生
  sensorValue=readSensorValue();
  data.sum <<=1; data.div[0] |=sensorValue & 1; // 偶奇性をメモリに登録

  // 周期性解析
  for(dim=0; dim<=10; dim++){
    if(dim==0){ // （１）dim==0 の時は単なる偏りを解析
      score=all_popcount(data.div)-16;
    }else{ // （２）dim分だけシフトさせた後XORでHIGH LOWが一致するものをカウント
      a=data.sum;
      b=(data.sum << dim);
      c.sum=((a ^ b) >> dim);
      score=(32-dim-all_popcount(c.div))-(32-dim)/2;
    }
    Serial.print(score*1);
    Serial.print(", ");
  }
  Serial.print("\n");
}

char all_popcount(unsigned char *data){ // __builtin_popcount は8ビット分しかカウントしてくれないので1バイト分ずつ分割して和を算出
  char count=0;
  count+=__builtin_popcount(data[0]);
  count+=__builtin_popcount(data[1]);
  count+=__builtin_popcount(data[2]);
  count+=__builtin_popcount(data[3]);
  return count;  
}

本当は「化けたんの再発明」シリーズでソースを全部公開したいのですが、Qiitaにそぐわない内容も含まれてしまうため、ここでは乱数の周期性を評価する部分だけ抜粋してご紹介しました。