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)

結果は

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にも搭載される予定ですが、これの乱数生成アルゴリズムも他とは異なる可能性があります。いつかこれらの解析もしたいですね。(投げやり)

~~全然はじめましてではない~~

自己紹介

名前

Tosuke

本名を魔改造してできた文字列です。特に意味はありません。(どうやらとすけは輪投げという意味らしい)

生息場所

主にTwitterに生息しています。 Miiverseにもたまに出没しています。某限界SNSでも姿を確認できると思います。

できること

D言語を書いていましたが、色々あって最近はJavaScriptやTypeScriptやC#を書いています。 D言語を書いていた流れでC言語やC++(ほんの少し、読める程度)、Rustもできます。 Pythonも一応経験あります。(文法やった程度)

特殊なところではSmileBasicを書きます。

職業

宮城県の某高校の学生です。(2017年現在)

ブログを始めた理由

上で書いた通り、私はTwitterによく出没しています。その中で、その時々に感じたことや知見をTwitterに書くことで流れてしまい、書いた本人ですらそれを再び見ることがないということがかなり多くありました。ブログという形で書きとめておくことはそのような問題に対する有効な解決手段だと思っています。

とはいうものの、私はブログを立ちあげることを長らく面倒くさがっていました。しかし、私はHexoを使えば簡単にブログを立ち上げることができることを知り、ブログを立ち上げましたが、放置してたらぶっ壊れたのではてなブログにしました(markdownで書けて数式も使えてよさそうだったので)

書こうと思っていること

技術的な知見
ポエム
ただのメモ

要はチラシの裏案件です。おそらく半分くらいは全く役に立たない内容になると思いますが、つらつら書いていこうと思います。

Tosuke’s diary

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

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