Torbjorn Granlund <t...@gmplib.org> writes: > ni...@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. _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org http://gmplib.org/mailman/listinfo/gmp-devel