"
======================================================================
|
| Copyright (C) 1988, 1989 Free Software Foundation, Inc.
| Written by Steve Byrne.
|
| This file is part of GNU Smalltalk.
|
| GNU Smalltalk is free software; you can redistribute it and/or modify it
| under the terms of the GNU General Public License as published by the Free
| Software Foundation; either version 1, or (at your option) any later version.
| 
| GNU Smalltalk is distributed in the hope that it will be useful, but WITHOUT
| ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
| FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
| details.
| 
| You should have received a copy of the GNU General Public License along with
| GNU Smalltalk; see the file LICENSE.  If not, write to the Free Software
| Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  
|
======================================================================

see notice in (Random>>documentation)
"

"{ Package: 'stx:libbasic2' }"

Stream subclass:#Random
	instanceVariableNames:'seed increment multiplier modulus'
	classVariableNames:'RandomGenerator RandomSalt'
	poolDictionaries:''
	category:'Magnitude-Numbers'
!

!Random class methodsFor:'documentation'!

copyright
"
======================================================================
|
| Copyright (C) 1988, 1989 Free Software Foundation, Inc.
| Written by Steve Byrne.
|
| This file is part of GNU Smalltalk.
|
| GNU Smalltalk is free software; you can redistribute it and/or modify it
| under the terms of the GNU General Public License as published by the Free
| Software Foundation; either version 1, or (at your option) any later version.
| 
| GNU Smalltalk is distributed in the hope that it will be useful, but WITHOUT
| ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
| FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
| details.
| 
| You should have received a copy of the GNU General Public License along with
| GNU Smalltalk; see the file LICENSE.  If not, write to the Free Software
| Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  
|
======================================================================

see notice in (Random>>documentation)
"
!

documentation
"
    random numbers - thanks to Steves GNU Smalltalk

    This implements a linear congruential maximum period random number generator
    which passes the spectral test for randomness for dimensions 2 3 4 5 6.

    DO NOT USE IT FOR CRYPTOGRAPHY, because linear congruential generators
    are predictable and can be broken easily!!

    Notice: although being included here,
            this file is NOT covered by the ST/X license, but by
            the FSF copyLeft (see copyright method).

            You can redistribute it under the terms stated there ...
            Also, the price you pay for ST/X does not include a charge for
            this file - it has to be considered as a separate piece of
            software, which can be copied and given away without any 
            restriction from my (CG) side.

    [author:]
        Steve Byrne
        Claus Gittinger

    [see also:]
        RandomTT800      - a new random generator
        RandomParkMiller - another new random generator
"
!

examples
"
                                                                        [exBegin]
    |rnd|

    rnd := Random new.
    10 timesRepeat:[
        Transcript showCR:(rnd next)
    ]
                                                                        [exEnd]

    rolling a dice:
                                                                        [exBegin]
    |rnd|

    rnd := Random new.
    10 timesRepeat:[
        Transcript showCR:(rnd nextIntegerBetween:1 and:6)
    ]
                                                                        [exEnd]
"
! !

!Random class methodsFor:'instance creation'!

new
    "return a new random generator"

    ^self basicNew setSeed
!

random
    "return a new random generator.
     Defined here for compatibility with StreamCipher"

    ^ self new

    "Created: / 12.11.1999 / 17:52:08 / stefan"
! !

!Random class methodsFor:'random numbers'!

nextBetween:start and:stop
    "return a random number between start and stop.
     This method behaves like the corresponding instance method,
     but allows generation of random numbers without
     a need for an instance of Random to be kept around.
     This uses a common, shared generator."

    RandomGenerator isNil ifTrue:[
        RandomGenerator := self new.
    ].
    ^ RandomGenerator nextBetween:start and:stop

    "
     Transcript showCR:(Random nextBetween:1 and:100).
     Transcript showCR:(Random nextBetween:1 and:100).
     Transcript showCR:(Random nextBetween:1 and:100).
     Transcript showCR:(Random nextBetween:1 and:100).
    "

    "Modified: 21.8.1997 / 18:08:56 / cg"
    "Created: 21.8.1997 / 18:09:36 / cg"
!

nextBoolean
    "return a boolean random.
     This method behaves like the corresponding instance method,
     but allows generation of random numbers without
     a need for an instance of Random to be kept around.
     This uses a common, shared generator."

    RandomGenerator isNil ifTrue:[
        RandomGenerator := self new.
    ].
    ^ RandomGenerator nextBoolean.

    "
     Transcript showCR:(Random nextBoolean).
     Transcript showCR:(Random nextBoolean).
     Transcript showCR:(Random nextBoolean).
     Transcript showCR:(Random nextBoolean).
    "

    "Created: 21.8.1997 / 18:08:23 / cg"
!

nextInteger
    "return an integral random number.
     This method behaves like the corresponding instance method,
     but allows generation of random numbers without
     a need for an instance of Random to be kept around.
     This uses a common, shared generator."

    RandomGenerator isNil ifTrue:[
        RandomGenerator := self new.
    ].
    ^ RandomGenerator nextInteger.

    "
     Transcript showCR:(Random nextInteger).
     Transcript showCR:(Random nextInteger).
     Transcript showCR:(Random nextInteger).
     Transcript showCR:(Random nextInteger).
    "

    "Created: 21.8.1997 / 18:08:23 / cg"
!

nextIntegerBetween:start and:stop
    "return an integral random number between start and stop.
     This method behaves like the corresponding instance method,
     but allows generation of random numbers without
     a need for an instance of Random to be kept around.
     This uses a common, shared generator."

    RandomGenerator isNil ifTrue:[
        RandomGenerator := self new.
    ].
    ^ RandomGenerator nextIntegerBetween:start and:stop

    "
     Transcript showCR:(Random nextIntegerBetween:1 and:10).
     Transcript showCR:(Random nextIntegerBetween:1 and:10).
     Transcript showCR:(Random nextIntegerBetween:1 and:10).
     Transcript showCR:(Random nextIntegerBetween:1 and:10).
    "

    "Created: 21.8.1997 / 18:07:00 / cg"
    "Modified: 21.8.1997 / 18:08:56 / cg"
! !

!Random class methodsFor:'testing'!

bucketTest: randy
    "A quick-and-dirty bucket test. Prints nbuckets values on the Transcript.
     Each should be 'near' the value of ntries. Any run with any value 'far' from ntries
     indicates something is very wrong. Each run generates different values.
     For a slightly better test, try values of nbuckets of 200-1000 or more; 
     go get coffee.
     This is a poor test; see Knuth.   
     Some 'OK' runs:
           1000 1023 998 969 997 1018 1030 1019 1054 985 1003
           1011 987 982 980 982 974 968 1044 976
           1029 1011 1025 1016 997 1019 991 954 968 999 991
           978 1035 995 988 1038 1009 988 993 976
    "

    | nbuckets buckets ntrys slot |

    nbuckets := 20.
    buckets := Array new: nbuckets.
    buckets atAllPut: 0.
    ntrys :=  1000.
    ntrys*nbuckets timesRepeat: [
            slot := (randy next * nbuckets) floor + 1.
            buckets at: slot put: (buckets at: slot) + 1 ].
    Transcript cr.
    1 to: nbuckets do: [ :nb |
            Transcript show: (buckets at: nb) printString, ' ' ]


    "Execute this:  
     Random bucketTest: Random new
    "

!

chiSquareTest   
    " Chi-Squared Test - from R.Sedgewick's 1st ed. of 'Algorithms', 
            o N = number of samples
            o r  = range of random numners is [0,r)      -- condition: N >= 10r.
            o Random number generator 'passes' if chisquare value is very close to r
            o Repeat test several times, since it may be *wrong* 1 out of 10 trials."

    | aRand frequencies n range t chisquare |

    chisquare := Array new: 10.     "Collect results from 10 trails"
    1 to: 10 do: [:k |       "k = trail number"
        aRand := Random new.  "Seeded differently each time"
        range := 100.   
        n := 1000.
        frequencies := Array new: range.
        1 to: frequencies size do: [ :i | frequencies at: i put: 0 ].
        1 to: n do: [ :i |
                t := ((aRand next) * range) truncated.
                frequencies at: (t+1) put: ((frequencies at: (t + 1)) + 1) ].
        t := 0.
        1 to: range do: [ :i |
                t := t +  ((frequencies at: i) squared) ].
        chisquare at: k put: (((range * t  / n) - n) asFloat).
    ].
    ^ chisquare

    "
     Random chiSquareTest 
    "

    "
      Sedgewick claims each chisquare number should be 100 +- 20. 
      The closer to 100, the better.
    "

    "Modified: 16.4.1997 / 16:48:26 / cg"
! !

!Random methodsFor:'Compatibility - Squeak'!

nextIntFrom:lowerBound to:upperBound
    "return a random integer in the given range"

    ^ self nextIntegerBetween:lowerBound and:upperBound

    "
     Random new nextIntFrom:5 to:10
    "
! !

!Random methodsFor:'accessing-reading'!

next
    "return the next random number in the range 0..1"

    ^ self nextInteger / modulus asFloat

    "|r|
     r := Random new.
     Transcript showCR:r next.
     Transcript showCR:r next.
     Transcript showCR:r next.
     Transcript showCR:r next.
    "

    "Modified: 1.4.1997 / 22:44:46 / cg"
!

nextBetween:start and:stop
    "return a random number between start and stop.
     claus: the original GNU version has a bug in returning values
     from the interval [start .. stop+1]"

    |rnd|

    rnd := self next.
    rnd := rnd * (stop - start) asFloat.
    rnd := rnd + start asFloat.
    ^ rnd

    "|r|
     r := Random new.
     Transcript showCR:(r nextBetween:1 and:10).
     Transcript showCR:(r nextBetween:1 and:10).
     Transcript showCR:(r nextBetween:1 and:10).
     Transcript showCR:(r nextBetween:1 and:10).
    "

    "Modified: / 21.8.1998 / 14:45:27 / cg"
