Unit circle/Circle length/Bisection/Program/Exercise

We consider the unit circle, i.e.

$\{\left(\begin{array}{c}x\\ y\end{array}\right)\mid x^2+y^2=1\}\subseteq {ℝ}^2.$

We put $P_0=\left(\begin{array}{c}1\\ 0\end{array}\right)$ and $P_1=\left(\begin{array}{c}0\\ 1\end{array}\right)$, and we define recursively the sequence $P_n$ (in the plane) by

$Q_n=\frac{1}{2}(P_0+P_{n-1})$

(that is, $Q_n$ is the bisection point of the line segment between $P_0$ and $P_{n-1}$), and $P_n$ is the intersection point of the half-line through $\left(\begin{array}{c}0\\ 0\end{array}\right)$ and $Q_n$ and the circle. We consider the lengths $d_n=d(P_0,P_n)$ as an approximation for the length of the circle arc between $P_0$ and $P_n$, and therefore

$x_n=2^n{d}_n$

is an approximation for the length of the half circle arc (that is, $\pi$). Since in the computation of the points $P_n$ and the lengths $d_n$, square roots occure (due to the Pythagorean theorem), we can approximate these by rational numbers only with certain errors.

Write a computer-program (in pseudocode), which computes and prints a sequence $y_n$ of approximations ($n\ge 1$) for $x_n$. In the computation of $y_n$, all square roots, which are used in the computation of $x_n$, shall be computed with $n$ steps of Heron's method, starting with the initial value $1$. Also, the program shall use better and better approximations for the auxiliary points, the computation of $y_n$ requires that better and better approximations for $P_2,\dots ,P_n$ are determined.

• The computer has as many memory units as needed, which can contain rational numbers.
• The natural numbers are provided in a data base (they do not have to be computed).
• It can write the content of a memory unit into another memory unit.
• It can do the arithmetic operations (addition, subtraction, multiplication, division by a number $\ne 0$) on rational numbers and write the result in another memory unit.
• It can compare the content of memory units and can, depending on the outcome, switch to a certain program line.
• It can print contents of memory units and it can print given texts.

The program shall run to infinity and write down the approximations $y_1,y_2,y_3,\mathrm{...}$.

Create a solution