next up previous

Overflow and Negative Integers

Consider performing the operation . A large value of a is desirable to provide sufficient randomness. A large value of m is also desired, so that the period is kept long. For example, on 32 bit computers, a and m are often 31 bits long, as the most significant bit (the 32nd bit) is generally used to indicate sign. When two 31 bit integers are multiplied together, a possibly 62 bit integer results. Thus, an overflow almost always occurs. Fortunately, floating point multipliers (and software emulations thereof) are designed to throw away the most significant bits, and retain the least significant 32 bits.

However, if the result of the multiplication is so as to have the most significant bit (the 32nd bit) set, then the computer may treat this as a negative integer, which is incompatible with the algorithm above. If this happens (it occurs during one-half of the multiply operations), this negative bit must be handled. One strategy to overcome this is to use a bit mask to mask off the most significant bit. In this case, a logical AND operation should be performed on the random, negative integer and the bit mask, imask=z'7fffffff', which is a leading 0 followed by 31 ones (i.e. ). This has the effect of the zeroing out the sign bit, forcing the number to be positive. Viz.,

xn = iand(xn, imask)

However, masking works only when m is a power of two. Otherwise, it destroys the sequence of numbers generated, and the theory no longer applies. In the general case, unless the number resulting from the multiplication fits in the register, special coding must be done. An approach to this is to perform remaindering, by decomposing the multiply operation into steps in which intermediate results are contained in 32 bits. This is the strategy used by Park and Miller [47]. Note that, in the language C, one can avoid the issue of the sign bit by using an unsigned integer.