GMP mpz_root() improvement
user42 at zip.com.au
Thu Jan 22 07:21:32 CET 2004
Ivo Moravec <imoravec at scg.math.uwaterloo.ca> writes:
> Halley Iterations (a third order) for computing integer nth roots.
I think I'd seen that (and higher order forms) at one time, but wasn't
smart enough to know if it would be an overall saving, since of course
each iteration does more work.
> Basically, I've written a replacement for
> your mpz_root() and mpn_rootrem() functions,
Good, fast, clean, well-tested code is always of interest.
> The new code runs about 10 to 30 or more times faster than the
> current implementation in gmp-4.1
The main problem with the current code, as noted in the projects file,
is that it uses full precision at every step.
A comparison with sqrt might be more indicative.
More information about the gmp-devel