9.2 PROBABILISTIC ALGORITHMS 241Buffon’s Needle
Let’s say that you have a set of 355 sticks and the lengths of these sticks are
one-half the widths of the boards in a hardwood floor. If we dump these
sticks on the floor, how many will fall across the cracks between two boards?
The number will have to be between 0 and 355, but Georges Louis Leclerc
showed the average number to be almost exactly 113. Each stick has a 1 in
chance of landing on a crack. This is because of the relationship of the rota-
tion of a stick to the spacing of the boards. If the stick falls perpendicular to
the cracks there is a one-half chance it will fall on a crack (the ratio of its
length to the width of the boards). But if it falls parallel to the crack, the
chance it will cross a crack is extremely small (the ratio of its width to the
width of the boards). So this technique could be used to calculate by ran-
domly dropping sticks and counting how many fall across the cracks. The
ratio of the total number of sticks to the number that cross a crack gives an
approximation of .
A similar technique can be used by simulating throwing darts at a board
that has a circle inscribed within a square (Fig. 9.3). We randomly choose
points in the square and count how many fall into the circle. If r is the radius
of the circle, the area of the circle is r^2 , and the area of the square is (2r)^2 , o r
4 r^2. The ratio of the area of the circle to the area of the square is / 4. If our
numbers are truly random, the darts will be spread relatively evenly across
the square. If we randomly "throw" darts at the square, can be estimated by(^4) *c / s, where c is the number of darts that fall in the circle and s is the
number of darts thrown. The more darts we throw, the more accurate our
calculation of .
This technique could also be used to approximate the area of any irregular
shape for which we can determine if a point (x,y) is inside or outside the
■FIGURE 9.3
A circle inscribed
within a square