疑似乱数生成器 spiegel-im-spiegel/mt

no extension

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

  • 従来の様々な生成法の欠点を考慮して設計されています
  • 従来にない長周期, 高次元均等分布を持ちます(周期が $2^{19937}-1$ で、623次元超立方体の中に 均等に分布することが証明されています)
  • 生成速度がかなり速い
  • メモリ効率が良い

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

spiegel-im-spiegel/mtMersenne Twister のオリジナルコード(C/C++)を pure Go で書き直したものである。

check vulns lint status GitHub license GitHub release

spiegel-im-spiegel/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/spiegel-im-spiegel/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.Sourcerand.Rand のソースとして利用するには以下のように記述すればよい。

import (
    "fmt"
    "math/rand"

    "github.com/spiegel-im-spiegel/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/spiegel-im-spiegel/mt"
    "github.com/spiegel-im-spiegel/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/spiegel-im-spiegel/mt"
    "github.com/spiegel-im-spiegel/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 間で共有可能である。

ライセンスについて

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

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

というわけで spiegel-im-spiegel/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/spiegel-im-spiegel/mt"
    "github.com/spiegel-im-spiegel/mt/secure"
)

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

参考図書

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

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

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

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

工学ガール,リサちゃん登場!

reviewed by Spiegel on 2015-04-19 (powered by PA-APIv5)