in Books, Doing Books, How to Solve it by Computer

How to Solve it by Computer #7

Algorithm 3.6: Use the linear congruential method to generate a uniform set of pseudo-random numbers.

This is great and something I never did before – like most of the stuff here. The method were using is the linear congruential method which should create a uniform distribution of numbers.

The basic idea is to use the following formula to create the next pseudo-random number:

x_{n+1} = (ax_n + b) mod n for n >= 0

However, there are specific criteria for each parameter.

Parameter x_0: 0 <= x_0 < m
Parameter m: m >= length sequence required, (ax+b) mod m is an integer
Parameter a: if m is a power of 2 then a mod 8 = 5; if m is a power of 10 then a mod 200 = 21
sqrt(m) < a < m – sqrt(m)
(a-1) should be a multiple of every prime dividing into m
if m is a multiple of 4 then (a-1) should be a multiple of 4
Parameter b: b should be odd, not a multiple of 5

These are a lot of requirements and the easiest thing to do is use existing values. Wikipedia provides common parameters.

The ones provided by the book are:

m = 4096
b = 853
a = 109

Here’s the code:

Super straight forward. Let’s see how good it works. We want to compare the average.

Problem 3.6.1: Confirm that the algorithm repeats after generating m random numbers. Compute the mean value and variance for the set of m pseudo-numbers.

Seems to work.

Looks fine. Let’s see how big the variance over the average over the set is.

 

Yup. By the way, here are the functions for calculating the average and variance:

 

Pretty standard.

Write a Comment

Comment