Java Reference
In-Depth Information
Fermat's Little Theorem
States that if
P
is prime and
,
then
. It is necessary but not sufficient to establish primality.
0
<<
AP
A
P
-
1
≡
1 mod
P
(
)
(409)
full-period linear congruential generator
A random number generator that has
period . (397)
linear congruential generator
A good algorithm for generating uniform distri-
butions. (397)
negative exponential distribution
A form of distribution used to model the time
between occurrences of random events. Its mean equals its variance. (404)
period
The length of the sequence until a number is repeated. A random num-
ber generator with period
P
generates the same random sequence of ran-
dom numbers after
P
iterations. (397)
permutation
A permutation of 1, 2, ,
N
is a sequence of
N
integers that
includes each of 1, 2, ,
N
exactly once. (394)
Poisson distribution
A distribution that models the number of occurrences of a
rare event. (402)
pseudorandom numbers
Numbers that have many properties of random num-
bers. Good generators of pseudorandom numbers are hard to find. (395)
random permutation
A random arrangement of
N
items. Can be generated in
linear time using one random number per item. (405)
randomized algorithm
An algorithm that uses random numbers rather than
deterministic decisions to control branching. (406)
seed
The initial value of a random number generator. (397)
trial division
The simplest algorithm for primality testing. It is fast for small
(32-bit) numbers but cannot be used for larger numbers. (409)
uniform distribution
A distribution in which all numbers in the specified range
are equally likely to occur. (395)
witness to compositeness
A value of
A
that proves that a number is not prime,
using Fermat's Little Theorem. (410)
M
-
1
…
…
Using an initial seed of zero gives bad random numbers.
1.
Inexperienced users occasionally reinitialize the seed prior to generating a
random permutation. This action guarantees that the same permutation
will be repeatedly produced, which is probably not intended.
2.
Many random number generators are notoriously bad; for serious applica-
tions in which long sequences of random numbers are required, the linear
congruential generator is also unsatisfactory.
3.
Search WWH ::
Custom Search