Updated 2013-03-10 21:28:29 by pooryorick

Summary  edit

information about the rand function

See Also  edit

expr
srand
Mersenne Twister
Random
a cryptographically useful rand()
Cryptographically secure random numbers using /dev/urandom
another method for generating cryptographic random numbers
Secure-Programs-HOWTO
True Random Numbers
Bruce Hartweg mentions source of truly random data

Examples  edit

Random Slash Maze
a very small and quirky visual example

Description  edit

The rand() function returns a pseudo-random floating point number. The result is always strictly greater than 0.0 and strictly less than 1.0.

It does not have its own man page, but is one of the many functions documented with expr.

The random number generator is a simple linear congruential generator (see below). This type of random number generator has the advantage that it's fast, and reasonably general purpose. Nevertheless, it's not appropriate for all applications.

First, it should never be used to generate one-time passwords, encryption keys, or the like. It is not cryptographically secure, however the seed for srand is chosen. Generating secure one-time keys is something of a black art. (Can someone provide some references?

Second, the least significant bits of the returned data are "not very random" in some sense.

Third, the returned sequence is prone to sequential correlations if large runs of numbers are taken. For example, if clusters of six sequential results from
expr { rand() }

are analyzed, it will turn out that they lie on only 40 hyperplanes in six-dimensional space. This limitation means that rand() is not suitable by itself for applications like high-resolution Monte Carlo integration.

This third problem can be cleaned up a little bit by the techniques in Sequential correlations and the output of rand.

Fourth, not all numbers are equally probable, if doing something like
expr {10+round(rand()*20)}

for getting a random number in some range. Jonathan Bromley elaborated on comp.lang.tcl Random, comp.lang.tcl, 2008-08-08:
rand()*20  has the range 0 to 19.9999999... 
round() applied to that expression has uniform 
probability of reaching each value in the range 
1 to 19, but only half that probability of 
reaching either 0 or 20.  To see why, consider 
the ranges that round() collapses on to each 
integer: 

  0.0 to 0.5  collapses to 0 
  0.5 to 1.5  collapses to 1 
  1.5 to 2.5  collapses to 2 
   .... 
  18.5 to 19.5  collapses to 19 
  19.5 to 19.99999999 collapses to 20 

Only half the real range for the extremes as for 
any of the other values! 

Try instead 
  expr { 10 + floor(rand() * 21.0) }

Note that the above will give numbers 10.0, 11.0, ..., 29.0, 30.0 (not integers, but doubles!) with equal probability. If the problem is instead to return integers in the range 0, 1, ..., 19 (e.g. to use as indices into a list of length 20) then
expr {int(rand()*20)}

is simpler.

David T. Ashley recommends the recurrence
x = (16807 * x) MOD 2147483647

as a good basis for a long-cycle Tcl-based generator.

DGP: A quick look inside tcl/generic/tclExecute.c will reveal that that is exactly the algorithm powering Tcl's [expr rand()] function, with all its features and all its weaknesses.

EKB: As of revision 1.288 of /tcl/generic/tclBasic.c (last edited Dec 8, 2007), the comment accompanying rand() states:
/*
 * Generate the random number using the linear congruential generator
 * defined by the following recurrence:
 *                seed = ( IA * seed ) mod IM
 * where IA is 16807 and IM is (2^31) - 1. The recurrence maps a seed in
 * the range [1, IM - 1] to a new seed in that same range. The recurrence
 * maps IM to 0, and maps 0 back to 0, so those two values must not be
 * allowed as initial values of seed.
 *
 * In order to avoid potential problems with integer overflow, the
 * recurrence is implemented in terms of additional constants IQ and IR
 * such that
 *                IM = IA*IQ + IR
 * None of the operations in the implementation overflows a 32-bit signed
 * integer, and the C type long is guaranteed to be at least 32 bits wide.
 *
 * For more details on how this algorithm works, refer to the following
 * papers:
 *
 *        S.K. Park & K.W. Miller, "Random number generators: good ones are hard
 *        to find," Comm ACM 31(10):1192-1201, Oct 1988
 *
 *        W.H. Press & S.A. Teukolsky, "Portable random number generators,"
 *        Computers in Physics 6(5):522-524, Sep/Oct 1992.
 */

If you are using Tcl on a 64-bit platform, and you notice that your first evaluation of expr {rand()} in a new interpreter sometimes returns a value >= 1.0, you should upgrade to Tcl 8.3.3 which contains a fix for bug 221072

A handy use of rand is for picking an arbitrary element from a list:
proc lrandom L {
    lindex $L [expr {int(rand()*[llength $L])}]
} ;#RS

TR has these small generators:
# generate random integer number in the range (0,max]
proc RandomInteger1 {max} {
    return [expr {int(rand()*$max) + 1}]
}

# generate random integer number in the range [0,max)
proc RandomInteger2 {max} {
    return [expr {int(rand()*$max)}]
}

# generate random integer number in the range [0,max]
proc RandomInteger3 {max} {
    return [expr {int(rand()*($max+1))}]
}

# generate random integer number in the range [min,max]
proc RandomInteger4 {min max} {
    return [expr {int(rand()*($max-$min+1)+$min)}]
}

DKF writes: When you are wanting to generate lots of random numbers you should use something more like an additive congruential RNG seeded from a linear congruential RNG (rand() is an LCRNG) taking great care to watch out for unpleasant interactions between the two. Knuth says a lot on this.

And if you are after a truly random number source, have fun. Many programs (e.g. PGP and SSH) take hashes of very rapidly changing parts of the system in the hope that they are different even if called from very similar situations. Another source of randomness is keystroke timings, but I'm told that many people are so regular at typing (particularly when they are touch typists) that this is not nearly as good a randomness-source as it might be.

There's a lot of deep theory associated with random number sequences. A maximally random sequence (if I'm not garbling my terminology) is one that has no description shorter than itself. Tcl does not use such a beast! It's description would probably fit on about a line of C, even with the contortions you have to go through to get 64-bit code working... :^)

