<p><div><div><div><div data-show-faces="false" data-height="21" data-width="100" data-layout="button_count" data-send="true" data-href="https://www.r-bloggers.com/linear-congruential-generator-in-r/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="http://www.aaronschlegel.com/linear-congruential-generator-r/"> R – Aaron Schlegel</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<div>Part of 1 in the series <a rel="nofollow" href="http://www.aaronschlegel.com/series/random-number-generation/" title="Random Number Generation" target="_blank">Random Number Generation</a></div>
<p>A Linear congruential generator (LCG) is a class of pseudorandom number generator (PRNG) algorithms used for generating sequences of random-like numbers. The generation of random numbers plays a large role in many applications ranging from cryptography to Monte Carlo methods. Linear congruential generators are one of the oldest and most well-known methods for generating random numbers primarily due to their comparative ease of implementation and speed and their need for little memory. Other methods such as the Mersenne Twister are much more common in practical use today.</p>
<p>Linear congruential generators are defined by a recurrence relation:</p>
<img alt=" \large{X_{i+1} = (aX_i + c) \space \text{mod} \space m} " title=" \large{X_{i+1} = (aX_i + c) \space \text{mod} \space m} " src="https://s0.wp.com/latex.php?latex=+%5Clarge%7BX_%7Bi%2B1%7D+%3D+%28aX_i+%2B+c%29+%5Cspace+%5Ctext%7Bmod%7D+%5Cspace+m%7D+&bg=ffffff&fg=000&s=0" class="latex">
<p>There are many choices for the parameters <img alt="m" title="m" src="https://s0.wp.com/latex.php?latex=m&bg=ffffff&fg=000&s=0" class="latex">, the modulus, <img alt="a" title="a" src="https://s0.wp.com/latex.php?latex=a&bg=ffffff&fg=000&s=0" class="latex">, the multiplier, and <img alt="c" title="c" src="https://s0.wp.com/latex.php?latex=c&bg=ffffff&fg=000&s=0" class="latex"> the increment. Wikipedia has a seemingly <a rel="nofollow" href="https://en.wikipedia.org/wiki/Linear_congruential_generator#Parameters_in_common_use" target="_blank">comprehensive list of the parameters</a> currently in use in common programs.</p>
<h6>Aside: ‘Pseudorandom’ and Selecting a Seed Number</h6>
<p>Random number generators such as LCGs are known as ‘pseudorandom’ as they require a seed number to generate the random sequence. Due to this requirement, random number generators today are not truly ‘random.’ The theory and optimal selection of a seed number are beyond the scope of this post; however, a common choice suitable for our application is to take the current system time in microseconds.</p>
<h6>A Linear Congruential Generator Implementation in R</h6>
<p>The parameters we will use for our implementation of the linear congruential generator are the same as the ANSI C implementation (Saucier, 2000.).</p>
<img alt=" \large{m = 2^{32} \qquad a = 1103515245 \qquad c = 12345} " title=" \large{m = 2^{32} \qquad a = 1103515245 \qquad c = 12345} " src="https://s0.wp.com/latex.php?latex=+%5Clarge%7Bm+%3D+2%5E%7B32%7D+%5Cqquad+a+%3D+1103515245+%5Cqquad+c+%3D+12345%7D+&bg=ffffff&fg=000&s=0" class="latex">
<p>The following function is an implementation of a linear congruential generator with the given parameters above.</p>
<pre>
lcg.rand &lt;- function(n=10) {
  
  rng &lt;- vector(length = n)
  
  m &lt;- 2 ** 32
  a &lt;- 1103515245
  c &lt;- 12345

  # Set the seed using the current system time in microseconds
  d &lt;- as.numeric(Sys.time()) * 1000
  
  for (i in 1:n) {
    d &lt;- (a * d + c) %% m
    rng[i] &lt;- d / m
  }
  
  return(rng)
}
</pre>
<p>We can use the function to generate random numbers <img alt="U(0, 1)" title="U(0, 1)" src="https://s0.wp.com/latex.php?latex=U%280%2C+1%29&bg=ffffff&fg=000&s=0" class="latex">.</p>
<pre>
# Print 10 random numbers on the half-open interval [0, 1)
lcg.rand()
##  [1] 0.4605103 0.6643705 0.6922703 0.4603930 0.1842995 0.6804419 0.8561535
##  [8] 0.2435846 0.8236771 0.9643965
</pre>
<p>We can also demonstrate how apparently ‘random’ the LCG is by plotting a sample generation in 3 dimensions. To do this, we generate three random vectors <img alt="x, y, z" title="x, y, z" src="https://s0.wp.com/latex.php?latex=x%2C+y%2C+z&bg=ffffff&fg=000&s=0" class="latex"> using our LCG above and plot. The <a rel="nofollow" href="https://cran.r-project.org/web/packages/plot3D/index.html" target="_blank">plot3d package</a> is used to create the scatterplot, and the <a rel="nofollow" href="https://cran.r-project.org/web/packages/animation/" target="_blank">animation package</a> is used to animate each scatterplot as the length of the random vectors, <img alt="n" title="n" src="https://s0.wp.com/latex.php?latex=n&bg=ffffff&fg=000&s=0" class="latex">, increases.</p>
<pre>
library(plot3D)
library(animation)
</pre>
<pre>
n &lt;- c(3, 10, 20, 100, 500, 1000, 2000, 5000, 10000, 20000)

