Anomaly in mpn_sqrtrem and mpn_rootrem

[Niels Möller]

bodrato at mail.dm.unipi.it writes:

>> Note that all the computations of the error/residual E is subject to a
>> lot of cancellation, so one can use mullo (for small sizes) or
>> wraparound arithmetic using mulmod_bnm1 for larger sizes.
>
> If we need both the sqrt of the high-half and the residual, we should
> directly use sqrtrem, don't we? 

Maybe, but it's not obvious. For simplicity, consider the case of
smallish numbers, so we use mullo rather than mulmod_bnm1 for the
cancellation. Then H (high half of the square root) depends only on the
high half of A, while the residual is computed from H and the low half
of A. So I see no obvious gain in computing the residual sooner.

> Once we compute a residual, correcting the
> "approximation" to obtain an "exact" result does not cost too much,
> right?

Exact for the current A input, yes. But one level up in the recursion,
where additional low limbs are used, it's no longer exact. Nothing is
very obvious here, but my gut feeling is that "exactness" isn't a very
useful property for the intermediate results based on truncated versions
of the top-level input. And it's best to defer the adjustment to
top-level.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.