是否可以统一产生一个随机的无限斑点？

发布于 2025-01-19 09:50:23 字数 1248 浏览 2 评论 0原文

我尝试构建一个 RNG，它在 3 个项目中均匀随机选择。因为，常见的习惯用法（例如 C 的 rand() % 3）很容易出现模偏差，因此不统一。

根据可接受性的概念，我的想法是统一生成随机无限位串，并通过函数映射它。以下陈述应满足：

函数对于几乎所有输入都停止（这个“几乎所有”是测度论中一个明确定义的概念）
这 3 个项目的诱导概率分布是均匀的

因此，我的代码草图是在 Haskell 中：

import Data.Word

import System.Random

infixr 5 :!

data InfWord64 = Word64 :! InfWord64

execute :: (InfWord64 -> a) -> IO a
execute f = do
    let getWordString = do
        headWord <- randomIO
        tailWords <- getWordString
        pure (headWord :! tailWords)
    fmap f getWordString

randomOrderingMap :: InfWord64 -> Ordering
randomOrderingMap (headWord :! tailWords)
  | headWord < 0x5555555555555555 = LT
  | 0x5555555555555555 < headWord && headWord < 0xAAAAAAAAAAAAAAAA = EQ
  | 0xAAAAAAAAAAAAAAAA < headWord = GT
  | otherwise = randomOrderingMap tailWords

randomOrdering :: IO Ordering
randomOrdering = execute randomOrderingMap

但它不能正常工作。似乎 execute 对于每个输入都会陷入无限循环。看起来单子语句 headWord <- randomIO 将被无限执行。

我需要某种惰性IO，但它不存在是有充分理由的。惰性 ST RealWorld 是一种替代方案，但当 random 包仅支持严格的 ST 时，我看不到任何使用它的方法。那么解决方法是什么呢？

原文

I tried to build an RNG that uniformly randomly chooses amongst 3 items. Because, the common idiom (something like C's rand() % 3) is prone to modulo bias, and thus not uniform.

As per the notion of admissibility, my idea was to uniformly generate a random infinite bitstring, and map it through a function. The following statements shall satisfy:

The function halts for almost all inputs (This "almost all" is a well-defined notion in measure theory)
The induced probability distribution over the 3 items is uniform

As such, my sketch of code was, in Haskell:

import Data.Word

import System.Random

infixr 5 :!

data InfWord64 = Word64 :! InfWord64

execute :: (InfWord64 -> a) -> IO a
execute f = do
    let getWordString = do
        headWord <- randomIO
        tailWords <- getWordString
        pure (headWord :! tailWords)
    fmap f getWordString

randomOrderingMap :: InfWord64 -> Ordering
randomOrderingMap (headWord :! tailWords)
  | headWord < 0x5555555555555555 = LT
  | 0x5555555555555555 < headWord && headWord < 0xAAAAAAAAAAAAAAAA = EQ
  | 0xAAAAAAAAAAAAAAAA < headWord = GT
  | otherwise = randomOrderingMap tailWords

randomOrdering :: IO Ordering
randomOrdering = execute randomOrderingMap

But it doesn't work properly. It seems execute would fall into an infinite loop for every input. It seems the monadic statement headWord <- randomIO would be executed infinitely.

I would need some kind of lazy IO, but it doesn't exist for good reasons. Lazy ST RealWorld would be an alternative, but I don't see any way to use this when the random package supports only strict ST. So what's the workaround?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

木森分化 2025-01-26 09:50:23

使用system.random生成懒惰的无限伪随机流的首选方法是使用Randoms。例如：

{-# LANGUAGE ScopedTypeVariables #-}

import Data.Word

import System.Random
main = do
  infwords :: [Word64] <- randoms <gt; newStdGen
  print $ take 10 infwords

这里，infwords是一个普通的，懒惰的，无限的haskell列表pseudorandom word64 s。

The preferred way of generating a lazy infinite pseudorandom stream using System.Random is to use randoms. For example:

{-# LANGUAGE ScopedTypeVariables #-}

import Data.Word

import System.Random
main = do
  infwords :: [Word64] <- randoms <gt; newStdGen
  print $ take 10 infwords

Here, infwords is a normal, lazy, infinite Haskell list of pseudorandom Word64s.

回复收藏 0 原文