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