Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-08-06
2002-11-12
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S491000
Reexamination Certificate
active
06480870
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a random number generator.
2. Background of the Related Art
In general, a multiplicative linear congruential pseudorandom number generator is often employed for software routines. A random number represents a number selected from a number set where the same probability is assigned to all the numbers in the number set.
The random number generated by a computer using a big cycle is called a pseudorandom number. Such a random number generator for generating pseudo random numbers is applicable to a variety of fields including computer programming, simulation and network routing. Among them, the multiplicative linear congruential pseudorandom number generator is most widely employed.
Based on the thesis “Hardware implementation of the Lehmer random number generator” (IEE Proc.-Compute. Digit. Tech., Vol. 143, p93-95, January 1996) disclosed by A. P. Paplinski and N. Bhattacharjee, the principle of the Lehmer random number generator and a conventional hardware implementation will now be described. A Lehmer generator is a method where a random number generator is implemented in software, and the principle of the Lehmer generator is as follows.
First, a integer pseudorandom number row of z
(1)
, z
(2)
, z
(3)
, . . . is generated as Equation 1:
z
(n−1)
=f
(
z
(n)
),
n=
1, 2, 3, . . . (1).
In Equation 1, a generation function F(·) is defined as follows in Equation 2:
r=f
(
z
)=
a·z
mod
M, z&egr;
1, 2,
. . . M−
1 (2).
At this time, for the Lehmer generator, Mersenne prime M=2
31
−1, and a=7
5
=16807 are satisfied. That is, a 15-bit binary system satisfies a
14:0
={100000110100111}, and a random number z
(z)
is an integer implemented in 31 bits.
Using a binary digit multiplication mod M as shown in Equation 2, a parallelized version of algorithm is considered to generate a previous random number z to a subsequent random number r.
To explain a hardware implementation of such a number algorithm, it is convenient to distinguish a number from its corresponding binary system. If a is an integer, a's (n+1)-bit binary representation may be expressed in a
n:0
. If a matrix is applied, a can be implemented using a scalar product of a
n:0
and 2's weight W
n:0
vector as follows in Equation 3:
a
=
a
n
:
0
·
W
n
:
0
=
∑
i
=
0
n
a
i
·
2
n
.
(
3
)
In Equation 3, a
n:0
={a
n
a
n−1
. . . a
1
a
0
} denotes a numeral Equation of a{a&egr;{0,1}}, and W
n:0
={2
n
2
n−1
. . . 2
1
2
0
} denotes a vector of binary digit weight.
Using Equation 3, a number multiplication can be expressed in a Silvester resultant matrix by a matrix product of a multiplier and a multiplicand thereof. If an m-bit multiplicand is Z
m−1:0
={Z
m−1
Z
m−2
. . . Z
1
Z
0
}, the product of the two numbers a and z may be expressed in a binary matrix as follows in Equation 4:
a·z=a
n:0
·(
z
)
n
·w
n+m−1:0
(4).
In Equation 4, (z)
n
is a (n+1)×(n+m) Silvester resultant matrix (i.e., a convolution matrix), and it is formed from a shifted number Z
m−1:0
as follows in Equation 5:
(
𝓏
)
n
=
[
𝓏
m
-
1
𝓏
m
-
2
⋯
𝓏
0
𝓏
m
-
1
𝓏
m
-
2
⋯
𝓏
0
0
0
⋯
⋯
𝓏
m
-
1
𝓏
m
-
2
⋯
𝓏
0
]
⟵
n
+
m
⟶
n
+
1.
(
5
)
In Equation 5, the large parenthesis is used to represent the resultant matrix and the zero values form an appropriate triangle.
In the Lehmer generator, m=31, n=14 so that the number a
14:0
is a magnitude of 1×15, in Equation 4. The magnitude of the resultant matrix (z)n is 15×45 and consequently the product of a and z is expressed in 1×45 number.
Generally, Equation 4 can be considered as a parallelized Equation of a product of two numbers. The respective rows of the above resultant Equation represents a shifted number Z
m−1:0
multiplied by respective digits of a multiplier, and the respective columns of the resultant Equation 5 are added up to provide a pseudorandom number result.
The subsequent step of the algorithm determines a residue obtained after dividing a·z by M=2
31
−1. In other words, a mod M operation is carried out. To expand the above product as shown in Equation 6, the resultant matrix is divided into two dependant matrixes: C with a magnitude of (n+1)×n in the left; and D with a magnitude of (n+1)×m in the right of Equation 7. Here, q denotes quotient and r denotes residue.
a·z =q·M+r
(6)
(
𝓏
)
n
=
[
𝓏
m
-
1
⋯
𝓏
m
-
n
❘
𝓏
m
-
n
-
1
⋯
𝓏
0
0
⋯
❘
𝓏
m
-
n
-
2
⋯
𝓏
1
𝓏
0
0
⋮
⋯
𝓏
m
-
1
❘
⋮
⋯
⋯
⋯
0
⋯
0
❘
𝓏
m
-
1
⋯
⋯
𝓏
1
𝓏
0
]
=
[
C
❘
D
]
(
7
)
By combining Equations 4 and 6, Equation 8 is obtained as follows:
a
·
z
=
a
n
:
0
·
(
z
)
n
·
w
n
+
m
-
1
:
0
=
a
n
:
0
·
[
C
D
]
·
w
n
+
m
-
1
:
0
=
a
n
:
0
·
C
·
w
n
-
1
:
0
·
2
m
+
D
·
w
m
-
1
:
0
)
=
a
n
:
0
·
C
·
w
n
-
1
:
0
·
2
m
-
C
·
w
n
-
1
:
0
+
D
·
w
m
-
1
:
0
+
C
·
w
n
-
1
:
0
)
=
a
n
:
0
·
C
·
w
n
-
1
:
0
·
M
+
D
·
w
m
-
1
:
0
+
C
·
w
n
-
1
:
0
)
.
(
8
)
Here, a relation of W
n+m−1:0
=W
n−1:0
·2
m
+W
m−1:0
was used. Considering an integer q, Equation 9 is obtained as follows:
(
q·M+r
)mod
M=r
mod
M
(9)
Equation 1 may be incorporated in Equation 10.
r
=
(
a
·
z
)
mod
M
=
a
n
:
0
(
D
·
w
m
-
1
:
0
+
C
·
w
n
-
1
:
0
)
mod
M
=
a
n
:
0
(
D
·
w
m
-
1
:
0
+
[
0
C
]
·
w
m
-
1
:
0
)
mod
M
(
10
)
Eventually, Equation 11 can be obtained as follows:
r=
(
a
n:0
·E·w
m−1:0
)mod
M
(11).
Here, E is formed of a (n+1)×m circulation convolution matrix as shown as follows in Equation 12:
&AutoLeftMatch;
E
=
D
+
[
0
C
]
=
[
𝓏
m
-
n
-
1
⋯
𝓏
0
𝓏
m
-
1
𝓏
m
-
2
⋯
𝓏
m
-
n
𝓏
m
-
n
-
2
⋯
𝓏
1
𝓏
0
𝓏
m
-
1
⋯
𝓏
m
-
n
+
1
⋮
⋮
⋮
⋮
⋮
𝓏
m
-
2
⋯
𝓏
n
-
1
𝓏
n
-
2
𝓏
n
-
3
⋯
𝓏
m
-
1
𝓏
m
-
1
⋯
𝓏
n
𝓏
n
-
1
𝓏
n
-
2
⋯
𝓏
0
]
⟵
n
⟶
.
⟵
m
⟶
(
12
)
At this time, considering that the multiplier a is a binary system wherein a corresponding bit for a
14
, a
8
, a
7
, a
5
, a
2
, a
1
, a
0
is “1”, Equation 11 can be written as Equation 13 as follows:
r
=
(
a
14
:
0
·
E
·
w
30
:
0
)
mod
M
.
=
(
E
14
:
+
E
8
:
+
E
7
:
+
E
5
:
+
E
2
:
+
E
1
:
+
E
0
:
)
·
w
30
:
0
mod
M
(
13
)
At this time, since (1 1 1)
2
=(1 0 0 −1)
2
is satisfied, three rows from the quotient a can be replaced by +1 and −1 in an appropriate position. Therefore, the finally implemented formula ca
Fleshner & Kim LLP
Hyundai Electronics Industries Co,. Ltd.
Ngo Chuong Dinh
LandOfFree
Random number generator using lehmer algorithm does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Random number generator using lehmer algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random number generator using lehmer algorithm will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2972493