PARALLEL GENERATORS OF RANDOM NUMBERS ON GEOMETRICAL STRUCTURES

Abstract

A method for realization of samples of random numbers distributed on temporal and spatial lattice points is described. The method may include using samples obtained by integrating a temporal and spatial white noise over the temporally smallest unit and over the spatial unit of volume, with the distribution of samples. The method may ensure small correlations to neighboring samples in temporal as well as spatial directions.

Claims

1. A method to realize a set of multiplicative congruential (MC) random numbers on geometrical lattice structures in such a way as to ensure little correlations among random numbers with neighboring coordinates, comprising: the method first prepares an integer lattice G.sub.N
G.sub.N:={(I.sub.1,I.sub.2, . . . ,I.sub.N)|I.sub.k is an integer, 0I.sub.kM.sub.k1, 1kN}, in the rectangular parallelepiped M.sub.1M.sub.2 . . . M.sub.N for integers {M.sub.k1|1kN} in the N-dimensional Euclidean space E.sub.N with N1, the method takes a MC generator (d, z, s) for uniform and independent random numbers constituted by the integer modulus d, the integer multiplier z coprime to d and the integer seed (or the starting value) s coprime to d, the generator (d, z, s) emitting an excellent sequence S of random numbers of period T, the excellence of S being in the sense that MC generators (d, z.sup.k) for exponents from k=1 to k=6 show valuations 1<.sub.d.sup.(2)(z.sup.k)<1.25 in (generalized) 2nd degree spectral tests and that (d, z) shows valuations 1<.sub.d.sup.(L)(z)<1.25 in L-th degree spectral tests with regular-simplex criteria for degrees L=3 up to (at least) L=4 or 5, and the method that then divides S into consecutive threads of a unanimous length M with M.sub.1M.sub.2 . . . M.sub.N and M<T, and the method tunes integers M, M.sub.1, M.sub.2, . . . , M.sub.N1 to their appropriate values by consecutive steps (1) to (N) of spectral tests noted below; (1) the first step tunes the length of threads by increasing M to M:=M+1, M+2, . . . until the procedure realizes that
:zM(mod d) gives (d, ().sup.k) passing the (generalized) 2nd degree spectral test with the valuation in the range 1<.sub.d.sup.(2)(().sup.k)<1.25 for 1k6, and gives (d, ) passing the degree L spectral test for regular L-simplex criterion starting from L=3 up to L=4, desirably up to L=5 or 6 within the valuation 1<.sub.d.sup.(L)()<1.25; (2) the 2nd step tunes the width M.sub.1 of the rectangular parallelepiped by increasing it to M.sub.1:=M.sub.1+1, M.sub.1+2, . . . until it realizes that
.sub.1:z(MM.sub.1)(mod d) gives (d, (.sub.1).sup.k) passing the (generalized) 2nd degree spectral test with the valuation in the range 1<.sub.d.sup.(2)((.sub.1).sup.k)<1.25 for 1k6, and gives (d, .sub.1) passing the degree L spectral test for regular L-simplex criterion starting from L=3 up to L=4, desirably up to L=5 or 6 within the valuation 1<.sub.d.sup.(L)(.sub.1)<1.25; (3) the 3rd step tunes the width M.sub.2 of the rectangular parallelepiped by increasing it to M.sub.2:=M.sub.2+1, M.sub.2+2, . . . until it realizes that
(.sub.2):z(MM.sub.1M.sub.2)(mod d) gives (d, (.sub.2).sup.k) passing the (generalized) 2nd degree spectral test with the valuation in the range 1<.sub.d.sup.(2)((.sub.2).sup.k)<1.25 for 1k6, and gives (d, .sub.2) passes the degree L spectral test for regular L-simplex criterion starting from L=3 up to L=4, desirably up to L=5 or 6 within the valuation 1<.sub.d.sup.(L)(.sub.2)<1.25; . . . (N) the N-th step tunes the width M.sub.N1 of the rectangular parallelepiped by increasing it to M.sub.N1: =M.sub.N1+1, M.sub.N1+2, . . . until it realize that
.sub.N1:z(MM.sub.1M.sub.2 . . . M.sub.N1)(mod d) gives (d, (.sub.N1).sup.k) passing the (generalized) 2nd degree spectral test giving the valuation in the range 1<.sub.d.sup.(2)((.sub.N1)}.sup.k)<1.25 for 1k6, and gives (d, .sub.N1) passing the degree L spectral test for regular L-simplex criterion starting from L=3 up to L=4, desirably up to L=5 or 6 within the valuation 1<.sub.d.sup.(L)(.sub.N1)<1.25; and in the case that all tunings noted above fulfill TMM.sub.1M.sub.2 . . . M.sub.N1M.sub.N the method finally defines the expanded integer lattice G.sub.N
G.sub.N:{(I.sub.1,I.sub.2, . . . ,I.sub.N)|0I.sub.kM.sub.k1,k=1,2, . . . ,N1,0I.sub.NM.sub.N1}, and defines an array of seeds ARRAY(I.sub.1, I.sub.2, . . . , I.sub.N) on G.sub.N and let the set of threads of (d, z) random numbers start on these seeds, the distribution of seeds being realized in the way to obtain small correlation between random numbers generated at geometrical neighbors, the distribution being described by simple operations in FORTRAN subprogram shown below with notations MPK for Mk, TABLE-US-00002 SBROUTINE SEEDER(D, Z, S, MP, MP1, MP2, MP3, ..., MN) INTEGER*8 A-Z COMMON ARRAY(0:MP11, 0:MP21, ..., 0:MN1) COUNT = 0 SEED = 1 CALL POWER(ZETA, D, Z, MP) !POWER is a subroutine to compute ZETA = MOD(Z**MP, D) !with 1 ZETA < D for the index MP that can be very large DO 10 IN = 0, MN 1 ......................................................... DO 10 I3 = 0, MP3 1 DO 10 I2 = 0, MP2 1 DO 10 I1 = 0, MP1 1 ARRAY(I1, I2, I3, ..., IN) = SEED SEED = MOD(SEED*ZETA, D) !this SEED may be computed within INTEGER*8 arithmetic !by Sun Tzu's theorem if D = D1*D2 is a product of coprime factors COUNT=COUNT+1 10 CONTINUE WRITE(6, I20) COUNT RETURN END wherein COUNT is the flag to confirm that all seeds are distributed; from {M, M_1, M_2, . . . M_N} thus constructed and reserved in the binary expansion or in more effective form, the simulation starts by preparing first to generate ARRAY from them, or the simulation starts by reading the data of ARRAY from HD, SSD, USB into the main memory, or the simulation starts by utilizing the ARRAY equipped in some standardized form in the function libraries of computer centers, or the simulation or the game starts utilizing the ARRAY installed in some standardized form in operating systems as one of their services on computers or in portable phones.

