[1X6 Random elements[0X In this chapter we describe some fundamental mechanisms to produce (pseudo-) random elements that are used later in Chapter [14X7[0m about searching in groups and orbits. [1X6.1 Randomizing mutable objects[0X For certain types of mutable objects one can get a "random one" by calling the following operation: [1X6.1-1 Randomize[0m [2X> Randomize( [0X[3Xob[, rs][0X[2X ) ___________________________________________[0Xoperation [6XReturns:[0X nothing The mutable object [3Xob[0m is changed in place. The value afterwards is random. The optional second argument [3Xrs[0m must be a random source and the random numbers used to randomize [3Xob[0m are created using the random source [3Xrs[0m (see [14X'Reference: Random Sources'[0m). If [3Xrs[0m is not given, then the global [5XGAP[0m random number generator is used. Currently, there are [2XRandomize[0m methods for compressed vectors and compressed matrices over finite fields. See also the [5Xcvec[0m package for methods for [10Xcvec[0ms and [10Xcmat[0ms. For vectors and one-dimensional subspaces there are two special functions to create a list of random objects: [1X6.1-2 MakeRandomVectors[0m [2X> MakeRandomVectors( [0X[3Xsample, number[, rs][0X[2X ) ________________________[0Xfunction [6XReturns:[0X a list of random vectors [3Xsample[0m must be a vector for the mutable copies of which [2XRandomize[0m ([14X6.1-1[0m) is applicable and [3Xnumber[0m must be a positive integer. If given, [3Xrs[0m must be a random source. This function creates a list of [3Xnumber[0m random vectors with the same type as [3Xsample[0m using [2XRandomize[0m ([14X6.1-1[0m). For the creation of random numbers the random source [3Xrs[0m is used or, if not given, the global [5XGAP[0m random number generator. [1X6.1-3 MakeRandomLines[0m [2X> MakeRandomLines( [0X[3Xsample, number[, rs][0X[2X ) __________________________[0Xfunction [6XReturns:[0X a list of normalised random vectors [3Xsample[0m must be a vector for the mutable copies of which [2XRandomize[0m ([14X6.1-1[0m) is applicable and [3Xnumber[0m must be a positive integer. If given, [3Xrs[0m must be a random source. This function creates a list of [3Xnumber[0m normalised random vectors with the same type as [3Xsample[0m using [2XRandomize[0m ([14X6.1-1[0m). "Normalised" here means that the first non-zero entry in the vector is equal to 1. For the creation of random numbers the random source [3Xrs[0m is used or, if not given, the global [5XGAP[0m random number generator. [1X6.2 Product replacement[0X 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 "product replacer object" 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. [1X6.2-1 ProductReplacer[0m [2X> ProductReplacer( [0X[3Xgens[, opt][0X[2X ) __________________________________[0Xoperation [6XReturns:[0X a new product replacer object [3Xgens[0m must be a list of group generators. If given, [3Xopt[0m is a [5XGAP[0m record with options. The operation creates a new product replacer object producing pseudo random elements in the group generated by the generators [3Xgens[0m. The exact algorithm used is explained below after the description of the options. The following components in the options record have a defined meaning: [8X[10Xrandomsource[0m[8X[0m A random source object that is used to generate the random numbers used. If none is specified the global [5XGAP[0m random number generator is used. [8X[10Xscramble[0m[8X[0m The [10Xscramble[0m value in the algorithm described below can be set using this option. The default value is 100. [8X[10Xscramblefactor[0m[8X[0m The [10Xscramblefactor[0m value in the algorithm described below can be set using this option. The default value is 10. [8X[10Xaddslots[0m[8X[0m The [10Xaddslots[0m value in the algorithm described below can be set using this option. The default value is 10. [8X[10Xmaxdepth[0m[8X[0m If [10Xmaxdepth[0m is set, then the production of pseudo random elements starts all over whenever [10Xmaxdepth[0m 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 [10Xmaxdepth[0m to 200 or 300. [8X[10Xnoaccu[0m[8X[0m Without this option set to [9Xtrue[0m the "rattle" version of product replacement is used which involves an accumulator and uses two products per random element. To use the "shake" version with only one product replacement per random element set this component to [9Xtrue[0m. [8X[10Xnormalin[0m[8X[0m 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 [10Xnormalin[0m component to a product replacer object working in the ambient group. It is recommended to switch off the accumulator in the product replacer object for the ambient group. Then to produce one random element in the normal closure needs three multiplications. The algorithm used does the following: A list of [10XLength([0m[3Xgens[0m[10X)+addslots[0m elements is created that starts with the elements [3Xgens[0m and is filled up with random generators from [3Xgens[0m. A product replacement randomly chooses two elements in the list and replaces one of them by the product of the two. One step in the algorithm is to do one product replacement followed by post-multiplying the result to the accumulator if one is used. First [10XMaximum(Length([0m[3Xgens[0m[10X)*scramblefactor,scramble)[0m steps are performed. After this initialisation for every random element requested one step is done done and the resulting element returned. [1X6.2-2 Next[0m [2X> Next( [0X[3Xpr[0X[2X ) ______________________________________________________[0Xoperation [6XReturns:[0X a (pseudo-) random group element g [3Xpr[0m must be a product replacer object. This operation makes the object generate the next random element and return it. [1X6.2-3 Reset[0m [2X> Reset( [0X[3Xpr[0X[2X ) _____________________________________________________[0Xoperation [6XReturns:[0X nothing [3Xpr[0m must be a product replacer object. This operation resets the object in the sense that it resets its random source (see [2XReset[0m ([14XReference: Reset[0m)) and reinitialises the random element generation as described above.