M6L5 Generalization of LCGs

pdf

School

California Lutheran University *

*We aren’t endorsed by this school

Course

ISYE6644

Subject

Electrical Engineering

Date

Oct 30, 2023

Type

pdf

Pages

Uploaded by CountTapir3340

Generalization of LCGs Example R Code This R script primarily focuses on the generation of pseudo-random numbers and visualizing their distributions. It includes various types of random number generators (RNGs) , including the Linear Congruential Generator (LCG) , a Generalized LCG, a Combined Generator, a Shuffle Generator, an XOR generator, and L'Ecuyer's (1999) MRG32k3a generator . Here is a summary of the major components: Box-Muller Method : The Box-Muller method is used to generate normally distributed random numbers from uniformly distributed random numbers. The function box_muller accepts a RNG function as an argument, and then transforms the output of that RNG into normally distributed values. Random Number Generators (RNGs): There are several RNGs defined, including genGLCG (a Generalized LCG), LCG (a basic Linear Congruential Generator), X_generator and Y_generator (two specific LCGs with given parameters), combined_generator (which combines the outputs of the X and Y generators), shuffle_generator (which shuffles the output of the X generator based on the rank of the Y generator), XOR_generator (which applies the XOR operation to the X and Y generators), and MRG32k3a (an implementation of L'Ecuyer's combined multiple recursive generator). Generation of Distributions and Plotting: For each RNG, the script generates a set of normally-distributed random numbers using the Box-Muller method, and stores them in variables genlcg, cg, sg, xorg, and bms. It then creates a ggplot2 scatterplot for each RNG, plots the generated values, and arranges all these plots on a grid using the grid.arrange function from the gridExtra package. Each scatterplot is a visualization of the normally-distributed random numbers generated by a different RNG, and should show the differences in the distributions produced by these various RNGs when transformed using the Box-Muller method. library(ggplot2) library(gridExtra) # Function to create a 4 quadrant coordinate axis create_4_quadrant_axis <- function () { list( geom_vline(aes( xintercept = 0 ), linetype = "dashed" , color = "black" ), geom_hline(aes( yintercept = 0 ), linetype = "dashed" , color = "black" ), coord_cartesian( xlim = c(- 4 , 4 ), ylim = c(- 4 , 4 )) ) }

# Box-Muller method box_muller <- function (n, rng, seed) { random_numbers <- rng(n * 2 , seed) uniform_random_numbers <- random_numbers / max(random_numbers) u1 <- uniform_random_numbers[seq( 1 , n * 2 , 2 )] u2 <- uniform_random_numbers[seq( 2 , n * 2 , 2 )] z0 <- sqrt(- 2 * log(u1)) * cos( 2 * pi * u2) z1 <- sqrt(- 2 * log(u1)) * sin( 2 * pi * u2) return(list( x = z0, y = z1)) } genGLCG <- function (seed, a, m, n) { q <- length(seed) if (q != length(a)) { stop( "Length of seed must be equal to length of a" ) } X <- numeric(n) X[ 1 :q] <- seed for (i in (q+ 1 ):n) { X[i] <- sum(a * rev(X[(i-q):(i -1 )])) %% m } X } LCG <- function (seed, a, b, m, n) { # Initialize the generator X <- numeric(n) X[ 1 ] <- seed # Generate the sequence for (i in 2 :n) { X[i] <- (a * X[i -1 ] + b) %% m } return(X) } # Create two generators X_generator <- function (n) LCG( 123 , 40014 , 0 , 2147483563 , n) Y_generator <- function (n) LCG( 456 , 40692 , 0 , 2147483399 , n)

# Combine two generators combined_generator <- function (n, m) { X <- X_generator(n) Y <- Y_generator(n) # Combine the two sequences Z <- (X + Y) %% m return(Z) } # Shuffle function shuffle_generator <- function (n) { # Generate the sequences X <- X_generator(n) Y <- Y_generator(n) # Convert Y to a sequence of indices indices <- rank(Y) # Use Y to shuffle X Z <- X[indices] return(Z) } # Combine two generators using XOR operation XOR_generator <- function (n) { # Generate the sequences X <- X_generator(n) Y <- Y_generator(n) # Convert to integers to perform XOR operation X_int <- as.integer(X) Y_int <- as.integer(Y) # XOR operation Z <- bitwXor(X_int, Y_int) return(Z) } MRG32k3a <- function (n, seeds = list( z1 = c( 12345 , 12345 , 123 ), z2 = c( 12345 , 12345 , 123 ) )) { # Constants m1 <- 2 ^ 32 - 209 m2 <- 2 ^ 32 - 22853 a12 <- 1403580 a13n <- 810728 a21 <- 527612

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