Description

DETAILED DESCRIPTION

Brief Summary

[0012] Necessary notations of MC random number generators are introduced. An MC generator comprises an integer d for the modulus, an integer z coprime to d as the multiplier and an integer s for the initial value or seed. They are summarized in a symbol (d, z, s), or (d, z) for short if the seed s is not relevant in arguments. The MC generator (d, z, s) generates the sequence of integers S: ={r.sub.0, r.sub.1, r.sub.2, . . . } by recursive congruence relations

r.sub.0:s(mod d), 0<r.sub.0<d,

r.sub.j:zr.sub.j1sz.sup.j1(mod d), 0<r.sub.j<d, j1,

and gives the output sequence of uniform and independent random numbers

{v.sub.j:=r.sub.j/d|j=0,1,2, . . . }.

We regard the consecutive L outputs of integers (r.sub.j, r.sub.j+1, . . . , r.sub.j+L1) as the coordinates of the point P.sub.j or its position vector in the L-dimensional Euclidean space E.sub.L. Points {P.sub.0, P.sub.1, P.sub.2, . . . } are known to be on lattice points of an integer lattice, and this fact was exploited for the valuation of the performance of (d, z) generator, ever since the epoch making work of Fishman and Moore (1986) under the name of spectral tests. We use here the so-called generalized 2nd degree tests of Nakazawa and Nakazawa (2014A), and demand the generator (d, z.sup.k) to pass criteria

