JPH04182828A - In-table entry selection method using pseudo-random numbers - Google Patents

Abstract

PURPOSE:To make all data in entries different and to obtain M mutually different pseudo-random numbers by selecting an entry into a sequence table according to the remainder obtained by dividing a psuedo-random number by N and storing it in a selection table. CONSTITUTION:This system is provided with a pseudo-random number table 1 wherein pseudo-random numbers (A, B-) are expanded and the sequential table 2 wherein N mutually different data from 0-N are arranged in sequence. The entry into the table 2 is selected according to the remainder obtained by dividing the pseudo-random number (A, B-) taken out of the table 1 by the number N of entries into the table 2 is selected and its contents are stored in the selection table 3 different from the table 2. Then the final entry into the table 2 is moved to the position of the selected entry. Thus, retrieval entries into the table 2 are decreased by one repeatedly. Then the contents of all the entries into the table 3 are made different and M(>=N) mutually different pseudo- random numbers are obtained.

Description

[Detailed Description of the Invention] [Summary] The present invention includes a pseudo-random number expansion table in which pseudo-random numbers (A, B, ~) are expanded, and a sequential table in which N mutually different data from 0 to N are sequentially arranged. , select the corresponding entry in the sequential table using the remainder of dividing the pseudo-random number (A, B, ~) taken out from the pseudo-random number expansion table by the above number N,
Regarding the in-table endley selection method in which all data in each entry is different, the purpose is to quickly select M (≦N) mutually different pseudorandom numbers, and the pseudorandom numbers ( A, B, ~) and divide it by the above number N, the remainder (α).

β, ~), the content of the corresponding entry when searching the above sequential table (remainder α, β,
~) and sequentially store them in each entry of a selection table different from the above sequential table, and
The process of moving the last entry of the sequential table to the entry position extracted from the sequential table and reducing the number of search entries for the sequential table by one is repeated M (≦N) times, and then the selection is performed. The table is configured to generate M mutually different pseudorandom numbers.

[Industrial application field]

The present invention includes a pseudo-random number expansion table in which pseudo-random numbers (A, B, ~) are expanded, and a sequential table in which N mutually different data from 0 to N are sequentially arranged. The present invention relates to an entry selection method in which each selected entry must be different when pseudorandom numbers are generated by randomly selecting entries from a list of entries.

For example, when executing a sequence of instructions in a test program for the central processing unit (CPU) of an electronic computer and testing that a certain instruction does not affect other instructions, all operands of each instruction are stored in different memories. Testing can be performed more effectively by placing the operands in the memory space, but if the memory space of the operands is retrieved using different pseudo-random numbers, the test program can be operated more effectively. I can do it.

Therefore, a method is required that can quickly select the different pseudo-random numbers.

[Prior art and problems to be solved by the invention] FIG. 2 is a diagram illustrating a conventional table entry selection method using pseudo-random numbers.

In this conventional method, entries in a table that store different numbers are rearranged using pseudo-random numbers, and the entries are used in order from the beginning.

