# R250/521 (Java)

**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:

privateinti;privateint[]x =newint[250];publicintrandom(){intresult = x[i]= x[i]^ x[(i + 103)% 250]; i++;returnresult;}

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>>=privateint[]r250_buffer =newint[250];privateint[]r521_buffer =newint[521];<<initialization>>=publicR250_521(){java.util.Random r =newjava.util.Random();inti = 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 *a*_{ij} is the *i*th bit of the *j*th 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 *i*th bit of the *i*th 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:

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>>=intmask1 = 1;intmask2 = 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>>=publicintrandom(){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 pointersreturnr ^ 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>>=privateintr250_index;privateintr521_index;<<initialize offsets>>=r250_index = 0; r521_index = 0;<<compute the indexes of the words we XOR with next in each buffer>>=inti1 = r250_index;inti2 = r521_index;intj1 = i1 -(250-103);if(j1 < 0)j1 = i1 + 103;intj2 = 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>>=intr = r250_buffer[j1]^ r250_buffer[i1]; r250_buffer[i1]= r;ints = 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>>=publicfinalclassR250_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 |