Bresenham’s Pie


Approximating \pi is always fun. Some approximations are well known, like Zu Chongzhi’s, \frac{355}{113}, that is fairly precise (it gives 6 digits).

We can derive a good approximation using continue fractions, series, or some spigot algorithm. We can also use Monte Carlo methods, such as drawing uniformly distributed values inside a square, count those who falls in the circle, then use the ratio of inside points to outside points to evaluate \pi. This converges slowly. How do we evaluate the area of the circle then? Well, we could do it exhaustively, but in a smart way.

Read the rest of this entry »