AM: Besides deep theory we can also remark that pseudo-random sequences, so sequences that can be repeated as a whole, are in general more useful than truly random sequences that can not be repeated. Just think of debugging your program!

TV: I think an essential remark here is that deep theory isn't needed to understand that IF one use a random generator formula, THEN that formula can be cracked in the sense of that the numbers are tracible, probably given that we can trace or invert the seed and keys. The idea that random numbers come from random generators is a bit of a limited, but of course useful and practical thought.

I experimented with making random numbers by feeding a soundcard with radio in-between-station noise, which works fine, and gives nicely distributed gaussian noise with a little processing. If there is a request, or when I feel like it, I can make such random sequences available, maybe I'll give my server [1] a special url to return a 'real' (at least untracible) random list or value.

For use on a local computer, sound could get you about a 100 thousand byte length random numbers per second, I guess that can be beat by making an uncompressed avi of data from noisy television screen digital recording. Of course any signal feed will give you random numbers at great rates, but then they wouldn't be more or less uniformly or maybe gaussian distributed in frequency sense.

For the sound idea: use the lower order byte only, than you don't need to worry much about 0dB level. Make sure your card is realy 16 bit. I works great, I tried, maybe I'll do a Snack based version.

Steve Offutt offers:
proc random_int { upper_limit } {
    global myrand
    set myrand [expr int(rand() * $upper_limit + 1)]
    return $myrand
}

for {set i 0} {$i < 20} {incr i} {
    set result [random_int 12]
    puts -nonewline "\t $result"
}

as an illustration of the use of rand(), and notes that tcllib has more on the subject.

RS: KISS - the global variable isn't needed at all, this is equivalent:
proc random_int limit {
    expr {int(rand() * $limit +1)}
}

Lars H: Some OSes have a random device /dev/random from which one can read random data. The exact implementation varies, but the idea is to collect "noise" from what is going on in the system and use that to improve the randomness of the data produced.

Arjen Markus: I have seen a completely different approach to random number generation. I do not know the mathematical details (and its merits are a mystery), but this is the reference: Mersenne Twister at [2] - Eric Amundsen says that this link was broken as of March 31 '03, perhaps this [3] is what was intended?

PT 203-04-01: I've done a Tcl package to provide a randmt() function that generates random numbers using the code from this PRNG algorithm. Perhaps someone with more analytical skills than me would like to test it out and see if is indeed (a) faster than the default, or (b) more random. From my reading of the above references it seems that it should be both.

PT 2003-04-03'': RandMT the Mersenne-Twister-based rand() package is now available through cvs at sourceforge as part of the tclsoap project:
cvs -d:pserver:anonymous@cvs.tclsoap.sourceforge.net:/cvsroot/tclsoap co RandMT

MC 2003-04-09: Perhaps this could be added to the forthcoming v1.4 release of tcllib?

PT 2003-04-11: No. This is a compiled extension so cannot be considered for tcllib.

PT 2003-04-15: RandMT is replaced by the Random package which now included the MT PRNG and also the ISAAC PRNG. See Random.

Here's some usage examples for random numbers:

Pick a random element from a list:
proc lpick list {
    lindex $list [expr {int(rand()*[llength $list])}]
}
% lpick {red orange yellow green blue purple}
green ;# your result may be different ;-)

Do something only in 25 % (0.25) of cases or put your favorite percentage in place:
if {rand()<=0.25} {puts "25% chance"}

DKF: Actually, that should be:
if {rand()<0.25} {puts "25% chance"}

because the range of rand() is [0,1)

DGP: Actually, the range of rand() is (0,1)

I am working on a small program to examine how random rand is. So I start with this:
#! /usr/local/bin/tclsh

proc r {limit} {
    return [expr {int(rand() * $limit)}]
}
 
proc lrepeat {value number} {
    set rlist [list]
    for {set i 0}  {$i < $number} {incr i} {
        lappend rlist $i $value
    }
    return $rlist
}
 
