A perfect power, and then?

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> For a prospective mpn_rootexact, I assume the time will decrease with k,
> given an n-bit input argument.  Right?

I think so. Not sure if it's going to be completely monotone, 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.

Right, if we have a 30-bit root, we need only 3 iterations (assuming we
use a starting approximation of 4 bits), rather than 4 for a full 64-bit
limb. And each iteration needs one potentially somewhat expensive
powlimb. So I think it may get a bit faster.

By the way, I wonder if there are some circumstanses when

  r <-- a^{1/k}  (mod 2^n)

is more effiently computed as

  k' <-- k^{-1} (mod 2^{n-1})  [binvert]
  r <-- a^{k'} (mod 2^n)       [powlo]

We get a typically cheaper newton iteration (for binvert), but a
typically much larger exponent for powlo. I doubt it's useful for large
n, since then k' is *much* larger than k. But maybe for some types of
small operands.

>   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.

Say that, at some point, we have n limbs of precision. Then one
iteration of kth root (k odd) gives us precisely 2n limbs. While one
iteration of bsqrt gives us 2n limbs minus one bit (or is it minus 2
bits? I don't remember now). To make use of the valid bits in that top
limb (rather than just discarding them and saying that we now have 2n-1
valid limbs, which is particularly bad for n == 1...), we need some
book-keeping in units of bits.

Regards,
/Niels

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