Sunday, August 07, 2011

[lpeivygh] Scaling random integers

{- |If sample_from_generator (which is a sample from a uniform random number generator with range [0...generator_modulus-1]) can be safely used to generate a uniform random integer [0...target_modulus-1], then returns Just that scaled number, else Nothing. This works by rejecting the upper end of the original random number generator's range. In the worst-case scenario, the target_modulus is slightly larger than half the generator_modulus, causing rejection almost 50% of the time. -}
scale_random :: forall num maybe . (Integral (num), MonadPlus (maybe)) => num -> num -> num -> maybe(num);
scale_random generator_modulus sample_from_generator target_modulus = (do{
let {
m :: num;
m = (mod sample_from_generator target_modulus);
over1 :: num;
over1 = ((+) target_modulus ((-) sample_from_generator m))
(guard ((<=) over1 generator_modulus));
(return m);

*Main> ((\range target -> map (\i -> scale_random range i target) [0..(range-1)]) 7 3) :: [Maybe Integer]
[Just 0,Just 1,Just 2,Just 0,Just 1,Just 2,Nothing]

No comments :