Random.curry

------------------------------------------------------------------------------
--- Library for pseudo-random number generation in Curry.
--- <P>
--- This library provides operations for generating pseudo-random
--- number sequences.
--- For any given seed, the sequences generated by the operations
--- in this module should be <B>identical</B> to the sequnces
--- generated by the java.util.Random package.
--- <P>
--- The algorithm is a linear congruential pseudo-random number generator
--- described in Donald E. Knuth, <i>The 
--- Art of Computer Programming,</i> Volume 2: <i>Seminumerical 
--- Algorithms</i>, section 3.2.1.
---
--- @author Sergio Antoy (with extensions by Michael Hanus)
--- @version December 2004
------------------------------------------------------------------------------

module Random(nextInt, nextIntRange, nextBoolean, getRandomSeed) where

import Time
import System(getCPUTime)

------------------------------------------------------------------
--                       Private Operations
------------------------------------------------------------------

-- a few constants

multiplier = 25214903917
addend     = 11
powermask  = 48
mask       = 281474976710656  -- 2^powermask
intsize    = 32
intspan    = 4294967296       -- 2^intsize
intlimit   = 2147483648       -- 2^(intsize-1)

-- the basic sequence of random values

sequence seed = next : sequence next
    where next = nextseed seed

-- auxiliary private operations

nextseed seed = (seed * multiplier + addend) `mod` mask

xor x y = if (x==0) && (y==0) then 0 else lastBit + 2 * restBits
    where lastBit  = if (x `mod` 2) == (y `mod` 2) then 0 else 1
          restBits = xor (x `div` 2) (y `div` 2)

power base exp = binary 1 base exp
    where binary x b e
              = if (e == 0) then x
                else binary (x * if (e `mod` 2 == 1) then b else 1)
                            (b * b)
                            (e `div` 2)

nextIntBits seed bits = map adjust list
    where init = (xor seed multiplier) `mod` mask
          list = sequence init
          shift = power 2 (powermask - bits)
          adjust x = if arg > intlimit then arg - intspan
                                       else arg
              where arg = (x `div` shift) `mod` intspan

------------------------------------------------------------------
--                       Public Operations
------------------------------------------------------------------

--- Returns a sequence of pseudorandom, uniformly distributed 32-bits
--- integer values.  All 2<font size="-1"><sup>32
--- </sup></font> possible integer values are produced with 
--- (approximately) equal probability.
---
--- @param seed - The seed of the random sequence.

nextInt :: Int -> [Int]
nextInt seed = nextIntBits seed intsize

--- Returns a pseudorandom, uniformly distributed sequence of values
--- between 0 (inclusive) and the specified value (exclusive).
--- Each value is a 32-bits positive integer.
--- All <tt>n</tt> possible values are produced with (approximately) equal
--- probability.
--- @param seed - The seed of the random sequence.
--- @param n - The bound on the random number to be returned. 
---            Must be positive.

nextIntRange :: Int -> Int -> [Int]
nextIntRange seed n | n>0
    = if power_of_2 n then map adjust_a seq
      else map adjust_b (filter adjust_c seq)
    where seq = nextIntBits seed (intsize - 1)
          adjust_a x = (n * x) `div` intlimit
          adjust_b x = x `mod` n
          adjust_c x = x - (x `mod` n) + (n - 1) >= 0
          power_of_2 k = k == 2 || 
                         k > 2 && k `mod` 2 == 0 && power_of_2 (k `div` 2)
                            
--- Returns a pseudorandom, uniformly distributed sequence of
--- <code>boolean</code> values.  The
--- values <code>True</code> and <code>False</code> are produced with
--- (approximately) equal probability. 
--- @param seed - The seed of the random sequence.

nextBoolean :: Int -> [Bool]
nextBoolean seed = map (/= 0) (nextIntBits seed 1)


--- Returns a time-dependent integer number as a seed for really random numbers.
--- Should only be used as a seed for pseudorandom number sequence
--- and not as a random number since the precision is limited to milliseconds

getRandomSeed :: IO Int
getRandomSeed =
  getClockTime >>= \time ->
  getCPUTime >>= \msecs ->
  let (CalendarTime y mo d h m s _) = toUTCTime time
   in return ((y+mo+d+h+m*s*msecs) `mod` mask)
                            
{-     Simple tests and examples

testInt = take 20 (nextInt 0)

testIntRange = take 120 (nextIntRange 0 6)

testBoolean = take 20 (nextBoolean 0)

reallyRandom = do seed <- getRandomSeed
                  putStrLn (show (take 20 (nextIntRange seed 100)))
-}