Calculated pi with 487 billion digits by diskized GMP

[Torbjörn Granlund]

cents2823 at yahoo.co.jp 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.

-- 
Torbjörn
Please encrypt, key id 0xC8601622