The Gauss-Legendre algorithm is a high-precision method for computing π using the arithmetic-geometric mean and Legendre's relation. It was discovered by Carl Friedrich Gauss and provides quadratic convergence, meaning the number of correct digits approximately doubles with each iteration. This makes it one of the fastest-converging algorithms for calculating π.
The Gauss-Legendre algorithm was discovered by Carl Friedrich Gauss around 1800, though it wasn't published until much later in his collected works. The method combines two important mathematical concepts: the arithmetic-geometric mean, which Gauss extensively studied, and Legendre's relation, developed by Adrien-Marie Legendre. This algorithm represented a significant advancement in computing π, as it converges much faster than classical methods like Archimedes' approach or infinite series.
from math import sqrt
def gauss_legendre_pi(iterations):
"""
Compute π using the Gauss-Legendre algorithm.
Args:
iterations: Number of iterations for precision
Returns:
Approximation of π
"""
# Initialize variables
a = 1.0
b = 1.0 / sqrt(2)
t = 0.25
p = 1.0
# Perform iterations
for _ in range(iterations):
a_next = (a + b) / 2
b = sqrt(a * b)
t = t - p * (a - a_next) ** 2
p = 2 * p
a = a_next
# Calculate π
return (a + b) ** 2 / (4 * t)
# Example usage
if __name__ == "__main__":
for i in range(1, 6):
pi = gauss_legendre_pi(i)
print(f"After {i} iterations: {pi:.12f}")
#include <iostream>
#include <cmath>
#include <iomanip>
class GaussLegendre {
private:
int iterations;
public:
GaussLegendre(int iter = 5) : iterations(iter) {}
double computePi() {
// Initialize variables
double a = 1.0;
double b = 1.0 / std::sqrt(2.0);
double t = 0.25;
double p = 1.0;
// Perform iterations
for (int i = 0; i < iterations; i++) {
double a_next = (a + b) / 2;
b = std::sqrt(a * b);
t = t - p * std::pow(a - a_next, 2);
p = 2 * p;
a = a_next;
}
// Calculate π
return std::pow(a + b, 2) / (4 * t);
}
};
int main() {
std::cout << std::fixed << std::setprecision(12);
for (int i = 1; i <= 5; i++) {
GaussLegendre gl(i);
double pi = gl.computePi();
std::cout << "After " << i << " iterations: "
<< pi << std::endl;
}
return 0;
}
public class GaussLegendre {
private readonly int iterations;
public GaussLegendre(int iterations = 5) {
this.iterations = iterations;
}
public double ComputePi() {
// Initialize variables
double a = 1.0;
double b = 1.0 / Math.Sqrt(2.0);
double t = 0.25;
double p = 1.0;
// Perform iterations
for (int i = 0; i < iterations; i++) {
double a_next = (a + b) / 2;
b = Math.Sqrt(a * b);
t = t - p * Math.Pow(a - a_next, 2);
p = 2 * p;
a = a_next;
}
// Calculate π
return Math.Pow(a + b, 2) / (4 * t);
}
public static void Main() {
for (int i = 1; i <= 5; i++) {
var gl = new GaussLegendre(i);
double pi = gl.ComputePi();
Console.WriteLine(
$"After {i} iterations: {pi:F12}"
);
}
}
}
The time complexity is O(M(n) log n), where:
The space complexity is O(n), which includes: