Free web design - 100 RANDOM NUMBERS 3.3.4 especially in higher dimensions.
100 RANDOM NUMBERS 3.3.4 especially in higher dimensions. During the exhaustive search, the vector Y will always be equal to zrUr + . . . + xJJt, so that f(xl, . . . , xt) = Ye Y. Since f(-x1,. . . , -xt) = f(xi,. . . , xt), we shall examine only vectors whose first nonzero component is positive. The method is essentially that of counting in steps of one, regarding (xi, . . . , xt) as the digits in a balanced number system with mixed radices (221 + 1,. . . ,2.z2 + 1); cf. Section 4.1.) S9. [Advance xk.1 If z k = Zk, go to Sll. Otherwise increase xk by 1 and set Y+Y+Uk. SlO. [Advance k.] Set k + k+l. Then if k 5 t, set xk t -Zk, Y c Y-2zkuk, and repeat step SlO. But if k > t, set s t min(s,Y . Y). Sll. [Decrease k.] Set k c k -1. If k 2 1, return to S9. Otherwise output vt = fi (the exhaustive search is completed) and return to S4. m In practice Algorithm S is applied for T = 5 or 6, say; it usually works reasonably well when T = 7 or 8, but it can be terribly slow when T 2 9 since the exhaustive search tends to make the running time grow as 3T. (If the minimum value vt occurs at many different points, the exhaustive search will hit them all; hence we typically find that all zk = 1 for large t. As remarked above, the values of vt are generally irrelevant for practical purposes when t is large.) An example will help to make Algorithm S clear. Consider the linear congruential sequence defined by m = lOlo, a = 3141592621, c = 1, x0 = 0. (32) Six cycles of the Euclidean algorithm in steps S2 and S3 suffice to prove that the minimum nonzero value of x1 + xi with xi + 3141592621×2 = 0 (modulo lOlo) occurs for x1 = 67654, 22 = 226; hence the two-dimensional accuracy of this generator is v2 = d676542 + 2262 e 67654.37748. Passing to three dimensions, we seek the minimum nonzero value of xy +xz +x: such that x1 + 3141592621×2 + 31415926212xs = 0 (modulo lOlo). (33) Step S4 sets up the matrices -67654 -226 0 -191 -44190611 2564918569 u = -44190611 191 0 , v = -226 67654 1307181134 . ( 5793866 33 11 ( 0 0 10000000000 1 The first iteration of step S5, with q = 1 for i = 2 and q = 4 for i = 3, changes them to -21082801 97 4 -191 -44190611 2564918569 u = -44190611 191 0 -35 44258265 -1257737435 . 5793866 33 1 764 176762444 -259674276