Python で乱数

Python で乱数

〜 Python で疑似乱数を生成〜

2022-10-10 作成福島

乱数とは

乱数とは、でたらめに現れる数のことです。
何かを決めるとき、自分では無い他の誰かに決めてほしいことが多々あります。

トランプをかき混ぜる時は誰かの意思が働かないほうが望ましいし、じゃんけんでは相手の手が分かっているとつまらなくなります。
ギャンブルにおいては、予め答えが分かっていたら勝負にならない上に、場合によっては罪に問われることもあります。

また、煙や水の動きなど、多すぎる不確定な数値をすべて人間の手によって決定するのは現実的ではありません。

そんな時に便利なのが「乱数」です。
自分の意志とは関係なく、でたらめに現れる数が答えを決めてくれます。

コンピュータにおける乱数

コンピュータにおける乱数は、実は乱数ではありません。
正しくは「疑似乱数」と呼び、一見して乱数に見える数字の羅列を計算で生成して、本物の乱数の代用にしています。
このため、アルゴリズムと初期値さえ同じであれば、同じ結果を得ることができます。

本物の乱数は物理法則に従うので、同じ結果を得ることはできません。
よく、「空中に放り投げたコインが着地した面の向き」や「サイコロを振った時の出目(でめ)」として使われます。
コインやサイコロを投げた時に全く同じ環境を再現することが物理的にできないことは理解できるでしょう。

環境が変わっても同じ乱数列を

最近のプログラミング言語には、ほぼすべてに高機能な乱数生成器が内蔵されており、内蔵でなくても付録として付いていたりします。
また、Linux の様に高機能な OS には乱数生成器が内蔵されており、気軽に利用できるようになっています。
アプリケーションを作るときはプログラムからこれらを使用すれば良いので、通常は乱数生成器そのものを作成する必要はありません。

Python では「n = random.randint(0, 9)」の記述で n に 0～9 の乱数を求めることができます。

便利な機能ですが、欠点もあります。
プログラミング言語や OS に内蔵されている乱数発生器は、それぞれ独自のアルゴリズムによって実装されているため、環境が異なると同じ乱数列を発生させることができません。
また、アルゴリズムが同一でも実数を返す形式の乱数発生器だと、小数の丸め誤差により値が同一になりません。

具体的には、乱数をキーにした暗号器で暗号化した文書を他の言語で復号化できなかったり、
シミュレーションの結果が、異なる OS で同じ再現にならないことになります。

ここでは乱数発生器を作成し、異なる環境でも同じ乱数列を生成させることにより、同じ実行結果を得られるようにします。

疑似乱数のアルゴリズム

ここでは、Xorshift という手法の中から 128bit 版の xorshift128() を実装します。
これは周期が 2⁹⁶-1 になる (らしい^*1) のです。
^*1すみません、ちゃんと証明していません。

疑似乱数の周期とは、生成した数字と同じパターンが次に現れるまでの回数のことを指します。
例えば、
1, 3, 2 , 1, 3, 2 , 1, 3, 2 , 1, 3, 2 , ···
であれば 3、
2, 13, 3, 11, 7 , 2, 13, 3, 11, 7 , 2, 13, 3, 11, 7 , ···
なら 5 です。

計算で疑似的に乱数を生成するので、どうしても周期が現れてしまいます。
2⁹⁶-1 は想像しにくいので 10 進数に直すと、

95 ≦ log₂X ＜ 96
95 ≦ log₁₀X / log₁₀2 ＜ 96
95 ≦ log₁₀X / 0.3010 ＜ 96
28.595 ≦ log₁₀X ＜ 28.896
2⁹⁶-1 = 10^{28.595～28.895}-1

となり、10 進数に直しても想像しにくいほど長い周期をもつということが分かりました。(10²⁸ は 1 穣(じょう))
(1 秒間に 100 億回の乱数を生成すると仮定して約 2,500 億年必要。えーと、ビッグバン説が正しいとして、宇宙の誕生って 138 億年前だっけ)

xorshift128 には制約があって、内部的に符号なし 32bit の整数演算が出来なければなりません。
Python は符号なし 32bit の整数演算を直接することはできませんが無限桁の整数を扱えるので、
これを使って符号なし 32bit の整数演算を実現します。(ちなみに、小数は 15 桁まで扱える)

乱数発生器の実装

アルゴリズムは xorshift128() の、そのまんまパクリです。
(符号なし 32bit 演算が前提なので、直接に負数や実数を扱うことは出来ません)

# 乱数発生器
def Xorshift128(state):
    t = state[3] & 0xFFFFFFFF   # fool proof^*2
    s = state[0] & 0xFFFFFFFF   # fool proof^*2
    state[3] = state[2]
    state[2] = state[1]
    state[1] = s
    t = (t ^ t << 11) & 0xFFFFFFFF    # t ^= t << 11      // unsigned 32bit
    t ^= t >> 8
    state[0] = t ^ s ^ (s >> 19)
    return state


xorshift_state = [123456789, 0, 0, 0]   # すべてが 0 にならないように初期化する。
for i in range(100):                    # 10²⁹ 個も確認してられないので、とりあえず 100 個。
    xorshift_state = Xorshift128(xorshift_state)
    n = xorshift_state[0]
    print(n)    # 乱数を表示する。(実際に使うときは % であまりを求める^*3)

^*2この 2 箇所の n & 0xFFFFFFFF は、人間が初期値として n < 2³² を暗算するのが苦手のため記述している。本来は不要。
^*3例えば 0～9 の値を求めるには「n % 10」と記述する。

実行結果
このプログラムと十進 BASIC 版の実行結果が同一になることを確認してください。

おまけ

乱数を使いやすくするために、公差が 1 の等差数列をかき混ぜる関数 DustShuffle を掲載します。(Dust: Richard Durstenfeld)
ダステンフェルドのシャッフルは、本来は要素を限定しないのですが、この関数では等差数列としています。
実行結果の数列を添え字として使用することで、本来の目的を果たせるように作ってあります。
DustShuffle の中から呼び出している関数 Xorshift128 は上記と同じものです。
# 乱数発生器
def Xorshift128(state):
    t = state[3] & 0xFFFFFFFF   # fool proof
    s = state[0] & 0xFFFFFFFF   # fool proof
    state[3] = state[2]
    state[2] = state[1]
    state[1] = s
    t = (t ^ t << 11) & 0xFFFFFFFF    # t ^= t << 11      // unsigned 32bit
    t ^= t >> 8
    state[0] = t ^ s ^ (s >> 19)
    return state


# ダステンフェルドのシャッフル
def DustShuffle(numLen):
    global xorshift_state
    idx = list(range(numLen))
    for i in reversed(range(numLen)):
        xorshift_state = Xorshift128(xorshift_state)
        p = xorshift_state[0] % (i + 1)
        n = idx[p]
        idx[p] = idx[i]
        idx[i] = n
    return idx


xorshift_state = [123456789, 0, 0, 0]   # すべてが 0 にならないように初期化する。
idx = DustShuffle(8)
print(idx)
実行結果
[5, 3, 7, 4, 0, 2, 1, 6]