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

Joerg Arndt arndt at jjj.de
Wed Jan 23 08:37:11 CET 2008


* Bruno Haible <bruno at clisp.org> [Jan 23. 2008 14:14]:
> Joerg Arndt wrote:
> > binsplit wins routinely whenever applicable, mostly for its memory
> > locality.  There are, however, things where (to my knowledge) no
> > binsplit based algorithm can be used.  So it is fine to also know
> > about the performance of the AGM.
> 
> To me it looks like the AGM is based on mathematical properties of
> particular algebraic curves. Whereas binsplit is a general technique
> that provides fast evaluation of any holonomic function (with algebraic
> initial conditions at an algebraic point) at regular and even at singular
> points. These are resuls from Joris van der Hoeven [1] (see the three papers
>   Fast evaluation of holonomic functions
>   Fast evaluation of holonomic functions near and in singularities
>   Efficient accelero-summation of holonomic functions
> there).
> 
> Bruno
> 
> [1] http://www.math.u-psud.fr/~vdhoeven/
> 

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.

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

regards,   jj



More information about the CLN-list mailing list