TweetFollow Us on Twitter

Random Cocoa

Volume Number: 22 (2006)
Issue Number: 3
Column Tag: Programming

Random Cocoa

Implementing Five PRNG Algorithms in Cocoa.

by Jose R.C. Cruz

Introduction

Random numbers are commonplace in the field of software design. They are often used in such applications as cryptography, statistics, and simulations. However, the digital computer is a deterministic machine. It executes specific software instructions in a specific order on data usually provided by the user. Some high-end systems use additional hardware to generate random numbers. These generators use natural events such as radioactive decay or thermal noise as a source for randomness. However, most systems nowadays, use algorithms known as pseudo-random number generators (PRNG).

This article will focus on five commonly known PRNG algorithms. A brief background on each algorithm will be presented, focusing on their respective traits and limitations. Later on, a core Cocoa class will be proposed for implementing each PRNG algorithm. Finally, three test algorithms will be presented. These algorithms are used to determine that a PRNG algorithm is generating a statistically acceptable random sequence.

To further assist software engineers in designing and implementing PRNG Cocoa classes, a demo application known as DiceC is developed to accompany this article. This application implements many of the concepts presented here. Both the application and the XCode project are available for downloading at the MacTech web site ftp://ftp.mactech.com/src/mactech/volume22_2006/22.03.sit.

The Pseudo-Random Number Generator

Basic Concepts

Pseudo-Random Number Generators are algorithms used to generate number sequences that have the appearance of randomness. They achieve this through the use of an iterative mathematical function and/or bit shifting.

As its name implies, PRNGs are not true random number generators. First of all, they all require an initial numeric value known as a seed. The seed value determines the numbers that will be generated in the sequence. Using the same seed will always result in to the same random sequence. This trait, known as repeatability, is desirable in many applications such as cryptography.

Another aspect of PRNG algorithms is that the random sequence repeats itself after X number of values. This trait, known as a period, is a distinguishing factor between PRNG algorithms. A well-designed algorithm should have a period as close to (if not greater than) the largest possible random value. A 32-bit PRNG, for example, should be able to generate close to 232 random numbers before the sequence repeats itself.

The Middle Square Method

The Middle Square Method (MSM) is one of the earliest known PRNG algorithms devised for the digital computer. It was proposed by Dr. John von Neumann and used on the ENIAC computer in 1946. It is also a poor generator; its inclusion in this article is mainly for comparative purposes.

Figure 1 shows the generating function used by the MSM algorithm. When generating a new random number, the previous number is first squared. Then only those digits located in the relative middle of the squared result are retrieved as the next random value. The number of significant digits of each random value matches those that comprise the seed value.

To illustrate, if the seed has a value of 1234, first calculate the square of the seed.

1234^2 =????????

The first random number would then be the middle 4 digits of the squared result.

mid(1522756)= 5227

To generate the second random number, simply take the first random number and follow the same two steps as shown above.

5227^2 = 27321529
mid(27321529) = 3215

The MSM algorithm has a number of shortcomings. One is that the algorithm suffers from a very short period of 10m, where m is the number of significant digits contained by the seed value. In the above example, the seed value only has 4 significant digits. This implies that the algorithm can theoretically generate no more than 9999 unique numbers before it repeats the entire sequence.

Another shortcoming is that the MSM algorithm sometimes implodes into a non-random sequence long before it reaches its maximum period. Unless it is provided with a new seed, the algorithm will start generating a small handful of single number values.


Figure 1. The Middle Square Method.

The Linear Feedback Shift Register

The Linear Feedback Shift Register (LFSR) algorithm uses bit taps and bit shifting to generate a random sequence. As shown in Figure 2, the algorithm first taps specific bits off a theoretical register. It then determines the odd parity of the tapped bits by using an XOR operation. The contents of the register are shifted to the left by one, and the most significantn bit (msb) replaced is by the computed parity bit.

The LFSR algorithm is fast, simple and reliable. It has a maximum theoretical period of 2m, where m is the bit precision of the register. The 32-bit example shown in Figure 2 has a maximum theoretical period of 232. This implies that up to 4 294 967 values can be generated before the random sequence repeats itself.

Due to its simplicity, the LFSR is often implemented as a hardware generator. It has found popular usage in embedded systems such as spread-spectrum radio and GPS units. Non-linear variants of the LFSR algorithm were also used in cryptography for generating stream ciphers.


Figure 2. The Linear Feedback Shift Register.

The Linear Congruential Generator

The Linear Congruential Generator (LCG) is one of the oldest and most widespread PRNG algorithms. Many modern operating systems and code libraries use a variation of this algorithm as their random number generator.