1<.sub.d.sup.(2)(z.sup.k)<1.25,k=1,2, . . . ,6.

Here, criteria take consecutive 2-tuples of integer outputs from the MC generator (d, z.sup.k) as points on 2-dimensional lattices, considers largest distances {.sub.d.sup.(2)(z.sup.k)|1k6} of said lattices between their adjacent parallel lattice lines, and compute

.sub.d.sup.(2)(z.sup.k):=.sub.d.sup.(2)(z.sup.k)/{(d/2).sup.1/23.sup.1/4},k=1,2, . . . ,6.

Likewise, consecutive L-tuples of integer outputs from the generator (d, z) is tested by the L-th degree spectral tests of Nakazawa and Nakazawa (2014B) with the so-named regular L-simplex criterion. This implies that said L-tuple of integers are regarded as point in the L-dimensional space and to form an L-dimensional lattice with its largest distance .sub.d.sup.(L)(z) should give the following performance

1<.sub.d.sup.(L)(z)<1.25, 3L6,

.sub.d.sup.(L)(z):=.sub.d.sup.(L)(z)/{L.sup.1/2(L+1).sup.(L1)/(2L)d.sup.(L1)/L}.

The premise for the present invention is the existence of an MC random number sequence S with its generator (d, z) fulfilling these two criteria; this is realized in 9 excellent generators posted in Nakazawa and Nakazawa (2014C). The invention aims to distribute such generators with suitable seeds on the geometrical lattice in the L-dimensional space so as to realize excellent non-correlation in time and to geometrical neighbors in the lattice.

[0013] We first describe the basic principle to be respected in the use of noted type of excellent MC generator and its output sequences of integers as well as of output random numbers. The first of the principle is that a simulation must use one and only one excellent MC generator and its output sequence. This is based on the technological reality met in finding excellent MC generators with the modulus d comprising 2 coprime factors d=d.sub.1d.sub.2. Suppose we choose excellent subgenerators (d.sub.1, z.sub.1) and (d.sub.2, z.sub.2) by spectral tests. This is a possible and almost exclusive way to evade the notorious computing-time difficulties of spectral tests for large modulus d. Yet, the probability that we obtain an excellent combined generator by Sun Tzu's theorem,

d=d.sub.1d.sub.2,z:z.sub.k(mod d.sub.k),k=1,2,

is extremely small. We should not expect without tests, therefore, that excellent subgenerators (d.sub.1, z.sub.1) and (d.sub.2, z.sub.2) will give an excellent combination. Additionally, large scale simulations of today need parallel computing without exception. The above stated circumstances demand us to use a single MC generator with long enough period T, and we should use its random number sequence S without any duplication. The sole possibility is to divide the sequence S into consecutive subsequences. We call such small subsequences as threads, and denote their unanimous length as M. This length M should be the smallest but sufficient number of steps needed in simulations. Our aim is thus how to define the length M and how to distribute MC subgenerators giving length-M threads on a geometrical lattices.

DESCRIPTION OF EMBODIMENTS OF THE INVENTION

[0014] As the simplest and the most useful geometrical structures, we consider the N-dimensional Euclidean space E.sub.N and its N-dimensional integer lattice L.sub.N in the parallelepiped M.sub.1M.sub.2 . . . M.sub.N,

L.sub.N;={(x.sub.1,x.sub.2, . . . ,x.sub.N)|x.sub.k is an integer, 0x.sub.kM.sub.k1, k=1,2,-,N}.

The aim is to distribute MC random number generators on lattice points of L.sub.N, so as for them to work in parallel giving random number threads at each lattice point. Namely, we plant threads of random numbers at every lattice points and let them extend along the 0th axis for the time t. We may also say that the aim is to plant threads forming an (N+1)-dimensional lattice and realize the distribution of random numbers on this (N+1)-dimensional lattice points which have as little correlations as possible to 0th, 1st, 2nd, . . . , Nth neighbors. This may figuratively be said to realize an (N+1)-dimensional white noise on computers. Note that if random numbers on S are ideally uniform and independent, any way of distribution of generated random numbers may be used to the end. However, this is not tenable in reality. Our aim is to seek technologically for the way to imitate the noted ideal distribution within the limited excellence of MC random number generators.

