US 2007/0165847 A1 · Defined-distribution pseudo-random number generator

Abstract

The present invention provides a method and an apparatus for generating sequences of pseudo-random numbers. Seed random sequences are used to establish independent pseudo-random sub-processes. Those independent pseudo-random sub-processes are combined through a technique of successive interaction to create final pseudo-random sequences. One set of pseudo-random sub-processes is used to continually reorder a table of potential output values. The table can contain uniformly distributed values or may contain values distributed in a non-uniform manner. A second set of pseudo-random sub-processes is used to select a sequence of output values from the table. The invention creates final pseudo-random sequences of output values that can be equidistributed over large samples or final pseudo-random sequences of output values that have non-uniform distributions.

Claims25

Dependent claims

A method of generating a pseudo-random number, said method comprising the steps of:

a. Establishing an output value set of all possible desired output values, with each possible desired output value represented only once in the output value set;
b. Transforming the output value set into a plurality of distribution sets, each distribution set having all possible desired output values, with each possible desired output value occurring in each distribution set with respect to all other values in that distribution set a number of times corresponding to a relative desired distribution for that desired output value in a final set of desired output values, and with each distribution set having p total elements;
c. Establishing a defined-distribution table containing (k+z) elements by:
i. setting a variable k to be a value greater than or equal to the total number of elements p of each distribution set,
ii. setting a variable z to be a value greater than or equal to 0 and satisfying the condition that (k+z) mod p is congruent to 0, and
iii. loading (k+z)/p multiple distribution sets into a table to create the defined-distribution table;
d. Determining an initial value j1 for an output pointer j;
and
e. Generating a pseudo random number by selecting an element of the defined-distribution table indexed by the output pointer j1.

6 more elements

A method of generating a plurality of pseudo-random numbers, said method comprising the steps of:

a. Establishing an output value set of all possible desired output values, with each possible desired output value represented only once in the output value set;
b. Transforming the output value set into a plurality of distribution sets, each distribution set having all possible desired output values, with each possible desired output value occurring in each distribution set with respect to all other values in that distribution set a number of times corresponding to a relative desired distribution for that desired output value in a final set of desired output values, and with each distribution set having p total elements;
c. Establishing a first defined-distribution table containing (k+z) elements by:
i. setting a variable k to be a value greater than or equal to the total number of elements p of each distribution set,
ii. setting a variable z to be a value greater than or equal to 0 and satisfying the condition that (k+z) mod p is congruent to 0, and
iii. loading (k+z)/p multiple distribution sets into a table to create said first defined-distribution table;
d. Determining an initial value j1 for an output pointer j;
e. Generating a pseudo-random number by selecting an element of said first defined-distribution table indexed by the first output pointer j1;
f. Utilizing a component pseudo-random number generator X to create values X1,a-X1,i;
g. Determining values h1,a-h1,i for shift pointer h from said values X1,a-X1,i;
h. Establishing a rearranged defined-distribution table by shuffling elements of the first defined-distribution table using the shift pointers h1,a-h1,i;
i. Determining a next value j2 for said output pointer j;
j Generating a next pseudo-random number by selecting an element of the rearranged defined-distribution table indexed by the next output pointer j2;
k. Utilizing said component pseudo-random number generator X to create next values X2,a-X2,i;
l. Determining next values h2,a-h2,i for shift pointer h from the next values X2,a-X2,i;
m. Establishing a newly rearranged defined-distribution table by shuffling elements of the prior rearranged defined-distribution table using shift pointers h2,a-h2,i;
and
n. Repeating steps i. through m. to generate a desired number of pseudo-random numbers.

15 more elements

A method of generating a plurality of pseudo-random numbers, said method comprising the steps of:

a. Establishing an output value set of all possible desired output values, with each possible desired output value represented only once in the output value set;
b. Transforming the output value set into a plurality of distribution sets, each distribution set having all possible desired output values, with each possible desired output value occurring in each distribution set with respect to all other values in that distribution set a number of times corresponding to a relative desired distribution for that desired output value in a final set of desired output values, and with each distribution set having p total elements;
c. Establishing a first defined-distribution table containing (k+z) elements by:
i. setting a variable k to be a value greater than or equal to the total number of elements p of each distribution set,
ii. setting a variable z to be a value greater than or equal to 0 and satisfying the condition that (k+z) mod p is congruent to 0, and
iii. loading (k+z)/p multiple distribution sets into a table to create said first defined-distribution table;
d. Determining an initial value j1 for an output pointer j;
e. Generating a pseudo-random number by selecting an element of said first defined-distribution table indexed by the first output pointer j1;
f. Utilizing a component pseudo-random number generator X to create value X1;
g. Determining an initial value h1 for shift pointer h from said value X1;
h. Establishing a rearranged defined-distribution table by shuffling elements of the first defined-distribution table using the shift pointers h1 and the output pointer j1;
i. Determining a next value j2 for said output pointer j;
j. Generating a next pseudo-random number by selecting an element of the rearranged defined-distribution table indexed by the next output pointer j2;
k. Utilizing said component pseudo-random number generator X to create next value X2;
l. Determining next value h2 for shift pointer h from the next value X2;
m. Establishing a newly rearranged defined-distribution table by shuffling elements of the prior rearranged defined-distribution table using shift pointer h2 and output pointer j2;
and
n. Repeating steps i. through m. to generate a desired number of pseudo-random numbers.

