GMP mpz_root() improvement (fwd)

[Kevin Ryde]

Ivo Moravec <imoravec at scg.math.uwaterloo.ca> writes:
>
> So, when I send the code, where do I send it?

You can post here.

> The difference would really start
> to really appear with numbers many tens of thousands of bits and up.

In that case we'll probably be wanting the current newton style
improved first, then think about a higher algorithm.

> mpn_rootrem() calculates the residual of the root (a-x^n), which
> mpz_root() is very happy to throw away.  I have made 2 routines.  One
> which computes the residual, and one that doesn't.  The one that doesn't
> is about twice as quick as the one that does.  How willing would you be to
> adding a "mpn_root" function which would enable the mpz_root() function to
> run much faster?

Yep, we can have an mpn_root, or an option to mpn_rootrem (like a NULL
remp) telling it not to bother with the remainder, whichever is
cleaner.

> I played around using floating point numbers to get an inital estimate for
> use in the refinement.  It worked quite well since my machine is an Intel
> based processor which has hardware log and exp instructions.  It's my
> understanding that not all hardware does have them however.  What's your
> policy on this?

log and exp are out, in general, since they require libm.  If a
particular processor has reliable insns, and we can force the compiler
to generate them, they could be considered there as an optimization.

> I have a regular integer based guesstimator too,

That'd be the way to go first.