sec_invert performance

[Niels Möller]

I'm confused by the pretty bad performance of sec_invert. Try e.g.,

  ./tune/speed -s 1-200 -P invert mpn_gcdext mpn_sec_invert mpz_powm_sec

Say we have inputs of n bits. Then my understadning of these algorithms
is:

* mpn_gcdext, for sizes of interest, is Lehmer's algorithm, O(n^2), with
  a reasonably small constant since it reduces roughly one limb per
  iteration.

* mpn_sec_powm does n squarings + redc (and then some n/window_size
  multiplies and table lookups). And the squarings and redc are O(n^2),
  so total running time should be O(n^3).

* mpn_sec_invert has a loop of 2n iterations. Each iterations makes 9
  calls to various O(n) functions, like mpn_cnd_add_n, mpn_rshift, etc.
  So it ought to be O(n^2), and a constant factor slower than
  mpn_gcdext.

But when I run speed, *both* ratios mpn_invert / mpn_gcdext and
mpz_sec_powm / mpn_gcdext keep growing with n. So mpn_invert is not a
constant factor slower than mpn_gcdext, as I would have expected, and
it's significantly slower than mpn_sec_powm for largish sizes like 100
limbs. So it looks like it's O(n^3), not O(n^2).

Any idea what's going on? 

And then, there's also a sharp step at n = 113 or 114 (maybe that's an
artifact of the testmachine, but it's reproducible here).

$ ./speed -s 100-120  -c -r mpn_gcdext mpn_sec_invert mpz_powm_sec 
overhead 5.42 cycles, precision 10000 units of 6.25e-10 secs, CPU freq 1600.00 MHz
           mpn_gcdext mpn_sec_invert  mpz_powm_sec
100        #286753.00       97.9985       68.7822
101        #290981.00       96.3812       69.3512
102        #297710.00       94.5395       68.9482
103        #301772.00       94.9747       69.6444
104        #308297.00       94.8706       69.0619
105        #310131.00       96.1709       70.7960
106        #312842.00       96.6907       70.8039
107        #321814.00       96.2753       70.4176
108        #313583.00      100.2901       73.2001
109        #321223.00      100.3469       72.9247
110        #328283.00       99.1086       72.5408
111        #333812.00       99.4312       72.9408
112        #335619.00      100.7185       73.4388
113        #343734.00       46.7804       73.1944
114        #352574.00       46.8327       72.9897
115        #356299.00       46.9179       73.3826
116        #366523.00       46.0239       72.2455
117        #371422.00       46.5541       72.7283
118        #367404.00       50.3468       74.7026
119        #374872.00       48.6011       74.7945
120        #376131.00       48.3491       75.4658

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.