Anomaly in mpn_sqrtrem and mpn_rootrem

[Marco Bodrato]

Ciao,

On Tue, July 14, 2015 11:48 am, bodrato at mail.dm.unipi.it wrote:

> estimate. The trick I suggest consists in adding some fractional digits of
> log2(n), by table lookup, then use log2(n)/k to estimate a few of the
> highest digits of n^(1/k), not just one.

With two 256-chars tables(too much?), it is possible to estimate 9 bits
(seldom the error is +2, previous code always used a single correction).

Before we started refining mpn_rootrem (changeset 16672:c86f4fc0aafe) the
timing (on shell.gmplib) was:
$tune/speed -cs 1-1024 -f3 mpn_root.3 mpn_root.32 mpn_root.332 mpn_root.3332
overhead 5.84 cycles, precision 100000000 units of 2.86e-10 secs, CPU freq
3500.08 MHz
           mpn_root.3   mpn_root.32  mpn_root.332 mpn_root.3332
1             2120.44        424.16         84.71        #84.70
3             2537.38       2255.13         86.57        #86.53
9             3556.60       4661.17        687.10        #99.87
27            4779.44       6667.10       7156.09       #151.71
81            8768.02      13230.91      31229.99      #6717.58
243          40720.39     #27991.11      72860.77      81112.17
729         135971.53    #112360.63     240474.62    1060633.50

The current repo gives:
           mpn_root.3   mpn_root.32  mpn_root.332 mpn_root.3332
1             1985.55        290.12        #27.20         27.21
3             2373.10       2015.57         27.21        #27.21
9             3359.58       4401.62        411.39        #27.21
27            4626.43       6317.53       6857.23        #27.21
81            8583.51      12816.22      30837.67      #5783.87
243          39055.19     #27236.95      71936.69      78244.04
729         134456.72    #111492.59     235518.65    1054410.50

The code I'm experimenting with, reduces timings for small results:
           mpn_root.3   mpn_root.32  mpn_root.332 mpn_root.3332
1              634.94        193.03        #28.22         28.25
3             1289.25        200.82        #28.17         28.18
9             1865.79       1341.31        384.23        #28.24
27            3411.88       3257.38        816.07        #28.24
81            7518.93       9572.27      18564.51      #1991.75
243          37723.17      24465.42      61376.28     #20745.56
729         133654.08    #108648.30     226299.89     768142.04

I'm still testing it, but I think I'll push it soon...

> Now, for small sizes, computing the 4th root with mpn_root is slower
> than calling mpn_sqrt twice.

Even with the new code, this is true on a wide range (up to 1000 limbs).
Should we write special code for k=4,8,16 that repeatedly calls mpn_sqrt?

Regards,
m

-- 
http://bodrato.it/