Unlike the previous two, the LCG algorithm uses a modular equation (Figure 3) to generate a random sequence. Its overall performance is strongly depended on values chosen for its generator constants A, B and M. A list of common LCG variants, and their respective generator constants, is shown in Table 1.

To ensure an optimal period, the following rules are usually followed when choosing values for the three generator constants:

  • Constant A is a positive integer much greater than 1.
  • Constants B and M needs to be relatively prime with each other. In other words, they share no common factors except 1. This does not imply that either B or M (or both) have to be prime numbers
  • The expression (A - 1) should be divisible by all prime factors of M. Consequently, if M happens to a multiple of 4, then (A - 1) should also be a multiple of 4.
  • The constant M should be greater than the constants A and B, and the seed value, R0.

To determine if constants B and M are relatively prime, the algorithm known as Euclid's Algorithm is used. This algorithm employs successive modular divisions to determine the greatest common denominator (GCD) shared by two integers. If the integers are relatively prime, they will have a GCD of 1. An implementation of Euclid's Algorithm as an ObjC method is shown in Listing 1.


Table 1. List of common LCG variants.


Figure 3. The Linear Congruential Generator.

Listing 1. Euclid's Algorithm implemented as an ObjC method.

- (BOOL)isValue:(unsigned int)argA
                        relativelyPrimeTo:(unsigned int)argB
{
   BOOL chk_flg;
   unsigned int loc_a, loc_b, loc_r;
   
   // initialize the following locals
   loc_a = (argA > argB) ? argA : argB;
   loc_b = (argA > argB) ? argB : argA;
   
   // run Euclid's Algorithm
   while (loc_b != 0)
   {
      loc_r = loc_a % loc_b;
      loc_a = loc_b;
      loc_b = loc_r;
   }
   
   // check the last non-zero remainder
   chk_flg = (loc_a == 1);
   
   // return the check results
   return (chk_flg);
}

The Lagged Fibonacci Generator

The Lagged Fibonacci Generator (LFG) is a specialized version of the LCG algorithm. It uses the Fibonacci sequence of Sn*Sn-1 to generate its pseudo-random sequence. Unlike other PRNG algorithms, the LFG algorithm uses an initialization vector containing multiple seed values. The vector is often initialized using a different PRNG algorithm. Also, the LFG algorithm uses its random sequence to update its initialization vector, thus improving the overall periodicity of the algorithm.

The generating function of the LFG algorithm is shown in Figure 4. The base modulus, M, is usually assigned a value of 2m, where m is the integer bit size. The token o indicates the binary operator used by the algorithm. This can be any of the following primitives: addition (+), multiplication (x) or exclusive-OR (?). The choice of operator also categorizes the LFG algorithm being used. If the algorithm uses an additive or a multiplicative operator, it is referred to respectively as an Additive or Multiplicative LFG. If an XOR operator is used, the algorithm is referred to as a Two-Tap Generalized Shift Feedback Register (GSFR).

The choice of operator also dictates the theoretical period of the LFG algorithm. If an additive or XOR operator is used, the algorithm has a theoretical period of (2k - 1 )*2M-1. If a multiplicative operator is used, the theoretical period becomes (2k - 1)*2M-3, which is 1/4 the period of the additive and XOR version.


Figure 4. The Lagged Fibonacci Generator.

The Blum Blum Shub Algorithm

The Blum Blum Shub (BBS) algorithm was developed in 1986 by Lenore and Manuel Blum, together with Michael Shub, as a secure PRNG for cryptographic applications. This algorithm can also be used for simulation projects; however, performance issues render it unattractive for such applications.

The generating function of the BBS algorithm is shown in Figure 5. The generator constant, M, is derived as a product of two prime numbers, p and q. For optimal performance, the following guidelines are proposed when choosing values for p and q:

  • Both p and q should be congruent to the modulus 3 mod 4. In other words, dividing either p or q by 4 should always result in a remainder of 3.
  • The GCD of the expressions (p-1) and (q-1) should be as small as possible to guarantee a large period.

Unlike the previous PRNGs, only the least significant bits of Rn+1 are used as the next random value. This ensures that the random sequence is resistant to linear cryptanalysis. For optimal security, it is proposed that no more than log(log(M)) bits of Rn+1 should be extracted and used as part of the random sequence.


Figure 5. The Blum Blum Shub algorithm.

The PRNG Cocoa Classes

The Class Structure

The UML diagram of the proposed PRNG Cocoa class structure is shown in Figure 6. The core class, RandBase, provides the code foundation that will be used by 5 other subclasses. Each subclass implements one of the PRNG algorithms covered in this article.


Figure 6. UML diagram of the PRNG class structure.

Figure 7 is the UML diagram of the RandBase core class. For purposes of clarity, I use the more familiar ObjC syntax (as opposed to the standard UML convention) in describing the properties and methods contained by each class.

