Calculated pi with 487 billion digits by diskized GMP

Torbjörn Granlund tg at
Sat Sep 2 19:08:46 CEST 2023

cents2823 at writes:

  Thank you for your comment.
  What is the algorithm name and multiplication performance?

The FFT variant we worked on uses 3 to 5 word-size primes of a special
form with high-order roots of unity.  This algorithm is sometimes called
the "small primes" algorithm.

It also uses Bailey's "4-step" multi-dimensional transform trick.

The performance problem with the current FFT code is, according to our
incomplete analysis, that its coefficient are large, so large infact
that when multiplying operands with billions of digits, no full
coefficient fits in cache.

Most Pi computation programs use FFTs over complex number, using
floating-point.  GMP has avoided that as it is hard to make sure
rounding errors cannot in corner cases produce incorrect results.

However, the advantage with that approach is that hardware supports that
much better than it does the prime field arithmetic used for the small
primes algorithm.

Please encrypt, key id 0xC8601622

More information about the gmp-discuss mailing list