Anomaly in mpn_sqrtrem and mpn_rottrem

Torbjörn Granlund tg at gmplib.org
Tue Jun 9 17:49:40 UTC 2015


tg at gmplib.org (Torbjörn Granlund) writes:

  I am not sure that div_q vs divrem matters a whole lot for this usage
  (i.e., 2n/n sizes).

Apparently wrong.  The first column is n, division is 2n-limb by n-limb:

                  mpn_divrem      mpn_div_q    ratio
         5        0.00000009     0.00000011    1.17
         7        0.00000012     0.00000012    0.96
        10        0.00000014     0.00000019    1.37
        15        0.00000028     0.00000026    0.92
        22        0.00000056     0.00000051    0.89
        33        0.00000099     0.00000090    0.91
        49        0.00000215     0.00000155    0.72
        73        0.00000444     0.00000306    0.69
       109        0.00000882     0.00000627    0.71
       163        0.00001767     0.00001293    0.73
       244        0.00003385     0.00002616    0.77
       366        0.00006530     0.00005040    0.77
       549        0.00012581     0.00009459    0.75
       823        0.00023138     0.00018117    0.78
      1234        0.00042985     0.00033642    0.78
      1851        0.00075588     0.00062548    0.83
      2776        0.00135386     0.00107124    0.79
      4164        0.00218069     0.00180242    0.83
      6246        0.00375453     0.00300871    0.80
      9369        0.00598697     0.00467305    0.78
     14053        0.00964423     0.00763366    0.79
     21079        0.01540152     0.01290730    0.84
     31618        0.02312424     0.01959218    0.85
     47427        0.03907867     0.03238867    0.83
     71140        0.05960059     0.04984235    0.84
    106710        0.09717958     0.08378117    0.86
    160065        0.16891133     0.13625322    0.81
    240097        0.21165200     0.17596529    0.83
    360145        0.38509720     0.30841320    0.80
    540217        0.67585650     0.56755350    0.84
    810325        1.17571375     0.96697025    0.82

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


More information about the gmp-devel mailing list