speed enhancement

[Torbjorn Granlund]

Paul Zimmermann <Paul.Zimmermann at loria.fr> writes:

  I suggest to add mpn_sqrt and mpn_root to the "speed" program, to measure
  the mpn_sqrtrem and mpn_rootrem functions with NULL 2nd argument. Patch below.
  
Thanks!

  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.

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?

-- 
Torbjörn