Anomaly in mpn_sqrtrem and mpn_rootrem

[Torbjörn Granlund]

bodrato at mail.dm.unipi.it writes:

  https://gmplib.org/repo/gmp/rev/87ba695c8878
  But I do not really like it. We alloc-copy-shift to add a dummy limb, then
  we call a code that allocs-copies-shifts to (virtually) add two more dummy
  limbs...
  
There is still a very noticeable difference between even and odd sizes:

             mpn_sqrt    mpn_root.2   mpn_sqrtrem
4090      #1701239.98    2159255.23    2270148.03
4091      #1717724.10    2161403.54    2314530.39
4092      #1677835.05    2156978.06    2263015.48
4093      #1713743.03    2164690.06    2306523.04
4094      #1689689.17    2192785.72    2302479.92
4095      #1733267.80    2193850.69    2301651.07
4096      #1702328.08    2193558.18    2254053.40
4097      #1742066.35    2267900.34    2321820.79
4098      #1699858.76    2186774.59    2269899.77
4099      #1734269.70    2195714.07    2331587.32
4100      #1712964.01    2195057.78    2293181.09

  Now, for small sizes, computing the 4th root with mpn_rootrem is slower
  than calling mpn_sqrtrem twice. Maybe we should improve mpn_rootrem for
  small sizes in general...
  
Indeed.  We start with a single-bit approximation, then initially make
very little progress in the first steps (one bit for higher-order
roots).

Tabling start values is hard, but we should consider doing it for k <
some limit, and perhaps provide just 4 bits.

Another great speedup would be to use special code for the single-limb
iterating.

-- 
Torbjörn
Please encrypt, key id 0xC8601622