''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''' [http://www.tldp.org/HOWTO/Secure-Programs-HOWTO/random-numbers.html])

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 [http://82.168.209.239] 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 [http://www.coyotegulch.com/algorithm/ac0003/TwistedRoad.html] - [Eric Amundsen] says that this link was broken as of March 31 '03, perhaps this [http://www.coyotegulch.com/algorithm/libcoyote/TwistedRoad/TwistedRoad.html] 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:anonymous@cvs.tclsoap.sourceforge.net:/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 <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 :)
----
See also:
   * [Mersenne Twister]
 
----
!!!!!!
%| [Category Function] | [Category Mathematics] | [Math function help] |%
!!!!!!