A perfect power, and then?

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> nisse at lysator.liu.se (Niels Möller) writes:
>
>   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]
>
> This is going to help for large enough k and small enough n...  Will
> that occur?

Maybe for the largest k values used in perfect_power_p?

> I suppose that in practice for both bsqrt and broot, we'll get a
> progression of limb sizes that is not optimial (except for root when
> n=2^t and for sqrt when n=2^t+1).

Assuming that the bitsize of the initial approximation is a power of two
(or more generally, a divisor of GMP_NUMB_BITS), and we want at least
one full limb of precision, I think the limb sizes for broot are
optimal.

> But for root is might be the case that iterations are much more
> expensive since they are something like O(f(n)log(k)) for computing
> a^(1/k) mod n.  Even improving an initial 4-bit approximation to say 20
> bits will be significant work.

Remember we can limit k for the current precision (if the current
iteration computes m bits, we need only the least signifivant m-1 bits
of k). For large k, this wil help the first few iterations.

> We don't want to go to 64 bits internally just because we don't know
> the actually needed precision.

For this case, it makes sense to have a broot_limb, with a precision
argument in bits.

> It might make more sense to have a coarser size in bsqrt, since its
> iteration to b bits of precision will be faster.

For the interface, maybe. Internally, I think we ought to count bits.

Regards,
/Niels

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