# Sub-quadratic mpf conversion, mpn highpart, mpn lowpart

**Torbjorn Granlund
**
tege@swox.com

*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.)
--
Torbjörn