gcdext, computing the biggest cofactor only [was: mpz reuse test takes too much time]

[Marco Bodrato]

Ciao,

Il Dom, 18 Dicembre 2016 6:00 pm, Marco Bodrato ha scritto:
> Another alternative is to zero-pad the smallest operand. The _documented_
> interface of mpn_gcdext allows this trick.

> A possible patch follows, it swaps back A and B if only the biggest
> cofactor is needed and zero pad the shortest operand. It works smoothly,
> but I did not test its impact on speed...

I pushed support for mpz_invert into tune/speed. But gaining or not
heavily depends on sizes:

[@shell ~/gmp-repo]$ tune/speed -s2-20000 -cf3 -p1000000 mpz_invert.-1
mpz_invert.-10 mpz_invert mpz_invert.10 mpz_invert.1
overhead 5.84 cycles, precision 1000000 units of 2.86e-10 secs, CPU freq
3500.06 MHz
     mpz_invert.-1 mpz_invert.-10 mpz_invert mpz_invert.10 mpz_invert.1
2          1524.39          n/a     #1518.50           n/a      1522.38
6          5021.01          n/a      3146.49           n/a     #1946.04
18        18531.14      8797.06     10083.48      11113.62     #2328.14
54       109251.90     81803.77     40258.52      15554.62     #3255.13
162      687961.50    644741.00    282852.50      30296.56     #6045.32
486     3953124.00   3884702.00   1618744.00      74521.64    #14269.19
1458   17832859.00  17755716.00   8272988.00     213988.80    #39827.93
4374   89611358.00  89362630.00  39388224.00     721864.50   #177316.71
13122 434822389.00 434784781.00 188403008.00    2024278.00   #518420.00

[@shell ~/gmp-repo]$ tune/speed.mygcdext -s2-20000 -cf3 -p1000000
mpz_invert.-1 mpz_invert.-10 mpz_invert mpz_invert.10 mpz_invert.1
overhead 5.84 cycles, precision 1000000 units of 2.86e-10 secs, CPU freq
3500.06 MHz
     mpz_invert.-1 mpz_invert.-10 mpz_invert mpz_invert.10 mpz_invert.1
2         #1523.55          n/a      1524.09           n/a      1526.81
6          4795.39          n/a      3137.65           n/a     #2091.84
18        17057.34      8771.64      9962.85      10850.25     #2665.12
54        98385.00     73186.00     41234.73      17559.27     #4182.19
162      611591.50    583680.50    304319.25      38175.66     #7522.62
486     3518115.00   3495012.00   1504933.00      60643.50    #20135.07
1458   15526382.00  15486173.00   8312573.00     205171.50    #95656.42
4374   79565185.00  79450405.00  45422279.00     628639.50   #294218.00
13122 397189334.00 397136460.00 235487793.00    1802649.00   #864902.50

Where mpz_invert computes the inverse mod m of an operand that is half the
size of m; with mpz_invert.-1 the size of the operand is one less than the
size of m; with mpz_invert.1 the size of the operand is 1.

Regards (and happy new year!),
m

-- 
http://bodrato.it/papers/