Specifically, first, pseudorandom numbers (A, B, ~) (for example,
It includes a pseudo-random number expansion table 1 in which a 4-byte unsigned binary number is expanded, and a sequential table 2 in which N mutually different data from 0 to N are sequentially arranged.

In the sequential table 2, numbers that are different from each other (numbers corresponding to "remainder r of the remainder operation described later") are sequentially arranged. Therefore, the pseudo random numbers (A, B.

~) by the number N of entries constituting the sequential table 2, and selecting each entry of the sequential table 2 corresponding to the remainder and replacing them in order from the beginning. This is a method that attempts to turn the sequence of numbers sequentially arranged on 2 into a sequence of pseudo-random numbers.

Therefore, first, after taking out the contents of the first entry (remainder O) of the above sequential table 2, the first pseudo-random number A is taken out from the above-mentioned pseudo-random number expansion table 1, and the pseudo-random number A is In the example, for example, '1
The above sequential table 2 is searched based on the remainder (remainder α: 512° in this example) when divided by , based on the above remainder, the entry (remainder °
The entry corresponding to 512゛) is replaced as shown.

As a result of this operation, the pseudorandom number '512' is entered in the first entry of the sequential table 2.

Next, after extracting the contents of the second entry (remainder l) of the sequential table 2, the next pseudo-random number B is extracted from the pseudo-random number expansion table 1, and the pseudo-random number B is converted to the number N (= Based on the remainder (remainder β: '514' in the zero example) when divided by Replace.

As a result of this operation, the pseudorandom number "514" is entered in the second entry of the sequential table 2.

Hereafter, the same operation is repeated, for example, in the 8th operation, a pseudo-random number H is taken out, and the remainder when the pseudo-random number H is divided by the above number N (=1024) (remainder θ: zero In the example, °0゛) Based on the above, the entries obtained by searching the sequential table 2, that is, the first entry corresponding to the remainder O and the eighth entry (the entry corresponding to the remainder 7) are shown in the figure. Replace as shown.

As a result, the pseudorandom number '512' in the first entry of the sequential table l obtained in the first operation is replaced with '7''.

In this way, in the conventional method, the pseudo-random numbers (A, B, ~) taken out from the pseudo-random number expansion table 1 are converted into the number N (
In this example, as mentioned above, the remainder when divided by '1024') may refer to an entry that has already been replaced, and although it is not illustrated or explained, the same remainder may occur. What was selected after being swapped may be selected again.

Therefore, in the conventional method, as mentioned above, for example,
Even when eight different pseudo-random numbers are required, if the same operation is not repeated N (in this example, "1024" as described above) times, different truths will be added to the first eight of the sequential table 2. This means that it is not possible to set pseudo-random numbers for the sequential table 2.
There is a problem in that as the number N of entries increases, the sorting takes more time.

In view of the above-mentioned conventional drawbacks, the present invention provides pseudorandom numbers (A, B).

), and a sequential table in which N mutually different data from 0 to N are sequentially arranged, and pseudorandom numbers (A, B, .

[Means to solve the problem]

The above problem can be solved by an in-table entry selection method using pseudo-random numbers configured as follows.

A pseudo-random number expansion table 1 in which pseudo-random numbers (A, B, ~) are expanded, and a sequential table 2 in which N mutually different data from O to N are sequentially arranged, and each entry of the sequential table 2 is provided. In this method, M (≦N) mutually different pseudorandom numbers are obtained by rearranging the pseudorandom numbers (A, B) using the pseudorandom number expansion table 1.

~) and divide it by the above number N, the remainder (α, β
, ~), the content of the corresponding entry when searching the above sequential table 2 (remainder α, β,
~) and sequentially store them in each entry of another selection table 3 different from the sequential table 2, and move the last entry of the sequential table 2 to the entry position extracted from the sequential table 2. Therefore, M(
≦N) times to generate M mutually different pseudo-random numbers on the selection table 3.

[Effect]

That is, according to the present invention, a pseudo-random number expansion table 1 in which pseudo-random numbers (A, B, ~) are expanded, and a sequential table 2 in which N mutually different data from remainder 0 to remainder N are sequentially arranged. In this method, M (≦N) mutually different pseudo-random numbers are obtained by rearranging each entry in the sequential table 2 using the pseudo-random number expansion table 1. Pseudo-random numbers (A
, B, ~), and the read pseudo-random numbers (A, B
, ~), for example, by the number of entries in the sequential table 2, for example, 1024, an entry in the sequential table 2 is selected, and the contents of the entry are selected by a separately provided selection. By repeating the process of sequentially storing data in Table 3 and moving the final entry in Sequential Table 2 to the selected entry position, next time when selecting an entry position from Sequential Table 2, the previous sequential An entry is selected from a sequential table 2 that is obtained by subtracting one entry from the size of table 2.

Therefore, the number of entries in sequential table 2 is
For example, even if there are 1024 pseudo-random numbers, in the entry selection method according to the present invention, if 8 mutually different pseudo-random numbers are required, by repeating the above operation 8 times, all different entries in the sequential table 2 can be selected. By selecting and obtaining the contents of the entry, it is possible to obtain mutually different pseudorandom numbers.

However, each time an entry is selected from sequential table 2, the selection range from then on decreases by one entry, and even if the number of entries in sequential table 2 increases, all different entries can be selected in a short time.
This has the effect of being able to obtain pseudorandom numbers that are different from each other.

〔Example〕

Embodiments of the present invention will be described in detail below with reference to the drawings.

FIG. 1 is a diagram showing an embodiment of the present invention, in which a pseudo-random number expansion table 1 in which pseudo-random numbers (A, B, ~) are expanded,
A sequential table 2 in which N pieces of mutually different data from O to N are sequentially arranged, and pseudorandom numbers (A, B
, ~) by the number N of entries in the sequential table 2, select an entry in the sequential table 2, and store the contents of the entry in a selection table 3 separate from the sequential table 2. , moves the final entry of the sequential table 2 to the position of the selected entry and reduces the number of subsequent search entries for the sequential table 2 by one M (≦N) times, and then selects the selected entry. Means for obtaining M (≦N) mutually different pseudorandom numbers by making the contents of each entry in Table 3 completely different is a means necessary to implement the present invention. Note that the same reference numerals indicate the same objects throughout the figures.

Hereinafter, an in-table entry selection method using pseudo-random numbers according to the present invention will be explained with reference to FIG.

Pseudo-random number expansion table 1. It is assumed that each entry of the sequential table 2 is, for example, a 4-byte unsigned binary integer, and that the sequential table 2 is made up of 1024 entries having sequential values of 0 to 1023.

In this embodiment, it is assumed that 8 mutually different entries are selected from the 1024 entries.

Pseudo-random numbers for selecting eight entries are prepared on the pseudo-random number expansion table 1, for example, 4 bytes x 8 = 32 bytes.

a) Take out the first 4 bytes A of the pseudo-random number expansion table 1 and calculate the number of entries N of the sequential table 2.
The entry corresponding to the remainder divided by (1024) is selected from the sequential table 2 (
512) and its contents are stored in the first area of the selection table 3.

