The last six functions in Table 18.2 deal with modular exponentiation, which computes

res = b^e mod m

This operation is important in cryptography for a simple reason: It’s easy to compute res given b, e, and m, but nearly impossible to reverse the operation and compute b given res, e, and m. Rapid modular exponentiation is critical in many encryption/decryption schemes, including the RSA cryptographic system.

The first three functions, mpm_mod_exp and its variants, rely on a sliding-window optimization to compute the value of res. The operation of the window goes beyond the scope of this book, but its maximum size is determined by the global parameter MPM_MOD_EXP_MAX_K. mpm_mod_exp and mpm_mod_exp2 accept variable window lengths, and mpm_mod_exp3 sets it to a constant value of 6 bits. mpm_mod_exp2 accepts an additional parameter u, where

The next three functions, mpm_mont_mod_exp and its variants, perform modular exponentiation using Montgomery modular multiplication and the sliding-window optimization. mpm_mont_mod_exp and mpm_mont_mod_exp2 accept variable lengths for the window, but mpm_mont_mod_exp3 specifies its size as MPM_MOD_EXP_MAX_K. mpm_mont_mod_exp2 accepts additional parameters u, a, and p where

u = 2^256*size(m) mod m

a = 2^128*size(m) mod m

and p equals 2¹²⁸ – g, where g is given by

Now let’s see how these functions are used in practice.

The Monte Carlo library provides two methods for generating pseudo-random numbers: the Kirkpatrick-Stoll method and the Mersenne Twister. To see how these work, you need to understand feedback shift registers (FSRs).

A shift register is a simple queue of bit-wide memory stages. This is shown on the upper portion of Figure 18.2. The bits shift with each clock signal: The last bit leaves the register, a new bit enters the register, and the rest of the bits shuffle toward the final position.

Figure 18.2. Shift register and linear-feedback shift register

This isn’t interesting. The register’s value (0xA in the figure) is just the concatenation of its bit sequence. But if the bit shifted out is XORed with one or more intermediate bits and the result is fed back into the input, the register’s value becomes interesting and useful. This is the structure of a linear-feedback shift register (LFSR), and the bottom part of Figure 18.2 shows an example LFSR with four stages, numbered from right to left.

LFSRs have been studied for decades, and if the XOR gates are put in the right places, an n-stage LFSR can produce a sequence of 2ⁿ − 1 values without repetition. These values have no clear pattern from one to the next, and any subset of the 2ⁿ − 1 values are suitable for use in Monte Carlo simulations. After producing 2ⁿ⁻¹ values, the sequence repeats itself from start to finish.

For example, suppose the LFSR in Figure 18.2 has a starting value of 1010. As clock signals proceed, the register takes the sequence of values listed in Table 18.3.

When the LFSR cycles through all 2⁴ − 1 stages, it returns to its original value of 0xA. It can never hold an all-zero value because it would remain in that stage indefinitely.

Keeping in mind that XOR gates perform modulo-2 addition, the operation of an LFSR can be expressed as a modulo-2 polynomial. The output from stage n is represented by xⁿ, and the input into the first stage is represented by x⁰ = 1. Other terms are included in the polynomial if the corresponding stage is connected to XOR gates. The LFSR in Figure 18.2 is expressed by the polynomial x⁴ + x + 1 because the output of the first stage (x) is connected to the XOR gate.

A generalized feedback shift register (GFSR) consists of identical LFSRs compressed on top of one another. That is, each stage of a GFSR stores n bits rather than one. There are no actual GFSRs in the Cell device; they’re implemented with loops that repeatedly bit-shift and XOR integer values. GFSRs can generate pseudo-random numbers at high speed, but require an initial value (the seed) and take time to initialize.

The simplest and fastest PRNG in libmc_rand is the Kirkpatrick-Stoll method (KS). This generates pseudo-random numbers using a 250-stage GFSR. The KS GFSR structure is simple and produces values quickly, but statistical analysis has shown that these values deviate from randomness.

Other libmc_rand functions generate pseudo-random numbers using the Mersenne Twister (MT) method. These values are statistically more random than those of the Kirkpatrick-Stoll, but take longer to generate. This method takes its name from its period (2¹⁹⁹³⁷ − 1, 19,937 is a Mersenne prime), and its GFSR structure, called a twisted generalized feedback shift register, or TGFSR. This is one of the most popular PRNGs available.

Table 18.4 lists the functions that access the hardware RNG, the Kirkpatrick-Stoll PRNG, and the Mersenne Twister. The XX in certain function names can be replaced with HW for the hardware generator, KS for Kirkpatrick-Stoll, or MT for Mersenne Twister. Parameter types are abbreviated: ui stands for unsigned int, vui stands for vector unsigned int, vf stands for vector float, and vd stands for vector double.

