Anomaly in mpn_sqrtrem and mpn_rootrem

[bodrato at mail.dm.unipi.it]

Ciao,

Il Mer, 24 Giugno 2015 10:48 am, bodrato at mail.dm.unipi.it 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
divrem:
https://gmplib.org/devel/lcov/shell/var/tmp/lcov/gmp/mpn/divrem.c.gcov.html

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,
m

-- 
http://bodrato.it/toom-cook/