Created by [CecilWesterhof].
'''Functions to Get Random Integers on a *NIX System'''
To get better random integers you can use /dev/urandom. I wrote a function getRandomBytesNix to get a series of random bytes see [Get Random Bytes on *NIX]. This is used for generating random numbers.
The first proc is a proc to get a a random integer from type c, s, i, or w.
======
proc getRandomIntNix {{type i}} { switch ${type} {
c {
set bytes 1
set format cu
}
s {
set bytes 2
set format su
}
i {
set bytes 4
set format iu
}
w {
set bytes 8
set format wu
}
default { error "type can only be c, s, i, or w (${type})"
}
} binary scan [getRandomBytesNix ${bytes}] ${format} random
return ${random}
}
======
Often you need another range (for example [-5, 12]), for this I created getRandomIntInRangeNix.
A naive version is something like the following:
======
proc getRandomIntInRangeNixBiased {min max {type i}} { if {${max} <= ${min}} {
error "Error: [info level 0] min should be lower as max"
} switch ${type} {
c {
set maxMod [expr 2 ** 8]
}
s {
set maxMod [expr 2 ** 16]
}
i {
set maxMod [expr 2 ** 32]
}
w {
set maxMod [expr 2 ** 64]
}
default { error "type can only be c, s, i, or w (${type})"
}
} set modulo [expr {${max} - ${min} + 1}]
if {${modulo} > ${maxMod}} {
error "Modulo should be <= ${maxMod} (${modulo})"
} set random [getRandomIntNix ${type}]
expr {${random} % ${modulo} + ${min}}
}
======
The problem with this is that this can result in biased results.
Say we have a generator that generates the values between 0 and 15. If we ask for a range between 0 and 10, then the values 0 to 4 are two times more likely to be generated as the values 5 to 10, because the values 11 to 15 are mapped to 0 to 4.
To show this I created the following script:
======
set range 99
set repeatCalc 250000
set repeatGen 5
for {set i 0} {${0} <= ${repeatGen}} {incr i} {
array set count {} for {set j 0} {${j} < ${repeatCalc}} {incr j} {
set index [expr {[getRandomIntInRangeNix 0 ${range} c] / 20}]
incr count(${index})
}
parray count
unset count
puts ""
}
======
An example output when this is run:
======
count(0) = 58899
count(1) = 58324
count(2) = 54793
count(3) = 39192
count(4) = 38792
count(0) = 58808
count(1) = 58317
count(2) = 54746
count(3) = 39129
count(4) = 39000
count(0) = 58295
count(1) = 58439
count(2) = 55095
count(3) = 39156
count(4) = 39015
count(0) = 58454
count(1) = 58674
count(2) = 54598
count(3) = 39202
count(4) = 39072
count(0) = 58825
count(1) = 58447
count(2) = 54700
count(3) = 39170
count(4) = 38858
======
This can be solved with the following code:
======
proc getRandomIntInRangeNix {min max {type i}} { if {${max} <= ${min}} {
error "Error: [info level 0] min should be lower as max"
}
# maxMod should not be bigger as half of the range
# otherwise calculating can take to long
# in this way the chance that you need 10 random values before returning
# is less as one promille switch ${type} {
c {
set range [expr 2 ** 8]
}
s {
set range [expr 2 ** 16]
}
i {
set range [expr 2 ** 32]
}
w {
set range [expr 2 ** 64]
}
default { error "type can only be c, s, i, or w (${type})"
}
} set maxMod [expr {${range} / 2}]
set modulo [expr {${max} - ${min} + 1}]
if {${modulo} > ${maxMod}} {
error "Modulo should be <= ${maxMod} (${modulo})"
}
# Values above maxVal would result in bias and should be rejected set maxVal [expr {${modulo} * (${range} / ${modulo}) - 1}]
while True { set random [getRandomIntNix ${type}]
if {${random} <= ${maxVal}} {
break
}
} expr {${random} % ${modulo} + ${min}}
}
======
Now a run could give something like:
======
count(0) = 50347
count(1) = 49748
count(2) = 49856
count(3) = 50155
count(4) = 49894
count(0) = 50381
count(1) = 49524
count(2) = 50101
count(3) = 49979
count(4) = 50015
count(0) = 50005
count(1) = 50035
count(2) = 49845
count(3) = 49950
count(4) = 50165
count(0) = 49911
count(1) = 50110
count(2) = 50171
count(3) = 50349
count(4) = 49459
count(0) = 49681
count(1) = 50095
count(2) = 49802
count(3) = 49995
count(4) = 50427
======
----
As always: comments, tips and questions are appreciated.
<<categories>>Linux | Numerics | Utilities