Three NSString properties store information describing the PRNG class. These are modified using the setDescription:toString method. The information stored is then displayed using the description method.

The prngSeed property stores the seed value used by the PRNG algorithm. Casting it as a generic datatype, id, allows the flexibility to use any Cocoa object as a potential seed. This property is initialized by the core class using either the initWithValue or initWithUnsignedInt methods.

The prngValue property stores the current random value generated by the PRNG algorithm. It is initially set to the same value as prngSeed through the placeholder method, initModelOnReset. This property is casted as an NSNumber so that the random value can be represented in any one of the following datatypes: string, unsigned integer, double, etc. This property is accessed and modified respectively using the randomValue and setRandomValue methods.

The placeholder method, initModelOnReset, contains the initialization code unique to the PRNG algorithm. Each of the RandBase subclasses overload this method to set their own description strings, default seed values and generator constants.

The placeholder method, generate, contains the actual PRNG algorithm. This is also where the actual numeric value of the seed is determined. The RandBase subclasses overload this method with their own implementations. In the core class, this method defaults to the BSD library function, rand(), as the random number generator. Also, the generator is initialized in the initModelOnReset method using the last random number generated by rand().

Regardless of what algorithm is used, the generate method saves the new random number using the setRandomValue method. It also returns the random number as an NSNumber.


Figure 7. The RandBase core class.

All of the RandBase subclasses proposed in this article will generate random sequences of 32-bit unsigned integers. Support for other numerical datatypes (64-bit, signed, etc.) can be accomplished by simply modifying each subclass.

The RandMSM Subclass

Figure 8 shows the UML diagram of the RandMSM subclass. This subclass contains the NSRange property, msm_mask, which stores the position and length of the middle-value mask. The contents of this property are accessed using the setMask and maskValue methods.

The overloaded method, generate, implements the MSM algorithm as shown in Listing 2. This method first retrieves the previous random value and calculates its square product in 64-bit precision. It then converts the resulting 64-bit value to an NSString.

If a middle-value mask has been defined, the method retrieves the mask and applies it to the NSString data. Otherwise, it uses the string length to make a best-guess estimate of the middle value range. The extracted substring is then converted to a 32-bit unsigned integer.


Figure 8. The RandMSM Subclass.

Listing 2. The [generate] method (RandMSM.m).

- (NSNumber *)generate
{
   NSString   *str_val;
   NSRange   old_msk, new_msk;
   BOOL      str_chk;
   unsigned int   str_pos, str_max, str_len, ui32_val;
   unsigned long long   ui64_val;
   
   // initialize the following locals
   ui64_val = [[super randomValue] unsignedLongLongValue];
   ui64_val = ui64_val * ui64_val;
   str_val = [NSString stringWithFormat:@"%qu", ui64_val];
   old_msk = [self maskValue];
   str_max = [str_val length];
   
   // determine the default MSM mask settings
   str_len = str_max / 2 + (str_max % 2);
   str_pos = str_len / 2;
   
   // validate the current  mask settings
   if (old_msk.location != old_msk.length)
   {
      // use the current mask settings
      new_msk.location = (old_msk.location > str_max) 
         ? str_pos : old_msk.location;
      new_msk.length = (old_msk.length > str_max) 
         ? str_len : old_msk.length;
   }
   else
      // use the default mask settings
      new_msk = NSMakeRange(str_pos, str_len);
   
   // extract the middle value
   str_val = [str_val substringWithRange:new_msk];
   ui32_val = [str_val intValue];
   
   // save the new random number
   [super setRandomValue:ui32_val];
   
   // return the new random number
   return ([super randomValue]);
}

The RandLFSR Subclass

The UML diagram of the RandLFSR subclass is shown in Figure 9. This subclass contains one private property, lfsr_taps[], which is an array of 32 BOOL datatypes. Contents of this property are accessed using the setTapAtIndex and isTapSetAtIndex methods.

The overloaded method, generate, implements the LFSR algorithm (Listing 3). The method first retrieves the previous random value as well as the tap mask. It applies the mask to the random value thus isolating the desired bits. The msb is then determined by computing the odd-parity of the tapped bits. Afterwards, the previous random value is then shifted to the left by one bit, and the msb applied to the shifted result.


Figure 9. The RandLFSR Subclass.

Listing 3. The [generate] method (RandLFSR.m).

