Java Reference
In-Depth Information
By definition of the mod function, all generated numbers must be in the range
0 to t 1. Now, consider what happens when r(i) = r(j) for values i and j. Of
course then r(i + 1) = r(j + 1) which means that we have a repeating cycle.
Since the values coming out of the random number generator are between 0 and
t1, the longest cycle that we can hope for has length t. In fact, since r(0) = 0, it
cannot even be quite this long. It turns out that to get a good result, it is crucial to
pick good values for both b and t. To see why, consider the following example.
Example16.4 Given a t value of 13, we can get very different results
depending on the b value that we pick, in ways that are hard to predict.
r(i) = 6r(i 1) mod 13 =
..., 1, 6, 10, 8, 9, 2, 12, 7, 3, 5, 4, 11, 1, ...
r(i) = 7r(i 1) mod 13 =
..., 1, 7, 10, 5, 9, 11, 12, 6, 3, 8, 4, 2, 1, ...
r(i) = 5r(i 1) mod 13 =
..., 1, 5, 12, 8, 1, ...
..., 2, 10, 11, 3, 2, ...
..., 4, 7, 9, 6, 4, ...
..., 0, 0, ...
Clearly, a b value of 5 is far inferior to b values of 6 or 7 in this example.
If you would like to write a simple LCM random number generator of your
own, an effective one can be made with the following formula.
r(i) = 16807r(i 1) mod 2 31 1:
16.3.5 The Fast Fourier Transform
As noted at the beginning of this section, multiplication is considerably more diffi-
cult than addition. The cost to multiply two n-bit numbers directly is O(n 2 ), while
addition of two n-bit numbers is O(n).
Recall from Section 2.3 that one property of logarithms is
log nm = log n + log m:
Thus, if taking logarithms and anti-logarithms were cheap, then we could reduce
multiplication to addition by taking the log of the two operands, adding, and then
taking the anti-log of the sum.
Under normal circumstances, taking logarithms and anti-logarithms is expen-
sive, and so this reduction would not be considered practical. However, this re-
duction is precisely the basis for the slide rule. The slide rule uses a logarithmic
scale to measure the lengths of two numbers, in effect doing the conversion to log-
arithms automatically. These two lengths are then added together, and the inverse
 
Search WWH ::




Custom Search