Random Bool

すごいHaskell P.340 に State モナドを使って乱数の生成をきれいに書く例が載っている。

import System.Random
import Control.Monad.State

randomSt :: (RandomGen g, Random a) => State g a
randomSt = state random

threeConins :: State StdGen (Bool, Bool, Bool)
threeConins = do
    a <- randomSt
    b <- randomSt
    c <- randomSt
    return (a, b, c)

これを何度か実行してみる。

*Main> runState threeConins $ mkStdGen 0
((True,True,True),1346387765 2103410263)
*Main> runState threeConins $ mkStdGen 1
((True,False,True),545291967 2103410263)
*Main> runState threeConins $ mkStdGen 2
((True,True,False),1891679732 2103410263)
*Main> runState threeConins $ mkStdGen 3
((True,True,False),1090583934 2103410263)
*Main> runState threeConins $ mkStdGen 4
((True,False,False),289488136 2103410263)

ランダムな値が返ってきているが、先頭の値が毎回 True になっている。先頭の値がはじめて False になるシードの値を調べてみたくなった。調べる為に以下の関数を作成した。

headTrueSeeds :: [Int]
headTrueSeeds = takeWhile (fst3 . (evalState threeConins) . mkStdGen) [0..]
  where
    fst3 (a, _, _) = a

実行してみる。

*Main> last headTrueSeeds
53667

53667 までずっと先頭がTrue のパターンが続いている。というわけで、先頭の値がはじめて False になるシードの値は 53668。

どうしてこうなるかを調べてみる。

System.Random

Bool のランダム値は以下のように生成される。random を適用する g が (mkStdGen 53668) の時にはじめて x が 0 になる （上で調べた結果から）。

instance Random Bool where
  randomR (a,b) g =
      case (randomIvalInteger (bool2Int a, bool2Int b) g) of
        (x, g') -> (int2Bool x, g')
       where
         bool2Int :: Bool -> Integer
         bool2Int False = 0
         bool2Int True  = 1

     int2Bool :: Int -> Bool
     int2Bool 0 = False
     int2Bool _ = True

  random g    = randomR (minBound,maxBound) g

ということは x を決めている randomIvalInteger に秘密がありそうなので、調べていくとその中で使用している next 関数が重要な役割を持っているようだ。以下は next の定義。

instance RandomGen StdGen where
  next  = stdNext

stdNext :: StdGen -> (Int, StdGen)
-- Returns values in the range stdRange
stdNext (StdGen s1 s2) = (fromIntegral z', StdGen s1'' s2'')
    where   z'   = if z < 1 then z + 2147483562 else z
        z    = s1'' - s2''

        k    = s1 `quot` 53668
        s1'  = 40014 * (s1 - k * 53668) - k * 12211
        s1'' = if s1' < 0 then s1' + 2147483563 else s1'

        k'   = s2 `quot` 52774
        s2'  = 40692 * (s2 - k' * 52774) - k' * 3791
        s2'' = if s2' < 0 then s2' + 2147483399 else s2'

53668 という数がある。random 値を生成した結果が False になる為には、z' が 0 にならなければいけない。その為には z が 0 でなければならない。その他には s1'' と　s2'' が等しくならなければいけない。その為には ... ...

全て追ったわけではないのだが、ここの 53668 が影響しているのは確かだろう（多分ね〜）。