疑似乱数生成器 goark/mt

Mersenne Twister とは松本眞・西村拓士両氏によって1996年に発表された擬似乱数生成アルゴリズムである。他の擬似乱数生成アルゴリズムと比べて以下の特徴があるそうだ。

従来の様々な生成法の欠点を考慮して設計されています

従来にない長周期, 高次元均等分布を持ちます（周期が $2^{19937}-1$ で、623次元超立方体の中に均等に分布することが証明されています）

生成速度がかなり速い

メモリ効率が良い

Mersenne Twister とは?より

特に2番目が重要で，モンテカルロ法などの科学技術計算に向いている。 Ruby などの一部のプログラミング言語では標準の疑似乱数生成器として組み込まれているらしい。

goark/mt は Mersenne Twister のオリジナルコード（C/C++）を pure Go で書き直したものである。

goark/mt の特徴は以下の通り。

math/rand 互換で rand.Rand のソースとして利用できる
並行的に安全（concurrency safe）な構成にできる（mt.PRNG 型を利用した場合）

mt/mt19937.Source の機能

mt/mt19937 パッケージは 64bit版 Mersenne Twister を元に pure Go で書き直したものである。

mt/mt19937.Source はそのまま疑似乱数生成器として使える。たとえば以下のように記述する。

import (
    "fmt"

    "github.com/goark/mt/mt19937"
)

fmt.Println(mt19937.New(19650218).Uint64())
//Output:
//13735441942630277712

提供するメソッドは以下の通り。

メソッド	機能
`Source.Seed(int64)`	乱数のシードをセットする
`Source.SeedArray([]uint64)`	乱数のシード（配列）をセットする
`Source.Uint64() uint64`	乱数として範囲 $[0, 2^{64}-1]$ の整数値を生成する
`Source.Int63() int64`	乱数として範囲 $[0, 2^{63}-1]$ の整数値を生成する
`Source.Real(int) float64`	乱数として浮動小数点数値を生成する

Source.Real() 関数の引数による乱数の出力範囲は以下の通り。

引数	生成範囲
1	範囲 $[0, 1)$ の浮動小数点数値
2	範囲 $(0, 1)$ の浮動小数点数値
上記以外	範囲 $[0, 1]$ の浮動小数点数値

なお mt/mt19937.Source は並行的に安全ではないので goroutine 間でインスタンスを共有できない。

math/rand と組み合わせる

mt/mt19937.Source を rand.Rand のソースとして利用するには以下のように記述すればよい。

import (
    "fmt"
    "math/rand"

    "github.com/goark/mt/mt19937"
)

fmt.Println(rand.New(mt19937.New(19650218)).Uint64())
//Output:
//13735441942630277712

これで rand.Rand が提供するメソッドはすべて使える。ただし rand.Rand 自体も並行的に安全ではないので，取り扱いにはやはり注意が必要である。

mt.PRNG と組み合わせる

mt/mt19937.Source 型を mt.PRNG 型と組み合わせることで並行的に安全な構成にできる。たとえばこんな感じに記述できる。

package main

import (
    "sync"
    "time"

    "github.com/goark/mt"
    "github.com/goark/mt/mt19937"
)

func main() {
    wg := sync.WaitGroup{}
    prng := mt.New(mt19937.New(time.Now().UnixNano()))
    for i := 0; i < 1000; i++ {
        wg.Add(1)
        go func() {
            defer wg.Done()
            for i := 0; i < 10000; i++ {
                prng.Uint64()
            }
        }()
    }
    wg.Wait()
}

mt.PRNG 型は mt/mt19937.Source のラッパーになっていて rand.Rand と組み合わせることも可能だが， rand.Rand の内部構造の問題で並行的に安全にならない。ご注意を。

io.Reader 互換の疑似乱数生成器

mt.PRNG のインスタンスから mt.Reader 型のインスタンスを生成できる。こんな感じに記述できる。

package main

import (
    "fmt"
    "sync"
    "time"

    "github.com/goark/mt"
    "github.com/goark/mt/mt19937"
)

func main() {
    wg := sync.WaitGroup{}
    prng := mt.New(mt19937.New(time.Now().UnixNano()))
    for i := 0; i < 1000; i++ {
        wg.Add(1)
        go func() {
            defer wg.Done()
            r := prng.NewReader()
            buf := [8]byte{}
            for i := 0; i < 10000; i++ {
                ct , err := r.Read(buf[:])
                if err != nil {
                    return
                }
                fmt.Println(binary.LittleEndian.Uint64(buf[:ct]))
            }
        }()
    }
    wg.Wait()
}

mt.Reader 型は io.Reader インタフェースと互換性がある。また mt.Reader インスタンスも並行的に安全なので goroutine 間で共有可能である。

ライセンスについて

goark/mt は MIT ライセンスで提供している。

オリジナルの Mersenne Twister コードは GPL または BSD ライセンスで提供されているが MIT ライセンスに書き換えてもいいらしい。

Mersenne Twisterの商業利用について

というわけで goark/mt は MIT ライセンスで提供することにした。ご利用はお気軽に。

【おまけ】 secure.Source について

暗号処理などで使われる crypto/rand 標準パッケージを math/rand 標準パッケージのソースとして使うための mt/secure サブパッケージを作った。今回追加した secure.Source 型は以下のメソッドを持つ。

メソッド	機能
`Source.Seed(int64)`	何もしないダミー・メソッド
`Source.SeedArray([]uint64)`	何もしないダミー・メソッド
`Source.Read([]byte) (int, error)`	オクテット単位で乱数を生成する（`io.Reader` 互換）
`Source.Uint64() uint64`	乱数として範囲 $[0, 2^{64}-1]$ の整数値を生成する
`Source.Int63() int64`	乱数として範囲 $[0, 2^{63}-1]$ の整数値を生成する
`Source.Real(int) float64`	乱数として浮動小数点数値を生成する

これで rand.Source / rand.Source64 および mt.Source として rand.Rand 型や mt.PRNG 型の機能を利用することができる。

//go:build run
// +build run

package main

import (
    "fmt"
    "math/rand"

    "github.com/goark/mt"
    "github.com/goark/mt/secure"
)

func main() {
    fmt.Println(rand.New(secure.Source{}).Uint64())
    fmt.Println(mt.New(secure.Source{}).Uint64())
}

参考図書

プログラミング言語Go: アラン・ドノバン (著), ブライアン・カーニハン (著), 柴田芳樹 (著); 丸善出版 2016-06-20 (Release 2021-07-13); Kindle版; B099928SJD (ASIN); 評価

Kindle 版出た！一部内容が古びてしまったが，この本は Go 言語の教科書と言ってもいいだろう。感想はこちら。

reviewed by Spiegel on 2021-05-22 (powered by PA-APIv5)

数学ガール／乱択アルゴリズム: 結城浩 (著); SBクリエイティブ 2011-02-25 (Release 2014-03-12); Kindle版; B00I8AT1FO (ASIN); 評価

工学ガール，リサちゃん登場！