There are no data structures representing the number generators; you just call a function to initialize a generator and then call functions to request numbers. The first three functions initialize the hardware number generator, Kirkpatrick-Stoll generator, and Mersenne Twister generator, respectively. The Kirkpatrick-Stoll and Mersenne Twister functions require seed values, but the hardware generator doesn’t.

Each of the next five functions returns a single vector as output. None of them have any arguments, and the only difference between them is the datatype and range of the output values. Here are some examples:

The next five functions are similar to the preceding five, but produce values in vector arrays rather than individual vectors. Each function takes two parameters: an integer identifying how many vectors are in the array, and a pointer to the vector array itself. Extending the earlier examples:

By calling these functions, you can generate large numbers of random values quickly and without a for loop.

The code in Listing 18.2 shows how these functions are used in practice. It generates values from the hardware generator if available. Then it calls on the Kirkpatrick-Stoll method and Mersenne Twister to generate values. The last two PRNGs are initialized with a value returned by gettimeofday().

#include <stdio.h>
#include <stdlib.h>
#include <spu_intrinsics.h>
#include <sys/time.h>
#include <mc_rand.h>

int main(int argc, char **argv) {

   int i, j;
   vector unsigned int int_vec;
   vector float float_vec;
   vector double double_vec[4];

   /* Get the current time to use as seed */
   struct timeval time;
   gettimeofday(&time, NULL);

   /* The hardware number generator */
   printf("
Hardware Generator:
");
   if(mc_rand_hw_init() == 0) {
      int_vec = mc_rand_hw_u4();
      for(i=0; i<4; i++)
         printf("%u ",spu_extract(int_vec, i));
      printf("

");
   }
   else
      printf("Hardware generator not available.

");

   /* The Kirkpatrick Stoll PRNG */
   mc_rand_ks_init(time.tv_sec);
   float_vec = mc_rand_ks_0_to_1_f4();
   printf("Kirkpatrick-Stoll:
");
   for(i=0; i<4; i++)
      printf("%f ", spu_extract(float_vec, i));
   printf("

");

   /* The Mersenne Twister PRNG */
   mc_rand_mt_init(time.tv_sec);
   mc_rand_mt_minus1_to_1_array_d2(4, double_vec);
   printf("Mersenne Twister:
");
   for(i=0; i<4; i++) {
      for(j=0; j<2; j++)
         printf("%g ",spu_extract(double_vec[i], j));
      printf("
");
   }

   return 0;
}

There are two points to keep in mind when using these functions. First, be sure to check whether the hardware generator is available before trying to generate numbers with it. Second, array generation functions like mc_rand_ks_0_to_1_array_f4 always return void, whereas the vector generation functions like mc_rand_hw_u4 always return vectors.

In addition to pseudo-random numbers, libmc_rand functions generate quasi-random numbers using the Sobol method. Each value in a Sobol sequence represents a point in a k-dimensional cube, where each of the cube’s dimensions extends from 0 and 1. As more bits are used in each point, more points can be packed inside the cube.

Initializing a Sobol generator is more complex than initializing any of the other generators. This is because Sobol generators require a table of direction numbers. A direction number is a special k-dimensional point whose dimensions lie between 0 and 1. The theory behind generating direction numbers requires a great deal of math, so this presentation only explains the method.

To compute n direction numbers in a k-dimensional cube, perform the following steps:

Each fractional direction number, v_i, must be converted to an unsigned integer. This is done by setting bits 2 through 2+i of a 32-bit value equal to m_i. To start, m₁ must be odd and less than 2¹ = 2, so m₁ always equals 1. Figure 18.3 shows how to compute direction numbers where m₁−m₄ equal [1, 3, 3, 7].

Figure 18.3. Expressing fractional direction numbers as integers

Successive values of m are calculated with the equation

m_i = 2a₁m_i−1 ⊕2²a₂m_i−2 ⊕2³ a₃m_i−3... ⊕2ⁿ a_nm_i−n ⊕m_i−n

where a_i are the lower terms of a polynomial corresponding to an n-stage LFSR. For example, the polynomial corresponding to the LFSR in Figure 18.3 is x⁴ + x + 1, so a_i = {0, 0, 1, 1}. If m_i = {1, 3, 3, 7}, m₅ is computed by

Once the direction numbers are determined for each of the k dimensions, the Sobol generator will produce quasi-random numbers that fill the k-dimensional space.

Table 18.5 lists the libmc_rand functions associated with the Sobol generator. The names of the functions are similar to those in Table 18.4, but the parameters differ significantly.

Direction numbers are contained in a sobol_cntrlblck_t structure, declared in mc_rand_sb.h:

typedef struct {
   vector unsigned int* pu32_vecDirection;
   unsigned int u32sizeofTable;
   unsigned int u32TableDimension;
   unsigned int u32TableBitCount;
   unsigned int u32MaxBitCount;
   unsigned int u32Seed;
} sobol_cntrlblck_t;

The first field, pu32_vecDirection, points to the table of direction numbers, and the second identifies how many dimensions each generated point should have. u32TableDirection specifies much memory the table takes up. The next two fields tell the generator how many bits should be used for each quasi-random number, and the last field, u32Seed, provides an initial value for the generator.

The Sobol initialization function, mc_rand_sb_init, accepts the sobol_cntrlblck_t as its first parameter. The rest of the parameters are as follows:

The Monte Carlo library documentation strongly recommends defining SOBOL_RUNS and SOBOL_DIMENSION in code. The first value identifies the maximum number of elements that will be needed in an array (112 by default), and the second identifies the desired dimensionality of the generated values (40 by default).

The SDK provides an excellent example that demonstrates how Sobol sequences are generated and used in code. The /opt/cell/sdk/prototype/src/examples/monte_carlo directory contains a project folder called pi. The pi application approximates the value of π by generating Sobol numbers. The direction numbers are taken from a header file called sobol_init_30_40.h, which provides Sobol numbers for 30 bits and 40 dimensions.

The mathematical derivations of the Box-Muller, Moro inversion, and Polar methods lie beyond the scope of this book, but to decide which one to use, it’s important to see how they work. The Box-Muller method takes two numbers from a uniform distribution (x and y) and produces two numbers from a normal distribution (a and b). The relationship between a, b, x, and y is given by the following equations:

The Box-Muller method can only transform an even number of input values.

The Polar method is similar to the Box-Muller method, but removes the need to compute sine and cosine values. The Polar equations are given by

and

where

q =(2x−1)² +(2y−1)²

The problem with the Polar method is that q must be less than 1. Any input values that would result in an invalid value must be discarded. Therefore, the number of output values will usually be less than the number of input values. Despite the discarding, the Polar method is as effective as the Box-Muller and generally computes values faster.

The last method is the Moro inversion, which is entirely different from the Box-Muller and Polar methods. It returns one normally distributed value for each uniformly distributed value, and does so by computing the inverse of the cumulative distribution function, or cdf. The cdf is the probability that a random variable is less than or equal to a specific value. You can find more information about Moro’s inversion and the other two methods in The Monte Carlo Programmer’s Guide and API Reference.

Table 18.6 lists all the libmc_rand functions that transform the distribution of numeric sequences. In each case, the input floats must lie between 0 and 1, but may not equal 0 or 1.

The Box-Muller functions are identified with bm2 and the Moro inversion functions are identified with mi. Each Box-Muller function operates on an array of uniformly distributed vectors and produces an output array of normally distributed values. The first two Moro inversion functions operate on arrays, and the second two receive individual vectors. The second pair of Moro inversion functions, mc_transform_mi_array_f4 and mc_transform_mi_array_d2, return their output values in a vector.

The last four functions in the table transform number distribution with the Polar method. Their usage is markedly different from the Box-Muller and Moro inversion functions. Each accepts a pointer to a function that generates pseudo-random numbers, and this is necessary because the Polar method discards unsuitable input values. To produce N output values, the Polar functions must call the generation function until all N outputs are produced.

The functions that use the Polar method can be confusing, so the code in Listing 18.3 shows how they’re used in practice. First, the spu_random2 application uses the Mersenne Twister to generate four vector floats containing uniformly distribute values. Then it transforms the uniformly distributed sequence into a normally distributed sequence using the Polar method.

#include <stdio.h>
#include <stdlib.h>
#include <spu_intrinsics.h>
#include <sys/time.h>
#include <mc_rand.h>
#include <simdmath.h>

int main() {

   int i, j;

   /* The input and output arrays */
   vector float uniform_vec[4];
   vector float normal_vec[4];

   /* Generate a seed */
   struct timeval time;
   gettimeofday(&time, NULL);

   /* Generate the random numbers */
   mc_rand_mt_init(time.tv_sec);
   mc_rand_mt_0_to_1_array_f4(4, uniform_vec);

   /* Transform the array */
   mc_transform_po_array_f4(4, uniform_vec, normal_vec,
      &mc_rand_mt_0_to_1_f4);

   /* Display the results */
   printf("Uniform Distribution: 
");
   for(i=0; i<4; i++)
      for(j=0; j<4; j++)
         printf("%f ", spu_extract(uniform_vec[i], j));

   printf("

Normal Distribution: 
");
   for(i=0; i<4; i++)
      for(j=0; j<4; j++)
         printf("%f ", spu_extract(normal_vec[i], j));
   printf("
");
   return 0;
}

The call to mc_transform_po_array_f4 might seem odd at first. The last parameter is a pointer to the function mc_rand_mt_0_to_1_f4, which uses the Mersenne Twister to produce a vector float of uniformly distributed values. If the Polar method can call the generation function, why does it need an input vector of floats? The answer is that the Polar method may need to discard input values, and the Mersenne Twister provides a backup mechanism to make sure that count values are always returned.