Haskell:RandomGen减少了一半的值

Question

我正在编写一个基于xorshift的简单确定性随机数生成器.这里的目标不是获得加密安全或统计上完美(伪)的随机数生成器,而是能够在编程语言中实现相同的半随机数确定性序列.

我的Haskell程序如下所示:

{-# LANGUAGE GeneralizedNewtypeDeriving #-}
module SimpleRNG where

import Data.Word (Word32)
import Data.Bits (xor, shift)
import System.Random (RandomGen(..))
import Control.Arrow

(|>) :: a -> (a -> b) -> b
(|>) x f = f x
infixl 0 |>

newtype SeedState = SeedState Word32
  deriving (Eq, Show, Enum, Bounded)

seed :: Integral a => a -> SeedState
seed = SeedState . fromIntegral

rand_r :: SeedState -> (Word32, SeedState)
rand_r (SeedState num) = (res, SeedState res)
  where
    res = num
      |> xorshift 13
      |> xorshift (-17)
      |> xorshift 5
    xorshift :: Int -> Word32 -> Word32
    xorshift amount x = x `xor` (shift x amount)

instance RandomGen SeedState where
  next seed_state = (first fromIntegral) $ rand_r seed_state
    where
  genRange seed_state = (fromEnum (minBound `asTypeOf` seed_state),
                fromEnum (maxBound `asTypeOf` seed_state))

  split seed_state@(SeedState num) =  (seed_state', inverted_seed_state')
    where
      (_, seed_state') = next seed_state
      (_, inverted_seed_state') = next inverted_seed_state
      inverted_seed_state = SeedState (maxBound - num)

现在,由于某种原因,在运行时

take 10 $ System.Random.randoms (seed 42) :: [Word32]

与以下Python程序的输出相比,它只返回'奇数'结果:

class SeedState(object):
    def __init__(self, seed = 42):
        self.data = seed

def rand_r(rng_state):
    num = rng_state.data
    num ^= (num << 13) % (2 ** 32)
    num ^= (num >> 17) % (2 ** 32)
    num ^= (num << 5) % (2 ** 32)
    rng_state.data = num
    return num


__global_rng_state = SeedState(42)

def rand():
    global __global_rng_state
    return rand_r(__global_rng_state)

def seed(seed):
    global __global_rng_state
    __global_rng_state = SeedState(seed)

if __name__ == '__main__':
    for x in range(0, 10):
        print(rand())

看起来System.Random模块的内部结构与生成器的返回结果做了一些奇怪的诡计(调用

map fst $ take 10 $ iterate (\(_, rng) -> rand_r rng) (rand_r $ seed 42)

给出了我期望的结果.

这很奇怪,因为生成器返回的类型已经是a Word32,所以它可以/应该在未发生任何重映射的情况下直接传递.

这里发生了什么,有没有办法将这个xorshift-generator插入到System.Random中,返回相同的结果？

Answer 1

这与System.Random.randoms的行为有关,它反复应用于randoma RandomGen,而不是next.

class Random a where
    ...
    random :: (RandomGen g) => g -> (a, g)

该Random班是什么,可以重复使用RandomGen在不同的枚举实例,该实例Word32(以及几乎所有其他类型)被定义为

instance Random Word32     where randomR = randomIvalIntegral; random = randomBounded

randomBounded只是调用randomR,所以行为random由`决定

 randomIvalIntegral (l,h) = randomIvalInteger (toInteger l, toInteger h)

randomIvalInteger是一个有趣的功能,你可以在这里阅读来源.它实际上导致了您的问题,因为该函数将根据生成器的范围和生成的范围丢弃一定数量的中间值.

要获得所需的值,您只需要使用next- 最简单的方法就是定义

randoms' g = x : (randoms' g') where (x, g') = next g