A perfect power, and then?
Niels Möller
nisse at lysator.liu.se
Tue Oct 30 14:38:40 CET 2012
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.
More information about the gmp-devel
mailing list