Haskell
HaskellDay 9

Haskellの乱数事情

More than 3 years have passed since last update.


まえおき

ここ数日触ってるElmが楽し過ぎてHaskellACがギリギリになってしまいました。。。日本語での情報が少ない気もしますし、擬似乱数生成器(pseudo random number generator; PRNG)ライブラリの話で茶を濁したいと思います。

Elmとても楽しいので是非触りましょう!Elm Advent Calendar 2014もまだ枠が空いてる様です!

さて、Haskellerの皆様、乱数はお使いでしょうか?私は殆ど使いません。

……ですが、ゲームや乱択アルゴリズム、シミュレーションなど乱数が必要となるシチュエーションも多いかと思われます。あと、Haskellの利点として挙げられる事も多い、QuickCheckといったランダムテストでも乱数が必要ですね。

Haskellの場合、Haskell98の時点では標準ライブラリとしてPRNGライブラリのAPIが策定されていたのですが、Haskell2010では削除されたため、ユーザーが自分でPRNGライブラリを作成または既存のライブラリから選定する必要があります。

Haskell98標準のrandomパッケージは、1.長くない周期、2.Haskell98由来の古いAPIの制約で内部状態を毎回コピーする、3.そのため遅い、4.CPU時間と現在時間で初期化(ポケモンかな???)など、過去に標準だったため多くの環境で使用出来ると考えられる、という点以外に余りお勧めできる所が有りません。

そこで、本稿ではHaskellのPRNGライブラリについての比較を行なった後、少し暗号論的擬似乱数生成器(cryptographically secure pseudo random number generator; CSPRNG)についても触れたいと思います。


HaskellのPRNGライブラリ

とりあえずざっと検索してみた所、ヒットしたPRNGライブラリはこの位でしょうか(大抵CategoryがMathだけなので凄く検索しにくい)。それぞれ適当に解説していきます。


random

Haskell98標準のPRNGライブラリです。Haskell98ReportではAPIとPRNGの満すべき条件を規定するに留め、実装の詳細については触れていませんが、randomパッケージでは[1]の方法を使用しています。すべてHaskellで実装されています。


random.hs

import System.Random

