Hand-rolled Random Number generator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
module Data.Random where

import Random             -- or 'import System.Random'

import Control.Monad

import Data.List
import Data.Ratio
import Data.Time.Clock

import Algorithmic.Automata.Cellular  -- http://lpaste.net/107206

import Control.Comonad                -- http://lpaste.net/107661

import Data.Universe                  -- http://lpaste.net/108632

-- Okay, now I get to write my own random number generator. Wheee!

data RNG = RND (U Bool) Int

instance Show RNG where
   show (RND (U a b c) bits) = "RNG ["
      ++ showBits (reverse (take bits a)) ++ " < " 
      ++ show (showBit b) ++ " > "
      ++ showBits (take bits c) ++ "]"
      where showBits = map showBit
            showBit bit = if bit then '1' else '0'

mkRNG :: Int -> Integer -> RNG
mkRNG precision slt = RND (U (salt slt) True (salt slt)) precision

{--

So, for example: 

> mkRNG 10 324789235687
RNG [1010110010 < '1' > 0100110101]

*Data.Random > genRange (mkRNG 10 23423) 
(-2147483648,2147483647)

*Data.Random> next it
(707226,RNG [1010101110 < '1' > 0111100101])
*Data.Random> next $ snd it
(703218,RNG [1010101000 < '1' > 0100011101])
*Data.Random> next $ snd it
(696974,RNG [0010101101 < '1' > 0110110001])
*Data.Random> next $ snd it
(177880,RNG [0110101001 < '0' > 0100101011])
*Data.Random> next $ snd it
(435349,RNG [1100101111 < '1' > 1111101010])

n.b. the results returned an 2^20 == 1048576, so, really, genRange is
(0, 2^bits)

 --}

salt :: Integer -> [Bool]
salt sommat = unfoldr (\val -> if val <= 0 then Nothing
                                else let (a, b) = val `divMod` 2
                                     in  Just (b == 0, a - b)) sommat
                      ++ repeat False

instance RandomGen RNG where
   next (RND d bits) = (x d, RND (d =>> rule30) bits)
       -- geddit? xD, x d, XD, geddit? ;)
      where x d = toInt $ toList (negate bits) bits d
   split (RND d bits) = (RND (a d) bits, RND (b d) bits)
      where a (U a b c) = U (repeat False) b c
            b (U a b c) = U a b (repeat False)
   genRange (RND d bits) = (0, 2^bits)

-- Okay, that's great; now let's replace System.Random

{--
instance Random RNG where
   randomR (lo, hi) g = 
      let (raw, newRNG) = next g
          (milo, myhi) = genRange g
          scaledRaw = raw - milo / (myhi - milo)
      in  (scaledRaw * (hi - lo) + lo, newRNG)
   random g = undefined -- ugh!

um, no. Random is not our generator, but the type to be randomized,
like Int or [a] or some-such.

--}

{--

*Data.Random Data.Time.Clock Control.Monad Data.Ratio> 
liftM (numerator . toRational . utctDayTime) getCurrentTime ~>
4187179659

--}

getCellRandom :: (RNG -> (a, RNG)) -> IO a
getCellRandom rndfn =
   liftM (numerator . toRational . utctDayTime) getCurrentTime >>=
   return . fst . rndfn . mkRNG 16

{--

*Data.Random> getCellRandom (randomR (1,6)) ~> 3
*Data.Random> getCellRandom (randomR (1,6)) ~> 3
*Data.Random> getCellRandom (randomR (1,6)) ~> 5
*Data.Random> getCellRandom (randomR (1,6)) ~> 3
*Data.Random> getCellRandom (randomR (1,6)) ~> 1
*Data.Random> getCellRandom (randomR (1,6)) ~> 4
*Data.Random> getCellRandom (randomR (1,6)) ~> 6

YAY!

--}

-- Okay, but how about for lists?

-- instance Random [a] where
   -- randomR (lo, hi) g = 

-- Bleh! another time!
99:4: Warning: Use liftM
Found:
liftM (numerator . toRational . utctDayTime) getCurrentTime >>=
return . fst . rndfn . mkRNG 16
Why not:
liftM (fst . rndfn . mkRNG 16)
(liftM (numerator . toRational . utctDayTime) getCurrentTime)