Sub-quadratic mpf conversion, mpn highpart, mpn lowpart

Torbjorn Granlund
13 May 2003 02:09:07 +0200

I have finally gotten around to writing a sub-quadratic mpf_get_str.
It simply generates a number for mpn_get_str, by multiplying
or dividing the original number with a suitable power of the base.

Computing and printing 1 million digits of Pi now takes 7 seconds on
king.  (With 4.1.2, it took 90 seconds.)

A side-effect of this new function is the new function
mpn_pow_1_highpart.  We should define and add several such _highpart
and _lowpart functions for the next major GMP release.  We might
actually want variants like _highpart_exact and _highpart_inexact.

Alternatively, we could call _lowpart something like _mod_2exp and
_highpart_exact something like _div_2exp, and let _highpart be an
inexact version.

("Inexact" should of course be well-defined, its inexactness meaning
that it might have an error of perhaps log(n)/2.  It could perhaps
return an error cap, allowing different implementations on a per
machine basis.  Or the caller could ask for an error cap.  This is
mainly relevant since some machines produce all product bits for a
multiply machine instructions, and other produce upper-part and
lower-part separately.)