Anomaly in mpn_sqrtrem and mpn_rottrem
tg at gmplib.org
Mon Jun 8 10:17:44 UTC 2015
tg at gmplib.org (Torbjörn Granlund) writes:
For mpn_rootrem, i.e., a^(1/k), I suppose we could make the work take
O(M(log(a^(1/k)))) as opposed to the current O(M(log(a))), where M(n) is
the time for an n-bit multiply. We'd need to make use of
mpn_pow_1_highpart. This will be a lot of work.
Note that O(M(log(a^(1/k)))) = O(M(log(a)/k)), i.e., that we can speed
mpn_rootrem up by a factor k (at least for large k, and large a).
Perhaps this does not need to be super-hard:. An outline:
(1) make the computation with log2(a)/k bits + eps extra bits (an extra
limb would do at least if the limb are not too small), happily
(2) at the end do two final exponentiations, one truncating towards 0
and one rounding towards +oo. These, keeping just log2(a)/k + eps high
bits, should be at most 1 apart sort of.
Please encrypt, key id 0xC8601622
More information about the gmp-devel