!

nextBoolean
    "return true or false by random"

    ^ self next < 0.5

    "|r|
     r := Random new.
     Transcript showCR:r nextBoolean.
     Transcript showCR:r nextBoolean.
     Transcript showCR:r nextBoolean.
     Transcript showCR:r nextBoolean.
    "

    "
     |r bag|
     r := Random new.
     bag := Bag new.
     1000000 timesRepeat:[
         bag add:(r nextBoolean).
     ].
     Transcript showCR:bag contents
    "

    "Modified: / 21.8.1998 / 14:45:55 / cg"
!

nextByte
    "return the next integral random number byte in the range 0 .. 16rFF"

    self step.
    ^ seed bitAnd:16rFF

    "
     |r|
     r := Random new.
     Transcript showCR:r nextByte.
     Transcript showCR:r nextByte.
     Transcript showCR:r nextByte.
     Transcript showCR:r nextByte.
    "

    "Modified: 1.4.1997 / 22:42:53 / cg"
!

nextBytes:count
    "return count random bytes (0..16rFF each)"

    |res|

    res := ByteArray new:count.

    1 to:count do:[:i|
        self step.
        res at:i put:(seed bitAnd:16rFF).
    ].

    ^ res

    "
     |r|
     r := Random new.
     Transcript showCR:(r nextBytes:20).
    "

    "Modified: 1.4.1997 / 22:42:53 / cg"
!

nextInteger
    "return the next integral random number,
     in the range 0 .. 16r3FFFFFFF.
     From Sedgewick's 'Algorithms', based on Lehmer's method"

    self step.
    ^ seed

    "
     |r|
     r := Random new.
     Transcript showCR:r nextInteger.
     Transcript showCR:r nextInteger.
     Transcript showCR:r nextInteger.
     Transcript showCR:r nextInteger.
    "

    "Modified: 1.4.1997 / 22:42:53 / cg"
!

nextIntegerBetween:start and:stop
    "return an integral random number between start and stop"

    |rnd|

    rnd := self next.                               
    rnd := rnd * ((stop - start) asFloat + 1.0).    
    ^ rnd truncated + start

    "
     |r|
     r := Random new.
     Transcript showCR:(r nextIntegerBetween:1 and:10).
     Transcript showCR:(r nextIntegerBetween:1 and:10).
     Transcript showCR:(r nextIntegerBetween:1 and:10).
     Transcript showCR:(r nextIntegerBetween:1 and:10).
    "

    "
     |r bag|
     r := Random new.
     bag := Bag new.
     1000000 timesRepeat:[
         bag add:(r nextIntegerBetween:-1 and:1).
     ].
     Transcript showCR:bag contents
    "

    "Modified: / 21.8.1998 / 14:45:04 / cg"
!

nextMatchFor: aNumber
    "generate the next random, return true iff it has the same
     value as aNumber. Redefined to avoid endless reading."

    ^self next = aNumber
! !

!Random methodsFor:'blocked methods'!

contents
    "blocked from use - contents makes no sense for random generators"

    self shouldNotImplement
!

nextPut: value
    "blocked from use - it makes no sense for randoms"

    self shouldNotImplement
! !

!Random methodsFor:'private'!

setSeed
    "set the initial seed value based on the current time.
     These numbers implement a maximum period generator which passes
     the spectral test for randomness for dimensions 2 3 4 5 6 and
     the product does not overflow  2 raisedTo:29.

     These numbers are carefully choosen, so don't change them, 
     unless you know what you are doing!!"

    seed := Time millisecondClockValue bitAnd:16rFFFF.
    RandomSalt isNil ifTrue:[
        RandomSalt := 1.
    ] ifFalse:[
        RandomSalt := RandomSalt + 1.
    ].
    seed := seed + RandomSalt.
    multiplier := 1597.
    increment := 51749.
    modulus := 244944 " 244957 " .

    self step.

    "Modified: / 1.4.1997 / 22:44:13 / cg"
    "Modified: / 12.11.1999 / 17:50:52 / stefan"
!

step
    "compute the next random integer"

    "/ seed := (seed times:31415821) + 1 bitAnd: 16r3FFFFFFF.
    seed := seed * multiplier + increment \\ modulus

    "Created: 1.4.1997 / 22:40:45 / cg"
    "Modified: 1.4.1997 / 22:43:01 / cg"
! !

!Random methodsFor:'testing'!

atEnd
    "instances of Random can always give more numbers"

    ^ false
!

isReadable
    ^ true
!

isWritable
    ^ false

    "Created: 1.4.1997 / 22:38:27 / cg"
! !

!Random class methodsFor:'documentation'!

version
    ^ '$Header: /cvs/stx/stx/libbasic2/Random.st,v 1.31 2002-12-06 10:17:28 cg Exp $'
! !