speed enhancement

[Paul Zimmermann]

       Torbjörn,

>   I realized that mpn_rootrem(2) with NULL 2nd argument is faster than
>   mpn_sqrtrem with NULL 2nd argument!
>   
>   Maybe mpn_sqrtrem can be improved in that case, or simply call mpn_rootrem(2)?
>   
> I wasn't aware of this!  Did you look into the reasons for this anomaly?
> Is it consistent over a large operand size range, including few-limb
> operands?  It it indeed is, I suppose we should just replace some
> current internal mpn_sqrtrem calls with mpn_rootrem calls.

the reason is simple: with remp=NULL mpn_rootrem computes an extra limb of
the k-th root, which in most cases is enough to deduce if the remainder is
zero or not (however it seems the code does not cover the corner case).

> I haven't looked at the code recently, but I suspect mpn_rootrem is
> cleverer about the intermediate values during the Newton iteration,
> allowing it to omit a correction step at the end?
> 
> In mpn_sqrtrem, instead of using a full multiply for the fonal
> adjustment, perhaps we could get away with a short multiply, or even
> just a O(n) column multiply?

yes, see my previous mail.

Paul