- (NSNumber *)generate
{
   unsigned int old_val, new_val, msk_val;
   unsigned int bit_pos, bit_val, bit_msb;
   
   // initialize the following locals
   old_val = [[super randomValue] unsignedIntValue];
   msk_val = [self getTapMask];
   
   // determine the masked bit values
   msk_val = old_val & msk_val;
      // determine the bit parity [odd-parity of 1]
   bit_msb = 0x0;
   for (bit_pos = 0; bit_pos < LFSR_MAX; bit_pos++)
   {
      bit_val = 0x1 & msk_val;
      bit_msb = (bit_msb == bit_val) ? 0x0 : 0x1;
      msk_val = msk_val >> 0x1;
   }
   
   // update the current random value
   new_val = old_val >> 0x1;
   bit_msb = bit_msb << (LFSR_MAX - 1);
   new_val = new_val | bit_msb;
   
   // save the new random number
   [super setRandomValue:new_val];
   
   // return the new random number
   return ([super randomValue]);
}

The RandLCG Subclass

Figure 10 shows the UML diagram of the RandLCG subclass. This subclass contains three properties (lcg_a, lcg_b and lcg_m) to store the generator-specific constants of the algorithm. The contents of these properties are modified by the setConstA:ConstB:ConstM method, and are accessed by the methods: getConstA, getConstB and getConstM.

The overloaded method, generate, implements the LCG algorithm as shown in Listing 4. The method first retrieves the previous random value as well as the generator-specific constants. It then calculates the LCG generator function shown in Figure 3 at 64-bit precision. The modulus operation, however, is performed at 32-bit precision, resulting into the new random value.

The checkForError function checks to see if the subclass will generate a random sequence with an optimal period. If so, it returns an Err_None; otherwise, it returns the appropriate error flag. The isValue:divisibleByFactorsOf function returns a YES if the specified numbers share the same prime number factors. Finally, the isValue:relativelyPrimeTo function (Listing 1) performs Euclid's Algorithm on the specified numbers. It returns a YES if both numbers are relatively prime. Both functions work in conjunction with the utility function, checkForError.


Figure 10. The RandLCG Subclass.

Listing 4. The [generate] method (RandLCGm).

- (NSNumber *)generate
{
   unsigned long long ui64_val, ui64_a, ui64_b;
   unsigned int ui32_val, mod_val;
   
   // initialize the following locals
   ui64_val = [[super randomValue] unsignedLongValue];
   ui64_a = [self getConstA];
   ui64_b = [self getConstB];
   mod_val = [self getConstM];
   
   // calculate the next random value
   ui64_val = ui64_val * ui64_val;
   ui64_val = ui64_val + ui64_b;
   ui32_val = ui64_val % mod_val;
   
   // save the new random number
   [super setRandomValue:ui32_val];
   
   // return the new random number
   return ([super randomValue]);
}

The RandLFG Subclass

The UML diagram of the RandLFG subclass is shown in Figure 11. This subclass contains two properties (lfg_p and lfg_q) to store the generators-specific constants to be used by the algorithm. It also contains the private property, lfg_ops, which determines the binary operator to be used. The contents of these properties are modified by the setConstP:constQ:opCode and are accessed by the methods: getConstP, getConstQ and getOpCode.

The RandLFG subclass also maintains the initialization vector in the form of the NSMutableArray property, lfg_vec. Another property, lfg_lim, contains the maximum size that the vector is allowed to grow. Lastly, the lfg_cnt property, keeps track of the number of random values generated by the subclass. It is used to determine which entry in the initialization vector will be updated.

The overloaded method, generate, implements the LFG algorithm (Listing 5). The method first retrieves the previous random value as well as the generators-specific constants. It then determines which seed value to retrieve from the initialization vector. The method calculates the next random value at 64-bit precision, using the selected binary operator. It then updates the initialization vector with the 32-bit result. This is the only subclass that does not save the new random value using the setRandomValue method.


Figure 11. The RandLFG Subclass.

Listing 5. The [generate] method (RandLFG.m).

- (NSNumber *)generate
{
   unsigned int   idx_p, idx_q, vec_lim, ui32_val;
   unsigned long long   ui64_p, ui64_q;
   unsigned long long   ui64_val, ui64_and, ui64_or;
   LFG_OPCODE arg_ops;
   
   // validate the initialization vector
   if ([super isSeeded])
   {
      // initialize the following locals
      idx_p = [self getConstP];
      idx_q = [self getConstQ];
      vec_lim = [self getVectorSize];
      arg_ops = [self getOpCode];
      
      // calculate the vector indices
      idx_p = lfg_cnt - idx_p;
      idx_p = idx_p % vec_lim;
      idx_q = lfg_cnt - idx_q;
      idx_q = idx_q % vec_lim;
      
      // retrieve the values at the specified indices
      ui64_p = [self getValueAtIndex:idx_p];
      ui64_q = [self getValueAtIndex:idx_q];
      
      // calculate the next state value
      switch (arg_ops)
      {
         case lfgAdd:
            // -- prng:LFG:additive
            ui64_val = ui64_p + ui64_q;
            break;
         case lfgMul:
            // -- prng:LFG:multiplicative
            ui64_val = ui64_p * ui64_q;
            break;
         case lfgXOR:
            // -- prng:LFG:XOR
            ui64_and = ui64_p & ui64_q;
            ui64_or = ui64_p | ui64_q;
            ui64_val = ui64_or & ~(ui64_and);
            break;
      }
      // include the modulus base
      ui32_val = (unsigned int)(ui64_val % DFLT_BASE);
            
      // update the initialization vector
      lfg_cnt++;
      idx_p = lfg_cnt % vec_lim;
      [self setValue:ui32_val atIndex:lfg_cnt];
      
      // save the new random number
      [super setRandomValue:ui32_val];
      
      // return the new random number
      return ([super randomValue]);
   }
   else
      // return the current seed value
      return ([super seedValue]);
}

