PSEUDORANDOM NUMBER GENERATION 263repeat
location = N * RanNum() + 1
until list[location] = 0
list[location] = i
end for
Even though the first bunch of values will be placed quickly, the problem
with this method is that as the list fills up, it will be harder and harder to find a
free location. This method, therefore, could take a long time to accomplish this
simple task.
■ B.2.2 Method 2
We saw in Method 1 that a problem occurred when the random location we
chose was “full.” In this alternative, if the location is full, we will just try suc-
cessive locations until we find one that is free. This gives the algorithm
for i = 1 to N do
list[i] = 0
end for
for i = 1 to N do
location = N * RanNum() + 1
while list[location] ≠ 0 do
location = (location mod N) + 1
end while
list[location] = i
end for
This method will work relatively quickly, but if we have a block of filled
locations, it is possible we may have a lot of values in relatively sequential order.
In other words, let’s say that in a list with 100 locations those from 1 to 25 are
filled first in some random order. There is now a 25% chance that our next
choice will be in the range of the first 25 locations, in which case, the value
will be stored in location 26. If it happens again, the next value will go into
location 27, then 28, and so on. This could happen anywhere in the list and has
the potential of creating a block of locations that have numbers that are
sequential or almost sequential.
■ B.2.3 Method 3
In this last method, we will use the random number we generate as a counter
for how many empty locations to skip in deciding on where to place the
next value. This eliminates the problem of Method 1 by placing a value for