next up previous

3.3 Using Logical Masks to Perform Modulo Operations

Generators where the modulus operation must be performed (requiring an integer division) are more costly to implement than are those with moduli of , where the integer division and remaindering can be accomplished much more efficiently. We illustrate this as follows. With a divisor of , after the multiplication of , the next seed is obtained simply by performing a logical AND of with a mask of ones, right-justified (see Figure 5). This is an extremely efficient operation on binary computers. Many computer languages have a bitwise AND intrinsic function. Use of the AND operation also avoids the problem with negative integers, discussed above. A FORTRAN implementation would look like:

xn = iand(xn, mask)

Figure 5: Modulus Operation with m=2^5 using IAND.