Linear feedback shift register (LFSR) random number generators [144], [119], [181], 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. | |
| 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. | |
| String | toString () |
| This method returns a string containing the polynomials and the stepping parameters. | |
| Public Member Functions inherited from umontreal.ssj.hups.CycleBasedPointSetBase2 | |
| double | getCoordinate (int i, int j) |
| Returns \(u_{i,j}\), the coordinate \(j\) of the point \(i\). | |
| PointSetIterator | iterator () |
| Constructs and returns a point set 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. | |
| void | clearRandomShift () |
| Erases the current digital random shift, if any. | |
| 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. | |
| Public Member Functions inherited from umontreal.ssj.hups.CycleBasedPointSet | |
| int | getDimension () |
| Returns the dimension (number of available coordinates) of the points. | |
| Public Member Functions inherited from umontreal.ssj.hups.PointSet | |
| int | getNumPoints () |
| Returns the number of points. | |
| void | randomize (PointSetRandomization rand) |
| Randomizes this point set using the given rand. | |
| void | addRandomShift (RandomStream stream) |
Same as addRandomShift(0, dim, stream), where dim is the dimension of the point set. | |
| 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. | |
| 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. | |
| 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. | |
| String | formatPoints (PointSetIterator iter, int n, int d) |
Same as invoking formatPoints(n, d), but prints the points by calling iter repeatedly. | |
| String | formatPointsBase (int b) |
Similar to formatPoints(), but the points coordinates are printed in base \(b\). | |
| String | formatPointsBase (int n, int d, int b) |
Similar to formatPoints(n, d), but the points coordinates are printed in base \(b\). | |
| String | formatPointsBase (PointSetIterator iter, int b) |
Similar to formatPoints(iter), but the points coordinates are printed in base. | |
| 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\). | |
| String | formatPointsNumbered () |
Same as invoking formatPointsNumbered(n, d) with \(n\) and \(d\) equal to the number of points and the dimension, respectively. | |
| String | formatPointsNumbered (int n, int d) |
Same as invoking formatPoints(n,d), except that the points are numbered. | |
Additional Inherited Members | |
| Static Public Member Functions inherited from umontreal.ssj.hups.PointSet | |
| static int | getMaxBits () |
| Returns the maximum number of usable bits. | |
| Protected Member Functions inherited from umontreal.ssj.hups.CycleBasedPointSet | |
| void | addCycle (AbstractList c) |
| Adds the cycle c to the list of all cycles. | |
| Protected Attributes inherited from umontreal.ssj.hups.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. | |
| 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. | |
| RandomStream | shiftStream |
| Stream used to generate the random shifts. | |
| Static Protected Attributes inherited from umontreal.ssj.hups.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. | |
Detailed Description
Linear feedback shift register (LFSR) random number generators [144], [119], [181], 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.
Definition at line 74 of file CycleBasedLFSR.java.
Constructor & Destructor Documentation
◆ CycleBasedLFSR() [1/3]
| umontreal.ssj.hups.CycleBasedLFSR.CycleBasedLFSR | ( | int | step1, |
| int | nbcoeff1, | ||
| int[] | nocoeff1 ) |
Definition at line 107 of file CycleBasedLFSR.java.
◆ CycleBasedLFSR() [2/3]
| umontreal.ssj.hups.CycleBasedLFSR.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.
Definition at line 120 of file CycleBasedLFSR.java.
◆ CycleBasedLFSR() [3/3]
| umontreal.ssj.hups.CycleBasedLFSR.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).
<center> <table class="SSJ-table SSJ-has-hlines"> <tr class="bt"> <td class="c bl br">Filename</td> <td class="c bl br">Num. of polynomials</td> </tr> <tr class="bt"> <td class="c bl br"><tt>j1_k11.dat</tt></td> <td class="c bl br">1</td> </tr> <tr> <td class="c bl br"><tt>j2_k17.dat</tt></td> <td class="c bl br">6</td> </tr> <tr> <td class="c bl br"><tt>j2_k19.dat</tt></td> <td class="c bl br">4</td> </tr> </table> </center>
Definition at line 170 of file CycleBasedLFSR.java.
Member Function Documentation
◆ toString()
| String umontreal.ssj.hups.CycleBasedLFSR.toString | ( | ) |
This method returns a string containing the polynomials and the stepping parameters.
Reimplemented from umontreal.ssj.hups.CycleBasedPointSet.
Definition at line 216 of file CycleBasedLFSR.java.
The documentation for this class was generated from the following file:
- src/main/java/umontreal/ssj/hups/CycleBasedLFSR.java