array set val [lrepeat 0 64]
for {set i 0} { $i < 1000} {incr i} {
    incr val([r 64])
}
puts "After filling"
set keys [lsort -integer [array names val]]
package require BLT
barchart .b -plotbackground black
pack .b
.b configure -title "expr rand's distribution" 
foreach key $keys {
    .b element create e$key -xdata $key -ydata $val($key)
}
 
# parray val

However, the above program has a problem. When I run it with bltsh, I get the error:
After filling
invalid command name "blt::barchart"
   while executing
"blt::barchart .b -plotbackground black"
   (file "/tmp/r.tcl" line 26)

However, it looks like the command is defined in the blt man page and when I look in the demo files, it appears there. Anyone know what I am missing?

RS: This discussion gets a bit off-topic, but I would start bltsh interactively and try the commands
% namespace children :: ;# is there a blt namespace at all?
% info commands b*

and so on, and see whether your bltsh matches your docs. Tcl is so great in introspection...

PT: I think we should point out here that just plotting the number of items in each bucket probably isn't the way to calculate the randomness. From some reading around it looks like you need to generate a chi-squared test result. Here's some code...
# assess.tcl Copyright (C) 2003 Pat Thoyts <patthoyts@users.sf.net>
#
# Attempt to assess the randomness of the rand() and randmt() function
# calls.
#
# 'assess' will print the standard deviation and chi-squared results for
# a given number of samples fitting into a number of buckets.
#
# $Id: 1549,v 1.46 2006-09-11 06:00:02 jcw Exp $

package require Tcl 8.4;                # we use lset
catch {package require RandMT};         # mersenne twister rand()

# -------------------------------------------------------------------------
# The random number generator functions. Each function here should return
# a single number between 0 and max each time it's called.

proc gen_rand {max} {
    return [expr {int(rand() * $max)}]
}

proc gen_randmt {max} {
    return [expr {int(randmt() * $max)}]
}

# -------------------------------------------------------------------------
# Fill a list with count values.

proc lrepeat {value count} {
    set r [list]
    for {set n 0} {$n < $count} {incr n} {
        lappend r $value
    }
    return $r
}

# -------------------------------------------------------------------------
# Generate count random numbers and assign into the list named by varname
# Use the random number generator function genProc.

proc fill {varname count genProc} {
    upvar $varname d
    set len [llength $d]
    for {set n 0} {$n < $count} {incr n} {
        set ndx [$genProc $len]
        set val [lindex $d $ndx]
        incr val
        lset d $ndx $val
    }
    return
}

# -------------------------------------------------------------------------
# Standard deviation for a list of values.

proc sd {l expected} {
    set sd 0
    set total 0
    set count [llength $l]
    for {set n 0} {$n < $count} {incr n} {
        set v [lindex $l $n]
        incr total $v
        set d [expr {double(abs($v - $expected)) / double($expected)}]
        set sd [expr {$sd + $d}]
    }
    set avg [expr {double($total) / double($count)}]
    return [list average $avg standard_deviation $sd]
}

# -------------------------------------------------------------------------
# Calculate the chi-squared for the result list.
# chi2 = sum [sqr(val - expected) / expected]

proc chi {l u} {
    set chi 0
    set count [llength $l]
    for {set n 0} {$n < $count} {incr n} {
        set v [lindex $l $n]
        set c [expr {pow($v - $u, 2) / double($u)}]
        #puts stderr "$n $v [expr {$v - $u}] [expr {pow($v - $u, 2)}] $c"
        set chi [expr {$chi + $c}]
    }
    return [list chi $chi]
}

# -------------------------------------------------------------------------
# The test proc.

proc assess {count {buckets 100} {procname gen_randmt}} {
    set bin [lrepeat 0 $buckets]
    fill bin $count ::$procname
    set n [expr {$count / $buckets}]
    puts "[sd $bin $n] [chi $bin $n]"
}

# -------------------------------------------------------------------------

if {$::tcl_interactive} {
    puts "try 'assess count ?buckets? ?generator?'"
} else {
    if {[llength $argv] < 1} {
        puts "usage: assess count ?buckets? ?generator?\n\
              eg: assess 100000 100 gen_rand\n\
                  assess 100000 100 gen_randmt"
        exit 1
    }
    catch {eval [list assess] $argv} msg
    puts $msg
}

# -------------------------------------------------------------------------
# Local variables:
#   mode: tcl
#   indent-tabs-mode: nil
# End:

Pat, where do we find that random package? is Random in tcllib ?

PT: I've made your question link to the answer :)

EKB Several tcllib routines use rand() internally, for example math::statistics::random-uniform. In Tcl 8.5 you can have them use another (pseudo-)random number generator, such as the ones listed on Random or the shuffled random number generator in Sequential correlations and the output of rand. For example:
# A silly "random number" generator -- this makes it obvious that the function has changed
proc myrand {} {return 0.50}

# Rename the mathfunc
proc tcl::mathfunc::rand {} {myrand}

Trying it out gives
% math::statistics::random-uniform 0 1 5
0.5 0.5 0.5 0.5 0.5