Pi_Chud Demo, mpf_out_str, etc

[Paul Zimmermann]

> From: Torbjorn Granlund <tege at swox.com>
> Date: Tue, 13 Nov 2007 14:44:51 +0100
> 
> I wrote:
> 
>   Both mpf_get_str and mpf_out_str used to need runtime quadratic to the
>   number of digits produced.  Now it is O(M(n)).
> 
> I suppose that's not really true, the mp*_get_str and consequently
> the mp*_out_str functions rely on division, which is O(M(n)log(n)).
> 
> -- 
> Torbjörn

right, thus they are in O(M(n) log(n)^2). With Newton's division, one
would have D(n) = O(M(n)), thus O(M(n) log(n)) for mp*_get_str, and
with Bernstein's scaled remainder tree technique, one could save a
constant factor. See Section 1.7 and Exercise 1.9.21 of [MCA].

[MCA] Modern Computer Arithmetic, Richard Brent and Paul Zimmermann,
version 0.1.1, November 2006, http://www.loria.fr/~zimmerma/mca/mca-0.1.1.pdf.

Paul