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