[seqfan] Re: Base conversion question

Joerg Arndt arndt at jjj.de
Thu Jul 23 06:34:17 CEST 2009


* victor miller <victorsmiller at gmail.com> [Jul 23. 2009 13:22]:
> I remember the Chudnovsky brothers telling me many years ago that when they
> were calculating pi to billions of decimal places they ended up using
> multiprecision in a base of 10^k (for some convenient k) since they had
> found that it took much longer to convert from the result in binary than it
> did to actually compute it!
> Victor
> 
> [...]

This is why one may want do the computations in base 10^k right away.
With (float!) FFT multiplication this does not slow things down.
Schoenhage multiplication needs radix-2 of course.

Computing Pi with binary splitting and Chudnovsky's formula is
blazing fast, and radix conversion is in the same order.
Radix conversion should not be much slower than the Pi
computation, rather a bit faster.

real world example:
The CLN library comes with a little example program for
doing this (binsplit-Pi, the radix conversion).

Timing with cln 1.2.0 (precision == 2^20 decimal digits):
% time pi 1048576 > /dev/null
pi 1048576 > /dev/null  5.76s user 0.10s system 99% cpu 5.892 total

cf. AGM scheme (Schoenhage's trick: one sqrt and one
squaring per iteration, also Schoenhage's version of the sqrt iteration),
using hfloat:
./pi 18 16 > /dev/null  14.58s user 0.05s system 100% cpu 14.628 total

Binsplit is memory local until the very end of the computation
(IF computed depth first), so _really_ fast in practice.





More information about the SeqFan mailing list