A perfect power, and then?
Torbjorn Granlund
tg at gmplib.org
Sun Oct 28 19:42:30 CET 2012
nisse at lysator.liu.se (Niels Möller) writes:
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.
For a prospective mpn_rootexact, I assume the time will decrease with k,
given an n-bit input argument. Right?
> 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.
if we consider the problem of identifying perfect powers, I'd expect
arguments of say, 30 bits to become faster if we can avoid a few initial
iterations in some broot function.
Do you disagree?
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).
I am afraid I don't appreciate the difference.
I pushed a few new function, somewhat immature in implementation and
interface. They are based on old mpn/generic/perfpow.c functions, but
with new names and slightly different parameters. They also don't mask
off results (neither in the loops, nor at the end); this will allow for
a non-bit size argument of future versions.
--
Torbjörn
More information about the gmp-devel
mailing list