Quick Info

Category: Numerical Methods
Time Complexity: O(M(n) log n)
Space Complexity: O(n)
Input Type: None (Computes π)

Gauss-Legendre Algorithm

Description

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

How It Works

  1. Initialization:
    • Set a₀ = 1
    • Set b₀ = 1/√2
    • Set t₀ = 1/4
    • Set p₀ = 1
  2. Iteration Process:
    • Calculate arithmetic mean: aₙ₊₁ = (aₙ + bₙ)/2
    • Calculate geometric mean: bₙ₊₁ = √(aₙbₙ)
    • Update t: tₙ₊₁ = tₙ - pₙ(aₙ - aₙ₊₁)²
    • Update p: pₙ₊₁ = 2pₙ
  3. Compute π:
    • After n iterations, π ≈ (aₙ + bₙ)²/(4tₙ)
    • Each iteration approximately doubles precision
  4. Convergence:
    • Continue until desired precision is reached
    • Usually 4-5 iterations give ~16 decimal places

History

Gauss-Legendre Algorithm Illustration

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.

Visualization

Select number of iterations and click Start

Implementation


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}"
            );
        }
    }
}
                                        

Complexity Analysis

Time Complexity

The time complexity is O(M(n) log n), where:

  • n is the desired number of bits of precision
  • M(n) is the complexity of n-bit multiplication
  • Each iteration doubles the precision
  • Number of iterations is logarithmic in n

Space Complexity

The space complexity is O(n), which includes:

  • Storage for high-precision numbers
  • Temporary variables for computation
  • No additional data structures needed

Advantages and Disadvantages

Advantages

  • Quadratic convergence
  • Very high precision possible
  • Few iterations needed
  • Numerically stable

Disadvantages

  • Complex square root calculations
  • High memory usage for large precision
  • Not as intuitive as other methods
  • Requires high-precision arithmetic