[CLN-list] applicability of AGM and binsplit

[Bruno Haible]

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

log being the inverse function of exp, a Newton iteration (with increasing
precision: precision n for the last iteration, n/2 for the second-to-last,
n/4 for the third-to-last etc.) of the equation  exp(x) = c  will yield
log(c). If the computation time for exp is   O(n (log n)^j (log log n)^k)
(j, k usually being 1 or 2), then the computation time for its inverse
function is the same: it differs only by a O(1) factor. This is already
contained in Brent's classical paper from the 70ies.

> I also did not study the "bit-burst" method so far.

The first part of Paul Zimmermann's presentation on the "bit-burst algorithm"
is a reminder to Brent's technique coming from the Newton iteration, as
outlined above.

Then he applies this technique to holonomic function. I think this is
the same idea as in van der Hoeven's paper, presented in a more understandable
form (and working with the coefficient recursion instead of the differential
equation - you cannot prove much mathematics when working on the coefficient
recursion, because you are no longer working in an integral domain, but when
it comes to doing the computations, the coefficient recursion side is often
a little more efficient than the differential equation side).

Bruno