The RandBBS Subclass

Figure 12 shows the UML diagram of the RandBBS subclass. This subclass contains two properties (bbs_p and bbs_q) to store the prime constants, p and q. It uses the property, bbs_m, to store the generator constant M. The subclass also has the property, bbs_mask, which is the user-defined bit mask used to extract the new random value. Finally, it has the BOOL property, bbs_opt, dictating whether to use the user-defined bit-mask or the optimal one discussed earlier in this article. All of these properties are accessed by their respective methods.

The overloaded method, generate, implements the BBS algorithm as shown in Listing 7. The method first retrieves the previous random value and the base modulus, M. It calculates the square of the random value at 64-bit precision, and then determines the modulus result at 32-bit precision. Afterwards, the method applies the appropriate bit mask to the modulus result. It then repeats all of the aforementioned steps until a full 32-bit random value is formed.

By default, the subclass uses the optimal bit mask to extract the bits that will comprise the new random value. The methods, optimalMaskLength and optimalMaskValue (Listing 6), are used to determine the optimal bit mask. However, the subclass can also use a user-defined bit mask. This is done by setting the bit mask using the setMask method and passing a NO to the useOptimalMask method.


Figure 12. UML Diagram of the RandBBS Subclass.

Listing 6. Calculating the optimal bit mask (RandBBS.m).

// -- Calculate the number of bits in the optimal mask
- (unsigned int)optimalMaskLength
{
   unsigned int ui32_len;
   double dbl_val;
   
   // calculate the optimal mask length
   dbl_val = (double) [self getBaseModulus];
   dbl_val = log(dbl_val);
   dbl_val = log(dbl_val);
   ui32_len = ceil(dbl_val);
   
   // return the calculation results
   return(ui32_len);
}

// -- Calculate the optimal BBS mask value
- (unsigned int)optimalMaskValue
{
   unsigned int ui32_len, ui32_msk, ui32_bit;   
   
   // calculate the optimal mask value
   ui32_len = [self optimalMaskLength];
   ui32_msk = 0x0;
   for (ui32_bit = 0; ui32_bit < ui32_len; ui32_bit++)
   {
      ui32_msk = ui32_msk | 0x1;
      ui32_msk = ui32_msk << 0x1;
   }
   ui32_msk = ui32_msk >> 0x1;
   
   // return the calculation results
   return (ui32_msk);
}

Listing 7. The [generate] method (RandBBS.m).

- (NSNumber *)generate
{
   unsigned long long ui64_val;
   unsigned int ui32_val, ui32_mod;
   unsigned int ui32_msk, msk_len, msk_cnt, msk_max;
   
   // initialize the following locals
   ui64_val = [[super randomValue] unsignedLongValue];
   ui32_mod = [self getBaseModulus];
   
   // is an optimal mask requested?
   if ([self isMaskOptimal])
   {
      msk_len = [self optimalMaskLength];
      ui32_msk = [self optimalMaskValue];
   }
   else
   {
      msk_len = [self getMaskLength];
      ui32_msk = [self getMaskValue];
   }
   
   // calculate the new random value
   msk_max = 32 / msk_len;
   ui32_val = 0x00;
   for (msk_cnt = 1; msk_cnt <= msk_max; msk_cnt++)
   {
      // calculate the next random value
      ui64_val = ui64_val * ui64_val;
      ui64_val = ui64_val % ui32_mod;
      
      ui32_val = ui32_val | (ui64_val & ui32_msk);
      if (msk_cnt < msk_max)
         ui32_val = ui32_val << msk_len;
   }
   
   // save the new random number
   [super setRandomValue:ui32_val];
   
   // return the new random number
   return ([super randomValue]);
}

Testing the PRNG Subclasses

