A perfect power, and then?

Niels Möller nisse at lysator.liu.se
Sun Oct 28 16:30:37 CET 2012

Torbjorn Granlund <tg at gmplib.org> writes:

> Do you have any interpretation of these numbers?

Nothing deep. It make sense that for small k (k'th root), it's a
constant factor slower than binvert. And for large k, time should grow
in the same way as powlo time grows with the bitsize of the exponent.

> It does make some sense to have a bit count argument here instead of a
> limb count argument.  The first few iterations will use limb precision,
> but perhaps the caller needs such small precision that only 3 or 4
> iterations are needed?

For k'th root (k odd >= 3), I don't think bit count argument is very
useful. One could consider a mpn_broot_limb (limb-sized input and output)
with a bit size argument. We have nothing analogous for binvert_limb,

bsqrt is different, there we need a bit count to keep track of precision
in the loop, so it makes sense to also use a bit count input. And then
we have the peculiarity that if the input is of size b bits, the output
is b-1 (since the top bit doesn't affect the square).


Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.

More information about the gmp-devel mailing list