[0015] The total number of lattice points L.sub.N in the space E.sub.N is :=M.sub.1M.sub.2 . . . M.sub.N. We put threads of length M on these lattice points. Hence we need the total number M=MM.sub.1M.sub.2 . . . M.sub.N of random numbers, and the planting of threads requires the period TM=MM.sub.1M.sub.2 . . . M.sub.N. We premise hereafter that this restriction on the period T is satisfied. The sole practical way to avoid duplicated use of random numbers is to divide the sequence S of random numbers into consecutive threads {.sub.0, .sub.1, . . . , .sub.1} of a unanimous length M. We regard these threads as (row) vectors along the 0th axis or the t-axis in the (N+1)-dimensional Euclidean space E.sub.N+1, and denote them explicitly as follows:

{.sub.k:s.sup.k(1,z,z.sup.2, . . . ,z.sup.M1)(mod d)|k=0,1,2, . . . ,1}, :z.sup.M(mod d).

An arbitrary thread Ok is thus the sequence generated by MC generator (d, z, s.sup.k). We may realize the planting or the distribution of all of these threads on the integer lattice L.sub.N by just putting these seeds {s.sup.k|(mod d)|k=0, 1, 2, . . . , 1}. The problem is how to distribute them.

[0016] We think on the computer program that will realize the noted distribution, without annoying ourselves with the complexity of high dimensional spaces. In order to cope with the convention of programming that does not admit suffixes, we first prepare notations. We use the classic notation of programming to use capital letters such as

D:=d, Z:=z, S:=s.

We introduce the convention

M1:=M.sub.1, M2:=M.sub.2, . . . , MN:=M.sub.N.

Lattice points of L.sub.N cannot help being expressed by variables

I1:=I.sub.1,I2:=I.sub.2, . . . ,IN:=I.sub.N, 0IKM.sub.k1, k=1,2, . . . ,N;

in particular, I.sub.N1 cannot be expressed in this way, and please understand that we avoid its use. With these notations the distribution of seeds on the integer lattice LN may be denoted as the ARRAY(I1, I2, . . . , IN). The computing of ARRAY(I1, I2, . . . , IN) may be realized by the following FORTRAN subprogram, which shows in somewhat simplified form the computing flow of the program posted in Claim.

TABLE-US-00001 SUBROUTINE SETTER(D, Z, S, M1, M2, ...,MN) INTEGER*8 A-Z COMMON ARRAY(0: M1 1, 0: M2 1, ..., 0: MN 1) SEED = S COUNT = 0 DO 10 IN = 0, MN 1 ................................................ DO 10 I2 = 0, M2 1 DO 10 I1 = 0, M1 1 ARRAY(I1, I2, ...,IN) = SEED COUNT = COUNT + 1 10 CONTINUE WRITE(6, I20 ) COUNT RETURN END
The integer variable COUNT is for the confirmation that the computing time amounts to =M1*M2* . . . *MN. This program shows that starting seeds SEED:=ARRAY(I1, I2, . . . , IN) have the following neighboring relations: [0017] (1) The transition I1.fwdarw.I1+1 is realized by the multiplication of SEED by =ZETAzM (mod d). [0018] (2) The transition I2.fwdarw.I2+1 is realized by the multiplication of SEED by .sub.1:(M.sub.1)z(MM.sub.1) (mod d). [0019] (3) The transition I3.fwdarw.I3+1 is realized by the multiplication of SEED by .sub.2:.sub.1(M.sub.2)z(MM.sub.1M.sub.2) (mod d). [0020] . . . [0021] (N) The transition IN.fwdarw.IN+1 is realized by the multiplication of SEED by .sub.N1:.sub.N2 (M.sub.N1)z(MM.sub.1M.sub.2 . . . M.sub.N1) (mod d).

[0022] We resume the ordinary notation, departing from the programming Seeds on the geometrical lattice L.sub.N in the space E.sub.N generally have the form s(z.sup.M).sup.k=s.sup.k (mod d) with 0kM.sub.1M.sub.2 . . . M.sub.N1. Threads starting from them may be denoted explicitly as