b) Move the last entry (1023) of the sequential table 2 to the selected entry position of the sequential table 2;

C) From the above pseudo-random number expansion table 1, extract the second 4 bytes B of the pseudo-random number and convert it to the sequential table 2.
The value obtained by subtracting 1 from the number of entries in (1021-1=10
The entry corresponding to the remainder divided by 23) is set as the selected entry (514), and its contents are stored in selection table 3
It is stored in the second area of .

d) Move an entry (1022) obtained by subtracting one entry from the last entry of the sequential table 2 to the selected entry position of the sequential table 2;

e) The above C) to d) for the specified number of entries,
That is, in this embodiment, the above-mentioned eight times are repeated.

f) At the time of repeating the eight times, the above selection table has the following information:
Numerical values indicating mutually different entries, that is, pseudo-random numbers are stored, and the number of entries in the sequential table 2 is the number of entries (=1017) obtained by subtracting 8 from the original number of entries (1024). .

Therefore, according to the present invention, even if the pseudo-random numbers taken out and used from the pseudo-random number expansion table 1 are the same, the remainder will always be a number within the number of entries in the sequential table 2, and the same entry will not be selected. Moreover, since the contents of the selected entry are already stored in another selection table 3, the entry will not be selected again.

In this way, by performing the operations a) to d) above for the required number of pseudo-random numbers, in this example 8, the required
"Eight mutually different pseudo-random numbers" can be obtained at high speed.

As described above, the in-table entry selection method using pseudo-random numbers according to the present invention sequentially selects the pseudo-random number expansion table 1 in which pseudo-random numbers (A, B, ~) are expanded, and N mutually different data from 0 to N. The pseudo-random numbers (A, B, ~) taken out from the pseudo-random number expansion table 1 are divided by the number N of entries in the sequential table 2, and the remainder is
Select the entry of the sequential table 2,
The contents are stored in a selection table 3 separate from the sequential table 2, and at the position of the selected entry,
Move the last entry of the sequential table 2 and reduce the number of search entries for the sequential table 2 by one in the subsequent steps, so that the contents of each entry in the selection table 3 are all different, The feature is that M (≦N) mutually different pseudorandom numbers are obtained.

〔Effect of the invention〕

As explained above, according to the present invention, pseudorandom numbers (A, B
, ~) and a sequential table in which N mutually different data from 0 to N are sequentially arranged, and the pseudorandom numbers extracted from the pseudorandom number expansion table are Select an entry in the sequential table using the remainder divided by N, and store its contents in a selection table different from the sequential table, so that the data in each entry in the selection table is all different. Therefore, even if the number N of entries in the sequential table increases, the pseudo-random numbers (A,
Even if B, ~) have the same value, it is possible to select all different entries in a short time and obtain mutually different pseudorandom numbers.

[Brief explanation of the drawing]

FIG. 1 is a diagram showing an embodiment of the present invention. FIG. 2 is a diagram illustrating a conventional table entry selection method using pseudo-random numbers. It is. In the drawing, 1 is a pseudo-random number expansion table. 2 is a sequential table. 3 is a selection table.

Claims (1)

[Claims] A pseudo-random number expansion table (1) in which pseudo-random numbers (A, B, ~) are expanded, and a sequential table (2) in which N mutually different data from 0 to N are sequentially arranged.
A method of obtaining M (≦N) mutually different pseudorandom numbers by rearranging each entry of the sequential table (2) using the pseudorandom number expansion table (1), Pseudo-random numbers (A, B,
~) and divide it by the above number N, the remainder (α, β
, ~), the above sequential table (2)
The content of the corresponding entry when searching for (remainder α,
β, ~) and the sequential table (2)
Sequentially stored in each entry of another selection table (3) different from the sequential table (2).
Repeat M (≦N) times by moving the final entry of the sequential table (2) to the entry position extracted from and reducing the number of subsequent search entries for the sequential table (2) by one; An in-table entry selection method using pseudo-random numbers, characterized in that M mutually different pseudo-random numbers are generated on the selection table (3).