GMP mpz_root() improvement (fwd)
user42 at zip.com.au
Tue Jan 27 09:56:11 CET 2004
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
> 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.
More information about the gmp-devel