Random Number States¶
AUTHORS:
Carl Witty (2008-03): new file
This module manages all the available pseudo-random number generators in Sage. (For the rest of the documentation in this module, we will drop the “pseudo”.)
The goal is to allow algorithms using random numbers to be reproducible from one run of Sage to the next, and (to the extent possible) from one machine to the next (even across different operating systems and architectures).
There are two parts to the API. First we will describe the command line oriented API, for setting random number generator seeds. Then we will describe the library API, for people writing Sage library code that uses random numbers.
Command line oriented API¶
We’ll start with the simplest usage: setting fixed random number seeds and showing that these lead to reproducible results.
sage: K.<x> = QQ[]
sage: G = PermutationGroup([[(1,2,3),(4,5)], [(1,2)]])
sage: rgp = Gp()
sage: def gap_randstring(n):
....: current_randstate().set_seed_gap()
....: return gap(n).SCRRandomString()
sage: def rtest():
....: current_randstate().set_seed_gp(rgp)
....: return (ZZ.random_element(1000), RR.random_element(),
....: K.random_element(), G.random_element(),
....: gap_randstring(5),
....: rgp.random(), ntl.ZZ_random(99999),
....: random())
The above test shows the results of six different random number
generators, in three different processes. The random elements from
ZZ
, RR
, and K
all derive from a single GMP-based random number
generator. The random element from G
comes from a GAP subprocess.
The random “string” (5-element binary list) is also from a GAP
subprocess, using the “classical” GAP random generator.
The random number from rgp
is from a Pari/gp subprocess. NTL’s
ZZ_random
uses a separate NTL random number generator in the main
Sage process. And random()
is from a Python random.Random
object.
Here we see that setting the random number seed really does make the results of these random number generators reproducible.
sage: set_random_seed(0)
sage: print(rtest())
(303, -0.266166246380421, 1/6, (1,2), [ 0, 1, 1, 0, 0 ], 265625921, 79302, 0.2450652680687958)
sage: set_random_seed(1)
sage: print(rtest())
(978, 0.0557699430711638, -1/8*x^2 - 1/2*x + 1/2, (1,2,3), [ 1, 0, 0, 0, 1 ], 807447831, 23865, 0.6170498912488264)
sage: set_random_seed(2)
sage: print(rtest())
(207, -0.0141049486533456, 0, (1,3)(4,5), [ 1, 0, 1, 1, 1 ], 1642898426, 16190, 0.9343331114872127)
sage: set_random_seed(0)
sage: print(rtest())
(303, -0.266166246380421, 1/6, (1,2), [ 0, 1, 1, 0, 0 ], 265625921, 79302, 0.2450652680687958)
sage: set_random_seed(1)
sage: print(rtest())
(978, 0.0557699430711638, -1/8*x^2 - 1/2*x + 1/2, (1,2,3), [ 1, 0, 0, 0, 1 ], 807447831, 23865, 0.6170498912488264)
sage: set_random_seed(2)
sage: print(rtest())
(207, -0.0141049486533456, 0, (1,3)(4,5), [ 1, 0, 1, 1, 1 ], 1642898426, 16190, 0.9343331114872127)
Once we’ve set the random number seed, we can check what seed was used. (This is not the current random number state; it does not change when random numbers are generated.)
sage: set_random_seed(12345)
sage: initial_seed()
12345L
sage: print(rtest())
(720, -0.612180244315804, 0, (1,3), [ 1, 0, 1, 1, 0 ], 1911581957, 65175, 0.8043027951758298)
sage: initial_seed()
12345L
If set_random_seed()
is called with no arguments, then a new
seed is automatically selected. On operating systems that support it,
the new seed comes from os.urandom()
; this is intended to be
a truly random (not pseudo-random), cryptographically secure number.
(Whether it is actually cryptographically secure depends on operating
system details that are outside the control of Sage.)
If os.urandom()
is not supported, then the new seed comes
from the current time, which is definitely not cryptographically
secure.
sage: set_random_seed()
sage: r = rtest()
sage: r # random
(909, -0.407373370020575, 6/7*x^2 + 1, (1,2,3)(4,5), 985329107, 21461, 0.30047071049504859)
After setting a new random number seed with set_random_seed()
,
we can use initial_seed()
to see what seed was automatically
selected, and call set_random_seed()
to restart the same
random number sequence.
sage: s = initial_seed()
sage: s # random
336237747258024892084418842839280045662L
sage: set_random_seed(s)
sage: r2 = rtest()
sage: r == r2
True
Whenever Sage starts, set_random_seed()
is called just before
command line interaction starts; so every Sage run starts with a
different random number seed. This seed can be recovered with
initial_seed()
(as long as the user has not set a different
seed with set_random_seed()
), so that the results of this run
can be reproduced in another run; or this automatically selected seed
can be overridden with, for instance, set_random_seed(0)
.
We can demonstrate this startup behavior by running a new instance of Sage as a subprocess.
sage: subsage = Sage()
sage: s = ZZ(subsage('initial_seed()'))
sage: r = ZZ(subsage('ZZ.random_element(2^200)'))
sage: s # random
161165040149656168853863459174502758403
sage: r # random
1273828861620427462924151488498075119241254209468761367941442
sage: set_random_seed(s)
sage: r == ZZ.random_element(2^200)
True
Note that wrappers of all the random number generation methods from
Python’s random
module are available at the Sage command
line, and these wrappers are properly affected by set_random_seed()
.
sage: set_random_seed(0)
sage: random(), getrandbits(20), uniform(5.0, 10.0), normalvariate(0, 1)
(0.111439293741037, 539332L, 8.26785106378383, 1.3893337539828183)
sage: set_random_seed(1)
sage: random(), getrandbits(20), uniform(5.0, 10.0), normalvariate(0, 1)
(0.8294022851874259, 624859L, 5.77894484361117, -0.4201366826308758)
sage: set_random_seed(0)
sage: random(), getrandbits(20), uniform(5.0, 10.0), normalvariate(0, 1)
(0.111439293741037, 539332L, 8.26785106378383, 1.3893337539828183)
That pretty much covers what you need to know for command-line use of this module. Now let’s move to what authors of Sage library code need to know about the module.
Library API¶
First, we’ll cover doctesting. Every docstring now has an implicit
set_random_seed(0)
prepended. Any uses of # random
that
are based on random numbers under the control of this module should be
removed, and the reproducible answers inserted instead.
This practice has two potential drawbacks. First, it increases the work
of maintaining doctests. For instance, in a long docstring that has
many doctests that depend on random numbers, a change near the beginning
(for instance, adding a new doctest) may invalidate all later doctests
in the docstring. To reduce this downside, you may add calls to
set_random_seed(0)
throughout the docstring (in the extreme case,
before every doctest).
Second, the # random
in the doctest served as a signal to the
reader of the docstring that the result was unpredictable and that it
would not be surprising to get a different result when trying out the
examples in the doctest. If a doctest specifically refers to
ZZ.random_element()
(for instance), this is presumably enough
of a signal to render this function of # random
unnecessary.
However, some doctests are not obviously (from the name) random, but
do depend on random numbers internally, such as the
composition_series
method of a PermutationGroup
. In these cases, the convention is to insert
the following text at the beginning of the EXAMPLES
section.
These computations use pseudo-random numbers, so we set the
seed for reproducible testing.
sage: set_random_seed(0)
Note that this call to set_random_seed(0)
is redundant, since
set_random_seed(0)
is automatically inserted at the beginning
of every docstring. However, it makes the example reproducible for somebody
who just types the lines from the doctest and doesn’t know about the
automatic set_random_seed(0)
.
Next, let’s cover setting the random seed from library code. The
first rule is that library code should never call
set_random_seed()
. This function is only for command-line
use. Instead, if the library code wants to use a different random
seed, it should use with seed(s):
. This will use the new seed
within the scope of the with
statement, but will revert to the previous
seed once the with
statement is completed. (Or the library can use
with seed():
to get a seed automatically selected using
os.urandom()
or the current time, in the same way as described for
set_random_seed()
above.)
Ideally, using with seed(s):
should not affect the outer random
number sequence at all; we will call this property “isolation.” We
achieve isolation for most, but not all, of the random number generators
in Sage (we fail for generators, such as NTL, that do not provide an API
to retrieve the current random number state).
We’ll demonstrate isolation. First, we show the sequence of random numbers
that you get without intervening with seed
.
sage: set_random_seed(0)
sage: r1 = rtest(); print(r1)
(303, -0.266166246380421, 1/6, (1,2), [ 0, 1, 1, 0, 0 ], 265625921, 79302, 0.2450652680687958)
sage: r2 = rtest(); print(r2)
(443, 0.185001351421963, -2, (1,3), [ 0, 0, 1, 1, 0 ], 53231108, 8171, 0.28363811590618193)
We get slightly different results with an intervening with seed
.
sage: set_random_seed(0)
sage: r1 == rtest()
True
sage: with seed(1): rtest()
(978, 0.0557699430711638, -1/8*x^2 - 1/2*x + 1/2, (1,2,3), [ 1, 0, 0, 0, 1 ], 807447831, 23865, 0.6170498912488264)
sage: r2m = rtest(); r2m
(443, 0.185001351421963, -2, (1,3), [ 0, 0, 1, 1, 0 ], 53231108, 51295, 0.28363811590618193)
sage: r2m == r2
False
We can see that r2
and r2m
are the same except for the
call to ntl.ZZ_random()
, which produces different results
with and without the with seed
.
However, we do still get a partial form of isolation, even in this case, as we see in this example:
sage: set_random_seed(0)
sage: r1 == rtest()
True
sage: with seed(1):
....: print(rtest())
....: print(rtest())
(978, 0.0557699430711638, -1/8*x^2 - 1/2*x + 1/2, (1,2,3), [ 1, 0, 0, 0, 1 ], 807447831, 23865, 0.6170498912488264)
(181, 0.607995392046754, -x + 1/2, (2,3)(4,5), [ 1, 0, 0, 1, 1 ], 1010791326, 9693, 0.5691716786307407)
sage: r2m == rtest()
True
The NTL results after the with seed
don’t depend on how many
NTL random numbers were generated inside the with seed
.
sage: set_random_seed(0) sage: r1 == rtest() True sage: with seed(1): ….: rtest() (978, 0.0557699430711638, -1/8*x^2 - 1/2*x + 1/2, (1,2,3), [ 1, 0, 0, 0, 1 ], 807447831, 23865, 0.6170498912488264) sage: r2m == rtest() True
(In general, the above code is not exactly equivalent to the with
statement, because if an exception happens in the body, the real
with
statement will pass the exception information as parameters to
the __exit__
method. However, our __exit__
method
ignores the exception information anyway, so the above is equivalent in
our case.)
Generating random numbers in library code¶
Now we come to the last part of the documentation: actually generating
random numbers in library code. First, the easy case. If you generate
random numbers only by calling other Sage library code (such as
random_element
methods on parents), you don’t need to do
anything special; the other code presumably already interacts with
this module correctly.
Otherwise, it depends on what random number generator you want to use.
gmp_randstate_t
– If you want to use some random number generator that takes agmp_randstate_t
(likempz_urandomm
ormpfr_urandomb
), then use code like the following:from sage.misc.randstate cimport randstate, current_randstate ... cdef randstate rstate = current_randstate()
Then a
gmp_randstate_t
is available asrstate.gmp_state
.Fetch the current
randstate
withcurrent_randstate()
in every function that wants to use it; don’t cache it globally or in a class. (Such caching would breakset_random_seed
).Python
– If you want to use the random number generators from therandom
module, you have two choices. The slightly easier choice is to import functions fromsage.misc.prandom
; for instance, you can simply replacefrom random import randrange
withfrom sage.misc.prandom import randrange
. However, this is slightly less efficient, because the wrappers insage.misc.prandom
look up the currentrandstate
on each call. If you’re generating many random numbers in a row, it’s faster to instead dofrom sage.misc.randstate import current_randstate ... randrange = current_randstate().python_random().randrange
Fetch the current
randstate
withcurrent_randstate()
in every function that wants to use it; don’t cache therandstate
, theRandom
object returned bypython_random
, or the bound methods on thatRandom
object globally or in a class. (Such caching would breakset_random_seed
).GAP
– If you are calling code in GAP that uses random numbers, callset_seed_gap
at the beginning of your function, like this:from sage.misc.randstate import current_randstate ... current_randstate().set_seed_gap()
Fetch the current
randstate
withcurrent_randstate()
in every function that wants to use it; don’t cache it globally or in a class. (Such caching would breakset_random_seed
).Pari
– If you are calling code in the Pari library that uses random numbers, callset_seed_pari
at the beginning of your function, like this:from sage.misc.randstate import current_randstate ... current_randstate().set_seed_pari()
Fetch the current
randstate
withcurrent_randstate()
in every function that wants to use it; don’t cache it globally or in a class. (Such caching would breakset_random_seed
).Pari/gp
– If you are calling code in a Pari/gp subprocess that uses random numbers, callset_seed_gp
at the beginning of your function, like this:from sage.misc.randstate import current_randstate ... current_randstate().set_seed_gp()
This will set the seed in the gp process in
sage.interfaces.gp.gp
. If you have a different gp process, say in the variablemy_gp
, then callset_seed_gp(my_gp)
instead.Fetch the current
randstate
withcurrent_randstate()
in every function that wants to use it; don’t cache it globally or in a class. (Such caching would breakset_random_seed
).NTL
– If you are calling code in the NTL library that uses random numbers, callset_seed_ntl
at the beginning of your function, like this:from sage.misc.randstate import current_randstate ... current_randstate().set_seed_ntl(False)
Fetch the current
randstate
withcurrent_randstate()
in every function that wants to use it; don’t cache it globally or in a class. (Such caching would breakset_random_seed
).libc
– If you are writing code that calls the libc functionrandom()
: don’t! Therandom()
function does not give reproducible results across different operating systems, so we can’t make portable doctests for the results. Instead, do:from sage.misc.randstate cimport random
The
random()
function insage.misc.randstate
gives a 31-bit random number, but it uses thegmp_randstate_t
in the currentrandstate
, so it is portable. (This range was chosen for two reasons: it matches the range of random() on 32-bit and 64-bit Linux, although not Solaris; and it’s the largest range of nonnegative numbers that fits in a 32-bit signed integer.)However, you may still need to set the libc random number state; for instance, if you are wrapping a library that uses
random()
internally and you don’t want to change the library. In that case, callset_seed_libc
at the beginning of your function, like this:from sage.misc.randstate import current_randstate ... current_randstate().set_seed_libc(False)
Fetch the current
randstate
withcurrent_randstate()
in every function that wants to use it; don’t cache it globally or in a class. (Such caching would breakset_random_seed
).
Classes and methods¶
- sage.misc.randstate.benchmark_libc()¶
This function was used to test whether moving from libc to GMP’s Mersenne Twister for random numbers would be a significant slowdown.
EXAMPLES:
sage: from sage.misc.randstate import benchmark_libc, benchmark_mt sage: timeit('benchmark_libc()') # random 125 loops, best of 3: 1.95 ms per loop sage: timeit('benchmark_mt()') # random 125 loops, best of 3: 2.12 ms per loop
- sage.misc.randstate.benchmark_mt()¶
This function was used to test whether moving from libc to GMP’s Mersenne Twister for random numbers would be a significant slowdown.
EXAMPLES:
sage: from sage.misc.randstate import benchmark_libc, benchmark_mt sage: timeit('benchmark_libc()') # random 125 loops, best of 3: 1.95 ms per loop sage: timeit('benchmark_mt()') # random 125 loops, best of 3: 2.11 ms per loop
- sage.misc.randstate.current_randstate()¶
Return the current random number state.
EXAMPLES:
sage: set_random_seed(0) sage: current_randstate() <sage.misc.randstate.randstate object at 0x...> sage: current_randstate().python_random().random() 0.111439293741037
- sage.misc.randstate.initial_seed()¶
Returns the initial seed used to create the current
randstate
.EXAMPLES:
sage: set_random_seed(42) sage: initial_seed() 42L
If you set a random seed (by failing to specify the seed), this is how you retrieve the seed actually chosen by Sage. This can also be used to retrieve the seed chosen for a new Sage run (if the user has not used
set_random_seed()
).sage: set_random_seed() sage: initial_seed() # random 121030915255244661507561642968348336774L
- sage.misc.randstate.random()¶
Returns a 31-bit random number. Intended as a drop-in replacement for the libc
random()
function.EXAMPLES:
sage: set_random_seed(31) sage: from sage.misc.randstate import random sage: random() 32990711
- class sage.misc.randstate.randstate¶
Bases:
object
The
randstate
class. This class keeps track of random number states and seeds. Typesage.misc.randstate?
for much more information on random numbers in Sage.- ZZ_seed()¶
When called on the current
randstate
, returns a 128-bitInteger
suitable for seeding another random number generator.EXAMPLES:
sage: set_random_seed(1414) sage: current_randstate().ZZ_seed() 48314508034782595865062786044921182484
- c_rand_double()¶
Returns a random floating-point number between 0 and 1.
EXAMPLES:
sage: set_random_seed(2718281828) sage: current_randstate().c_rand_double() 0.22437207488974298
- c_random()¶
Returns a 31-bit random number. Intended for internal use only; instead of calling
current_randstate().c_random()
, it is equivalent (but probably faster) to call therandom
method of thisrandstate
class.EXAMPLES:
sage: set_random_seed(1207) sage: current_randstate().c_random() 2008037228
We verify the equivalence mentioned above.
sage: from sage.misc.randstate import random sage: set_random_seed(1207) sage: random() 2008037228
- long_seed()¶
When called on the current
randstate
, returns a 128-bit Python long suitable for seeding another random number generator.EXAMPLES:
sage: set_random_seed(1618) sage: current_randstate().long_seed() 256056279774514099508607350947089272595L
- python_random(cls=None, seed=None)¶
Return a
random.Random
object. The first time it is called on a givenrandstate
, a newrandom.Random
is created (seeded from the currentrandstate
); the same object is returned on subsequent calls.It is expected that
python_random
will only be called on the currentrandstate
.INPUT:
cls
– (optional) a class with the same interface asrandom.Random
(e.g. a subclass thereof) to use as the Python RNG interface. Otherwise the standardrandom.Random
is used.seed
– (optional) an integer to seed therandom.Random
instance with upon creation; if not specified it is seeded usingZZ.random_element(1 << 128)
.
EXAMPLES:
sage: set_random_seed(5) sage: rnd = current_randstate().python_random() sage: rnd.random() 0.013558022446944151 sage: rnd.randrange(1000) 544
- seed()¶
Return the initial seed of a
randstate
object. (This is not the current state; it does not change when you get random numbers.)EXAMPLES:
sage: set_random_seed(0) sage: from sage.misc.randstate import randstate sage: r = randstate(314159) sage: r.seed() 314159L sage: r.python_random().random() 0.111439293741037 sage: r.seed() 314159L
- set_seed_gap()¶
Checks to see if
self
was the most recentrandstate
to seed the GAP random number generator. If not, seeds the generator.EXAMPLES:
sage: set_random_seed(99900000999) sage: current_randstate().set_seed_gap() sage: gap.Random(1, 10^50) 1496738263332555434474532297768680634540939580077 sage: gap(35).SCRRandomString() [ 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1 ]
- set_seed_gp(gp=None)¶
Checks to see if
self
was the most recentrandstate
to seed the random number generator in the given instance of gp. (If no instance is given, uses the one ingp
.) If not, seeds the generator.EXAMPLES:
sage: set_random_seed(987654321) sage: current_randstate().set_seed_gp() sage: gp.random() 23289294
- set_seed_libc(force)¶
Checks to see if
self
was the most recentrandstate
to seed the libc random number generator. If not, seeds the libc random number generator. (Do not use the libc random number generator if you have a choice; its randomness is poor, and the random number sequences it produces are not portable across operating systems.)If the argument
force
isTrue
, seeds the generator unconditionally.EXAMPLES:
sage: from sage.misc.randstate import _doctest_libc_random sage: set_random_seed(0xBAD) sage: current_randstate().set_seed_libc(False) sage: _doctest_libc_random() # random 1070075918
- set_seed_ntl(force)¶
Checks to see if
self
was the most recentrandstate
to seed the NTL random number generator. If not, seeds the generator. If the argumentforce
isTrue
, seeds the generator unconditionally.EXAMPLES:
sage: set_random_seed(2008)
This call is actually redundant;
ntl.ZZ_random()
will seed the generator itself. However, we put the call in to make the coverage tester happy.sage: current_randstate().set_seed_ntl(False) sage: ntl.ZZ_random(10^40) 1495283511775355459459209288047895196007
- set_seed_pari()¶
Checks to see if
self
was the most recentrandstate
to seed the Pari random number generator. If not, seeds the generator.Note
Since pari 2.4.3, pari’s random number generator has changed a lot. the seed output by getrand() is now a vector of integers.
EXAMPLES:
sage: set_random_seed(5551212) sage: current_randstate().set_seed_pari() sage: pari.getrand().type() 't_INT'
- sage.misc.randstate.seed¶
alias of
sage.misc.randstate.randstate
- sage.misc.randstate.set_random_seed(seed=None)¶
Set the current random number seed from the given
seed
(which must be coercible to a Python long).If no seed is given, then a seed is automatically selected using
os.urandom()
if it is available, or the current time otherwise.Type
sage.misc.randstate?
for much more information on random numbers in Sage.This function is only intended for command line use. Never call this from library code; instead, use
with seed(s):
.Note that setting the random number seed to 0 is much faster than using any other number.
EXAMPLES:
sage: set_random_seed(5) sage: initial_seed() 5L