101 Ways To Find PI

The goal of this project is to enumerate (and implement) all known ways to calculate an approximated value of PI.

Table of contents

1. Summary
2. List
3. Best Results
   1. EPS-based methods
   2. Iteration-based methods
   3. Point-based methods
4. Contributions

Summary

Despite the name, there are only 14 algorithms currently implemented. Here they are in alphabetical order.

Name	Type
Bayley	Iteration-based
Chebyshev	Iteration-based
Continuos fraction	Iteration-based
Gauss	EPS-based
Grid	EPS-based
Leibniz	Iteration-based
Montecarlo circle	Point-based
Montecarlo sphere	Point-based
Newton	Iteration-based
Polygon	Point-based
Recursive 4-splitting	EPS-based
Recursive binary-search	EPS-based
Row-wise binary-search	EPS-based
Viete	Iteration-based

List

1. montecarlo_circle performs the classic Montecarlo method of calculating the ratio between the area of the unit circle and the area of its circumscribed square.
2. grid performs a "deterministic" version of the Montecarlo method: instead of generating some random points, considers all points at fixed locations.
3. montecarlo_sphere performs the same algorithm of montecarlo_circle, but with a sphere inside a cube.
4. recursive_4_splitting performs a recursive call (each time splitting the area 4 times) to find the area of the quarter-circle in the first quadrant.
5. row_binary_search works on the first quadrant section of the unit circle, for each row it binary-searches for the border of the circle and then adds together all those little slices to compute the area of the unit circle.
6. recursive_binary_search_2d is an improvement of recursive_4_splitting by using binary search to find the border of the circle.
7. gauss_integral computes the integral of exp(-x*x), which tends towards sqrt(pi).
8. continuous_fraction computes the value of a continuous fraction with a depth limit.
9. viete computes the infinite product of Viete's formula.
10. leibniz computes the infinite sum of Leibniz's formula.
11. bailey computes the infinite sum of Bailey-Borwein-Plouffe's formula.
12. newton computes the infinite sum of Newton's factorial's formula.
13. chebyshev computes the infinite sum of Chebyshev's formula.
14. polygon computes the area of the unit circle approximating it as a polygon.

Best Results

EPS-based methods

All the following methods have been executed using EPS=1e-8. The relative error is calculated using the macro M_PI defined in math.h.

Method	Correct digits	Relative Error	WCT
Deterministic Montecarlo
Gauss
Recursive 4-splitting
Recursive binary-search
Row-wise binary-search

Iteration-based methods

All the following methods have been executed using steps=20. The relative error is calculated using the macro M_PI defined in math.h.

Method	Correct digits	Relative Error	WCT
Bayley
Chebyshev
Continuous fraction
Leibniz
Newton
Viete

Point-based methods

All the following methods have been executed using points=1000. The relative error is calculated using the macro M_PI defined in math.h.

Method	Correct digits	Relative Error	WCT
Montecarlo circle
Montecarlo sphere
Polygon

Contributions

Each one of these programs is really simple and requires at most two hours of work. In that little time, some bugs can appear unnoticed so if you happen to find one, please let me know. If you want to contribute, feel free to do so.