J2ee Web Hosting, Perl Scripting And Developing Blog

3.3.4 THE SPECTRAL TEST 99 S3. [Compute vs.] Set u c u -h, v t v -p; and if u2 + v2 < s, set s +- u2 + v2, h +- u, p + v. Then output fi = v2. (The validity of this calculation for the two-dimensional case is proved in exercise 5. Now we will set up the U and V matrices satisfying (28) and (29), in preparation for calculations in higher dimensions.) Set where the -sign is chosen for V if and only if p > 0. S4. [Advance t.] If t = T, the algorithm terminates. (Otherwise we want to increase t by 1. At this point U and V are t X t matrices satisfying (28) and (29) and we must enlarge them by adding an appropriate new row and column.) Set t t t + 1 and r e (or) modm. Set Ut to the new row (–r, 0, 0, . . . ,O, 1) of t elements, and set uit t-0 for 1 5 i < t. Set V, to the new row (O,O, 0,. . . ,O, m). Finally, for 1 5 i < t, set g c round(v,l r/m), vzt + vile -gm, and Ut t Ut + qUi. (Here round(z) denotes the nearest integer to z, e.g., 1~ + l/2]. We are essentially setting vit + viir and immediately applying transformation (23) with j = t, since the numbers ]vilr] are so large they ought to be reduced at once.) Finally set s c min(s, U,. Ut), k t t, and j + 1. (In the following steps, j denotes the current row index for transformation (23), and Ic denotes the last such index where the transformation shortened at least one of the Vi.) S5. [Transform.] For 1 5 i 5 t, do the following operations: If i # j and 2lVi . Vjl > Vy . Vy, set q + round(Vi . Vj / I+ . Vj), Vi +-Vi -qV7, Uy + Vi + qUi, and k + j. (The fact that we omit this transformation, when 21Vi . Vjl exactly equals V, . V,, prevents the algorithm from looping endlessly; see exercise 19.) S6. [Examine new bound.] If k = j (i.e., if the transformation in S5 has just done something useful), set s +- min(s, Uj . Uj). S7. [Advance j.] If j = t, set j c 1; otherwise set j c j + 1. Now if j # k, return to step S5. (If j = k, we have gone through t -1 consecutive cycles of no transformation, so the transformation process is stuck.) S8. [Prepare for search.] (Now the absolute minimum will be determined, using an exhaustive search over all (Q, . . . , Q) satisfying condition (21) of Lemma A.) Set X t Y t (0, . . . ,O), set k t t, and set (We will examine all X = (51, . . . ,zt) with ]zrj] 2 zj for 1 5 j 5 t. In hundreds of applications of this algorithm, no zJ has yet turned out to be greater than 1, nor has the exhaustive search in the following steps ever reduced s; however, such phenomena are probably possible in weird cases,
Note: If you are looking for high quality webhost to host and run your jsp application check Vision jsp web hosting services

98 RANDOM NUMBERS 3.3.4 be quite small in most cases. Occasionally these bounds (21) will be poor, and another type of transformation will usually get the algorithm unstuck again and reduce the bounds (see exercise 18). However, transformation (23) by itself has proved to be quite adequate for the spectral test; in fact, it has proved to be amazingly powerful when the computations are arranged as in the algorithm discussed below. *D. How to perform the spectral test. Here now is an efficient computational procedure that follows from our considerations. R. W. Gosper and U. Dieter have observed that it is possible to use the results of lower dimensions to make the spectral test significantly faster in higher dimensions. This refinement has been incorporated into the following algorithm, together with a significant simp- lification of the two-dimensional case. Algorithm S (The spectral test). This algorithm determines the value of v,=rnin{fi+…+xz ).~+.~~+…+at- s~O(modulorn)} (27) for 2 2 t < T, given a, m, and T, where 0 < a < m and a is relatively prime to m. (The number vt measures the t-dimensional accuracy of random number generators, as discussed in the text above.) All arithmetic within this algorithm is done on integers whose magnitudes rarely if ever exceed m2, except in step S8; in fact, nearly all of the integer variables will be less than m in absolute value during the computation. When vt is being calculated for t 2 3, the algorithm works with two t x t matrices U and V, whose row vectors are denoted by Vi = (uir, . . . , uit) and vi = (Wil,..., vit) for 1 5 i 5 t. These vectors satisfy the conditions uil + uuis + 1.. + ut-ruit = 0 (modulo m), 1Note: In case you are looking for affordable and reliable webhost to host and run your j2ee application check Vision web and email hosting services

