GMP mpz_root() improvement

Kevin Ryde user42 at
Thu Jan 22 07:21:32 CET 2004

Ivo Moravec <imoravec at> 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 mailing list