saveGIF({
  for (i in 1:length(n)) {
    x &lt;- lcg.rand(n[i])
    y &lt;- lcg.rand(n[i])
    z &lt;- lcg.rand(n[i])
    
    scatter3D(x, y, z, colvar = NULL, pch=20, cex = 0.5, theta=20, main = paste('n = ', n[i]))
  }
}, movie.name = 'lcg.gif')
</pre>
<p><a rel="nofollow" href="http://www.aaronschlegel.com/?attachment_id=22620" target="_blank"><img alt="Linear Congruential Generator plot of generated points" src="https://i1.wp.com/www.aaronschlegel.com/wp-content/uploads/lcg.gif?resize=480%2C480" class="wp-image-22620" data-recalc-dims="1"></a></p>
<p>As <img alt="n" title="n" src="https://s0.wp.com/latex.php?latex=n&bg=ffffff&fg=000&s=0" class="latex"> increases, the LCG appears to be ‘random’ enough as demonstrated by the cloud of points.</p>
<h6>Linear Congruential Generators with Poor Parameters</h6>
<p>The values chosen for the parameters <img alt="m, a \text{and} c" title="m, a \text{and} c" src="https://s0.wp.com/latex.php?latex=m%2C+a+%5Ctext%7Band%7D+c&bg=ffffff&fg=000&s=0" class="latex"> are very important in driving how ‘random’ the generated values from the linear congruential estimator; hence that is why there are so many different parameters in use today as there has not yet been a clear consensus on the ‘best’ parameters to use.</p>
<p>We can demonstrate how choosing poor parameters for our LCG leads to not so random generated values by creating a new LCG function.</p>
<pre>
lcg.poor &lt;- function(n=10) {
  
  rng &lt;- vector(length = n)
  
  # Parameters taken from https://www.mimuw.edu.pl/~apalczew/CFP_lecture3.pdf
  m &lt;- 2048
  a &lt;- 1229
  c &lt;- 1

  d &lt;- as.numeric(Sys.time()) * 1000
  
  for (i in 1:n) {
    d &lt;- (a * d + c) %% m
    rng[i] &lt;- d / m
  }
  
  return(rng)
}
</pre>
<p>Generating successively longer vectors using the ‘poor’ LCG and plotting as we did previously, we see the generated points are very sequentially correlated, and there doesn’t appear to be any ‘randomness’ at all as <img alt="n" title="n" src="https://s0.wp.com/latex.php?latex=n&bg=ffffff&fg=000&s=0" class="latex"> increases.</p>
<pre>
n &lt;- c(3, 10, 20, 100, 500, 1000, 2000, 5000, 10000, 20000)
saveGIF({
  for (i in 1:length(n)) {
    x &lt;- lcg.poor(n[i])
    y &lt;- lcg.poor(n[i])
    z &lt;- lcg.poor(n[i])
    
    scatter3D(x, y, z, colvar = NULL, pch=20, cex=0.5, theta=20, main = paste('n = ', n[i]))
  }
}, movie.name = 'lcg_poor.gif')
</pre>
<p><a rel="nofollow" href="http://www.aaronschlegel.com/?attachment_id=22621" target="_blank"><img alt="Linear congruential generator with poor parameters" src="https://i0.wp.com/www.aaronschlegel.com/wp-content/uploads/lcg_poor.gif?resize=480%2C480" class="wp-image-22621" data-recalc-dims="1"></a></p>
<h6>References</h6>
<p>Saucier, R. (2000). Computer Generation of Statistical Distributions (1st ed.). Aberdeen, MD. Army Research Lab.</p>
<p>The post <a rel="nofollow" href="http://www.aaronschlegel.com/linear-congruential-generator-r/" target="_blank">Linear Congruential Generator in R</a> appeared first on <a rel="nofollow" href="http://www.aaronschlegel.com/" target="_blank">Aaron Schlegel</a>.</p>
	<p>