.sub.k:s.sup.k(1,z,z.sup.2, . . . ,z.sup.M1)(mod d).

When we distribute seeds on the lattice L.sub.N by the noted program, the whole of the (N+1)-dimensional array of generated random numbers (which we denote as V.sub.N+1) has an element that moves to its neighbors by following multiplications modulo d,

[0023] (to t-axis or the 0th axis) multiplication by z modulo d;

[0024] (to x.sub.1-axis) the multiplication by :z.sup.M (mod d);

[0025] (to x.sub.2-axis) the multiplication by .sub.1:zM.sub.1z(MM.sub.1) (mod d); [0026] . . .

[0027] (to x.sub.N-axis) the multiplication by .sub.N1:z(MM.sub.1M.sub.2 . . . M.sub.N1) (mod d).

As above, let V.sub.N+1 denote the geometrical array of random numbers be constructed on L.sub.N in the way described so far. Our aim is to make all random numbers are ensured to have little correlation in transitions to above shown neighbors. Clearly, the aim is realized by the following set of spectral tests:

[0028] (test 0, to t-axis or the 0th axis) spectral tests on the generator (d,z);

[0029] (test 1, to x.sub.1-axis) spectral tests on the generator (d, );

[0030] (test 2, to x.sub.2-axis) spectral tests on the generator (d, .sub.1); [0031] . . .

[0032] (test N, to x.sub.N-axis) spectral tests on the generator (d, .sub.N1).

We premised that (d, z) is excellent in test 0. Therefore, the excellence of all threads to the t-axis direction is ensured, up to 6th neighbors. We describe test 1 to test N separately. Cumbersome inferences to (mod d) will be abbreviated.
(Test 1) The transition in V.sub.N+1 to neighbors along the x.sub.1-axis is effected by the MC generator (d, z.sup.M). We need to tune (d, ) to be excellent. This is effected by replacing M with M=M, M+1, M+2, . . . step by step with =z(M), performing the generalized 2nd degree spectral tests of (d, ().sup.k) for k=1, 2, . . . , 6, say, within the criterions

1<.sub.d.sup.(2)(().sup.k)<1.25, 1k6.

Then we perform regular-simplex-criterion spectral tests of (d, ) from 3rd up to 4th, 5th or 6th degrees so as to realize

1<.sub.d.sup.(L)()<1.25, L=3,4, . . . .

Though the degree L up to 6 is ideal and desirable, the matter depends on many circumstantial elements, such as the available computing time. The multiplier z in the original MC generator (d, z) is the very rare existence under the modulus d chosen up to the 6th degree spectral tests. Thus, we may well have to be content asking (d, ) to pass spectral tests only up to the 5th degree. Or, we might well have to loosen the criterion to 1<.sub.d.sup.(L)<1.30 or so. The compromise will be necessary according to the amount of our computing time, or of our computing budget. When an admissible valuation is obtained with (d, z(M)), we replace M by M.
(Test 2) The transition to neighbors along the x.sub.2-axis is effected now by the MC generator (d, .sub.1) with .sub.1=z(MM.sub.1). To make the multiplier z(MM.sub.1) excellent we tune the width M.sub.1: We replace M.sub.1 with M.sub.1=M.sub.1, M.sub.1+1, . . . , perform generalized 2nd degree tests of (d, (.sub.1).sup.k=zz(kMM.sub.1) for 1k6 say, and throw (d, .sub.1) into the regular-simplex Lth degree spectral tests for degrees L=3, 4, . . . , and select an excellent (M.sub.1).
. . .
(Test N) The final step of tuning takes the multiplier .sub.N1:z(MM.sub.1 . . . M.sub.N1), increases M.sub.N1 as M.sub.N1, M.sub.N1+1, . . . , so as to find an excellent M.sub.N1 for which .sub.N1:z(MM.sub.2 . . . M.sub.N1) is excellent in generalized 2nd degree spectral tests of (d, (.sub.N1).sup.k) for 1k6 and 3rd up to 5th (say) degrees of regular simplex spectral tests of (d, .sub.N1). Tuning steps end up with noted M, M.sub.1, M.sub.2, . . . , M.sub.N1 with unchanged M.sub.N. We should again remind ourselves that the inequality for the total number of used random numbers

MM.sub.1M.sub.2 . . . M.sub.N1M.sub.NT, M.sub.N:=M.sub.N

must hold true for the construction of parallel generators to be possible at all. In practices this restriction is experienced non-restrictive. In terms of threads to be distributed on the lattice G.sub.N), the total number of threads is

