<p>In this chapter we describe some fundamental mechanisms to produce (pseudo-) random elements that are used later in Chapter <a href="chap7_mj.html#X7DF379C283FE23EF"><span class="RefLink">7</span></a> about searching in groups and orbits.</p>
<p>The mutable object <var class="Arg">ob</var> is changed in place. The value afterwards is random. The optional second argument <var class="Arg">rs</var> must be a random source and the random numbers used to randomize <var class="Arg">ob</var> are created using the random source <var class="Arg">rs</var> (see <a href="../../../doc/ref/chap14_mj.html#X85361FAE8088C006"><span class="RefLink">Reference: Random Sources</span></a>). If <var class="Arg">rs</var> is not given, then the global <strong class="pkg">GAP</strong> random number generator is used.</p>
<p>Currently, there are <code class="func">Randomize</code> methods for compressed vectors and compressed matrices over finite fields. See also the <strong class="pkg">cvec</strong> package for methods for <code class="code">cvec</code>s and <code class="code">cmat</code>s.</p>
<p>For vectors and one-dimensional subspaces there are two special functions to create a list of random objects:</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MakeRandomVectors</code>( <var class="Arg">sample</var>, <var class="Arg">number</var>[, <var class="Arg">rs</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a list of random vectors</p>
<p><var class="Arg">sample</var> must be a vector for the mutable copies of which <code class="func">Randomize</code> (<a href="chap6_mj.html#X83DD8B39864A2C94"><span class="RefLink">6.1-1</span></a>) is applicable and <var class="Arg">number</var> must be a positive integer. If given, <var class="Arg">rs</var> must be a random source. This function creates a list of <var class="Arg">number</var> random vectors with the same type as <var class="Arg">sample</var> using <code class="func">Randomize</code> (<a href="chap6_mj.html#X83DD8B39864A2C94"><span class="RefLink">6.1-1</span></a>). For the creation of random numbers the random source <var class="Arg">rs</var> is used or, if not given, the global <strong class="pkg">GAP</strong> random number generator.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MakeRandomLines</code>( <var class="Arg">sample</var>, <var class="Arg">number</var>[, <var class="Arg">rs</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a list of normalised random vectors</p>
<p><var class="Arg">sample</var> must be a vector for the mutable copies of which <code class="func">Randomize</code> (<a href="chap6_mj.html#X83DD8B39864A2C94"><span class="RefLink">6.1-1</span></a>) is applicable and <var class="Arg">number</var> must be a positive integer. If given, <var class="Arg">rs</var> must be a random source. This function creates a list of <var class="Arg">number</var> normalised random vectors with the same type as <var class="Arg">sample</var> using <code class="func">Randomize</code> (<a href="chap6_mj.html#X83DD8B39864A2C94"><span class="RefLink">6.1-1</span></a>). <q>Normalised</q> here means that the first non-zero entry in the vector is equal to <span class="SimpleMath">\(1\)</span>. For the creation of random numbers the random source <var class="Arg">rs</var> is used or, if not given, the global <strong class="pkg">GAP</strong> random number generator.</p>
<p>For computations in finite groups product replacement algorithms are a viable method of generating pseudo-random elements. This section describes a framework and an object type to provide these algorithms. Roughly speaking a <q>product replacer object</q> is something that is created with a list of group generators and produces a sequence of pseudo random group elements using some random source for random numbers.</p>
<p><var class="Arg">gens</var> must be a list of group generators. If given, <var class="Arg">opt</var> is a <strong class="pkg">GAP</strong> record with options. The operation creates a new product replacer object producing pseudo random elements in the group generated by the generators <var class="Arg">gens</var>.</p>
<p>The exact algorithm used is explained below after the description of the options.</p>
<p>The following components in the options record have a defined meaning:</p>
<dl>
<dt><strong class="Mark"><code class="code">randomsource</code></strong></dt>
<dd><p>A random sourceobject that is used to generate the random numbers used. If none is specified the global <strong class="pkg">GAP</strong> random number generator is used.</p>
</dd>
<dt><strong class="Mark"><code class="code">scramble</code></strong></dt>
<dd><p>The <code class="code">scramble</code> value in the algorithm described below can be set using this option. The default value is <span class="SimpleMath">\(30\)</span>.</p>
</dd>
<dt><strong class="Mark"><code class="code">scramblefactor</code></strong></dt>
<dd><p>The <code class="code">scramblefactor</code> value in the algorithm described below can be set using this option. The default value is <span class="SimpleMath">\(4\)</span>.</p>
</dd>
<dt><strong class="Mark"><code class="code">addslots</code></strong></dt>
<dd><p>The <code class="code">addslots</code> value in the algorithm described below can be set using this option. The default value is <span class="SimpleMath">\(5\)</span>.</p>
</dd>
<dt><strong class="Mark"><code class="code">maxdepth</code></strong></dt>
<dd><p>If <code class="code">maxdepth</code> is set, then the production of pseudo random elements starts all over whenever <code class="code">maxdepth</code> product replacements have been performed. The rationale behind this is that the elements created should be evenly distributed but that the expressions in the generators should not be too long. A good compromise is usually to set <code class="code">maxdepth</code> to <span class="SimpleMath">\(300\)</span> or <span class="SimpleMath">\(400\)</span>.</p>
</dd>
<dt><strong class="Mark"><code class="code">noaccu</code></strong></dt>
<dd><p>Without this option set to <code class="keyw">true</code> the <q>rattle</q> version of product replacement is used which involves an accumulator and uses two or three products per random element. To use the <q>shake</q> version with only one or two product replacement per random element set this component to <code class="keyw">true</code>. The exact number of multiplications per random element also depends on the value of the <code class="code">accelerator</code> component.</p>
</dd>
<dt><strong class="Mark"><code class="code">normalin</code></strong></dt>
<dd><p>There is a variant of the product replacement algorithm that produces elements in the normal closure of the group generated by a list of elements. It needs random elements in the ambient group in which the normal closure is defined. This is implemented here by setting the <code class="code">normalin</code> component to a product replacer object working in the ambient group. In every step two elements <span class="SimpleMath">\(a\)</span> and <span class="SimpleMath">\(b\)</span> are picked and then <span class="SimpleMath">\(a\)</span> is either replaced by <span class="SimpleMath">\(a*b^c\)</span> or <span class="SimpleMath">\(b^c*a\)</span> (with equal probability), where <span class="SimpleMath">\(c\)</span> is a random element from the ambient group produced by the product replacer in the <code class="code">normalin</code> component. It is recommended to switch off the accumulator and accelerator in the product replacer object for the ambient group. Then to produce one random element in the normal closure needs four multiplications.</p>
</dd>
<dt><strong class="Mark"><code class="code">accelerator</code></strong></dt>
<dd><p>If this option is set to <code class="keyw">true</code> (which is the default), then the accelerator is used. This means that in each step two product replacement steps are performed, where both involve one distinguished slot called the <q>captain</q>. The idea is that the current <q>team</q> of random elements uses one amongst them more often to increase the length of the words produced. See below for details of the algorithm with and without accelerator.</p>
</dd>
<dt><strong class="Mark"><code class="code">retirecaptain</code></strong></dt>
<dd><p>If this component is bound to a positive integer then the captain retires after so many steps of the algorithm. This is to use only two multiplications for each random element in the long run after proper mixing. The default value for <code class="code">retirecaptain</code> is twice the scrambling time.</p>
</dd>
<dt><strong class="Mark"><code class="code">accus</code></strong></dt>
<dd><p>This component (default is 5) is the number of accumulators to use in the rattle variant. All accus are used in a round robin fashion. The purpose of multiple accus is to have a greater stochastical independence of adjacent random elements in the sequence.</p>
</dd>
</dl>
<p>The algorithm used does the following: A list of <code class="code">Length(</code><var class="Arg">gens</var><code class="code">)+addslots</code> elements is created that starts with the elements <var class="Arg">gens</var> and is filled up with random generators from <var class="Arg">gens</var>. This element is called the <q>team</q>. A product replacement without accelerator randomly chooses two elements in the list and replaces one of them by the product of the two. If an accelerator is used, then one product replacement step randomly chooses two slots <span class="SimpleMath">\(i\)</span> and <span class="SimpleMath">\(j\)</span> where <span class="SimpleMath">\(i,j > 1\)</span> but <span class="SimpleMath">\(i=j\)</span> is possible. Then first <span class="SimpleMath">\(l[1]\)</span> is replaced by <span class="SimpleMath">\(l[1]*l[i]\)</span> and after that <span class="SimpleMath">\(l[j]\)</span> is replaced by <span class="SimpleMath">\(l[j]*l[1]\)</span>. The first team member is called the <q>captain</q>, so the captain is involved in every product replacement.</p>
<p>One step in the algorithm is to do one product replacement followed by post-multiplying the result to the accumulator if one (or more) is used. Multiple accus (see the <code class="code">accus</code> component) are used in a round robin fashion.</p>
<p>First <code class="code">Maximum(Length(</code><var class="Arg">gens</var><code class="code">)*scramblefactor,scramble)</code> steps are performed. After this initialisation for every random element requested one step is done and the resulting element returned.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Next</code>( <var class="Arg">pr</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: a (pseudo-) random group element g</p>
<p><var class="Arg">pr</var> must be a product replacer object. This operation makes the object generate the next random element andreturn it.</p>
<p><var class="Arg">pr</var> must be a product replacer object. This operation resets the object in the sense that it resets the product replacement back to the state it had after scrambling. Note that since the random source is not reset, the product replacer object will return another sequence of random elements than before.</p>
<p><var class="Arg">pr</var> must be a product replacer object. This operation adds the new generator <var class="Arg">el</var> to the product replacer without needing a completely new initialisation phase. From after this call on the product replacer will generate random elements in the group generated by the old generators and the new element <var class="Arg">el</var>.</p>
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
