[CLN-list] Re: applicability of AGM and binsplit

Richard B. Kreckel kreckel at ginac.de
Sat Jan 26 00:37:22 CET 2008


Dear Jörg,

Joerg Arndt wrote:
> For the computation of a logarithm of a real number (that ist not a
> rational a/b with both a nd b small) the AGM approach(s) are IIRC the
> fastest known.  I do not see how to use binsplit there but that may
> just reflect some lack of knowledge on my side.


BTW, I just read what your upcoming book has to say about binary 
splitting. The section about the memory consumption in "Computation of 
π: binary splitting versus AGM-type iterations" is too pessimistic. You 
write:

"The drawback of the binary splitting scheme is that it may need 
significantly more memory than two full words. This may happen if the 
numerator and denominator grow fast which is more likely if no series so 
favorable as [Chudnovsky's series for pi] can be used for the quantity 
to be computed."

With the truncation technique I described earlier, the memory needed is 
basically independent of the series. The growth of numerator and 
denominator is limited to the precision of the result. The computation 
of Euler's γ in CLN-1.2.0 is actually an excellent example for this. See 
the two graphs at [0] and observe that the blue curves' maximum is not 
so different after all (it peaks at 8.4MiB for π and for 15.6MiB for γ.) 
What you write is correct without truncation, though. See the red and 
green curves.

Cheers
   -richy.

[0] <http://www.ginac.de/~kreckel/news.html#EulerConstantOneBillionDigits> 
-- 
Richard B. Kreckel
<http://www.ginac.de/~kreckel/>


More information about the CLN-list mailing list