Here we'll see two examples about how random numbers could be used in programming, as it was hinted in article about Random Number Generators.
Were you ever curious how ancient matematician found the value of PI = 3.14159...? Direct measuring of the
circumference of some round pillar with a rope will give quite inaccurate results (you can easily check).
Archimedes used the method of approximating the circle with successive sequence of polygons (with 6, 12, 24... sides). Perimeter of these figures could be found with comparatively simple equations and at the same time they soon become very close to circle so that dividing perimeter by diameter very precise value could be found.
For programmer simplest way is based on virtual experiment:
- suppose, we have a circle target with radius R = 1 tightly fit inside a square with sides of length A = 2;
- suppose we shoot at it so that bullet hits any point of a square with equal probability;
- number of bullets which also hit the circle will be proportional to area of a circle.
So if Ntotal is the whole number of bullets hitting the square and Ncircle is the number of bullets hitting the
circle we can calculate
PI = 4 * Ncircle / Ntotal
with accuracy increasing with growth of Ntotal.
To conduct such experiment programmatically, let us perform many attempts of throwing virtual bullet onto plane -
simply choose random values X and Y both in range 0 ... 2 - these are coordinates of hit inside the square and
then calculate distance from the center:
dist = sqrt((X - 1)^2 + (Y - 1)^2)
if it is less than radius of the circle (dist <= R), then the bullet hits the circle. Surely with computers we can
perform this million times in a few seconds and get good enough approximation for PI. However it is important that
random numbers are generated uniformly enough - obviously if both X and Y will be generated so that values
closer to 1 are encountered bit more often, we'll get PI greater than it should be.
This algorithm is one of the use-case for the Monte-Carlo method.
Suppose we have some horrible function of several variables, like this:
Z = 3.29 * X^2 + 7 * X + 1.09 * X * Y + 2.15 * EXP(Y^2) - 11.59 * Y^(1/3)
And we are seeking for point where it has a minimum. There are a bunch of good iterative methods, but some require calculation of derivative, others want function to have some specific properties etc.
Instead we can do the following procedure (supposing we have slight idea of range where minimun could be):
- chose random X and Y from the range we are suspect minimum is;
- calculate Z here and remember it;
- repeat this action 1000 times and select point (X, Y) where value of Z is the smallest (current minimum);
- shrink the range from which points are chosen to be 2 ... 5 times smaller and with center at current minimum;
- choose another 1000 points in this smaller range and improve current minimum with smallest value of Z again;
- continue shrinking range until it becomes satisfactory small.
This method though not very speedy is good because it allows searching for optimal values of many variables in almost any task - it could be used even for "teaching" neural networks (by improving coefficients of neurons). And at the same time it does not depend critically on some specific mathematical properties of the task.