a23n <- 1370589 # Initial seed values (must be larger than 0 and less # than m1 and m2 respectively) z1 <- seeds$z1 # example seeds z2 <- seeds$z2 # example seeds # Output vector U <- numeric(n) for (i in 1 :n) { # Component 1 z1_new <- (a12 * z1[ 2 ] - a13n * z1[ 1 ]) %% m1 z1 <- c(z1[- 1 ], z1_new) # Component 2 z2_new <- (a21 * z2[ 3 ] - a23n * z2[ 1 ]) %% m2 z2 <- c(z2[- 1 ], z2_new) # Combining components y <- (z1[ 3 ] - z2[ 3 ]) %% m1 U[i] <- y / m1 # normalize } return(U) } n <- 1e4 genlcg <- box_muller(n, function (n, seed) genGLCG( seed = c( 1 , 2 , 3 ), a = c( 2 , 3 , 5 ), m = 2 ^ 32 , n)) cg <- box_muller(n, function (n, seed) combined_generator(n, 2 ^ 32 )) sg <- box_muller(n, function (n, seed) shuffle_generator(n)) xorg <- box_muller(n, function (n, seed) XOR_generator(n)) bms <- box_muller(n, function (n, seed) MRG32k3a(n, seed = list( z1 = c( 1 , 2 , 3 ), z2 = c( 4 , 5 , 6 )))) plot_list <- list( genlcg = genlcg, cg = cg, sg = sg, xorg = xorg, bms = bms) colors <- c( "purple" , "blue" , "orange" , "red" , "green" ) titles <- c( "Generalized LCG" , "Combined Generator 1" , "Shuffle Generator" , "XOR Generator" , "L'Ecuyer (1999)" ) plots <- lapply( 1 :length(plot_list), function (i) {

p <- ggplot() + create_4_quadrant_axis() + geom_point( data = data.frame( x = plot_list[[i]]$x, y = plot_list[[i]]$y), aes( x = x, y = y), col = colors[i], alpha = 0.05 ) + labs( title = titles[i], x = "x" , y = "y" ) + theme_minimal() + theme( plot.title = element_text( size = 16 ), axis.title = element_text( size = 14 ), axis.text = element_text( size = 12 )) return(p) }) grid.arrange( grobs = plots, ncol = 2 ) Generalization of LCGs Example Python Code Python Notebook

Mersenne Twister The Mersenne Twister is a pseudorandom number generator developed in 1997 by Makoto Matsumoto and Takuji Nishimura. It's widely used for its superior performance in a number of statistical tests, speed, and long period. As you noted, the period of this generator is 2^19937 - 1, a Mersenne prime. Here's a simplified overview of how the Mersenne Twister works: Initialization: The generator is initialized with a seed that's used to generate an initial state vector of 624 elements (this number isn't arbitrary; it's related to the Mersenne prime used for the period). The state vector is an internal state of the generator which is used to produce output values. Transformation: For each number the generator produces, it modifies its internal state. This involves taking a few of the elements from the state vector, combining and transforming them, and replacing one of the elements with the result. This transformation ensures the uniformity of the output. Tempering: The generator then takes one element from the state vector and applies a "tempering" transformation to it to produce the output. The tempering transformation involves a series of bitwise operations (shifts and XORs) designed to improve the statistical properties of the generator's output. Periodicity: After 2^19937 - 1 iterations, the generator will start repeating its output sequence. This period is derived from the properties of the Mersenne prime and is much longer than what could be achieved with older pseudorandom number generators. The Mersenne Twister's properties make it a good choice for many simulation and modeling applications, though it's worth noting that it's not suitable for cryptography without modification because its next output can be predicted after observing enough previous outputs. The Mersenne Twister, specifically the MT19937 variant, remains one of the most widely used pseudorandom number generators in a variety of fields. However, new pseudorandom number generators like the Xoroshiro128+ and Permuted Congruential Generator (PCG) have been proposed with claims of better performance and statistical properties

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version