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 _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org http://gmplib.org/mailman/listinfo/gmp-devel