Congruential Algorithms
Uploaded by
ScribdTranslationsCongruential Algorithms
Uploaded by
ScribdTranslationsCongruential algorithms
[Link] algorithm
This congruential algorithm was proposed by D. H. Lehmer in 1951. According to
Law y
Kelton has not been the most used. The linear congruential algorithm generates a
sequence of integers through the following recursive equation:
X i +1=(ax1 +c) mod(m)i=0 , 1 , 2 , 3 , . . . , n
where Xis0 the seed, aes is the multiplicative constant, ces is a constant
additive, and you put the module.0> 0,
X a > 0, c > 0 and m > 0 must be integers.
The operation 'mod (m)' means to multiply, add c,Xand i divide the
X
result between to obtain the remainderi +1It is important to note that the
the recursive equation of the linear congruential algorithm generates a sequence of
integer numbers S = {0, 1, 2, 3, ..., m - 1}, and that to obtain numbers
pseudo-random in the interval (0, 1The following equation is required:
XI
r i= i=0 , 1 , 2 , 3 , . . . , n
m−1
Example:
Generate 4 numbers between 0 and 1 with the following parameters: X0= 37, a = 19, c = 33 and
m = 100.
Solution:
X1 = (19*37 + 33) mod 100 = 36 r1 = 36/99 = 0.3636
X2= (19*36 + 33) mod 100 = 17 r2 = 17/99 = 0.1717
X3= (19* 17 + 33) mod 100 = 56 r3= 56/99 = 0.5656
X4= (19*56 + 33) mod 100 = 97 r4 = 97/99 = 0.9797
In the previous example, each of the parameters was given arbitrarily.
required: X0, a, c, m. However, for the algorithm to be able to achieve the
maximum lifespan N, it is necessary for those parameters to meet certain
conditions. Banks, Carson, Nelson, and Nicol suggest the following:
m=2 g
a = 1 + 4k
it must be an integer
relatively first am
it must be whole
Under these conditions, a maximum lifespan is obtained: N=m=2g
2. Multiplicative congruential algorithm
The multiplicative congruential algorithm arises from the linear congruential algorithm.
when
c = 0. Then the recursive equation is:
X i +1={aX1 ¿ mod(m) i=0 , 1 , 2 , 3 , . . . , n In comparison with the algorithm
linear congruential, the advantage of the multiplicative algorithm is that it involves a
operation to be performed. The startup parameters of this algorithm are
X0, aym, which must be integers and greater than zero. For
transform the numbers X in the interval (0,1) the equation is usedi= (m-
, r x
1). According to Banks, Carson, Nelson, and Nicol, the conditions that must
meet the parameters for the multiplicative congruential algorithm
reach their maximum period N, they are:
M =2 g
a=3+8k o a = 5 + 8k
k = 0, 1, 2, 3, ...
X 0=it must be an odd number
g=it must be whole
g−2
Under these conditions, a maximum lifespan is achieved. N=k /4=2
Example:
Generate enough numbers between 0 and 1 with the following parameters:0= 17,X
k=2y
g = 5, until finding the period or life cycle.
Solution:
a = 5 + 8 (2) = 21 and m = 32
X0= 17
X1 =(21*17) mod 32 = 5 r1 = 5/31 = 0.612
X2= (21*5) mod 32 = 9 r2 = 9/31 = 0.2903
X3 = (21 * 9) mod 32 = 29 r3 = 29/31 = 1.9354
X4 = (21*29) mod 32 = 1 r4 = 1/31 = 0.3225
X5=(21*1) mod 32 = 21 r5= 21/31 = 0.6774
X6= (21*21) mod 32 = 2 5 r6 = 25/31 = 0.8064
X7 = (21*25) mod 32 = 13 r? = 13/31 = 0.4193
X8 = (21*13) mod 32 = 17 r8= 17/31 =0.5483
If seed X0 is repeated, the same numbers will be generated again.
Thus, the lifespan is n = 8, which corresponds to N = m / 4 = 32 / 4 = 8.
3. Additive congruential algorithm
This algorithm requires a previous sequence of integers X1, X2, X3X
4, ..., Xn for
generate a new sequence of integers that starts at Xn+1, Xn+2,
X n+3, X+4 , ...
Its recursive equation is:
Xi = ( Xi +1+ Xi−n ) mod (m) i = n + 1, n + 2, n + 3, ... N
r i be generated using the equation
The numbers can
r i = xi/m – 1
Example
Generate 7 pseudo-random numbers between zero and one from the following
sequence
de números enteros: 65 ,89 , 98 ,03 ,69 ; m = 100.
Sean X1 = 65, X2 = 89, X3 = 98, X4 = 03, X5 = 69. To generate r1, r2, r3, r4, r5, r6 and
It is necessary to generate X^ X7, X8, X9, X10, X11, X12.
Solution:
X6 = (X5 + X1) mod 100 = (69 + 65) mod 100 = 34
X7= (X6 + X2) mod 100 = (34 + 89) mod 100 = 23
X8 = (X7 + X3) mod 100 = (23 + 98) mod 100 = 21
X9 = (X8 + X4) mod 100 = (21 + 03) mod 100 = 24
X 10= (X 9+ X5) mod 100 = (24 + 69) mod 100 = 93
X u = (X10 + X J mod 100 = (93 + 34) mod 100 = 27
X 12= (X „ + X 7) mod 100 = (27+ 23) mod 100 = 5 0
r1 = 34/99 = 0.3434
r2=23/99 = 0.2323
r3=21/99 = 0.2121
r4 = 24/99 = 0.2424
93/99=0.9393
r6 = 27/99 = 0.2727
r7 = 50/99 = 0.5050
