Anomaly in mpn_sqrtrem and mpn_rootrem

bodrato at bodrato at
Fri Jul 3 04:48:00 UTC 2015


Il Mer, 24 Giugno 2015 10:48 am, bodrato at ha scritto:
> Il Mer, 10 Giugno 2015 9:54 pm, Niels Möller ha scritto:
>> And the divisions really ought to use divappr, rather than exact
>> truncating division.
> You are right, I did not try divappr yet. I'll do.

Using div_q (not computing remainder) instead of divrem gave a 10% speedup.
Using divappr instead of div_q we gain a barely measurable 1%.

Moreover we don't have an mpn_divappr_q interface, and different
implementations *_divappr_q give different approximations. I hope I
correctly understood the comments in the code ... I assumed the worst case
is a possible +4 error when using mu_divappr.

We gained another 1% (probably less) using tdiv_qr instead of divrem (in
the sqrtrem branch). This drastically reduced the test coverage for

About divrem, why do we allocate a copy for the reminder?
	rp = TMP_ALLOC_LIMBS (dn);
	mpn_tdiv_qr (q2p, rp, 0L, np, nn, dp, dn);
	MPN_COPY (np, rp, dn);	/* overwrite np area with remainder */
We can directly ask tdiv to overwrite np, can't we?
	mpn_tdiv_qr (q2p, np, 0L, np, nn, dp, dn);

Best regards,


More information about the gmp-devel mailing list