96 RANDOM NUMBERS 3.3.4 has the same answer.
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