3.3.4 THE SPECTRAL TEST 97 diagram makes this plain. (25) Turning to question (b), we want to choose the q2 so that U, +&+ qiiIJi has minimum length; geometrically, we want to start with Uj and add some vector in the (t -1)-dimensional hyperplane whose points are the sums of multiples of { Ui 1 i # j }. Again the best solution is to choose things so that Uj’ is perpendicular to the hyperplane, i.e., so that Uj . Uk = 0 for all k # j, i.e., U, . Uk + C qi(Ui ‘ uk) O? 1Note: In case you are looking for affordable webhost to host and run your web application check Vision http web server services

96 RANDOM NUMBERS 3.3.4 has the same answer. For example, Euclid s algorithm has this form; if we don t know the gcd of the input numbers, we change them into smaller numbers having the same gtd. (In fact, a slightly more general approach probably underlies the discovery of nearly all algorithms: If you can t solve a problem directly, change it into one or more simpler problems, from whose solution you can solve the original one. ) In our case, a simpler problem is one that requires less searching because the right-hand side of (22) is smaller. The key idea we shall use is that it is possible to change one quadratic form into another one that is equivalent for all practical purposes. Let j be any fixed subscript, 1 5 j 5 t; let (qi, . . . , CJ~-…1, . . . , qt) oj+l, be any sequence of t - 1 integers; and consider the following transformation of the vectors: Vi’ = vi -qivj, xi = xi -qixj, Vi’ = vi, for i # j; Vj = Vj, X[1 = Xj, Uj = Uj + Cifj q%Ui. (23) It is easy to see that the new vectors VI , . . . , U, define a quadratic form f for which f/(x$, . . . ,xi) = f(xl,. . . , xt); furthermore the basic orthogonality condition (19) remains valid, because it is easy to check that Vi . Vj = Sij. As (Xl,…, xt) runs through all nonzero integer vectors, so does (xi,. . . , xi); hence the new form j has the same minimum as f. Our goal is to use transformation (23), replacing Vi by Vi and Vi by Vi for all i, in order to make the right-hand side of (22) small; and the right-hand side of (22) will be small when both Uj . Uj and Vk . vk are small. Therefore it is natural to ask the following two questions about the transformation (23): a) What choice of qi makes Vi . Vi as small as possible? b) What choice of 41, . . . , qj-1, qj+l, . . . , qt makes Uj . Uj as small as possible? It is easiest to solve these questions first for real values of the qi. Question (a) is quite simple, since and the minimum occurs when qi=Vi Vj/Vj Vj. (24) Geometrically, we are asking what multiple of Vj should be subtracted from Vi so that the resulting vector Vi has minimum length, and the answer is to choose qi so that Vi is perpendicular to Vj (i.e., so that Vi . Vj = 0); the following
Note: In case you are looking for affordable and reliable webhost to host and run your j2ee application check Vision web and email hosting services

3.3.4 THE SPECTRAL TEST 95 vl,…, Vt such that For example, in the special form (16) that arises in the spectral test, we have Ul = ( m, 070,. . . ,017 Vl =+$,a$2 ,…) at- ), u2 = ( –a, 1, 0, . . . , O), v2 = (0, 1, 0,. . . , O), us = ( -u2, 0, 1, . . . ) O), v, = (O,O, 1,. . . , O), (20) . . . . . . . . . . . . ut = (-d-l, 0, 0, . . . , l), vt = (O,O, 0,. . . , 1). These V, are precisely the vectors (8), (9) that we used to define our original lattice Lo. As the reader may well suspect, this is not a coincidence-indeed, if we had begun with an arbitrary lattice LO, defined by any set of linearly independent vectors VI, . . ,V,, the argument we have used above can be generalized to show that the maximum separation between hyperplanes in a covering family is equivalent to minimizing (17), where the coefficients uij are defined by (19). (See exercise 2.) Our first step in minimizing (18) is to reduce it to a finite problem, i.e., to show that we won t need to test infinitely many vectors (~1, . . . , Q) to find the minimum. This is where the vectors VI, . . . , Vt come in handy; we have xk = (xl& + +xtut) vk, and Cauchy s inequality tells us that ((xlul + + xtut) vk)2 2 j-(x1,. . . > xt)(Vk vk). Hence we have derived a useful upper bound on each coordinate xk: Lemma A. Let (xl,…, q) be a nonaero vector that minimizes (18) and let (Yl,.. . , yt) be any nonzero integer vector. Then 2: 2 (vk vk/k)f(Yl , . . , Yt ), for 1 < k 5 t. (21) In particular, letting yz = Sij for all i, 2; 5 (vk vk)(uy u,), for 15 j,k 5 t. 1 (22) Lemma A reduces the problem to a finite search, but the right-hand side of (21) is usually much too large to make an exhaustive search feasible; we need at least one more idea. On such occasions, an old maxim provides sound advice: If you can t solve a problem as it is stated, change it into a simpler problem that
Note: In case you are looking for affordable and reliable webhost to host and run your j2ee application check Vision web and email hosting services