A variety of algorithms are available for testing the efficacy of PRNG implementations. These algorithms examine the generated random sequence to determine whether a PRNG is properly configured. They also determine whether or not the generated sequence is statistically suitable for the task at hand.

PRNG test algorithms range from the elegantly simple Lempel-Ziv to the mathematically oriented maximum-of-t test. They all require a large number of random values in order to be effective. A large sample size helps reveal indications of poor randomness such as skewing ness. In fact, it is quite common to have a PRNG generate at least 1000 random values for testing purposes.

This article introduces three simple and effective test algorithms: Lempel-Ziv, Run Method, and Spectral Method. The demo application, DiceC, uses the Spectral Method as its test algorithm.

The Lempel-Ziv Method

The Lempel-Ziv method is one of the simplest test algorithms for a PRNG. In its most basic form, the PRNG in question first outputs its random sequence into a binary file. This file is then compressed using the LZ algorithm or any of its variants. Some implementations do away with file I/O by compressing the random sequence directly in the memory.

Since the LZ algorithm works by identifying and consolidating byte patterns, a pure random sequence should have a near-zero compression ratio. The compression ratio of PRNG random sequence, however, should be very low if it has a near optimal period. Higher compression ratios are often good indications of non-random patterns present in the sequence.

The Lempel-Ziv method is an effective baseline test when comparing various PRNG algorithms. It is also useful for fine-tuning algorithms such as LCG or LFG, whose overall performance is strongly depended on its generator constants or seed values.

The Run Method

The Run method converts a random sequence into a series of states. An ascending state is where each subsequent random value increases with respect to time. It is represented by a (+) sign. The opposite would be a descending state, which is represented by a (-) sign. If the values remain unchanged, the state is considered to be neutral and is represented by a (0).

To illustrate, the random sequence

255 758 029 974 984 320 583 765

has the following random values exhibit an ascending state:

255 -" 758    029 -" 974    974 -" 984
320 -" 583    583 -" 765

whereas the following exhibit a descending state.

758 -" 029      984 -" 320

This reduces the random sequence to the following state sequence

+ - + + - +    +

Once the state sequence is determined, it becomes a simple matter of examining the sequence for any patterns. Long successions of one or more states are undesirable as they indicate a numerical bias in the PRNG random sequence.

The Spectral Method

The Spectral Method divides a random sequence into specific intervals (sometimes known as a spectral period) and then plots the number values within each interval as a scatter graph. The result is a spectrum of data points that can then be examined for patterns.

Figure 13 shows a typical spectrum graph for the BSD rand() function. The random sequence consists of 1000 32-bit unsigned integers. It is generated using a seed value of 0x1ebbccf. The scatter graph is then drawn using a spectral period of 200 values.


Figure 13. Spectral graph of the BSD rand() function.

Notice that the data points are well distributed across the resulting graph. There are no areas where the data points would cluster together forming a pattern. Now, compare this with the spectrum graph for the RandMSM subclass(Figure 14). The random sequence of 1000 integers used in this graph is generated with a seed value of 0x457. Notice the 6 dashed lines located at the bottom of the graph. This indicates that the sequence converged to 6 distinct values after 11 iterations. This is an undesirable trait, especially considering that the implemented MSM algorithm is expected to have a period of 9999 values.


Figure 14. Spectral graph of the MSM generator.

The spectrum graph for the other three subclasses fared much better by comparison. Shown in Figure 15 is the spectrum graph for the RandLFSR subclass. Its random sequence is generated using a seed value of 0xbeef. Like that of the BSD rand() function, the graph shows well-distributed data points with no noticeable patterns.


Figure 15. Spectral graph of the LFSR generator.

Summary

The ability to generate random sequences is an essential component of any software code library. Since digital computers are deterministic machines, the only feasible way of generating random sequences is through the use of a pseudo-random number generators or PRNGs. Five different PRNG algorithms are then introduced and discussed.

Later, the class, RandCore, is proposed to serve as the basis for developing a PRNG Cocoa object. Five different subclasses are then based off the RandCore class, with each subclass implementing one of the five PRNG algorithms. Both RandCore and its five subclasses are implemented in the demo application, DiceC. Also, introduced are three test algorithms for testing the PRNG subclasses. One of these algorithms, the Spectral Method, is implemented in DiceC to evaluate the performance of RandCore and its five subclasses.

Bibliography and References

Harvey Gould, Jan Tobochnik, Wolfgang Christian. Random Number Sequences. An Introduction to Computer Simulation Methods. pp.245-249. PDF document posted on 2005 May 19. (c) 2005 Gould, Tobochnik and Christian.

Makoto Matsumoto, Takuji Nishimura. Mersenne Twister:A 623-dimensionally equidistributed uniform pseudorandom number generator. ACM Transactions on Modeling and Computer Simulations:Special Issue on Uniform Random Number Generation. 1998.

