Algorithmics - The Computing Universe: A Journey through a Revolution - page 88

number of darts that land within the square to the number that land within the
circle of radius R, we can obtain an estimate of π:

(Number of darts inside circle)/(Number of darts inside square) =
(Area of circle)/(Area of square) = πR 2 /4R 2 = π/4

In order for this method to give an accurate value of π, we need the darts
to be thrown genuinely at random, so that they cover the entire area uniformly.
We also need a large number of throws. Because generating large numbers of
truly random numbers is extremely difficult, von Neumann developed a clever
algorithm to generate “pseudorandom” numbers on the computer. Given an
initial starting number as a “seed,” these pseudorandom numbers are then gen-
erated deterministically by von Neumann's algorithm and approximate a truly
random distribution. This technique has the advantage that the exact sequence
of numbers can be reproduced by starting with the same seed, and this turns
out to be very helpful in debugging Monte Carlo simulation programs.
Although we have only given a very simple example here, Monte Carlo
methods can be used to evaluate complex integrals in a similar manner. These
methods are now widely used in many areas of science and business - and in
computer algorithms for playing games.

Fig. 5.4. Determination of π using Monte
Carlo method. The diagram shows a
circle of radius R inside a square of side
2R. The area of circle is πR 2 and the area
of the square is 4R 2 . Throwing randomly
distributed darts gives an estimate of
π by comparing the number of darts
landing inside the circle to the number
landing inside the square.

Sorting

Although the earliest electronic computers were generally used to find
numerical solutions to scientific problems, it was clear from early on that
they were capable of solving other types of problems. During World War II,
the Colossus computer at Bletchley Park in the United Kingdom was used for
breaking codes, and soon after the war the LEO computer demonstrated the
utility of computers for assisting with routine business problems, such as stock
keeping, distribution, and payroll.
Let's take a look at how computers handle such nonnumerical tasks. We
will do so by examining the problem of sorting a list of names into alphabeti-
cal order. We will show how this can be done using two different algorithms,

B.5.5. Stanislav Ulam was born in 1909 in the city of Lwow in Poland, now the city of Lviv in
the Ukraine. He studied mathematics at university and was a member of the Lwow School of
Mathematics. The members met at the Scottish Café in Lwow and recorded their discussions in the
“Scottish Book.” Ulam met John von Neumann and was invited to visit the institute at Princeton in
1935. He left Poland in 1939 just before the German invasion and many members of his family died
in the Holocaust. In 1943 Ulam was an assistant professor at the University of Wisconsin in Madison
and he asked von Neumann if he could join the war effort. As a result he received a letter from
Hans Bethe inviting him to join the Manhattan Project, a top-secret project to build the atom bomb,
based at Los Alamos, near Santa Fe, New Mexico. Because he knew nothing about New Mexico, Ulam
checked out a guidebook from the university library. On the checkout slip he found the names of
three colleagues who had mysteriously “disappeared” a few months before! At Los Alamos he worked
on numerical solutions to the hydrodynamical equations for the plutonium implosion bomb. After
the war, Ulam returned to Los Alamos to work on the development of the hydrogen bomb. In 1951,
Ulam and Edward Teller came up with a mechanism for a working fusion bomb using “radiation
implosion.”