Anomaly in mpn_sqrtrem and mpn_rottrem

[Niels Möller]

bodrato at mail.dm.unipi.it writes:

> The last functions called by mpn_sqrtrem when computing the root of a 2000
> limb operand are:
>
> mpn_divrem nn=500/dn=250 -> qn=250,rn=250
> mpn_sqr an=250 ^ 2 -> rn=500
> mpn_divrem nn=1000/dn=500 -> qn=500,rn=500
> mpn_sqr an=500 ^ 2 -> rn=1000
>
> Similarly, for mpn_rootrem:
>
> mpn_div_q nn=500/dn=251 -> qn=249
> mpn_sqr an=501 ^ 2 -> rn=1002
> mpn_div_q nn=1000/dn=501 -> qn=499
> mpn_sqr an=1000 ^ 2 -> rn=2000
>
> It uses div_q instead of divrem, but squares used by rootrem are doubled
> in size...

That explains why rootrem is a lot slower, right? Is that what needs
explaining?

> When we do not ask for the reminder mpn_rootrem (say mpn_root) skips the
> last squaring:

Which is where most of the slowdown was.

> probably div_q is faster than divrem.

It should be. And if there's an adjustment step anyway, maybe it would
be even better to use divappr? (speed seems to lack support for many of
the interesting division functions).

Regards,
/Niels

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