Linear feedback shift register (LFSR) random number generators [147], [124], [187], produce numbers by generating a sequence of bits from a linear recurrence modulo 2, and forming fractional numbers by taking blocks of successive bits. More...
Public Member Functions | |
| CycleBasedLFSR (int step1, int nbcoeff1, int [] nocoeff1) | |
| CycleBasedLFSR (int step1, int step2, int nbcoeff1, int nbcoeff2, int [] nocoeff1, int [] nocoeff2) | |
| Constructs a point set based on a combination of two polynomials in base 2 with \(2^{k_1 + k_2}\) points. More... | |
| CycleBasedLFSR (String filename, int no) | |
Constructs a point set after reading its parameters from file filename; the parameters associated with number no of filename corresponds to the no-th polynomial. More... | |
| String | toString () |
| This method returns a string containing the polynomials and the stepping parameters. | |
 Public Member Functions inherited from CycleBasedPointSetBase2 | |
| double | getCoordinate (int i, int j) |
| PointSetIterator | iterator () |
| void | addRandomShift (int d1, int d2, RandomStream stream) |
Adds a random digital shift in base 2 to all the points of the point set, using stream stream to generate the random numbers, for coordinates d1 to d2 - 1. More... | |
| void | clearRandomShift () |
| Erases the current digital random shift, if any. | |
| String | formatPoints () |
| Public Member Functions inherited from CycleBasedPointSet | |
| double | getCoordinate (int i, int j) |
| void | addRandomShift (int d1, int d2, RandomStream stream) |
Same as the same method in PointSet. More... | |
| void | clearRandomShift () |
| Erases the current random shift, if any. | |
| int | getDimension () |
| PointSetIterator | iterator () |
| String | toString () |
| String | formatPoints () |
| Public Member Functions inherited from PointSet | |
| int | getDimension () |
| Returns the dimension (number of available coordinates) of the points. More... | |
| int | getNumPoints () |
| Returns the number of points. More... | |
| abstract double | getCoordinate (int i, int j) |
| Returns \(u_{i,j}\), the coordinate \(j\) of the point \(i\). More... | |
| PointSetIterator | iterator () |
| Constructs and returns a point set iterator. More... | |
| void | randomize (PointSetRandomization rand) |
Randomizes this point set using the given rand. More... | |
| void | addRandomShift (int d1, int d2, RandomStream stream) |
By default, this method generates a random shift in the protected double[] array shift, to be used eventually for a random shift modulo 1. More... | |
| void | addRandomShift (RandomStream stream) |
Same as addRandomShift(0, dim, stream), where dim is the dimension of the point set. More... | |
| void | addRandomShift (int d1, int d2) |
Refreshes the random shift (generates new uniform values for the random shift coordinates) for coordinates d1 to d2-1, using the saved shiftStream. | |
| void | addRandomShift () |
Same as addRandomShift(0, dim), where dim is the dimension of the point set. | |
| void | clearRandomShift () |
| Erases the current random shift, if any. | |
| String | toString () |
| Formats a string that contains information about the point set. More... | |
| String | formatPoints () |
| Same as invoking formatPoints(n, d) with \(n\) and \(d\) equal to the number of points and the dimension of this object, respectively. More... | |
| String | formatPoints (int n, int d) |
| Formats a string that displays the same information as returned by toString, together with the first \(d\) coordinates of the first \(n\) points. More... | |
| String | formatPoints (PointSetIterator iter) |
| Same as invoking formatPoints(iter, n, d) with \(n\) and \(d\) equal to the number of points and the dimension, respectively. More... | |
| String | formatPoints (PointSetIterator iter, int n, int d) |
Same as invoking formatPoints(n, d), but prints the points by calling iter repeatedly. More... | |
| String | formatPointsBase (int b) |
| Similar to formatPoints(), but the points coordinates are printed in base \(b\). More... | |
| String | formatPointsBase (int n, int d, int b) |
| Similar to formatPoints(n, d), but the points coordinates are printed in base \(b\). More... | |
| String | formatPointsBase (PointSetIterator iter, int b) |
| Similar to formatPoints(iter), but the points coordinates are printed in base \(b\). More... | |
| String | formatPointsBase (PointSetIterator iter, int n, int d, int b) |
| Similar to formatPoints(iter, n, d), but the points coordinates are printed in base \(b\). More... | |
| String | formatPointsNumbered () |
| Same as invoking formatPointsNumbered(n, d) with \(n\) and \(d\) equal to the number of points and the dimension, respectively. More... | |
| String | formatPointsNumbered (int n, int d) |
| Same as invoking formatPoints(n,d), except that the points are numbered. More... | |
Additional Inherited Members | |
| Protected Member Functions inherited from CycleBasedPointSet | |
| void | addCycle (AbstractList c) |
Adds the cycle c to the list of all cycles. More... | |
| Protected Attributes inherited from CycleBasedPointSetBase2 | |
| int | numBits |
| double | normFactor |
| Protected Attributes inherited from CycleBasedPointSet | |
| int | numCycles = 0 |
| ObjectArrayList | cycles = new ObjectArrayList() |
| Protected Attributes inherited from PointSet | |
| double | EpsilonHalf = 1.0 / Num.TWOEXP[55] |
| To avoid 0 for nextCoordinate when random shifting, we add this to each coordinate. | |
| int | dim = 0 |
| Dimension of the points. | |
| int | numPoints = 0 |
| Number of points. | |
| int | dimShift = 0 |
| Current dimension of the shift. More... | |
| int | capacityShift = 0 |
| Number of array elements in the shift vector, always >= dimShift. | |
| double [] | shift |
This is the shift vector as a double[] array, which contains the current random shift in case we apply a random shift modulo 1. More... | |
| RandomStream | shiftStream |
| Stream used to generate the random shifts. More... | |
| Static Protected Attributes inherited from PointSet | |
| static final int | MAXBITS = 31 |
| Since Java has no unsigned type, the 32nd bit cannot be used efficiently, so we have only 31 bits. More... | |
Detailed Description
Linear feedback shift register (LFSR) random number generators [147], [124], [187], produce numbers by generating a sequence of bits from a linear recurrence modulo 2, and forming fractional numbers by taking blocks of successive bits.
More precisely, let \(\mathbb F_2\) denote the finite field with two elements (say, 0 and 1). Let \(P(z) = z^k - a_1 z^{k-1} - \cdots- a_k\) be a polynomial with coefficients in \(\mathbb F_2\), and consider the recurrence
\[ x_n = a_1 x_{n-1} + \cdots+ a_k x_{n-k}, \tag{mrg} \]
whose characteristic polynomial is \(P(z)\). It should be understood that in (mrg) all computations are performed in \(\mathbb F_2\) (this can be identified with working in integer arithmetic modulo 2). Suppose that \(\mathbf{s}_0 = (x_0,…,x_{k-1})\in\{0,1\}^k\) is fixed and define
\[ u_n = \sum_{i=1}^L x_{ns+i-1} 2^{-i}, \tag{taus} \]
where \(s\) and \(L\) are positive integers. If \(P\) is primitive, \(\mathbf{s}_0\not0\), and \(\rho= 2^k-1\) is coprime to \(s\), then the sequences (mrg) and (taus) are both purely periodic with period \(\rho\). Computing \(u_n\) from \(u_{n-1}\) involves performing \(s\) steps of the recurrence (mrg).
Suppose now that we have \(J\) LFSR recurrences, the \(j\)-th one having a primitive characteristic polynomial \(P_j(z)\) of degree \(k_j\), and step size \(s_j\). Let \(\{x_{j,n}, n\ge0\}\) be the \(j\)-th LFSR sequence, and define \(x_n = (x_{1,n} + \cdots+ x_{J,n}) \bmod 2\) and \(u_n\) as in (taus). Equivalently, if \(\{u_{j,n}, n\ge0\}\) is the output sequence from the \(j\)-th LFSR, then \(u_n = u_{1,n}\oplus\cdots\oplus u_{J,n}\) where \(\oplus\) denotes the bitwise exclusive-or in the binary expansion. The sequence \(\{x_n\}\) is called the combined LFSR sequence and a generator that produces this \(\{u_n\}\) is called a combined LFSR generator.
Constructor & Destructor Documentation
◆ CycleBasedLFSR() [1/2]
| CycleBasedLFSR | ( | int | step1, |
| int | step2, | ||
| int | nbcoeff1, | ||
| int | nbcoeff2, | ||
| int [] | nocoeff1, | ||
| int [] | nocoeff2 | ||
| ) |
Constructs a point set based on a combination of two polynomials in base 2 with \(2^{k_1 + k_2}\) points.
The meaning of the parameters is the same as in the case of one polynomial.
◆ CycleBasedLFSR() [2/2]
| CycleBasedLFSR | ( | String | filename, |
| int | no | ||
| ) |
Constructs a point set after reading its parameters from file filename; the parameters associated with number no of filename corresponds to the no-th polynomial.
The existing files and the number of polynomials they contain are in the table below. The name of the files describe the number of polynomials \(J\) in the combined LFSR and the number of points \(2^k\) generated. For example, the parameters in file j1_k11.dat are based on \(J = 1\) polynomial and generates \(2^k = 2^{11}\) points, while those in file j2_k17.dat are based on a combination of \(J=2\) polynomials and generates \(2^k = 2^{17}\) points. Thus to use the 3-th combined LFSR of file j2_k17.dat, one must use CycleBasedLFSR("j2_k17", 3).
| Filename | Num. of polynomials |
j1_k11.dat | 1 |
j2_k17.dat | 6 |
j2_k19.dat | 4 |
The documentation for this class was generated from the following file:
- CycleBasedLFSR.java
