\centerline{\bf CS/MATH 3414 Homework \# 1}\bigskip

In 250 B. C. E., the Greek mathematician Archimedes estimated the
number $\pi$ as follows. He looked at a circle with diameter 1, and
hence circumference $\pi$. Inside the circle he inscribed a square.
The perimeter of the square is smaller than the circumference of the
circle, and so it is a lower bound for $\pi$. Archimedes then
considered an inscribed octagon, 16-gon, etc., each time doubling the
number of sides of the inscribed polygons, and producing ever better
estimates for $\pi$. Using 96-sided inscribed and circumscribed
polygons, he was able to show that $223/71 < \pi < 22/7$. There is a
recursive formula for these estimates. Let $p_n$ be the perimeter of
the inscribed polygon with $2^n$ sides. Then $p_2$ is the perimeter of
the inscribed square, $p_2=2\sqrt{2}$. In general
$$\eqalign{p_{n+1}&=2^n \sqrt{2(1-\sqrt{1-(p_n/2^n)^2})},\cr
p_2&=2\sqrt{2}.\cr}$$
Compute $p_n$ for $n=3$, 4, $\ldots$, 60. Try to explain the failure in
the formula.  (This problem was suggested by Alan Cline.)

\bigskip
The formula derived above to estimate $\pi$ fails due to a combination
of underflow and catastrophic cancellation.  The formula can be
improved so that the subtraction is eliminated.  First write $p_{n+1}$
as $$p_{n+1}=2^n\sqrt{r_{n+1}},$$ where
$$r_{n+1}=2(1-\sqrt{1-(p_n/2^n)^2}), \quad r_3=2/(2+\sqrt{2}).$$ Show
that $$r_{n+1}= {r_n \over {2+\sqrt{4-r_n}}}.$$ Use the last iteration
to calculate $r_n$ and $p_n$ for $n=3$, 4, $\ldots$, 60. (This revision
was suggested by W. Kahan.)

\bigskip Eventually, $4-r_n$ will round to 4, and so the latter formula
is still affected by rounding errors for large values of $n$. Should
this concern us?

\vfil\eject