Karl Entacher, Hannes Leeb. Inversive Pseudo-random Number Generators:Empirical Results. Parallel Numerics 95. Department of Mathematics. University of Salzburg, Austria. 1995 Sep 27-29.

Jagannath Pisharath. Linear Congruential Number Generators. Newer Math. 2003 Sep.

Martin Geisler, Mikkel Kroigard and Andreas Danielsen. About Random Bits. 2004 Dec 03.

Wikipedia. Euclid's Algorithm. In Wikipedia, the free encyclopedia. The Wikipedia Community, Oct 2005. Online: http://en.wikipedia.org/wiki/Euclidean_algorithm.

Wikipedia. Pseudorandom number generator. In Wikipedia, the free encyclopedia. The Wikipedia Community, Oct 2005. Online: http://en.wikipedia.org/wiki/PRNG.


JC is a freelance engineering consultant currently residing in North Vancouver, BC. He divides his time between custom application development for OS X, technical writing, and teaching origami to children at the local district libraries.

 
AAPL
$104.83
Apple Inc.
+1.84
MSFT
$45.02
Microsoft Corpora
+0.64
GOOG
$543.98
Google Inc.
+11.27

MacTech Search:
Community Search:

Software Updates via MacUpdate

Delicious Library 3.3.2 - Import, browse...
Delicious Library allows you to import, browse, and share all your books, movies, music, and video games with Delicious Library. Run your very own library from your home or office using our... Read more
Art Text 2.4.8 - Create high quality hea...
Art Text is an OS X application for creating high quality textual graphics, headings, logos, icons, Web site elements, and buttons. Thanks to multi-layer support, creating complex graphics is no... Read more
Live Interior 3D Pro 2.9.6 - Powerful an...
Live Interior 3D Pro is a powerful yet very intuitive interior designing application. View Video Tutorials It has every feature of Live Interior 3D Standard, plus some exclusive ones: Create multi... Read more
The Hit List 1.1.7 - Advanced reminder a...
The Hit List manages the daily chaos of your modern life. It's easy to learn - it's as easy as making lists. And it's powerful enough to let you plan, then forget, then act when the time is right.... Read more
jAlbum Pro 12.2.4 - Organize your digita...
jAlbum Pro has all the features you love in jAlbum, but comes with a commercial license. With jAlbum, you can create gorgeous custom photo galleries for the Web without writing a line of code!... Read more
jAlbum 12.2.4 - Create custom photo gall...
With jAlbum, you can create gorgeous custom photo galleries for the Web without writing a line of code! Beginner-friendly, with pro results Simply drag and drop photos into groups, choose a design... Read more
ExpanDrive 4.1.7 - Access remote files o...
ExpanDrive builds cloud storage in every application, acts just like a USB drive plugged into your Mac. With ExpanDrive, you can securely access any remote file server directly from the Finder or... Read more
OmniOutliner Pro 4.1.3 - Pro version of...
OmniOutliner Pro is a flexible program for creating, collecting, and organizing information. Give your creativity a kick start by using an application that's actually designed to help you think. It'... Read more
Evernote 5.6.2 - Create searchable notes...
Evernote allows you to easily capture information in any environment using whatever device or platform you find most convenient, and makes this information accessible and searchable at anytime, from... Read more
OmniOutliner 4.1.3 - Organize your ideas...
OmniOutliner is a flexible program for creating, collecting, and organizing information. Give your creativity a kick start by using an application that's actually designed to help you think. It's... Read more

Latest Forum Discussions

See All

