Tosuke’s diary

役に立(つ/たない)技術情報やポエム

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

miiverse.nintendo.net プチコン界隈ではこの投稿が衝撃をもたらしたとかもたらしてないとかという話ですが、今回はこの解析の方法について書きたいと思います。 なお、この解析結果はプチコン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とすると、

{ \displaystyle
X=K\times n+R(K)
} (nは整数)

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

{\displaystyle \left\{
\begin{array}{@{}1}
X=0x7FFFFFFF\times n+397858342 \\
X=0x7FFFFFFE\times n+397858343
\end{array}
\right.
}

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

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

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

あとがき

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