94 RANDOM NUMBERS 3.3.4 hence the minimum in (12) occurs when each xj = uj/(uf + .. . + uz); the distance between neighboring hyperplanes is 1 dm = l/length(U). (14I In other words, the quantity ut we seek is precisely the length of the shortest ve&or U that defines a family of hyperplanes { X. U = q 1 integer q } containing all the elements of Lo. Such a vector U = (~1,. . . , ut) must be nonzero, and it must satisfy V.U = integer for all V in Lo. In particular, since the points (1, 0, . . . , 0), (0, 1, . . . , 0), . . . . (0,O )…) 1) are all in Lo, all of the uj must be integers. Furthermore since VI is in Lo, we must have &(ul + au2 + . . . + atP1ut) = integer, i.e., Ul + au2 + . . . + &lut s 0 (modulo m). (15) Conversely, any nonzero integer vector U = (ul, . . . , ut) satisfying (15) defines a family of hyperplanes with the required properties, since all of LO will be covered: (y1Vl + . . + + yt&) . U will be an integer for all integers yl, . . . , yt. We have proved that u:= min {uf+-..+uF Iu1+uu2+..-+cP1ut =O(modulom)} (~1,..-,~t)#(O,…,O) =(%I,…,$; (O,…,0)(( mx~-ux~-u2×3-*. . -ut-1xt)2+x;+x;+~~~ +xt ). (16) C. Deriving a computational method. We have now reduced the spectral test to the problem of finding the minimum value (16); but how on earth can we determine that minimum value in a reasonable amount of time? A brute-force search is out of the question, since m is very large in cases of practical interest. It will be interesting and probably more useful if we develop a computational method for solving an even more general problem: Find the minimum value of the quantity f(Xl,… , xt) = (%1X1 + . . . + Utlxt)2 + . . . + (%X1 + * *. + %xt)2 (17) over all nonzero integer vectors (xl,. . . , xt), given any nonsingular matrix of oefficients U = (uij). The expression (17) is called a positive definite quadratic . form m t variables. Since U is nonsingular, (17) cannot be zero unless the xj are all zero. Let us write VI, .,., Ut for the rows of U. Then (17) may be written f(Xl,.-. , xt) = (Xl& + . . . + XtUt) . (Xl& + … $-x&s), (18) the square of the length of the vector x1 VI + . . . + xtUt . The nonsingular matrix U has an inverse, which means that we can find uniquely determined vectors
Note: In case you are looking for affordable and reliable webhost to host and run your j2ee application check Vision j2ee hosting services

