プチコン3号乱数解析の話

なお、この解析結果はプチコン3号限定です。(プチコンBIGはまた別の乱数生成アルゴリズムを採用しているらしい)

乱数の内部実装を予測する

なぜ？

SmileBasicにおいて乱数を取得する方法は、 0からK-1までの乱数を生成するRND(K)と、0から1までの乱数を生成するRNDF()があります。 つまり、プチコン内から直接これらの関数の内部で使用されている"生"の乱数を取得する方法はありません。 そのため、乱数生成アルゴリズムを知るには、これらの関数の実装を予測し、"生"の乱数を計算する必要があります。

予想

とりあえず、実装が簡単そうなRNDF()について予想してみましょう 。

double RNDF() {
  return raw_rand() / RND_MAX;
} 

ここではraw_rand()は0からRND_MAXまでの整数の乱数を返す関数とします。 RNDF()の仕様から考えて、これ以外の実装はあまり考えられないでしょう。

次はRND(K)です。 これは、複数の実装が考えられます。 1つ目はRNDF()を内部で利用する方法です。

int RND(int K) {
  return (int)( RNDF() * K );
} 

RNDF()の範囲を拡大する方法ですね。

2つ目はraw_rand()の余りを取る方法です。

int RND(int K) {
  return raw_rand() % K
} 

raw_rand()のアルゴリズムが線形合同法だとプログラマー格付けチェックに引っかかるあれですね。

実験

次のコードを使います。

RANDOMIZE 0,1
?"RNDF",RNDF()

RANDOMIZE 0,1
?"RND ",RND(&H7FFFFFFF)/&H7FFFFFFF

RANDOMIZE命令を使って乱数のシード値を1に固定しています。 もしRND(K)の実装が内部でRNDF()を利用する実装の場合、RND(K)の値をKで割ることによってRNDF()に近い値が得られると考えられます。 では実行してみましょう！

RNDF 0.59263361
RND 0.18526723

2つの値が大きく異なっています。

結果

この結果からRND(K)とRNDF()の実装を予測することができます。

int RND(int K) {
  return raw_rand() % K
} 

double RNDF() {
  return raw_rand() / RND_MAX;
} 

"生"の乱数値を計算する

乱数関数の実装を知ることができたので、"生"の乱数値を計算できます。 次のコードを使います。

DEF R(K)
 RANDOMIZE 0,1
 return RND(K)
END

?R(&H7FFFFFFF)
?R(&H7FFFFFFE)
?R(&H7FFFFFFD)
?R(&H7FFFFFFC)

結果は

397858342
397858343
397858344
397858345

R(K)に渡す値を1減らすたびに結果が1増えていて、規則性を感じますね。 R(K)は"生"の乱数の値をKで割った余りなので、この時の"生"の乱数をXとすると、

(nは整数)

と表すことができます。 これに実際の数字を代入してみましょう。(nは変化しないと仮定します。)

これを解くと、 より、シード値が1のときの"生"の乱数は2545341989であると考えられます。

乱数生成アルゴリズムを推測する

一口に乱数生成アルゴリズムといっても様々な種類があります。 それらについてより深く知るためにGoogle先生の力を借りましょう。 一瞬で答えが出てしまいました。 このことから、プチコン3号の乱数生成アルゴリズムはTiny Mersenne Twisterであるということがわかります！

あとがき

最初にも書きましたが、プチコンBIGの乱数生成アルゴリズムはプチコン3号とは違います。 また、SmileBasicはPasocomMiniにも搭載される予定ですが、これの乱数生成アルゴリズムも他とは異なる可能性があります。 いつかこれらの解析もしたいですね。(投げやり)