main :: IO ()
main = do
gen0 <- newStdGen
let (r1, gen1) = random gen0
(r1', _ ) = random gen0 -- 同じgenを使用して同じ型を生成すると結果も同じ
(r2, gen2) = random gen1
(r3, gen3) = randomR (-100, 100) gen2
r4 = randoms gen3 -- 乱数の無限リストを返す
print (r1 :: Int)
print (r1' :: Int)
print (r2 :: Double) -- Doubleの範囲は[0,1)
print (r3 :: Int)
print (take 3 r4 :: [Double])


$ runhaskell examples/random.hs

-140564301203516694
-140564301203516694
0.19977632985837557
-90
[0.4047517803031183,0.2450618611537484,0.5026396495543536]

はい、普通に使えますね。基本的にgenを引数で持ち回して使用します。複数のgenが必要な時(マルチスレッドとか、randomsに入れるとか)はsplitを使用してgenを2つに分けます。


mwc-random

キャリー付き乗算(multiply-with-carry; MWC)の内、lag-256 MWCと呼ばれるバージョンを実装しています。すべてHaskellで実装されています

primitiveパッケージを使用しており、IO/STを共通のコードで使用する事が出来ます。

まずはIOモナドを使用したサンプルを記載します。


mwc-io.hs

import System.Random.MWC

main :: IO ()
main = withSystemRandom . asGenIO $ \gen -> do
uniform gen >>= \i -> print (i :: Int)
uniformR (-100, 100) gen >>= \d -> print (d :: Double)


$ runhaskell examples/mwc-io.hs

-5961215003745553123
6.167462573191315

次にSTモナドを使用したサンプルを記載します。


mwc-st.hs

{-# LANGUAGE NoMonomorphismRestriction #-}

import qualified Data.Vector.Unboxed as U
import Control.Applicative
import Control.Monad.ST(runST)
import System.Random.MWC

-- 毎回同じ値を返す
pureA :: (Int, Double)
pureA = runST $ do
gen <- initialize (U.fromList [4, 8, 15, 16, 23, 42])
(,) <$> uniform gen <*> uniformR (-100, 100) gen

-- Seedを使うことでrandom等のインターフェースの真似事を出来る
pureB :: Seed -> ((Int, Double), Seed)
pureB seed = runST $ do
gen <- restore seed
ret <- (,) <$> uniform gen <*> uniformR (-100, 100) gen
seed' <- save gen
return (ret, seed')

main :: IO ()
main = do
print pureA
seed0 <- createSystemRandom >>= save
let (b0, seed1) = pureB seed0
(b1, _ ) = pureB seed1
print b0
print b1


$ runhaskell examples/mwc-st.hs

(8017236977809806739,75.8981759359263)
(-2290309892113622472,15.327453033603632)
(6768560660450525899,-50.111907886352355)


mersenne-random-pure64

メルセンヌツイスター(mersenne twister; MT)の内、MT19937-64(2004/9/29 version)へのバインディングです。

RandomGen型クラスを使用しrandomパッケージと同じ感じで使用するため例は割愛します。


mersenne-random

ちょっと古い(<1.4)SIMD-oriented Fast Mersenne Twister(SFMT)へのバインディングです。


mersenne.hs

import System.Random.Mersenne

main :: IO ()
main = do
gen <- getStdGen
random gen >>= \i -> print (i :: Int)
randoms gen >>= \i -> print (take 3 i :: [Double])


$ runhaskell examples/mersenne.hs

-619718723374138645
[0.4551769174016148,0.30478929015057205,0.1370638521698185]


tf-random

[2]の方法を使用しています。内部で使用しているthreefish-256部分はCで、その他の部分はHaskellで書かれています。

RandomGen型クラスを使用しrandomパッケージと同じ感じで使用するため例は割愛します。


xorshift

32/64bitのxorshiftのHaskell実装です。

RandomGen型クラスを使用しrandomパッケージと同じ感じで使用するため例は割愛します。


特徴

以上の各PRNGライブラリの特徴を表にしておきます。

ライブラリ
アルゴリズム
周期
Haskell
初期化
Pure
ST
IO

random
[1]
~2.30584e18

CPU時間/現在時間

-
-

mwc-random
lag-256 MWC
2^8222

/dev/urandom(無ければCPU時間/現在時間)
1


mersenne-random-pure64
MT19937-64
2^19937 - 1
×
CPU時間/現在時間

-
-

mersenne-random
SFMT
2^19937 - 1
×
CPU時間/現在時間
×
×

tf-random
[2]
?
×
/dev/urandom(無ければCPU時間/現在時間)

-
-

xorshift
xorshift
2^32 - 1 or 2^64 - 1

現在時間

-
-


  • Haskell: 純Haskell実装か否か

  • 初期化: newSystemGenなどの関数で内部状態を初期化する時に何を使用して初期化するか

  • Pure: 純粋なインターフェース

  • ST: STRefを使用したインターフェース。純粋なインターフェースが有れば不要なので-とした。

  • IO: IORefを使用したインターフェース。純粋なインターフェースが有れば不要なので-とした。

1: 一旦Seedに変換すれば可能。サンプルコード参照


速度比較

特にモンテカルロ法など大量の乱数を必要とする手法を用いる時に、乱数の生成速度が重要となります。

1000個の64bit-Intの生成時間についてベンチマークを取っておいたので参考になればと思います。

全体

速いもののみ

mersenne-random-pure64を含む、RandonGen型クラスを使用するものは毎回内部状態をコピーしているのでかなり遅いことが見て取れます(つらい)。

mersenne-randomは内部状態を持ち回すので高速ですが、IOモナド内でしか使用することが出来ません(ちょっとつらい)。

mwc-randomは全てHaskellで実装されているにも関わらず、かなり高速(1を1000回足すだけのbaselineと比較して2.3倍程度の時間で済んでいる)です。スゴイ!


どれを使えば良いか

PRNGについて余り詳しくない&&状況によって必要とされるものも異なるのでアレですが、とりあえずmwc-randomを使っておけば良いのではないでしょうか。

mwc-randomには一様乱数以外にも様々な分布の乱数を生成する機能もあり、そちらも場合によっては便利かと思います。


でもメルセンヌツイスター使いたい

と思いまして、今風な(mwc-randomのインターフェースをパクったに合わせた)SFMTバインディングを作りました!よろしければお使い下さい。

ライブラリ
アルゴリズム
周期
Haskell
初期化
Pure
ST
IO

sfmt
SFMT(1.4.1)
2^19937 - 1
×
entropy(後述)
1


ベンチマーク


CSPRNGについて

さて、ここまではPRNGの話。ここから少しCSPRNGの話に移りましょう。更に詳しくない上に特に選択肢が広い訳でも無いので列挙するだけになりますがご容赦ください。

Haskellで暗号論的な乱数を扱うライブラリはこれら位かと思われます。


entropy/crypto-random

*nixの/dev/urandomやWindowsのCryptoAPI等から乱数を取得する為のライブラリです。プラットフォーム毎のコード書くの苦痛でしかないので/dev/urandomとか直接触る必要があるならこれらを使った方が幸せになれるかと思います。


cprng-aes

aesを使用して 暗号論的擬似乱数生成器 - 暗号プリミティブに基づく設計 - Wikipediaの方法でCSPRNGを構成しています。crypto-randomのAPIで初期状態を生成し、1MB毎にre-seedを行っております。

yesodが標準でセッション管理に使用してるclientsession等で使用されています。


threefish

触った事無いので説明は割愛させていただきます。スミマセン。。。こんなのも有るよーって事で。。。


おわりに

すごい尻すぼみですみません。。。

軽い気持ちでPRNGの記事でも書こうとした結果がコレだよ!!!


参考文献

[1] Pierre L'Ecuyer, Efficient and portable combined random number generators, Comm ACM, 31(6), Jun 1988, pp742-749.

[2] Koen Claessen and Michał H. Pałka, Splittable Pseudorandom Number Generators Using Cryptographic Hashing by Claessen, Haskell Symposium 2013, Sep 2013