Anomaly in mpn_sqrtrem and mpn_rottrem

[Torbjörn Granlund]

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
truncating intermediates.

(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.

-- 
Torbjörn
Please encrypt, key id 0xC8601622