101 Ways To Find PI

This project's intent is to try 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

Name	Type	OpenMP available	CUDA available
Bayley	Iteration-based	Not yet	Not yet
Chebyshev	Iteration-based	Not yet	Not yet
Continuos fraction	Iteration-based	Not yet	Not yet
Deterministic Montecarlo	EPS-based	Not yet	Not yet
Gauss	EPS-based	Not yet	Not yet
Leibniz	Iteration-based	Not yet	Not yet
Montecarlo circle	Point-based	Not yet	Not yet
Montecarlo sphere	Point-based	Not yet	Not yet
Newton	Iteration-based	Not yet	Not yet
Polygon	Point-based	Not yet	Not yet
Recursive 4-splitting	EPS-based	Not yet	Not yet
Recursive binary-search	EPS-based	Not yet	Not yet
Row-wise binary-search	EPS-based	Not yet	Not yet
Viete	Iteration-based	Not yet	Not yet

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. deterministic_montecarlo 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

All results reported here have been measured on a machine with the following components.

| CPU | Intel Core i7 7700 | | CPU cores | 4 + HyperThreading | | RAM | 16 GB | | RAM frequency | 2400 MHz | | GPU | NVIDIA GeForce GTX 1070 | | GPU memory | 8 GB | | CUDA cores | 1920 |

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, also let me know.