Anomaly in mpn_sqrtrem and mpn_rootrem

Marco Bodrato bodrato at mail.dm.unipi.it
Wed Aug 19 05:55:59 UTC 2015


Ciao,

On Tue, August 18, 2015 10:51 am, Torbjörn Granlund wrote:
> I miss some rootrem logs from ChangeLog.

Before the changes I just pushed, I simply reordered the steps in the loop
to shorten the first and the last iteration in the loop...

> How much speed difference is there now, for k = 4 vs sqrt(sqrt())?

             mpn_sqrt    mpn_root.4    mpn_root.8   mpn_root.16
1              #33.86        659.37        229.62        178.01
2             #112.47        916.25        789.81        273.80
4             #245.35       1350.10       1111.97       1117.45
8             #419.01       1934.60       1683.93       1570.81
16           #1015.91       2611.44       2558.12       2472.39
32           #1666.53       3837.72       3969.28       4031.27
64           #3305.67       6295.23       6160.25       6654.23

> Is the difference small enough that we could fix it by running the first
> few iterations using plain limb arithmetic?

I fear it is not.

-- 
http://bodrato.it/



More information about the gmp-devel mailing list