R250/521 (Java)

From LiteratePrograms
Jump to: navigation, search
Other implementations: C | Java

This program implements the R250/521 combined generalized feedback shift register algorithm for generation of pseudorandom numbers. The original code was written by Michael Brundage and has been placed in the public domain. [1]

R250 is a simple but efficient algorithm where we keep a buffer of the last 250 words generated. To generate a new word, we XOR the words at indexes 0 and 103. The new word is added to the end of the buffer, pushing all other words down by 1 index and removing the word at index zero. This is most efficiently implemented using a circular buffer, like this:

private int i;
private int[] x = new int[250];

public int random() {
    int result = x[i] = x[i] ^ x[(i + 103) % 250];
    i++;
    return result;
}

R521 is similar except that it keeps a buffer of the last 521 numbers and XORs words 0 and 168.

[edit] Main implementation

We begin our implementation by defining and initializing the two buffers. To initialize the buffers, we must initialize each entry using another random number generator, such as the standard java.util.Random:

<<R250_521 data members>>=
private int[] r250_buffer = new int[250];
private int[] r521_buffer = new int[521];

<<initialization>>=
public R250_521() {
    java.util.Random r = new java.util.Random();
    int i = 521;
	
    while (i-- > 250) {
        r521_buffer[i] = r.nextInt();
    }
    while (i-- > 31) {
        r250_buffer[i] = r.nextInt();
        r521_buffer[i] = r.nextInt();
    }
    
    initialize first 32 elements with linearly independent values
    initialize offsets
}

Loops are reversed and fused for speed; this is probably unnecessary.

Note that we don't simply compute every value using Random. Suppose we view our buffer as a bit matrix where aij is the ith bit of the jth word. If the columns of this matrix are not linearly independent, in other words if one can be formed by XORing a subset of the others, then this will affect the period of the generator. This is highly improbable if we initialize the buffer with random data, but with pseudorandom data it's difficult to be sure. In any case, it's easy to force the columns to be linearly independent by simply setting setting the ith bit of the ith row to 1 and all bits to the right of that bit to zero, where i goes up to the word size, as in this miniature example:


\begin{bmatrix}
2 \\
7 \\
4 \\
3 \\
6
\end{bmatrix}
\rightarrow
\begin{bmatrix}
0 & 0 & 0 \\
1 & 0 & 1 \\
1 & 0 & 0 \\
0 & 1 & 1 \\
1 & 1 & 0
\end{bmatrix}
\rightarrow
\begin{bmatrix}
1 & 0 & 0 \\
1 & 1 & 0 \\
1 & 0 & 1 \\
0 & 1 & 1 \\
1 & 1 & 0
\end{bmatrix}

In the code, we accomplish this by applying a sliding bitmask to the initializers for the first 32 elements while assigning them:

<<initialize first 32 elements with linearly independent values>>=
int mask1 = 1;
int mask2 = 0xFFFFFFFF;
while (i-- > 0) {
    r250_buffer[i] = (r.nextInt() | mask1) & mask2;
    r521_buffer[i] = (r.nextInt() | mask1) & mask2;
    mask2 ^= mask1;
    mask1 >>= 1;
}
r250_buffer[0] = mask1;
r521_buffer[0] = mask2;

Note that we use the fact that ints are always 32 bits in Java.

In the following code, we will combine R250 and R521 to obtain a generator with a much larger period and better statistical properties. To do this, each time a random number is asked for we simply give the XOR of the next random number from R250 and the next random number from R521. In outline the procedure looks like this:

<<main number generator>>=
public int random() {
    compute the indexes of the words we XOR with next in each buffer
    compute and store the next words r and s in each sequence
    update offset pointers
    return r ^ s;
}

In our first code block we found the index to XOR with using (i + 103) % 250. Instead of performing an expensive modulus operation, we can accomplish the same thing by either adding 103 to i or subtracting 250−103, depending on which yields a nonnegative value (since 0 ≤ i < 250, one of them must). Two private data members store the current index into each buffer:

<<R250_521 data members>>=
private int r250_index;
private int r521_index;

<<initialize offsets>>=
r250_index = 0;
r521_index = 0;

<<compute the indexes of the words we XOR with next in each buffer>>=
int i1 = r250_index;
int i2 = r521_index;
    
int j1 = i1 - (250-103);
if (j1 < 0)
    j1 = i1 + 103;
int j2 = i2 - (521-168);
if (j2 < 0)
    j2 = i2 + 168;

We can now extract the desired word and XOR the current word with it to get our next random integers r and s:

<<compute and store the next words r and s in each sequence>>=
int r = r250_buffer[j1] ^ r250_buffer[i1];
r250_buffer[i1] = r;
int s = r521_buffer[j2] ^ r521_buffer[i2];
r521_buffer[i2] = s;

Finally, we increment the offset pointers to the next word, wrapping around if necessary:

<<update offset pointers>>=
i1 = (i1 != 250-1) ? (i1 + 1) : 0;
r250_index = i1;
i2 = (i2 != 521-1) ? (i2 + 1) : 0;
r521_index = i2;

In summary, here is our source file, ready to use:

<<R250_521.java>>=
public final class R250_521 {
    R250_521 data members

    initialization

    main number generator
}

[edit] Performance

This code performs very quickly. Below is an ad hoc comparison with the Sun JRE 1.4.2_09 standard Random.nextInt call on a 2.8 GhZ Pentium 4 machine, which is also a carefully optimized implementation. Both runs use the Sun Java 1.4.2_09 compiler and VM.

Numbers Random (sec) R250/521 (sec)
100 0.233 0.265
10,000 0.273 0.285
1,000,000 0.297 0.245
10,000,000 1.34 0.429
100,000,000 10.6 5.13
1,000,000,000 103.3 47.2

For the first few values, the overhead of loading the Java runtime dominates. The C version at R250/521 (C) does not have this overhead and is about 2.5 times faster all around, but even this Java version admirably outperforms Java's built-in RNG support.

Download code
hijacker
hijacker
hijacker
hijacker