15 more elements

A method of generating a plurality of pseudo-random numbers, said method comprising the steps of:

a. Establishing an output value set of all possible desired output values, with each possible desired output value represented only once in the output value set;
b. Transforming the output value set into a plurality of distribution sets, each distribution set having all possible desired output values, with each possible desired output value occurring in each distribution set with respect to all other values in that distribution set a number of times corresponding to a relative desired distribution for that desired output value in a final set of desired output values, and with each distribution set having p total elements;
c. Establishing a first defined-distribution table containing (k+z) elements by:
i. setting a variable k to be a value greater than or equal to the total number of elements p of each distribution set,
ii. setting a variable z to be a value greater than or equal to 0 and satisfying the condition that (k+z) mod p is congruent to 0, and
iii. loading (k+z)/p multiple distribution sets into a table to create said first defined-distribution table;
d. Establishing a sequence of initial values for an output series of pseudo-random number sequence Y;
e. Establishing an initial selector value Y1 from the sequence of initial values for the output series of the pseudo-random number sequence Y;
f. Establishing initial shift values Y1,a-Y1,i from the sequence of initial values for the output series of the pseudo-random number sequence Y;
g. Determining an initial value j1 for an output pointer j from the initial selector value Y1;
h. Generating a pseudo-random number by selecting an element of said first defined-distribution table indexed by the first output pointer j1;
i. Determining initial values h1,a-h1,i for shift pointer h from said initial shift values Y1,a-Y1,i;
j. Establishing a rearranged defined-distribution table by shuffling elements of the first defined-distribution table using initial values h1,a-h1,i for the shift pointers h;
k. Establishing a next sequence of values for an output series of pseudo-random number sequence Y;
l. Establishing a next selector value Y2 from the next sequence of values for the output series of the pseudo-random number sequence Y;
m. Establishing next shift values Y2,a-Y2,i from the next sequence of values for the output series of the pseudo-random number sequence Y;
n. Determining a next value j2 for the output pointer j from the next selector value Y2;
o. Generating a next pseudo-random number by selecting an element of the rearranged defined-distribution table indexed by the next output pointer j2;
p. Determining next values h2,a-h2,i for shift pointer h from the next shift values Y2,a-Y2,i;
q. Establishing a newly rearranged defined-distribution table by shuffling elements of the prior rearranged defined-distribution table using values h2,a-h2,i for shift pointer h;
and
r. Repeating steps k. through q. to generate a desired number of pseudo-random numbers.

19 more elements

An apparatus for generating a plurality of pseudo-random numbers, comprising:

a. Output value means for establishing an output value set of all possible desired output values, with each possible desired output value represented only once in the output value set;
b. Distribution set means for transforming the output value set into a plurality of distribution sets, each distribution set having all possible desired output values, with each possible desired output value occurring in each distribution set with respect to all other values in that distribution set a number of times corresponding to a relative desired distribution for that desired output value in a final set of desired output values, and with each distribution set having p total elements;
c. Defined-distribution table means for establishing a first defined-distribution table containing (k+z) elements by:
i. setting a variable k to be a value greater than or equal to the total number of elements p of each distribution set,
ii. setting a variable z to be a value greater than or equal to 0 and satisfying the condition that (k+z) mod p is congruent to 0, and
iii. loading (k+z)/p multiple distribution sets into a table to create said first defined-distribution table;
d. Output pointer means for determining an initial value j1 for an output pointer j;
e. Pseudo-random number means for generating a pseudo-random number by selecting an element of said first defined-distribution table indexed by the first output pointer j1;
f. Component means for utilizing a component pseudo-random number generator X to create values Xa-Xi;
g. Shift pointer means for determining values ha-hi for shift pointer h from said values Xa-Xi;
h. Rearranged table means for establishing a rearranged defined-distribution table by shuffling elements of the first defined-distribution table using the shift pointers ha-hi;
i. Updating output pointer means for determining a next value j2 for said output pointer j;
j. Next pseudo-random number means for generating a next pseudo-random number by selecting an element of the rearranged defined-distribution table indexed by the next output pointer j2;
k. Updating component means for utilizing said component pseudo-random number generator X to create next values X2a-X2,i;
l. Updating shift pointer means for determining next values h2,a-h2,i for shift pointer h from the next values X2,a-X2,i;
m. Newly rearranged table means for establishing a newly rearranged defined-distribution table by shuffling elements of the prior rearranged defined-distribution table using shift pointers h2,a-h2,i;
and
n. Repetitive means for sequentially utilizing the rearranged table means, the updated outpoint pointer means, the next pseudo-random number means, the updating component means, the updating shift pointer means, and the newly rearranged table means to generate a desired number of pseudo-random numbers.

15 more elements

Dependencies are inferred from the claim text.

Defined-distribution pseudo-random number generator

Life of this patent

Defined-distribution pseudo-random number generator

Life of this patent

Abstract

Claims25