Version 48 of rand

Updated 2008-01-05 12:27:38 by torsten

Purpose: Help about the expr rand function in Tcl.

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 - instead, it is one of the many functions documented on http://purl.org/tcl/home/man/tcl8.4/TclCmd/expr.htm .

See also: srand


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? Secure-Programs-HOWTO [L1 ])

For a cryptographically useful rand() see Random

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.


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 the bug.

http://sourceforge.net/tracker/?group_id=10894&atid=110894&func=detail&aid=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 [L2 ] 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)}}

Bruce Hartweg refers you to True Random Numbers for an interface to getting truly random data

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 [L3 ] - Eric Amundsen says that this link was broken as of March 31 '03, perhaps this [L4 ] is what was intended?

PT 01-Apr-03: 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 03-Apr-03: RandMT the Mersenne Twister based rand() package is now available through cvs at sourceforge as part of the tclsoap project:

 cvs -d:pserver:[email protected]:/cvsroot/tclsoap co RandMT

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

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

PT 15-Apr-03: 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 <[email protected]>
 #
 # 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 :)


See also: