Randomize algoritması

Question

Biz yaklaşık sayım algoritması uygulanması am beklendiği gibi çalışmıyorsa:

kaydını kullanarak bir sayaç x ettirilir (N log)

• başlatma x bitleri 0

• Bir ürün geldiğinde, X değerini artırın (& Frac12;) olasılık ile 1 ile ^x

• akışı üzerinde, çıkış 2 ^x − 1 böylece e [2 ^x] = N + 1 aşağıdaki gibi

Benim uygulamasıdır:

import System.Random 

type Prob = Double 
type Tosses = Int 

-- * for sake of simplicity we assume 0 <= p <= 1 
tos :: Prob -> StdGen -> (Bool,StdGen) 
tos p s = (q <= 100*p, s') 
    where (q,s') = randomR (1,100) s 

toses :: Prob -> Tosses -> StdGen -> [(Bool,StdGen)] 
toses _ 0 _ = [] 
toses p n s = let t@(b,s') = tos p s in t : toses p (pred n) s' 

toses' :: Prob -> Tosses -> StdGen -> [Bool] 
toses' p n = fmap fst . toses p n 

morris :: StdGen -> [a] -> Int 
morris s xs = go s xs 0 where 
    go _ []  n = n 
    go s (_:xs) n = go s' xs n' where 
    (h,s') = tos (0.5^n) s 
    n'  = if h then succ n else n 

main :: IO Int 
main = do 
    s <- newStdGen 
    return $ morris s [1..10000] 

sorun benim X daima herhangi |stream| > 2 için yanlış olduğunu, ve

X = 7 Ben Matlab aynı algoritmayı test edilmiş ve o orada çalışıyor, hepsi StdGen ve |stream| > 1000 için gibi görünüyor, bu yüzden o da varsayıyorum Doublebüyük bir n 1/2 yükselterek

1. benim rasgele sayı üreteci ile bir sorun varken veya

Lütfen ileri bir yol öneriniz?

Answer 1

Sorun aslında çok basit: randomR (1,100) ile değerleri ilk yüzde içinde engellersiniz, böylece 1/2 (her biri küçük aralıkta) yüksek güçlerde tam bir kesme yaparsınız. Aslında genel bir şey: ranges should start at zero, bir ^{& hançer; Belirli bir nedeni olmadıkça}.

Ama neden ilk etapta 100'ü bile kullanıyorsunuz? Sadece yapmak istiyorum bunun

tos :: Prob -> StdGen -> (Bool,StdGen) 
tos p s = (q <= p, s') 
    where (q,s') = randomR (0,1) s 

---

^{& hançer;} _{Biliyorum ki, Matlab her yeri yanlış anladı. Bu dil ile ilgili many korkunç şeyler sadece bir tanesi. sorununuza İlgisiz}

---

: chi yerine elle etrafında StdGen s geçme, sen uygun bir rasgele monad kullanırsanız kod bu tür çok daha güzel görünüyor belirttiği gibi.

import Data.Random 
import Data.Random.Source.Std 

type Prob = Double 

tos :: Prob -> RVar Bool 
tos p = do 
    q <- uniform 0 1 
    return $ q <= p 

morris :: [a] -> RVar Int 
morris xs = go xs 0 where 
    go []  n = return n 
    go (_:xs) n = do 
    h <- tos (0.5^n) 
    go xs $ if h then succ n else n 

morrisTest :: Int -> IO Int 
morrisTest n = do 
    runRVar (morris [1..n]) StdRandom