:M.sub.1M.sub.2 . . . M.sub.N1M.sub.NT/M.

This configuration of threads is realized by distributing seeds

{ARRAY(I.sub.1,I.sub.2, . . . ,I.sub.N)|I.sub.k=0,1, . . . ,M.sub.k1, 1kN}

on G.sub.N, where we may instead take the subset G.sub.N as said. But this operation might be dangerous in these intricate relations. By this reason claim 1 is stated without such streamlining in the present specification.

SUMMARY

[0033] By taking a sequence S of MC random numbers with excellent statistics of uniformity and independence as generated from a (d, z, s) generator, and by exploiting the generalized 2nd degree spectral tests of (d, z.sup.k) for 1k6 as well as L-th degree spectral tests under the regular L-simplex criterion for L3, the invention presents a method to divides S into consecutive threads of length M, plants threads on lattice points of a lattice G.sub.N in the N-dimensional Euclidean space with 1st, 2nd, . . . , Nth coordinate axes, and constructs in total an (L+1)-dimensional distribution of random numbers including the 0th time axis, in such a way that each random numbers are ensured to have little correlation with neighbors in 0th, 1st, 2nd, . . . , Nth axis directions.

Problem

[0034] The presented invention aims to realize an excellent set of MC random numbers distributed on a lattice with bounded but large extension in space-time, showing little correlations to respective neighbors to temporal as well as geometrical directions, thus ensuring high-quality parallel simulations on computers for particles distributed on geometrical set and under the effect of external, non-correlated forces.

Solution

[0035] Prepare an excellent MC random number sequence S with a sufficiently long period T, divide S into consecutive threads of length M. With generalized 2nd degree spectral tests up to the 6th power of the multiplier as well as with spectral tests of the generator for degrees greater 3, tune the length M along the time axis, also tune respective lengths along spatial and ensure little correlations to neighbors in temporal as well in spatial directions by suitably realizing the planting of the root of threads to spatial lattice points, and realize a set of random number threads on geometrical structures which may be generated in parallel.

Effects of the Invention

[0036] The aimed ideal result is the realization of samples of random numbers distributed on temporal and spatial lattice points, with samples obtained by integrating a temporal and spatial white noise over the temporally smallest unit and over the spatial unit of volume, with the distribution of samples so realized as to ensure small correlations to neighboring samples in temporal as well as spatial directions. The present invention has shown the method to realize said ideal distribution of MC threads of random number samples which allows for their spatially parallel generation on computers. If the temporal development is not needed, as in random initial value problems of degrees of freedom distributed on spatial lattice points, the time axis may be re-interpreted as a spatial axis and the spatial dimension N in Claim may be taken as N1 to recover the total dimension N. The Invention is thus amenable to generalizations and specializations to various random number problems on geometrical structures. A point to be noted, however, is that even the presented simplest construction may be totally very difficult, starting from the excellent random number sequence S, construction of spectral test programs for tuning, and probably long computing time to find good tuned results, will be a highly intricate and difficult procedures for usual researchers using simulations, programmers for computing games, not to say usual consumers who would need random numbers on their computers or portable phones. Their realization and equipment on computers will require the skill of professional computer engineers. and the use should be enabled as software archived in function libraries in computing centers or installed in programming languages, or as services in operating systems for computers or portable phones. The present Invention is believed to enable these innovative applications.

Prospects

[0037] Said possibilities in applications fundamentally call for excellent MC random number generators with still larger period T. The prospects call for the general use of computers equipped with quadruple precision integer arithmetic beyond the present double precision machines. It is wished that universities, computer centers and their engineers, who are at present the sole people with accesses to such large scale computers, are heartily solicited to find excellent MC random number sequences with periods T2.sup.60; their existence will facilitate greatly the standardization of invented generators on geometrical structures and greatly benefit researchers and general consumers in the world.