Ciao, On Tue, July 14, 2015 11:48 am, bodr...@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/ _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel