Calculating pi on Python

Calculating the Digits of Pi: Benchmarking the Bailey–Borwein–Plouffe (BBP) formula and the Chudnovsky algorithm

Don’t judge me; what do you do on a Wednesday night?

I asked ChatGPT to spit out some Python code to calculate pi to 1,000 digits. Then asked if it could speed it up. Computing the digits of π (pi) is a fascinating exercise in both mathematical theory and computational prowess. There are It described two different methods. I asked ChatGPT to provide a benchmark. Here is some of the detail it provided.

There are several methods to calculate π, each with its strengths and peculiarities. In this post, we’ll explore two prominent algorithms: the Bailey–Borwein–Plouffe (BBP) formula and the Chudnovsky algorithm, implemented with the mpmath library in Python. We’ll also discuss their performance, especially for generating a large number of digits.

The Bailey–Borwein–Plouffe (BBP) Formula

The BBP formula is notable for allowing the extraction of individual hexadecimal (base-16) digits of π without needing to calculate the preceding digits. This makes it unique and efficient for certain applications, though it’s not typically the fastest for generating a large number of consecutive digits.

Here’s how the BBP algorithm works in Python:

import decimal
from decimal import Decimal, getcontext

def bbp_algorithm(n):
    """Generate the first n digits of pi using the BBP formula."""
    getcontext().prec = n + 2
    pi = Decimal(0)
    k = 0
    while k < n:
        pi += (Decimal(1) / (16 ** k)) * (
            Decimal(4) / (8 * k + 1) -
            Decimal(2) / (8 * k + 4) -
            Decimal(1) / (8 * k + 5) -
            Decimal(1) / (8 * k + 6)
        )
        k += 1
    return str(pi)

def main():
    num_digits = 10000  # Adjust the number of digits to test
    pi_str = bbp_algorithm(num_digits)
    print(f"First {num_digits} digits of pi:\n{pi_str[:50]}...")

if __name__ == "__main__":
    main()

The Chudnovsky Algorithm

The Chudnovsky algorithm is highly efficient for generating a large number of digits of π. It converges rapidly, making it a go-to choice for high-precision calculations. When implemented with the mpmath library, it leverages advanced optimizations to handle the arithmetic operations involved.

Here’s the Chudnovsky algorithm implemented with mpmath:

import mpmath

def chudnovsky_mpmath(digits):
    """Compute pi to the specified number of digits using the Chudnovsky algorithm with mpmath."""
    mpmath.mp.dps = digits + 10  # Set precision slightly higher
    pi = mpmath.pi
    return str(pi)

def main():
    num_digits = 10000  # Adjust the number of digits to test
    pi_str = chudnovsky_mpmath(num_digits)
    print(f"First {num_digits} digits of pi:\n{pi_str[:50]}...")

if __name__ == "__main__":
    main()

Benchmarking the Algorithms

To determine which algorithm performs better for our purposes, we can benchmark them by measuring the time taken to compute a specific number of digits. Here’s a combined script that benchmarks both the BBP and Chudnovsky algorithms:

import time

def benchmark_algorithm(algorithm, digits):
    """Benchmark the specified algorithm."""
    start_time = time.time()
    result = algorithm(digits)
    end_time = time.time()
    return end_time - start_time, result

def main():
    num_digits = 10000  # Adjust the number of digits to test

    bbp_time, bbp_result = benchmark_algorithm(bbp_algorithm, num_digits)
    chudnovsky_time, chudnovsky_result = benchmark_algorithm(chudnovsky_mpmath, num_digits)

    print(f"BBP algorithm time for {num_digits} digits: {bbp_time:.6f} seconds")
    print(f"Chudnovsky algorithm (mpmath) time for {num_digits} digits: {chudnovsky_time:.6f} seconds")

    # Optionally, verify the first few digits of the results for sanity check
    print(f"First 50 digits of Pi (BBP): {bbp_result[:50]}")
    print(f"First 50 digits of Pi (Chudnovsky, mpmath): {chudnovsky_result[:50]}")

if __name__ == "__main__":
    main()

Results and Analysis

When running the benchmark on an older Intel i3 processor, we obtained the following results for computing 10,000 digits of π:

• BBP Algorithm: Approximately 91.56 seconds
• Chudnovsky Algorithm (mpmath): Approximately 0.011 seconds

These results show a stark contrast in performance. The BBP algorithm, while fascinating for its ability to extract specific digits, is not optimized for generating long sequences of digits. On the other hand, the Chudnovsky algorithm with mpmath is incredibly efficient, leveraging rapid convergence and advanced optimizations to deliver results almost instantaneously.

Conclusion

For anyone looking to compute a large number of digits of π, the Chudnovsky algorithm with mpmath is the clear choice. It combines mathematical elegance with computational efficiency, making it suitable for high-precision arithmetic.

On the flip side, the BBP formula remains an interesting and useful method for scenarios where specific digit extraction is required without computing all preceding digits.

I asked ChatGPT to make it faster still and expected next jumps might require more effort – ChatGPT provided code written in C but as it is late, that may be another Wednesday evening.