Toca Boo (Education)
Toca Boo 1.0.2 Device: iOS Universal Category: Education Price: $2.99, Version: 1.0.2 (iTunes) Description: BOO! Did I scare you!? My name is Bonnie and my family loves to spook! Do you want to scare them back? Follow me and I'll... | Read more »
Intuon (Games)
Intuon 1.1 Device: iOS Universal Category: Games Price: $.99, Version: 1.1 (iTunes) Description: Join the battle with your intuition in a new hardcore game Intuon! How well do you trust your intuition? Can you find a needle in a... | Read more »
Ravenous Rampage (Games)
Ravenous Rampage 1.0 Device: iOS Universal Category: Games Price: $.99, Version: 1.0 (iTunes) Description: | Read more »
Partia 2 (Games)
Partia 2 1.0.1 Device: iOS Universal Category: Games Price: $5.99, Version: 1.0.1 (iTunes) Description: Partia 2 is a SRPG (Strategy Role-playing) video game inspired by Fire Emblem and Tear Ring Saga series. In a high fantasy... | Read more »
Puzzle to the Center of the Earth Review
Puzzle to the Center of the Earth Review By Campbell Bird on October 23rd, 2014 Our Rating: :: SPELUNKING PUZZLESUniversal App - Designed for iPhone and iPad Do some puzzles to make some platforms in this smart and fun free-to-play... | Read more »
Sleep Attack TD Review
Sleep Attack TD Review By Jennifer Allen on October 23rd, 2014 Our Rating: :: A TRUE TWISTUniversal App - Designed for iPhone and iPad Sleep Attack TD is a tower defense game with a difference – you can rotate the layout – and it’s... | Read more »
Mecanic (Education)
Mecanic 1.0 Device: iOS Universal Category: Education Price: $1.99, Version: 1.0 (iTunes) Description: Plates, screws, wheels ... Everything you need to achieve whatever you want... MECHANICWith 'MECANIC' kids will have fun... | Read more »
Earn Your Master Camper Badge in Camp Po...
Earn Your Master Camper Badge in Camp Pokemon Posted by Jessica Fisher on October 23rd, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Garruk Gets His Revenge in a New Magic 2...
Garruk Gets His Revenge in a New Magic 2015 Expansion, Coming This November Posted by Jessica Fisher on October 23rd, 2014 [ permalink ] | Read more »
Sentinels of the Multiverse Review
Sentinels of the Multiverse Review By Rob Thomas on October 23rd, 2014 Our Rating: :: SENTINELS ASSEMBLEiPad Only App - Designed for the iPad Greater Than Games’ tabletop classic, Sentinels of the Multiverse swoops in to save the... | Read more »

Price Scanner via MacPrices.net

Save up to $125 on Retina MacBook Pros
B&H Photo has the new 2014 13″ and 15″ Retina MacBook Pros on sale for up to $125 off MSRP. Shipping is free, and B&H charges NY sales tax only. They’ll also include free copies of Parallels... Read more
Apple refurbished Time Capsules available sta...
The Apple Store has certified refurbished Time Capsules available for up to $60 off MSRP. Apple’s one-year warranty is included with each Time Capsule, and shipping is free: - 2TB Time Capsule: $255... Read more
Textilus New Word, Notes and PDF Processor fo...
Textilus is new word-crunching, notes, and PDF processor designed exclusively for the iPad. I haven’t had time to thoroughly check it out yet, but it looks great and early reviews are positive.... Read more
WD My Passport Pro Bus-Powered Thunderbolt RA...
WD’s My Passport Pro RAID solution is powered by an integrated Thunderbolt cable for true portability and speeds as high as 233 MB/s. HighlightsOverviewSpecifications Transfer, Back Up And Edit In... Read more
Save with Best Buy’s College Student Deals
Take an additional $50 off all MacBooks and iMacs at Best Buy Online with their College Students Deals Savings, valid through November 1st. Anyone with a valid .EDU email address can take advantage... Read more
iPad Air 2 & iPad mini 3 Best Tablets Yet...
The new iPads turned out to be pretty much everything I’d been hoping for and more than I’d expected.”More” particularly in terms of a drinking-from-a-firehose choice of models and configurations,... Read more
Drafts 4 Reinvents iOS Productivity App
N Richland Hills, Texas based Agile Tortoise has announced the release of Drafts 4 for iPhone and iPad. Drafts is a quick capture note taking app with flexible output actions. Drafts 4 scales from... Read more
AT&T accepting preorders for new iPads fo...
AT&T Wireless is accepting preorders for the new iPad Air 2 and iPad mini 3, cellular models, for $100 off MSRP with a 2-year service agreement: - 16GB iPad Air 2 WiFi + Cellular: $529.99 - 64GB... Read more
Apple offering refurbished Mac Pros for up to...
The Apple Store is offering Apple Certified Refurbished 2013 Mac Pros for up to $600 off the cost of new models. An Apple one-year warranty is included with each Mac Pro, and shipping is free. The... Read more
Select MacBook Airs $100 off MSRP, free shipp...
B&H Photo has 2014 a couple of MacBook Airs on sale for $100 off MSRP. Shipping is free, and B&H charges NY sales tax only. They also include free copies of Parallels Desktop and LoJack for... Read more

Jobs Board

*Apple* Solutions Consultant - Apple Inc. (U...
…important role that the ASC serves is that of providing an excellent Apple Customer Experience. Responsibilities include: * Promoting Apple products and solutions Read more
Senior Event Manager, *Apple* Retail Market...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global event strategy. Delivering an overarching brand story; in-store, Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Project Manager / Business Analyst, WW *Appl...
…a senior project manager / business analyst to work within our Worldwide Apple Fulfillment Operations and the Business Process Re-engineering team. This role will work Read more
*Apple* Retail - Multiple Positions (US) - A...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.