## I Calculate the Digits of Pi – Very Slowly – Reprise

This post somehow got lost a year ago.  I am reposting it here.

Years ago I wrote an assembly language routine that drew circles with  a pen plotter.  This entailed approximating the arc of a circle with a series of small horizontal and vertical steps.  I was proud of the method because its critical loop used only additions and multiplications by 2 (bit shift left in assembly language) and was very fast.

So I thought this summer that if I can draw a circle fast, I ought to be able to calculate $\pi$ fast.  I wrote a routine in the Python programming language, optimized it as best I could and here are my results.   (My method also allowed me to calculate $\sqrt {2}$ – also very slowly)

Calculating Pi Data

This is just terribly slow.  As I read the table, it takes 10 times the time to get one more digit of $\pi$.  I stopped when the program ran 524 seconds and still hadn’t calculated 9 digits of $\pi$.  I will describe the method I used and the reason it was so slow in the rest of the article.

Our object is to trace the arc of a circle as closely as possible using only up and down, and right and left movements of one step.  Start with a point $(x,y)$ on a circle with radius $r$, for example $(r,0)$, so that $x^2+y^2=r^2$.  Without loss of generality assume we are in the first quadrant and we are drawing the circle in a counterclockwise direction.  Since we can only take one step vertically or horizontally at a time, we either increase $y$ by $1$ or decrease $x$ by $1$.  If we increase $y$ by $1$, the square of the distance of the new point from the origin is $x^2+(y+1)^2=x^2+y^2+2y+1$.  The change in the distance squared ($\Delta r^2$) is $2y+1$. Call this $yinc$.  If we decrease $x$ by $1$, the change in $\Delta r^2$ is $-2x+1$. Call this $xinc$.  We choose to keep $\Delta r^2$ nonnegative and as small as possible.  So we calculate $yinc$ and $xinc$,  add each to $\Delta r^2$ separately, and see which result is nonnegative and smallest.

The cool thing is that each time, our new $\Delta r^2$ is just the old $\Delta r^2$ plus $yinc$ or $xinc$ depending on which change in variable we chose.  Here is why.  Say we start at $(x,y)$ on the circle and choose $y$ to increase by  $1$.  Now $\Delta r^2 =2y+1$.  Call the new $y$, $y_1=y+1$ so that we are now at $(x,y_1)$. As an example now say we wish to increase  $y_1$ by  $1$ so that our new $y$ is $y_1+1$.

Now $\Delta r^2=x^2+(y_1+1)^2-x^2-y^2\\=x^2+y_1^2+2y_1+1-x^2-y^2\\=x^2+(y+1)^2+2y_1+1-x^2-y^2\\=2y+1+2y_1+1$.

The $2y+1$ is just the old $\Delta r^2$, so we just add  $2y_1+1$ to the old $\Delta r^2$ to get the updated $\Delta r^2$ and continue.  By the way this method can be used to “draw” any conic section with axes parallel to the coordinate axes.

To calculate $\pi$, every time $y$ is increased, add the current $x$ to a area accumulator.  Stop the process when $x=y$.  From the outlined area in the diagram subtract the area of the triangle OAB and what’s left is the approximate area of an eighth of a circle.  Calculate $\pi$.  This is basically a crude integration.

Calculating Pi - Diagram

Here are two python program fragments that show the algorithm.  The first is the original version which was written for clarity to stay close to the mathematics and the second was optimized for speed – not that it helped much.

Pi Calculation - First Try

Pi Calculation - "Optimized"

It is fairly easy to see where the error comes from.  By staying just outside of the circle – at most one vertical or horizontal step, the area is overestimated by at most $2\pi r\sqrt{2}$.  The calculated area is at most $\pi r^2+2\pi r\sqrt{2}$.  Dividing by $r^2$ gives $\pi + \frac{2\pi\sqrt{2}}{r}$.  Increasing $r$ ten times moves the decimal point over one.

My discovery of “drawing” conic sections by looking only one step ahead was satisfying and at least years ago useful.   I was sobered by the sad slow algorithm that I devised to calculate $\pi$.  A method with linear efficiency is really slow.  I now have more than a theoretical understanding of this fact.