Scientific Computing

This module compares random and quasi-random sequences by plotting in two dimensions sequences of pairs of numbers of each type. For Monte Carlo integration and a variety of other applications, random numbers are used to sample within some geometric domain. In some cases it may be more important to achieve approximately uniform coverage of the domain than for the sampling to be truly random. Quasi-random sequences, also known as low-discrepancy sequences, are carefully constructed to spread approximately uniformly over a given domain while still maintaining some appearance of randomness. Hence, quasi-random sequences may sometimes be more appropriate than truly random sequences.

This module plots a sequence of random points on the left and a
sequence of quasi-random points on the right. The user adds points to
the plots by clicking *Add Points*. The user can select how many
points are added to the graph with each click of the button,
controlling how quickly the graphs fill in with points. Clicking
*Reset* clears the graphs and resets the quasi-random sequences.
The pseudorandom sequence used to generate the points on the left is
the linear congruential generator used in Java's Math.random( )
function. Menus allow the user to select how the quasi-random points
are generated:

- Halton sequences, one of the earliest methods for generating
quasi-random sequences, depend on choosing a prime number
*b*as the base or radix to generate the sequence. The*j*th number in the sequence,*x*_{j}, is computed by writing*j*in base*b*and flipping the base-*b*digits across the radix point. For example, in base 2, the 6th number in the sequence is0.011 . For Halton sequences, the user can select the radix_{2}= 3 ⁄ 8 = 0.375_{10}*b*defining a specific sequence. - Sobol sequences, one of the most commonly used quasi-random sequences today, are more complicated. Each primitive polynomial over the finite field GF(2) generates a Sobol sequence depending on a set of initial “direction numbers”. This module allows the user to select a primitive polynomial, completing the definition of the Sobol sequence with a table of predetermined initial direction numbers. For a more complete description of Sobol sequences, see reference [2].

For either Halton sequences or Sobol sequences, the user chooses a
sequence for each of the coordinates in the plane. Each coordinate
sequence assigns the *j*th number of the quasi-random sequence to
its coordinate in the *j*th point in the sequence of points,
regardless of whether the same sequence is chosen for both
coordinates. Thus if the same sequence is chosen for both coordinates,
every point will lie on the line *x* = *y*

**References:**

- Michael T. Heath,
*Scientific Computing, An Introductory Survey*, 2nd edition, McGraw-Hill, New York, 2002. See Section 13.4, especially Figure 13.1. - W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery.
*Numerical Recipes*, 2nd edition, Cambridge University Press, New York, 1992. See Section 7.7.

**Developers:** Evan VanderZee and Michael Heath