Re: Proper scaling of randoms
(Redirected to haskell-cafe.) On Mon, May 06, 2002 at 04:49:55PM -0700, [EMAIL PROTECTED] wrote: > Problem: given an integer n within [0..maxn], design a scaling > function sc(n) that returns an integer within [s..t], t>=s. > The function sc(n) must be 'monotonic': > 0<=a < b ==> sc(a) <= sc(b) > and it must map the ends of the interval: > sc(0) -> s and sc(maxn) -> t. Just an aside (which Oleg surely knows): for actual random number generation, you often don't care about the monotonicity, and only care about uniform generation. In this case, there is a very simple algorithm: work modulo (s-t+1). scm(n) = (n `rem` (s-t+1)) + s Warning: some, broken, random number generators do not behave well when used like this. Also, although this is as uniform as possible, there is a systematic skew towards the lower end of the range [s..t]. --Dylan Thurston msg01661/pgp0.pgp Description: PGP signature
administrative question
dear haskell-o-tronics, >From time to time i get emails from haskell-cafe, with the subject "RE: " but since i am only subscribe since some days i dont have the original message and thus would be habby if anybody could bounce me the list-mails from the last year? Matthias ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Bug in the scaling of randoms ...
Dimitre Novatchev writes (to the Haskell mailing list): > In his excellent book Simon Thompson defines scaling of the elements of > a sequence of random numbers from the interval [0, 65535] to an > interval [s,t] in the following way (top of page 368): > > scaleSequence :: Int -> Int -> [Int] -> [Int] > > scaleSequence s t > > = map scale > > where > > scale n = n `div` denom + s > > range = t - s + 1 > > denom = modulus `div` range > > where modulus = 65536 > However, the following expression: > > e4000 = (scaleSequence 1 966 ([65231] ++ [1..965]))!!0 > evaluates to 974 -- clearly outside of the specified interval. The function fails in this case because the range doesn't divide the modulus. In the book (I checked the Miranda version), there's a remark after the function that "[The] range of numbers 0 to modulus-1 is split into range blocks, each of the same length." When the range doesn't divide the modulus, it's not possible to get a uniform distribution if you scale each value individually. I assume this is acceptable, otherwise you'll have to discard or combine values from the original sequence. Oleg answers: >We aim to find a function sc(n) defined over integers 0 <= n <= M so >that >sc(0) -> s (given integral number) >sc(M) -> t (given integral number), t>=s >and >0<=a < b ==> sc(a) <= sc(b) > >Such a function sc(n) is given by the following expression: >sc(n) = (n*(t-s)) `div` M + s (M = modulus - 1) I think a more natural function would be sc(n) = (n * (t-s+1)) `div` modulus + s This satifies the conditions (assuming range = t-s+1 <= modulus), and distributes the values more evenly, in particular when the range divides the modulus. Cheers, Ronny Wichers Schreur ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
