speed of unbalanced multiplication

[Zimmermann Paul]

       Hi,

in GMP 5.1.0, a multiplication of n x m limbs for m < n can be slower than
a multiplication of n x n limbs. Compare for example the line starting with
775660 in the first output from speed, and the one starting with 1000000 in
the second one below.

frite% ./speed -s 500000-1000000 -f 1.05 mpn_mul.1000000 mpn_mul.1000000
overhead 0.000000002 secs, precision 10000 units of 3.33e-10 secs, CPU freq 3000.00 MHz
        mpn_mul.1000000 mpn_mul.1000000
500000    0.572035000  #0.556034000
525000    0.608038000  #0.604038000
551250    0.568035000  #0.564035000
578812   #0.672042000   0.680042000
607752   #0.708044000   0.708044000
638139   #0.676042000   0.684043000
670045   #0.676042000   0.676042000
703547   #0.688043000   0.692043000
738724   #0.728045000   0.728045000
775660   #0.740046000   0.744046000
814443   #0.720045000   0.724045000
855165   #0.732046000   0.736046000
897923    0.728046000  #0.720045000
942819    0.764048000  #0.748047000
989959    0.744047000  #0.732046000

frite% ./speed -s 1000000 mpn_mul_n mpn_mul_n
overhead 0.000000002 secs, precision 10000 units of 3.33e-10 secs, CPU freq 3000.00 MHz
            mpn_mul_n     mpn_mul_n
1000000    0.736046000  #0.728045000

This is quite embarrassing, especially when one optimizes an algorithm by
reducing the multiplications sizes, and the algorithm gets slower...

Paul