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,
though.
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).
Regards,
/Niels
--
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