<div>
<div>To <strong>leave a comment</strong> for the author, please follow the link and comment on their blog: <strong><a href="http://www.aaronschlegel.com/linear-congruential-generator-r/"> R – Aaron Schlegel</a></strong>.</div>
<hr>
<a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers.com</a> offers <strong><a rel="nofollow" href="https://feedburner.google.com/fb/a/mailverify?uri=RBloggers">daily e-mail updates</a></strong> about <a rel="nofollow" href="https://www.r-project.org/" title="The R Project for Statistical Computing">R</a> news and <a rel="nofollow" href="https://www.r-bloggers.com/search/tutorial" title="R tutorials">tutorials</a> on topics such as: <a rel="nofollow" href="https://www.r-bloggers.com/search/data%20science" title="Data science">Data science</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Big%20Data" title="Big Data">Big Data, <a rel="nofollow" href="https://www.r-users.com/" title="R jobs">R jobs</a>, visualization (<a rel="nofollow" href="https://www.r-bloggers.com/search/ggplot2" title="ggplot and ggplot2 tutorials">ggplot2</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/boxplot" title="Boxplots using lattice and ggplot2 tutorials">Boxplots</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/map" title="Maps and gis">maps</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/animation" title="Animation in R">animation</a>), programming (<a rel="nofollow" href="https://www.r-bloggers.com/search/RStudio" title="RStudio IDE for R">RStudio</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/sweave" title="Sweave and literate programming">Sweave</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/LaTeX" title="LaTeX in R">LaTeX</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/SQL" title="SQL and databases">SQL</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/eclipse" title="Eclipse IDE for R">Eclipse</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/git" title="git and github, Version Control System">git</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/hadoop" title="Large data in R using Hadoop">hadoop</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Web+Scraping" title="Web Scraping of google, facebook, yahoo, twitter and more using R">Web Scraping</a>) statistics (<a rel="nofollow" href="https://www.r-bloggers.com/search/regression" title="Regressions and ANOVA analysis tutorials">regression</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/PCA" title="principal component analysis tutorial">PCA</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/time+series" title="Time series">time series</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/trading" title="finance trading">trading</a>) and more...
<img width="1" alt="" src="http://feeds.feedburner.com/~r/RBloggers/~4/3Q4Y8j2W5Ek" height="1"></a></div>