3.3.4 THE SPECTRAL TEST 93 where l4) = k(o, c, (1 + a)c, . . . , (1 + a + . + cP )c) (6) is a constant vector. The variable k1 is redundant in this representation of L, be- cause we can change (5, ki, Its, . . . , k,) to (z+kim, 0, ks –&I,. . . , kt –at- kl), reducing kl to zero without loss of generality. Therefore we obtain the compara- tively simple formula L={Vo+ylK+y2V2+~~~+ytVt I integeryl,ya,…,yt}, (7) where vl = ~(l,u,u2 ,.. , CL- ); (8) Vs=(O,l,O )…, O), vs=(o,o,1,. .) O), . ..) Vt=(O,O,O ) .) 1). (9) The points (zi, x2,. . . , xt) of L that satisfy 0 5 x3 < 1 for all j are precisely the m points of our original set (2). Note that the increment c appears only in Vo, and the effect of V. is merely to shift all elements of L without changing their relative distances; hence c does not affect the spectral test in any way, and we might as well assume that Vi = 640,. . . , 0) when we are calculating LQ. When Vo is the zero vector we have a so-called lattice of points Lo={~IK+Y~V~+.~.+Y~K I integeryl,yz,...,yt), (10) and our goal is to study the distances between adjacent (t -1)-dimensional hyperplanes, in families of parallel hyperplanes that cover all the points of Lo. A family of parallel (t -1)-dimensional hyperplanes can be defined by a nonzero vector U = (ui, . . . , Ut) that is perpendicular to all of them; and the set of points on a particular hyperplane is then {(Xl,. . . 7 xt) I 21% + . . * + xtw = 4 >, (11) where 4 is a different constant for each hyperplane in the family. In other words, each hyperplane is the set of all X for which the dot product X . U has a given value 4. In our case the hyperplanes are all separated by a fixed distance, and one of them contains (O,O, . . . ,O); hence we can adjust the magnitude of U so that the set of all integer values c~ gives all the hyperplanes in the family. Then the distance between neighboring hyperplanes is the minimum distance from (O,O,. . . , 0) to the hyperplane for o = 1, namely Cauchy s inequality (cf. exercise 1.2.3-30) tells us that (13)
Note: If you are looking for reliable webhost to maintain and run your java application check Vision java hosting services

92 RANDOM NUMBERS 3.3.4 in each subcube of the unit cube, when the unit cube has been divided into 64 subcubes of size $ X 4 X a; this same generator might yield completely empty subsquares of the unit square, when the unit square has been divided into 64 subsquares of size & x isl. Since we increase our expectations in lower dimensions, a separate test for each dimension is required. It is not always true that vt 5 milt, although this upper bound is valid when the points form a rectangular grid. For example, it turns out that uz = m > m in Fig. 8, because a nearly hexagonal structure brings the m points closer together than would be possible in a strictly rectangular arrrangement. In order to develop an algorithm that computes vt efficiently, we must look more deeply at the associated mathematical theory. Therefore a reader who is not mathematically inclined is advised to skip to part D of this section, where the spectral test is presented as a plug-in method accompanied by several examples. On the other hand, we shall see that the mathematics behind the spectral test requires only some elementary manipulations of vectors. Some authors have suggested using the minimum number Nt of parallel covering lines or hyperplanes as the criterion, instead of the maximum distance l/z,+ between them. However, this number does not appear to be as important as the concept of accuracy defined above, because it is biased by how nearly the slope of the lines or hyperplanes matches the coordinate axes of the cube. For example, the 20 nearly vertical lines that cover all the points of Fig. 8 are actually l/J328 units apart, and this might falsely imply an accuracy of one part in &%, or perhaps even of one part in 20. The true accuracy of only one part in $% is realized only for the larger family of 21 lines with a slope of 7/15; another family of 24 lines, with a slope of -11/13, also has a greater inter-line distance than the 20-line family, since l/m > l/m. The precise way in which families of lines act at the boundaries of the unit hypercube does not seem to be an especially clean or significant criterion; however, for those people who prefer to count hyperplanes, it is possible to compute Nt using a method quite similar to the way in which we shall calculate vt (see exercise 16). *B. Theory behind the test. In order to analyze the basic set (2), we start with the observation that ( ujx + (1 + a + *. . + aj- )c mod 1 $j(x) = m > We can get rid of the mod 1 operation by extending the set periodically, making infinitely many copies of the original t-dimensional hypercube, proceed- ing in all directions. This gives us the set L= ;+k$g+kz,…,q+kt integer x, kl, lcz, . . . , Ict {( >I I = vi+ ;+kl,;+ks,…, 5 + kt> integer :c, ICI, k2, . . . , kt , r (
Note: If you are looking for reliable webhost to maintain and run your java application check Vision java hosting services

3.3.4 THE SPECTRAL TEST 91 essentially good to one part in v2. Similarly, let l/z+ be the maximum distance between planes, taken over all families of parallel planes that cover all points { (4m7 s(z)lm w4Ym)); we shall call ~3 the accuracy in three dimensions. The t-dimensional accuracy vt is the reciprocal of the maximum distance between hyperplanes, taken over all families of parallel (t -1)-dimensional hyperplanes that cover all points {(s/m, s(z)/m, . . . , s - (z)/m)}. The essential difference between periodic sequences and truly random se- quences that have been truncated to multiples of l/v is that the accuracy of truly random sequences is the same in all dimensions, while the accuracy of periodic sequences decreases as t increases. Indeed, since there are only m points in the t-dimensional cube when m is the period length, we can t achieve a t-dimensional accuracy of more than about milt. When the independence of t consecutive values is considered, computer- generated random numbers will behave essentially as if we took truly random numbers and truncated them to lgv, bits, where tit decreases with increasing t. In practice, such varying accuracy is usually all we need. We don t insist that the lo-dimensional accuracy be 235, in the sense that all (235)10 possible lo-tuples (Un, &x+1,. , ) should be equally likely on a 35-bit machine; for such large . . &x+9 values of t we want only a few of the leading bits of (Un, Un+i, . . . , Un+t-i) to behave as if they were independently random. On the other hand when an application demands high resolution of the random number sequence, simple linear congruential sequences will necessarily be inadequate; a generator with larger period should be used instead, even though only a small fraction of the period will actually be generated. Squaring the period will essentially square the accuracy in higher dimensions, i.e., it will double the effective number of bits of precision. The spectral test is based on the values of z,+ for small t, say 2 2 t 2 6. Dimensions 2, 3, and 4 seem to be adequate to detect important deficiencies in a sequence, but since we are considering the entire period it seems best to be somewhat cautious and go up into another dimension or two; on the other hand the values of Vt for t > 10 seem to be of no practical significance whatever. (This is fortunate, because it appears to be rather difficult to calculate Vt when t 2 10.) Note that there is a vague relation between the spectral test and the serial test; for example, a special case of the serial test, taken over the entire period as in exercise 3.3.3-19, counts the number of boxes in each of 64 subsquares of Fig. 8(a). The main difference is that the spectral test rotates the dots so as to discover the least favorable orientation. We shall return to a consideration of the serial test later in this section. It may appear at first that we should apply the spectral test only for one suitably high value of t; if a generator passes the test in three dimensions, it seems plausible that it should also pass the 2-D test, hence we might as well omit the latter. The fallacy in this reasoning occurs because we apply more stringent conditions in lower dimensions. A similar situation occurs with the serial test: Consider a generator that (quite properly) has almost the same number of points
Note: If you are looking for cheap webhost to host and run your apache application check Vision apache web hosting services

90 RANDOM NUMBERS 3.3.4 Fig. 8. (a) The two-dimensional grid formed by all pairs of successive points (Xn, X,+1), when Xn+l = (137X, + 187) mod 256. (b) The three-dimensional grid of triplets (Xn, X=+1, Xn+z). [Illustrations courtesy of Bruce G. Baumgart.] Perhaps the most striking thing about the pattern of boxes in Fig. 8 is that we can cover them all by a fairly small number of parallel lines; indeed, there are many different families of parallel lines that will hit all the points. For example, a set of 20 nearly vertical lines will do the job, as will a set of 21 lines that tilt upward at roughly a 300 angle. We commonly observe similar patterns when driving past farmlands that have been planted in a systematic manner. If the same generator is considered in three dimensions, we obtain 256 points in a cube, obtained by appending a height component s(s(z)) to each of the 256 points (5, S(X)) in the plane of Fig. 8(a), as shown in Fig. 8(b). Let s imagine that this 3-D crystal structure has been made into a physical model, a cube that we can turn in our hands; as we rotate it, we will notice various families of parallel planes that encompass all of the points. In the words of Wallace Givens, the random numbers stay mainly in the planes. At first glance we might think that such systematic behavior is so nonrandom as to make congruential generators quite worthless; but more careful reflection, remembering that m is quite large in practice, provides a better insight. The regular structure in Fig. 8 is essentially the grain we see when examining our random numbers under a high-power microscope. If we take truly random numbers between 0 and 1, and round or truncate them to finite accuracy so that each is an integer multiple of l/v for some given number V, then the t- dimensional points (1) we obtain will have an extremely regular character when viewed through a microscope. Let l/v2 be the maximum distance between lines, taken over all families of parallel straight lines that cover the points {(z/m, s(z)/m)} in two dimen- sions. We shall call ~2 the two-dimensional accuracy of the random number generator, since the pairs of successive numbers have a fine structure that is
Note: If you are looking for high quality webhost to host and run your jsp application check Vision florida web design services