Add FFT_TABLE3 tables for more machines.

9 files changed, 727 insertions, 133 deletions

diff --git a/mpn/alpha/ev6/gmp-mparam.h b/mpn/alpha/ev6/gmp-mparam.h
index 259f4cccc..e047f523d 100644
--- a/mpn/alpha/ev6/gmp-mparam.h
+++ b/mpn/alpha/ev6/gmp-mparam.h
@@ -61,13 +61,91 @@ along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
 #define MULMOD_BNM1_THRESHOLD               20
 #define SQRMOD_BNM1_THRESHOLD               23
 
-#define MUL_FFT_TABLE  { 368, 864, 1984, 3840, 9216, 20480, 81920, 327680, 0 }
-#define MUL_FFT_MODF_THRESHOLD             464
-#define MUL_FFT_THRESHOLD                 7808
-
-#define SQR_FFT_TABLE  { 432, 864, 1856, 4864, 9216, 20480, 81920, 327680, 0 }
-#define SQR_FFT_MODF_THRESHOLD             408
-#define SQR_FFT_THRESHOLD                 4736
+#define MUL_FFT_MODF_THRESHOLD             480  /* k = 5 */
+#define MUL_FFT_TABLE3                                      \
+  { {    480, 5}, {     18, 6}, {     10, 5}, {     21, 6}, \
+    {     11, 5}, {     23, 6}, {     12, 5}, {     25, 6}, \
+    {     19, 7}, {     10, 6}, {     25, 7}, {     13, 6}, \
+    {     27, 7}, {     14, 6}, {     29, 7}, {     25, 8}, \
+    {     13, 7}, {     29, 8}, {     15, 7}, {     32, 8}, \
+    {     17, 7}, {     35, 8}, {     19, 7}, {     39, 8}, \
+    {     29, 9}, {     15, 8}, {     37, 9}, {     19, 8}, \
+    {     41, 9}, {     23, 8}, {     51, 9}, {     27, 8}, \
+    {     55, 9}, {     31, 8}, {     63, 9}, {     35, 8}, \
+    {     71, 9}, {     39,10}, {     23, 9}, {     55,10}, \
+    {     31, 9}, {     67,10}, {     39, 9}, {     83,10}, \
+    {     47, 9}, {     99,10}, {     55,11}, {     31,10}, \
+    {     79,11}, {     47,10}, {    103,12}, {     31,11}, \
+    {     63,10}, {    135,11}, {     79,10}, {    167,11}, \
+    {     95,10}, {    191,11}, {    111,12}, {     63,11}, \
+    {    127,10}, {    255,11}, {    143,10}, {    287, 9}, \
+    {    575,11}, {    159,10}, {    319,12}, {     95,11}, \
+    {    191,10}, {    383,11}, {    207,13}, {     63,12}, \
+    {    127,11}, {    255,10}, {    511,11}, {    271,10}, \
+    {    543,11}, {    287,10}, {    575,12}, {    159,11}, \
+    {    319,10}, {    639,11}, {    351,10}, {    703,12}, \
+    {    191,11}, {    383,10}, {    767,11}, {    415,10}, \
+    {    831,11}, {    447,13}, {    127,12}, {    255,11}, \
+    {    543,12}, {    287,11}, {    575,10}, {   1151,12}, \
+    {    319,11}, {    639,12}, {    351,11}, {    703,13}, \
+    {    191,12}, {    383,11}, {    767,12}, {    415,11}, \
+    {    831,12}, {    447,11}, {    895,14}, {    127,13}, \
+    {    255,12}, {    543,11}, {   1087,12}, {    575,11}, \
+    {   1151,12}, {    607,13}, {    319,12}, {    671,11}, \
+    {   1343,12}, {    703,13}, {    383,12}, {    831,13}, \
+    {    447,12}, {    927,14}, {    255,13}, {    511,12}, \
+    {   1087,13}, {    575,12}, {   1151,13}, {    639,12}, \
+    {   1279,13}, {    703,12}, {   1407,14}, {    383,13}, \
+    {    767,15}, {    255,14}, {    511,13}, {   1215,14}, \
+    {    639,13}, {   1407,14}, {    767,13}, {   1663,14}, \
+    {    895,13}, {   1791,15}, {  32768,16}, {  65536,17}, \
+    { 131072,18}, { 262144,19}, { 524288,20}, {1048576,21}, \
+    {2097152,22}, {4194304,23}, {8388608,24} }
+#define MUL_FFT_TABLE3_SIZE 151
+#define MUL_FFT_THRESHOLD                 7552
+
+#define SQR_FFT_MODF_THRESHOLD             476  /* k = 5 */
+#define SQR_FFT_TABLE3                                      \
+  { {    476, 5}, {     19, 6}, {     10, 5}, {     23, 6}, \
+    {     12, 5}, {     25, 6}, {     27, 7}, {     14, 6}, \
+    {     29, 7}, {     28, 8}, {     15, 7}, {     31, 8}, \
+    {     29, 9}, {     15, 8}, {     35, 9}, {     19, 8}, \
+    {     41, 9}, {     23, 8}, {     49, 9}, {     27,10}, \
+    {     15, 9}, {     35, 8}, {     71, 9}, {     39,10}, \
+    {     23, 9}, {     51,11}, {     15,10}, {     31, 9}, \
+    {     67,10}, {     39, 9}, {     79,10}, {     47, 9}, \
+    {     95,10}, {     55,11}, {     31,10}, {     79,11}, \
+    {     47,10}, {    103,12}, {     31,11}, {     63,10}, \
+    {    135,11}, {     79,10}, {    159, 9}, {    319,11}, \
+    {     95,10}, {    191, 9}, {    383,11}, {    111,12}, \
+    {     63,11}, {    127,10}, {    255, 9}, {    511,10}, \
+    {    271,11}, {    143,10}, {    287, 9}, {    575,10}, \
+    {    303,11}, {    159,10}, {    319,12}, {     95,11}, \
+    {    191,10}, {    383, 9}, {    767,13}, {     63,12}, \
+    {    127,11}, {    255,10}, {    511,11}, {    271,10}, \
+    {    543,11}, {    287,10}, {    575,11}, {    303,12}, \
+    {    159,11}, {    319,10}, {    639,11}, {    335,10}, \
+    {    671,11}, {    351,10}, {    703,11}, {    367,10}, \
+    {    735,12}, {    191,11}, {    383,10}, {    767,11}, \
+    {    415,10}, {    831,11}, {    447,10}, {    895,13}, \
+    {    127,12}, {    255,11}, {    543,12}, {    287,11}, \
+    {    575,10}, {   1151,11}, {    607,12}, {    319,11}, \
+    {    671,12}, {    351,11}, {    735,13}, {    191,12}, \
+    {    383,11}, {    767,12}, {    415,11}, {    831,12}, \
+    {    447,11}, {    895,12}, {    479,14}, {    127,13}, \
+    {    255,12}, {    575,11}, {   1151,12}, {    607,13}, \
+    {    319,12}, {    735,13}, {    383,12}, {    831,13}, \
+    {    447,12}, {    959,14}, {    255,13}, {    511,12}, \
+    {   1023,13}, {    575,12}, {   1215,13}, {    639,12}, \
+    {   1279,13}, {    703,12}, {   1407,14}, {    383,13}, \
+    {    767,12}, {   1535,13}, {    831,12}, {   1663,13}, \
+    {    895,12}, {   1791,15}, {    255,14}, {    511,13}, \
+    {   1215,14}, {    639,13}, {   1407,14}, {    767,13}, \
+    {   1663,14}, {    895,13}, {   1791,15}, {  32768,16}, \
+    {  65536,17}, { 131072,18}, { 262144,19}, { 524288,20}, \
+    {1048576,21}, {2097152,22}, {4194304,23}, {8388608,24} }
+#define SQR_FFT_TABLE3_SIZE 152
+#define SQR_FFT_THRESHOLD                 5248
 
 #define MULLO_BASECASE_THRESHOLD             0  /* always */
 #define MULLO_DC_THRESHOLD                 130
@@ -101,7 +179,3 @@ along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
 #define GET_STR_PRECOMPUTE_THRESHOLD        19
 #define SET_STR_DC_THRESHOLD              3754
 #define SET_STR_PRECOMPUTE_THRESHOLD      8097
-
-#define MUL_FFT_TABLE2 {{1,4}, {273,5}, {609,6}, {1729,7}, {4097,8}, {8961,9}, {11777,8}, {12545,9}, {13825,10}, {15361,9}, {19969,10}, {23553,9}, {26113,10}, {31745,9}, {35841,10}, {39937,9}, {42497,10}, {48129,9}, {50689,10}, {56321,11}, {63489,10}, {80897,11}, {96257,10}, {105473,12}, {126977,11}, {129025,10}, {143361,11}, {161793,10}, {171009,11}, {227329,12}, {258049,11}, {292865,10}, {310273,11}, {326657,12}, {389121,11}, {391169,10}, {394241,11}, {397313,10}, {408577,11}, {423937,13}, {516097,12}, {520193,11}, {620545,12}, {651265,11}, {751617,12}, {782337,11}, {915457,13}, {1040385,12}, {1044481,11}, {1112065,12}, {1175553,11}, {1243137,12}, {1306625,11}, {1374209,12}, {1437697,11}, {1439745,13}, {1564673,12}, {1568769,11}, {1636353,12}, {1961985,14}, {MP_SIZE_T_MAX, 0}}
-
-#define SQR_FFT_TABLE2 {{1,4}, {305,5}, {801,6}, {1729,7}, {3713,8}, {3841,7}, {4097,8}, {10497,9}, {11777,8}, {12545,9}, {20481,10}, {23553,9}, {26113,11}, {30721,10}, {31745,9}, {34305,10}, {48641,9}, {50177,10}, {56321,11}, {63489,10}, {80897,11}, {96257,10}, {105473,12}, {126977,11}, {129025,10}, {140289,11}, {227329,12}, {258049,11}, {260097,10}, {261121,11}, {266241,10}, {275457,11}, {292865,10}, {310785,11}, {325633,10}, {326657,12}, {389121,11}, {391169,10}, {408577,11}, {409601,13}, {516097,12}, {520193,11}, {621569,12}, {651265,11}, {751617,12}, {913409,13}, {1040385,12}, {1044481,11}, {1112065,12}, {1175553,11}, {1243137,12}, {1306625,11}, {1374209,12}, {1384449,11}, {1388545,12}, {1425409,11}, {1429505,12}, {1437697,11}, {1505281,13}, {1564673,12}, {1568769,11}, {1636353,12}, {1961985,14}, {MP_SIZE_T_MAX, 0}}
diff --git a/mpn/pa32/hppa2_0/gmp-mparam.h b/mpn/pa32/hppa2_0/gmp-mparam.h
index f0bda14a2..44543c748 100644
--- a/mpn/pa32/hppa2_0/gmp-mparam.h
+++ b/mpn/pa32/hppa2_0/gmp-mparam.h
@@ -23,8 +23,6 @@ along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
 
 /* 552 MHz PA8600 (gcc61.fsffrance.org) */
 
-/* Generated by tuneup.c, 2009-11-29, gcc 4.2 */
-
 #define DIVREM_1_NORM_THRESHOLD              3
 #define DIVREM_1_UNNORM_THRESHOLD            4
 #define MOD_1_NORM_THRESHOLD                 3
@@ -60,17 +58,74 @@ along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
 #define MULMOD_BNM1_THRESHOLD               13
 #define SQRMOD_BNM1_THRESHOLD               15
 
-#define MUL_FFT_TABLE  { 304, 672, 896, 2560, 10240, 24576, 98304, 0 }
-#define MUL_FFT_MODF_THRESHOLD             296
+#define MUL_FFT_MODF_THRESHOLD             244  /* k = 5 */
+#define MUL_FFT_TABLE3                                      \
+  { {    244, 5}, {      8, 4}, {     17, 5}, {     13, 6}, \
+    {      7, 5}, {     17, 6}, {      9, 5}, {     19, 6}, \
+    {     13, 7}, {      7, 6}, {     17, 7}, {      9, 6}, \
+    {     19, 7}, {     11, 6}, {     24, 7}, {     13, 8}, \
+    {      7, 7}, {     19, 8}, {     11, 7}, {     25, 8}, \
+    {     15, 7}, {     33, 8}, {     23, 9}, {     15, 8}, \
+    {     39, 9}, {     23,10}, {     15, 9}, {     31, 8}, \
+    {     67, 9}, {     39, 8}, {     79, 9}, {     47,10}, \
+    {     31, 9}, {     71, 8}, {    143, 9}, {     79,10}, \
+    {     47,11}, {     31,10}, {     63, 9}, {    127, 8}, \
+    {    255, 9}, {    135, 8}, {    271, 9}, {    143,10}, \
+    {     79, 9}, {    159, 8}, {    319, 9}, {    175, 8}, \
+    {    351,10}, {     95, 9}, {    191, 8}, {    383, 9}, \
+    {    207,11}, {     63,10}, {    127, 9}, {    255, 8}, \
+    {    511, 9}, {    271,10}, {    143, 9}, {    287, 8}, \
+    {    575,10}, {    159, 9}, {    319,10}, {    175, 9}, \
+    {    351,11}, {     95,10}, {    191, 9}, {    383,10}, \
+    {    207, 9}, {    415,12}, {     63,11}, {    127,10}, \
+    {    255, 9}, {    511,10}, {    271, 9}, {    543, 8}, \
+    {   1087,10}, {    287, 9}, {    575,10}, {    303,11}, \
+    {    159,10}, {    351, 9}, {    703, 8}, {   1407,11}, \
+    {    191,10}, {    415, 9}, {    831,11}, {    223, 9}, \
+    {    895,10}, {    479,12}, {    127,11}, {    255,10}, \
+    {    543, 9}, {   1087,11}, {    287,10}, {    607, 9}, \
+    {   1215,11}, {    351,10}, {    703, 9}, {   1407,12}, \
+    {    191,11}, {    415,10}, {    831,11}, {    479,13}, \
+    {   8192,14}, {  16384,15}, {  32768,16} }
+#define MUL_FFT_TABLE3_SIZE 107
 #define MUL_FFT_THRESHOLD                 2112
 
-#define SQR_FFT_TABLE  { 304, 672, 1152, 2560, 6144, 24576, 98304, 0 }
-#define SQR_FFT_MODF_THRESHOLD             232
-#define SQR_FFT_THRESHOLD                 1728
+#define SQR_FFT_MODF_THRESHOLD             240  /* k = 5 */
+#define SQR_FFT_TABLE3                                      \
+  { {    240, 5}, {      8, 4}, {     17, 5}, {     19, 6}, \
+    {     17, 7}, {      9, 6}, {     20, 7}, {     11, 6}, \
+    {     23, 7}, {     13, 8}, {      7, 7}, {     19, 8}, \
+    {     11, 7}, {     25, 8}, {     15, 7}, {     33, 8}, \
+    {     19, 7}, {     39, 8}, {     23, 9}, {     15, 8}, \
+    {     39, 9}, {     23,10}, {     15, 9}, {     31, 8}, \
+    {     63, 9}, {     47,10}, {     31, 9}, {     63, 8}, \
+    {    127, 9}, {     71, 8}, {    143, 9}, {     79,10}, \
+    {     47,11}, {     31,10}, {     63, 9}, {    127, 8}, \
+    {    255, 7}, {    511, 9}, {    135, 8}, {    271, 9}, \
+    {    143,10}, {     79, 9}, {    159, 8}, {    319, 9}, \
+    {    175, 8}, {    351, 7}, {    703,10}, {     95, 9}, \
+    {    191, 8}, {    383, 9}, {    207,11}, {     63,10}, \
+    {    127, 9}, {    255, 8}, {    511, 9}, {    271,10}, \
+    {    143, 9}, {    287, 8}, {    575,10}, {    159, 9}, \
+    {    319,10}, {    175, 9}, {    351, 8}, {    703,11}, \
+    {     95,10}, {    191, 9}, {    383,10}, {    207, 9}, \
+    {    415,12}, {     63,11}, {    127,10}, {    255, 9}, \
+    {    511,10}, {    271, 9}, {    543, 8}, {   1087,10}, \
+    {    287, 9}, {    575,11}, {    159,10}, {    319, 9}, \
+    {    639,10}, {    351, 9}, {    703, 8}, {   1407,11}, \
+    {    191,10}, {    415, 9}, {    831,11}, {    223, 8}, \
+    {   1791,10}, {    479, 9}, {    959,12}, {    127,11}, \
+    {    255,10}, {    543,11}, {    287,10}, {    607,11}, \
+    {    319,10}, {    639,11}, {    351,10}, {    703, 9}, \
+    {   1407,12}, {    191,11}, {    415,10}, {    831,11}, \
+    {    479,10}, {    959,13}, {   8192,14}, {  16384,15}, \
+    {  32768,16} }
+#define SQR_FFT_TABLE3_SIZE 109
+#define SQR_FFT_THRESHOLD                 1600
 
 #define MULLO_BASECASE_THRESHOLD             0  /* always */
 #define MULLO_DC_THRESHOLD                  90
-#define MULLO_MUL_N_THRESHOLD             3176
+#define MULLO_MUL_N_THRESHOLD             4167
 
 #define DC_DIV_QR_THRESHOLD                100
 #define DC_DIVAPPR_Q_THRESHOLD             342
diff --git a/mpn/powerpc32/gmp-mparam.h b/mpn/powerpc32/gmp-mparam.h
index f4239c77d..c1f25532b 100644
--- a/mpn/powerpc32/gmp-mparam.h
+++ b/mpn/powerpc32/gmp-mparam.h
@@ -66,12 +66,95 @@ along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
 #define MULMOD_BNM1_THRESHOLD                9
 #define SQRMOD_BNM1_THRESHOLD               14
 
-#define MUL_FFT_TABLE  { 304, 672, 896, 2560, 6144, 24576, 98304, 0 }
-#define MUL_FFT_MODF_THRESHOLD             320
+#define MUL_FFT_MODF_THRESHOLD             284  /* k = 5 */
+#define MUL_FFT_TABLE3                                      \
+  { {    284, 5}, {     17, 6}, {      9, 5}, {     19, 6}, \
+    {     13, 7}, {      7, 6}, {     17, 7}, {      9, 6}, \
+    {     20, 7}, {     11, 6}, {     23, 7}, {     13, 8}, \
+    {      7, 7}, {     19, 8}, {     11, 7}, {     25, 9}, \
+    {      7, 8}, {     15, 7}, {     33, 8}, {     19, 7}, \
+    {     39, 8}, {     23, 7}, {     47, 9}, {     15, 8}, \
+    {     39, 9}, {     23, 8}, {     47,10}, {     15, 9}, \
+    {     31, 8}, {     67, 9}, {     39, 8}, {     79, 9}, \
+    {     47, 8}, {     95,10}, {     31, 9}, {     71, 8}, \
+    {    143, 9}, {     79,10}, {     47, 9}, {     95,11}, \
+    {     31,10}, {     63, 9}, {    127, 8}, {    255, 9}, \
+    {    135, 8}, {    271, 9}, {    143,10}, {     79, 9}, \
+    {    159, 8}, {    319, 9}, {    175,10}, {     95, 9}, \
+    {    191, 8}, {    383, 9}, {    207, 8}, {    415,11}, \
+    {     63,10}, {    127, 9}, {    255, 8}, {    511, 9}, \
+    {    271,10}, {    143, 9}, {    287, 8}, {    575,10}, \
+    {    159, 9}, {    319,10}, {    175,11}, {     95,10}, \
+    {    191, 9}, {    383,10}, {    207, 9}, {    415, 8}, \
+    {    831,12}, {     63,11}, {    127,10}, {    255, 9}, \
+    {    511,10}, {    271, 9}, {    543, 8}, {   1087,10}, \
+    {    287, 9}, {    575,11}, {    159,10}, {    319, 9}, \
+    {    639,10}, {    351, 9}, {    703,11}, {    191,10}, \
+    {    415, 9}, {    831,11}, {    223,10}, {    447, 9}, \
+    {    895,10}, {    479, 9}, {    959,12}, {    127,11}, \
+    {    255,10}, {    543, 9}, {   1087,11}, {    287,10}, \
+    {    607,11}, {    319,10}, {    639,11}, {    351,10}, \
+    {    703, 9}, {   1407,12}, {    191,11}, {    383,10}, \
+    {    767,11}, {    415,10}, {    831,11}, {    447,10}, \
+    {    895,11}, {    479,10}, {    959,13}, {    127,12}, \
+    {    255,11}, {    543,10}, {   1087,11}, {    607,12}, \
+    {    319,11}, {    639,10}, {   1279,11}, {    703,10}, \
+    {   1407,12}, {    383,11}, {    831,12}, {    447,11}, \
+    {    959,10}, {   1919,13}, {    255,12}, {    511,11}, \
+    {   1087,12}, {    575,11}, {   1215,10}, {   2431,12}, \
+    {    639,11}, {   1279,12}, {    703,11}, {   1407,13}, \
+    {    383,12}, {    959,11}, {   1919,14}, {    255,13}, \
+    {    511,12}, {   1215,11}, {   2431,13}, {    639,12}, \
+    {   1471,13}, {    767,12}, {   1599,13}, {    895,12}, \
+    {   1919,14}, {    511,13}, {   1023,12}, {   2111,13}, \
+    {   1151,12}, {   2431,13}, {   1407,14}, {    767,13}, \
+    {   1535,12}, {   3071,13}, {   1919,12}, {   3839,15}, \
+    {  32768,16} }
+#define MUL_FFT_TABLE3_SIZE 165
 #define MUL_FFT_THRESHOLD                 3712
 
-#define SQR_FFT_TABLE  { 272, 672, 1152, 2560, 10240, 40960, 98304, 0 }
-#define SQR_FFT_MODF_THRESHOLD             288
+#define SQR_FFT_MODF_THRESHOLD             248  /* k = 5 */
+#define SQR_FFT_TABLE3                                      \
+  { {    248, 5}, {     17, 6}, {      9, 5}, {     19, 6}, \
+    {     17, 7}, {      9, 6}, {     20, 7}, {     11, 6}, \
+    {     23, 7}, {     13, 8}, {      7, 7}, {     19, 8}, \
+    {     11, 7}, {     25, 9}, {      7, 8}, {     15, 7}, \
+    {     33, 8}, {     19, 7}, {     39, 8}, {     23, 7}, \
+    {     47, 8}, {     27, 9}, {     15, 8}, {     39, 9}, \
+    {     23, 8}, {     47,10}, {     15, 9}, {     31, 8}, \
+    {     63, 9}, {     39, 8}, {     79, 9}, {     47,10}, \
+    {     31, 9}, {     63, 8}, {    127, 9}, {     71, 8}, \
+    {    143, 9}, {     79,10}, {     47, 9}, {     95,11}, \
+    {     31,10}, {     63, 9}, {    127, 8}, {    255, 7}, \
+    {    511, 9}, {    143,10}, {     79, 9}, {    159, 8}, \
+    {    319, 9}, {    175, 8}, {    351,10}, {     95, 9}, \
+    {    191, 8}, {    383, 9}, {    207, 8}, {    415,11}, \
+    {     63,10}, {    127, 9}, {    255, 8}, {    511,10}, \
+    {    143, 9}, {    287, 8}, {    575,10}, {    159, 9}, \
+    {    319,10}, {    175, 9}, {    351,11}, {     95,10}, \
+    {    191, 9}, {    383,10}, {    207, 9}, {    415, 8}, \
+    {    831,12}, {     63,11}, {    127,10}, {    255, 9}, \
+    {    511,10}, {    271, 9}, {    543,10}, {    287, 9}, \
+    {    575,11}, {    159,10}, {    319, 9}, {    639,10}, \
+    {    351, 9}, {    703, 8}, {   1407, 9}, {    735,11}, \
+    {    191,10}, {    415, 9}, {    831,11}, {    223,10}, \
+    {    447, 9}, {    895,10}, {    479,12}, {    127,11}, \
+    {    255,10}, {    543,11}, {    287,10}, {    607,11}, \
+    {    319,10}, {    639,11}, {    351,10}, {    703, 9}, \
+    {   1407,12}, {    191,11}, {    383,13}, {    127,12}, \
+    {    255,11}, {    543,10}, {   1087,11}, {    575,10}, \
+    {   1151,12}, {    319,11}, {    703,10}, {   1407,12}, \
+    {    383,11}, {    831,12}, {    447,11}, {    959,13}, \
+    {    255,12}, {    511,11}, {   1087,12}, {    575,11}, \
+    {   1215,12}, {    639,11}, {   1279,12}, {    703,11}, \
+    {   1407,13}, {    383,12}, {    959,14}, {    255,13}, \
+    {    511,12}, {   1215,11}, {   2431,13}, {    639,12}, \
+    {   1471,13}, {    767,12}, {   1599,13}, {    895,12}, \
+    {   1919,14}, {    511,13}, {   1023,12}, {   2111,13}, \
+    {   1151,12}, {   2431,13}, {   1407,12}, {   2815,14}, \
+    {    767,13}, {   1535,12}, {   3199,13}, {   1919,15}, \
+    {  32768,16} }
+#define SQR_FFT_TABLE3_SIZE 153
 #define SQR_FFT_THRESHOLD                 2688
 
 #define MULLO_BASECASE_THRESHOLD             0  /* always */
diff --git a/mpn/powerpc64/mode64/p5/gmp-mparam.h b/mpn/powerpc64/mode64/p5/gmp-mparam.h
index 0062f3287..1ed896814 100644
--- a/mpn/powerpc64/mode64/p5/gmp-mparam.h
+++ b/mpn/powerpc64/mode64/p5/gmp-mparam.h
@@ -55,17 +55,119 @@ along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
 #define MULMOD_BNM1_THRESHOLD               13
 #define SQRMOD_BNM1_THRESHOLD                9
 
-#define MUL_FFT_TABLE  { 336, 736, 1728, 2816, 7168, 20480, 81920, 196608, 0 }
-#define MUL_FFT_MODF_THRESHOLD             352
+#define MUL_FFT_MODF_THRESHOLD             348  /* k = 5 */
+#define MUL_FFT_TABLE3                                      \
+  { {    348, 5}, {     17, 6}, {      9, 5}, {     19, 6}, \
+    {     10, 5}, {     21, 6}, {     21, 7}, {     11, 6}, \
+    {     23, 7}, {     12, 6}, {     25, 7}, {     21, 8}, \
+    {     11, 7}, {     25, 8}, {     13, 7}, {     27, 8}, \
+    {     15, 7}, {     31, 8}, {     21, 9}, {     11, 8}, \
+    {     27, 9}, {     15, 8}, {     33, 9}, {     19, 8}, \
+    {     39, 9}, {     23, 8}, {     47, 9}, {     27,10}, \
+    {     15, 9}, {     39,10}, {     23, 9}, {     51,11}, \
+    {     15,10}, {     31, 9}, {     67,10}, {     39, 9}, \
+    {     79,10}, {     47, 9}, {     95,10}, {     55,11}, \
+    {     31,10}, {     79,11}, {     47,10}, {     95,12}, \
+    {     31,11}, {     63,10}, {    127, 9}, {    255,10}, \
+    {    135,11}, {     79,10}, {    159, 9}, {    319,11}, \
+    {     95,10}, {    191, 9}, {    383,12}, {     63,11}, \
+    {    127,10}, {    255, 9}, {    511,10}, {    271,11}, \
+    {    143,10}, {    287, 9}, {    575,10}, {    319,12}, \
+    {     95,11}, {    191,10}, {    383,13}, {     63,12}, \
+    {    127,11}, {    255,10}, {    511,11}, {    271,10}, \
+    {    543,11}, {    287,10}, {    575, 9}, {   1151,11}, \
+    {    319,10}, {    639,11}, {    351,10}, {    703,12}, \
+    {    191,11}, {    383,10}, {    767,11}, {    415,12}, \
+    {    223,11}, {    447,13}, {    127,12}, {    255,11}, \
+    {    511,10}, {   1023,11}, {    543,10}, {   1087,12}, \
+    {    287,11}, {    575,10}, {   1151,12}, {    319,11}, \
+    {    639,12}, {    351,11}, {    703,13}, {    191,12}, \
+    {    383,11}, {    767,12}, {    415,11}, {    831,12}, \
+    {    447,11}, {    895,14}, {    127,13}, {    255,12}, \
+    {    511,11}, {   1023,12}, {    543,11}, {   1087,10}, \
+    {   2175,12}, {    575,11}, {   1151,12}, {    607,13}, \
+    {    319,12}, {    639,11}, {   1279,12}, {    671,11}, \
+    {   1343,12}, {    703,11}, {   1407,13}, {    383,12}, \
+    {    767,11}, {   1535,12}, {    831,13}, {    447,12}, \
+    {    959,11}, {   1919,14}, {    255,13}, {    511,12}, \
+    {   1087,11}, {   2175,13}, {    575,12}, {   1215,11}, \
+    {   2431,10}, {   4863,13}, {    639,12}, {   1343,13}, \
+    {    703,12}, {   1407,14}, {    383,13}, {    767,12}, \
+    {   1535,13}, {    831,12}, {   1663,13}, {    959,12}, \
+    {   1919,11}, {   3839,15}, {    255,14}, {    511,13}, \
+    {   1087,12}, {   2175,13}, {   1215,12}, {   2431,11}, \
+    {   4863,14}, {    639,13}, {   1343,12}, {   2687,13}, \
+    {   1407,12}, {   2815,13}, {   1471,12}, {   2943,14}, \
+    {    767,13}, {   1599,12}, {   3199,13}, {   1663,14}, \
+    {    895,13}, {   1919,12}, {   3839,15}, {    511,14}, \
+    {   1023,13}, {   2175,14}, {   1151,13}, {   2431,12}, \
+    {   4863,14}, {   1279,13}, {   2687,14}, {   1407,13}, \
+    {   2943,15}, {    767,14}, {   1535,13}, {   3199,14}, \
+    {   1663,13}, {   3327,14}, {   1919,13}, {   3839,16}, \
+    {    511,15}, {   1023,14}, {   2431,13}, {   4863,15}, \
+    {   1279,14}, {   2943,12}, {  11775,15}, {   1535,14}, \
+    {   3327,15}, {   1791,14}, {  16384,15}, {  32768,16}, \
+    {  65536,17}, { 131072,18}, { 262144,19}, { 524288,20}, \
+    {1048576,21}, {2097152,22}, {4194304,23}, {8388608,24} }
+#define MUL_FFT_TABLE3_SIZE 208
 #define MUL_FFT_THRESHOLD                 3712
 
-#define SQR_FFT_TABLE  { 304, 608, 1472, 2816, 7168, 20480, 49152, 196608, 0 }
-#define SQR_FFT_MODF_THRESHOLD             320
+#define SQR_FFT_MODF_THRESHOLD             272  /* k = 5 */
+#define SQR_FFT_TABLE3                                      \
+  { {    272, 5}, {     15, 6}, {      8, 5}, {     17, 6}, \
+    {     19, 7}, {     17, 8}, {      9, 7}, {     21, 8}, \
+    {     11, 7}, {     24, 8}, {     13, 7}, {     27, 8}, \
+    {     15, 7}, {     31, 8}, {     21, 9}, {     11, 8}, \
+    {     27, 9}, {     15, 8}, {     33, 9}, {     19, 8}, \
+    {     39, 9}, {     23, 8}, {     47, 9}, {     27,10}, \
+    {     15, 9}, {     39,10}, {     23, 9}, {     47,11}, \
+    {     15,10}, {     31, 9}, {     63,10}, {     47,11}, \
+    {     31,10}, {     71, 9}, {    143,10}, {     79,11}, \
+    {     47,10}, {     95,12}, {     31,11}, {     63,10}, \
+    {    127, 9}, {    255, 8}, {    511, 9}, {    271,10}, \
+    {    143,11}, {     79,10}, {    159, 9}, {    319,10}, \
+    {    175, 9}, {    351,11}, {     95,10}, {    191, 9}, \
+    {    383,10}, {    207, 9}, {    415,12}, {     63,11}, \
+    {    127,10}, {    255, 9}, {    511,10}, {    271,11}, \
+    {    143,10}, {    287, 9}, {    575,11}, {    159,10}, \
+    {    319,11}, {    175,10}, {    351,12}, {     95,11}, \
+    {    191,10}, {    383,11}, {    207,10}, {    415,13}, \
+    {     63,12}, {    127,11}, {    255,10}, {    511,11}, \
+    {    271,10}, {    543,11}, {    287,10}, {    575,12}, \
+    {    159,11}, {    319,10}, {    639,11}, {    351,10}, \
+    {    703,12}, {    191,11}, {    383,10}, {    767,11}, \
+    {    415,12}, {    223,11}, {    447,10}, {    895,11}, \
+    {    479,10}, {    959,12}, {    255,11}, {    511,10}, \
+    {   1023,11}, {    543,12}, {    287,11}, {    575,12}, \
+    {    319,11}, {    639,12}, {    351,11}, {    703,13}, \
+    {    191,12}, {    383,11}, {    767,12}, {    415,11}, \
+    {    831,12}, {    447,11}, {    895,12}, {    479,11}, \
+    {    959,13}, {    255,12}, {    511,11}, {   1023,12}, \
+    {    543,11}, {   1087,12}, {    575,13}, {    319,12}, \
+    {    639,11}, {   1279,12}, {    703,11}, {   1407,13}, \
+    {    383,12}, {    831,13}, {    447,12}, {    959,14}, \
+    {    255,13}, {    511,12}, {   1087,13}, {    575,12}, \
+    {   1215,13}, {    639,12}, {   1279,13}, {    703,12}, \
+    {   1407,14}, {    383,13}, {    831,12}, {   1663,13}, \
+    {    959,12}, {   1919,15}, {    255,14}, {    511,13}, \
+    {   1023,12}, {   2047,13}, {   1087,12}, {   2175,13}, \
+    {   1215,14}, {    639,13}, {   1407,12}, {   2815,14}, \
+    {    767,13}, {   1663,14}, {    895,13}, {   1919,15}, \
+    {    511,14}, {   1023,13}, {   2175,14}, {   1151,13}, \
+    {   2431,12}, {   4863,14}, {   1407,13}, {   2815,15}, \
+    {    767,14}, {   1663,13}, {   3327,14}, {   1919,13}, \
+    {   3839,16}, {    511,15}, {   1023,14}, {   2431,13}, \
+    {   4863,15}, {   1279,14}, {   2943,13}, {   5887,12}, \
+    {  11775,15}, {   1535,14}, {   3327,15}, {   1791,14}, \
+    {  16384,15}, {  32768,16}, {  65536,17}, { 131072,18}, \
+    { 262144,19}, { 524288,20}, {1048576,21}, {2097152,22}, \
+    {4194304,23}, {8388608,24} }
+#define SQR_FFT_TABLE3_SIZE 190
 #define SQR_FFT_THRESHOLD                 2752
 
 #define MULLO_BASECASE_THRESHOLD             2
 #define MULLO_DC_THRESHOLD                  31
-#define MULLO_MUL_N_THRESHOLD             6633
+#define MULLO_MUL_N_THRESHOLD             7246
 
 #define DC_DIV_QR_THRESHOLD                 29
 #define DC_DIVAPPR_Q_THRESHOLD             102
@@ -93,5 +195,5 @@ along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
 
 #define GET_STR_DC_THRESHOLD                13
 #define GET_STR_PRECOMPUTE_THRESHOLD        23
-#define SET_STR_DC_THRESHOLD               532
+#define SET_STR_DC_THRESHOLD               632
 #define SET_STR_PRECOMPUTE_THRESHOLD      1790
diff --git a/mpn/x86/k6/gmp-mparam.h b/mpn/x86/k6/gmp-mparam.h
index 6a103b7e4..168ea065e 100644
--- a/mpn/x86/k6/gmp-mparam.h
+++ b/mpn/x86/k6/gmp-mparam.h
@@ -56,13 +56,70 @@ along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
 #define MULMOD_BNM1_THRESHOLD               13
 #define SQRMOD_BNM1_THRESHOLD               17
 
-#define MUL_FFT_TABLE  { 368, 672, 1152, 3584, 10240, 24576, 163840, 0 }
-#define MUL_FFT_MODF_THRESHOLD             624
-#define MUL_FFT_THRESHOLD                 7808
-
-#define SQR_FFT_TABLE  { 400, 672, 1408, 4608, 10240, 24576, 98304, 393216, 0 }
-#define SQR_FFT_MODF_THRESHOLD             528
-#define SQR_FFT_THRESHOLD                 9600
+#define MUL_FFT_MODF_THRESHOLD             476  /* k = 5 */
+#define MUL_FFT_TABLE3                                      \
+  { {    476, 5}, {     17, 6}, {      9, 5}, {     19, 6}, \
+    {     11, 5}, {     23, 6}, {     17, 7}, {      9, 6}, \
+    {     19, 7}, {     11, 6}, {     23, 7}, {     13, 6}, \
+    {     27, 7}, {     15, 6}, {     31, 7}, {     17, 6}, \
+    {     35, 7}, {     21, 8}, {     11, 7}, {     27, 8}, \
+    {     15, 7}, {     35, 8}, {     19, 7}, {     39, 8}, \
+    {     23, 7}, {     47, 8}, {     27, 9}, {     15, 8}, \
+    {     31, 7}, {     63, 8}, {     39, 9}, {     23, 8}, \
+    {     51,10}, {     15, 9}, {     31, 8}, {     67, 9}, \
+    {     47,10}, {     31, 9}, {     79,10}, {     47, 9}, \
+    {     95,11}, {     31,10}, {     63, 9}, {    135,10}, \
+    {     79, 9}, {    167,10}, {     95, 9}, {    191,10}, \
+    {    111,11}, {     63,10}, {    127, 9}, {    255,10}, \
+    {    143, 9}, {    287,10}, {    159,11}, {     95,10}, \
+    {    191, 9}, {    383,12}, {     63,11}, {    127,10}, \
+    {    255, 9}, {    511,10}, {    271, 9}, {    543,10}, \
+    {    287,11}, {    159,10}, {    351,11}, {    191,10}, \
+    {    415, 9}, {    831,11}, {    223,12}, {    127,11}, \
+    {    255,10}, {    543,11}, {    287,10}, {    575,11}, \
+    {    351,10}, {    703,12}, {    191,11}, {    415,10}, \
+    {    831,13}, {    127,12}, {    255,11}, {    543,10}, \
+    {   1087,11}, {    575,12}, {    319,11}, {    703,12}, \
+    {    383,11}, {    831,12}, {    447,11}, {    895,13}, \
+    {    255,12}, {    511,11}, {   1087,12}, {    575,11}, \
+    {   1151,12}, {    703,13}, {    383,12}, {    959,14}, \
+    {    255,13}, {    511,12}, {   1215,13}, {   8192,14}, \
+    {  16384,15}, {  32768,16} }
+#define MUL_FFT_TABLE3_SIZE 106
+#define MUL_FFT_THRESHOLD                 7424
+
+#define SQR_FFT_MODF_THRESHOLD             432  /* k = 5 */
+#define SQR_FFT_TABLE3                                      \
+  { {    432, 5}, {     17, 6}, {      9, 5}, {     19, 6}, \
+    {     11, 5}, {     23, 6}, {     21, 7}, {     11, 6}, \
+    {     24, 7}, {     13, 6}, {     27, 7}, {     15, 6}, \
+    {     31, 7}, {     21, 8}, {     11, 7}, {     29, 8}, \
+    {     15, 7}, {     35, 8}, {     19, 7}, {     39, 8}, \
+    {     23, 7}, {     49, 8}, {     27, 9}, {     15, 8}, \
+    {     39, 9}, {     23, 7}, {     93, 8}, {     47, 7}, \
+    {     95, 8}, {     51,10}, {     15, 9}, {     31, 8}, \
+    {     67, 9}, {     39, 8}, {     79, 9}, {     47, 8}, \
+    {     95, 9}, {     55,10}, {     31, 9}, {     71, 8}, \
+    {    143, 9}, {     79,10}, {     47, 9}, {     95,11}, \
+    {     31,10}, {     63, 9}, {    135,10}, {     79, 9}, \
+    {    167,10}, {     95, 9}, {    191,11}, {     63,10}, \
+    {    127, 9}, {    255,10}, {    143, 9}, {    287, 8}, \
+    {    575,10}, {    159, 9}, {    319,11}, {     95,10}, \
+    {    191,12}, {     63,11}, {    127,10}, {    255, 9}, \
+    {    511,10}, {    271, 9}, {    543,10}, {    287,11}, \
+    {    159,10}, {    319, 9}, {    639,10}, {    351, 9}, \
+    {    703,11}, {    191,10}, {    415,11}, {    223,12}, \
+    {    127,11}, {    255,10}, {    543,11}, {    287,10}, \
+    {    607,11}, {    319,10}, {    639,11}, {    351,10}, \
+    {    703,12}, {    191,11}, {    415,10}, {    831,13}, \
+    {    127,12}, {    255,11}, {    543,10}, {   1087,11}, \
+    {    607,12}, {    319,11}, {    703,12}, {    383,11}, \
+    {    831,12}, {    447,13}, {    255,12}, {    511,11}, \
+    {   1087,12}, {    575,11}, {   1215,12}, {    703,13}, \
+    {    383,12}, {    895,14}, {    255,13}, {    511,12}, \
+    {   1215,13}, {   8192,14}, {  16384,15}, {  32768,16} }
+#define SQR_FFT_TABLE3_SIZE 112
+#define SQR_FFT_THRESHOLD                 7040
 
 #define MULLO_BASECASE_THRESHOLD             3
 #define MULLO_DC_THRESHOLD                  60
diff --git a/mpn/x86/p6/sse2/gmp-mparam.h b/mpn/x86/p6/sse2/gmp-mparam.h
index 7fa81b97a..2e7eb838a 100644
--- a/mpn/x86/p6/sse2/gmp-mparam.h
+++ b/mpn/x86/p6/sse2/gmp-mparam.h
@@ -62,17 +62,89 @@ along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
 #define MULMOD_BNM1_THRESHOLD               13
 #define SQRMOD_BNM1_THRESHOLD               18
 
-#define MUL_FFT_TABLE  { 400, 928, 1664, 3584, 10240, 24576, 163840, 0 }
-#define MUL_FFT_MODF_THRESHOLD             720
-#define MUL_FFT_THRESHOLD                 7552
-
-#define SQR_FFT_TABLE  { 400, 928, 1664, 3584, 10240, 40960, 163840, 0 }
-#define SQR_FFT_MODF_THRESHOLD             592
+#define MUL_FFT_MODF_THRESHOLD             565  /* k = 5 */
+#define MUL_FFT_TABLE3                                      \
+  { {    565, 5}, {     25, 6}, {     13, 5}, {     27, 6}, \
+    {     25, 7}, {     13, 6}, {     28, 7}, {     15, 6}, \
+    {     31, 7}, {     17, 6}, {     35, 7}, {     27, 8}, \
+    {     15, 7}, {     35, 8}, {     19, 7}, {     41, 8}, \
+    {     23, 7}, {     47, 8}, {     27, 9}, {     15, 8}, \
+    {     31, 7}, {     63, 8}, {     39, 9}, {     23, 5}, \
+    {    383, 4}, {    991, 5}, {    511, 6}, {    267, 7}, \
+    {    157, 8}, {     91, 9}, {     47, 8}, {    111, 9}, \
+    {     63, 8}, {    127, 9}, {     79,10}, {     47, 9}, \
+    {     95,11}, {     31,10}, {     63, 9}, {    135,10}, \
+    {     79, 9}, {    159,10}, {     95,11}, {     63,10}, \
+    {    143, 9}, {    287,10}, {    159,11}, {     95,10}, \
+    {    191,12}, {     63,11}, {    127,10}, {    255, 9}, \
+    {    511,10}, {    271, 9}, {    543,10}, {    287,11}, \
+    {    159,10}, {    335, 9}, {    671,11}, {    191,10}, \
+    {    383, 9}, {    767,10}, {    399, 9}, {    799,10}, \
+    {    415,11}, {    223,12}, {    127,11}, {    255,10}, \
+    {    543, 9}, {   1087,11}, {    287,10}, {    607,11}, \
+    {    319,10}, {    671,12}, {    191,11}, {    383,10}, \
+    {    799,11}, {    415,10}, {    831,13}, {    127,12}, \
+    {    255,11}, {    543,10}, {   1087,11}, {    607,10}, \
+    {   1215,12}, {    319,11}, {    671,10}, {   1343,11}, \
+    {    735,10}, {   1471,12}, {    383,11}, {    799,10}, \
+    {   1599,11}, {    863,12}, {    447,11}, {    959,13}, \
+    {    255,12}, {    511,11}, {   1087,12}, {    575,11}, \
+    {   1215,12}, {    639,11}, {   1343,12}, {    703,11}, \
+    {   1471,13}, {    383,12}, {    831,11}, {   1727,12}, \
+    {    959,14}, {    255,13}, {    511,12}, {   1215,13}, \
+    {    639,12}, {   1471,11}, {   2943,13}, {    767,12}, \
+    {   1727,13}, {    895,12}, {   1919,14}, {    511,13}, \
+    {   1023,12}, {   2111,13}, {   1151,12}, {   2431,13}, \
+    {   1407,12}, {   2815,14}, {    767,13}, {   1663,12}, \
+    {   3455,13}, {   8192,14}, {  16384,15}, {  32768,16} }
+#define MUL_FFT_TABLE3_SIZE 132
+#define MUL_FFT_THRESHOLD                 6784
+
+#define SQR_FFT_MODF_THRESHOLD             472  /* k = 5 */
+#define SQR_FFT_TABLE3                                      \
+  { {    472, 5}, {     25, 6}, {     13, 5}, {     27, 6}, \
+    {     25, 7}, {     13, 6}, {     27, 7}, {     15, 6}, \
+    {     31, 7}, {     17, 6}, {     35, 7}, {     27, 8}, \
+    {     15, 7}, {     35, 8}, {     19, 7}, {     41, 8}, \
+    {     23, 7}, {     49, 8}, {     27, 9}, {     15, 8}, \
+    {     39, 9}, {     23, 8}, {     51,10}, {     15, 9}, \
+    {     31, 8}, {     63, 4}, {   1023, 8}, {     67, 9}, \
+    {     39, 5}, {    639, 4}, {   1471, 6}, {    383, 7}, \
+    {    209, 8}, {    119, 9}, {     63, 7}, {    255, 8}, \
+    {    139, 9}, {     71, 8}, {    143, 9}, {     79,10}, \
+    {     47, 9}, {     95,11}, {     31,10}, {     63, 9}, \
+    {    135,10}, {     79, 9}, {    159, 8}, {    319, 9}, \
+    {    167,10}, {     95,11}, {     63,10}, {    143, 9}, \
+    {    287,10}, {    159,11}, {     95,10}, {    191,12}, \
+    {     63,11}, {    127,10}, {    255, 9}, {    543, 8}, \
+    {   1087,10}, {    287, 9}, {    575,11}, {    159,10}, \
+    {    319, 9}, {    639,10}, {    335, 9}, {    671,10}, \
+    {    351, 9}, {    703,11}, {    191,10}, {    383, 9}, \
+    {    767,10}, {    399, 9}, {    799,10}, {    415, 9}, \
+    {    831,11}, {    223,12}, {    127,11}, {    255,10}, \
+    {    543, 9}, {   1087,11}, {    287,10}, {    607, 9}, \
+    {   1215,11}, {    319,10}, {    671, 9}, {   1343,11}, \
+    {    351,10}, {    703,12}, {    191,11}, {    383,10}, \
+    {    799,11}, {    415,10}, {    831,13}, {    127,12}, \
+    {    255,11}, {    543,10}, {   1087,11}, {    607,12}, \
+    {    319,11}, {    671,10}, {   1343,11}, {    735,12}, \
+    {    383,11}, {    799,10}, {   1599,11}, {    863,12}, \
+    {    447,11}, {    959,13}, {    255,12}, {    511,11}, \
+    {   1087,12}, {    575,11}, {   1215,12}, {    639,11}, \
+    {   1343,12}, {    703,11}, {   1471,13}, {    383,12}, \
+    {    767,11}, {   1599,12}, {    831,11}, {   1727,12}, \
+    {    959,14}, {    255,13}, {    511,12}, {   1215,13}, \
+    {    639,12}, {   1471,13}, {    767,12}, {   1727,13}, \
+    {    895,12}, {   1919,14}, {    511,13}, {   1023,12}, \
+    {   2111,13}, {   1151,12}, {   2431,13}, {   1407,14}, \
+    {    767,13}, {   1663,12}, {   3455,13}, {   8192,14}, \
+    {  16384,15}, {  32768,16} }
+#define SQR_FFT_TABLE3_SIZE 146
 #define SQR_FFT_THRESHOLD                 5760
 
 #define MULLO_BASECASE_THRESHOLD             0  /* always */
 #define MULLO_DC_THRESHOLD                  34
-#define MULLO_MUL_N_THRESHOLD            13463
+#define MULLO_MUL_N_THRESHOLD             8907
 
 #define DC_DIV_QR_THRESHOLD                 19
 #define DC_DIVAPPR_Q_THRESHOLD              56
@@ -102,7 +174,3 @@ along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
 #define GET_STR_PRECOMPUTE_THRESHOLD        22
 #define SET_STR_DC_THRESHOLD               587
 #define SET_STR_PRECOMPUTE_THRESHOLD       983
-
-#define MUL_FFT_TABLE2 {{1,4}, {337,5}, {801,6}, {1601,7}, {3457,8}, {3841,7}, {4481,8}, {4865,7}, {5249,8}, {6913,9}, {7681,8}, {9985,9}, {11777,8}, {13057,10}, {16897,8}, {22273,9}, {28417,10}, {30721,9}, {40961,10}, {48641,9}, {49153,11}, {63489,10}, {64513,9}, {72705,10}, {112641,11}, {129025,10}, {162817,11}, {194561,10}, {196609,12}, {258049,11}, {260097,10}, {278529,11}, {392705,9}, {395265,10}, {407553,11}, {452609,12}, {520193,11}, {522241,10}, {556545,11}, {587777,10}, {622081,11}, {653313,10}, {687105,12}, {782337,11}, {784385,10}, {818177,11}, {819201,13}, {1040385,12}, {1044481,11}, {1244161,12}, {1306625,11}, {1506305,12}, {1568769,11}, {1701889,10}, {1704961,12}, {1830913,11}, {1964033,13}, {2088961,12}, {2093057,11}, {2226177,12}, {2355201,11}, {2488321,12}, {2617345,11}, {2750465,12}, {2879489,11}, {3012609,13}, {3137537,12}, {3141633,11}, {3274753,12}, {3403777,11}, {3536897,12}, {3928065,14}, {MP_SIZE_T_MAX, 0}}
-
-#define SQR_FFT_TABLE2 {{1,4}, {337,5}, {801,6}, {1601,7}, {3457,8}, {3841,7}, {4481,8}, {4865,7}, {5249,8}, {5889,7}, {6273,8}, {6913,9}, {7681,8}, {9985,9}, {11777,8}, {13057,10}, {16641,8}, {17153,9}, {20993,7}, {25985,8}, {29697,9}, {40449,10}, {48129,9}, {49153,11}, {63489,10}, {64513,9}, {72705,10}, {97281,11}, {129025,10}, {162817,11}, {194561,10}, {195585,12}, {258049,11}, {260097,10}, {262145,9}, {264705,10}, {265729,9}, {267265,10}, {268289,9}, {269313,10}, {272897,9}, {278273,11}, {325633,10}, {359425,9}, {359937,11}, {391169,10}, {413697,11}, {456705,12}, {520193,11}, {522241,10}, {577537,11}, {581633,10}, {583681,11}, {585729,10}, {622081,11}, {653313,10}, {687617,11}, {718849,10}, {720897,12}, {782337,11}, {784385,10}, {818689,11}, {850945,13}, {1040385,12}, {1044481,11}, {1244161,12}, {1306625,11}, {1506305,12}, {1568769,11}, {1701889,10}, {1703937,12}, {1830913,11}, {1965057,13}, {2088961,12}, {2093057,11}, {2226177,12}, {2355201,11}, {2488321,12}, {2617345,11}, {2750465,12}, {2879489,11}, {3012609,13}, {3137537,12}, {3141633,11}, {3274753,12}, {3403777,11}, {3536897,12}, {3930113,14}, {MP_SIZE_T_MAX, 0}}
diff --git a/mpn/x86/pentium/mmx/gmp-mparam.h b/mpn/x86/pentium/mmx/gmp-mparam.h
index 2aa26ab65..958a32224 100644
--- a/mpn/x86/pentium/mmx/gmp-mparam.h
+++ b/mpn/x86/pentium/mmx/gmp-mparam.h
@@ -35,7 +35,7 @@ along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
 #define MOD_1U_TO_MOD_1_1_THRESHOLD         12
 #define MOD_1_1_TO_MOD_1_2_THRESHOLD         0
 #define MOD_1_2_TO_MOD_1_4_THRESHOLD        11
-#define PREINV_MOD_1_TO_MOD_1_THRESHOLD  MP_SIZE_T_MAX  /* never */
+#define PREINV_MOD_1_TO_MOD_1_THRESHOLD     63
 #define USE_PREINV_DIVREM_1                  0
 #define DIVEXACT_1_THRESHOLD                 0  /* always (native) */
 #define BMOD_1_TO_MOD_1_THRESHOLD           51
@@ -61,29 +61,78 @@ along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
 #define MULMOD_BNM1_THRESHOLD               11
 #define SQRMOD_BNM1_THRESHOLD               12
 
-#define MUL_FFT_TABLE  { 304, 672, 1152, 3584, 10240, 40960, 163840, 0 }
-#define MUL_FFT_MODF_THRESHOLD             368
-#define MUL_FFT_THRESHOLD                 4736
-
-#define SQR_FFT_TABLE  { 272, 672, 1152, 4608, 10240, 40960, 98304, 393216, 0 }
-#define SQR_FFT_MODF_THRESHOLD             288
+#define MUL_FFT_MODF_THRESHOLD             364  /* k = 5 */
+#define MUL_FFT_TABLE3                                      \
+  { {    364, 5}, {     15, 6}, {      8, 5}, {     17, 6}, \
+    {      9, 5}, {     19, 6}, {     17, 7}, {      9, 6}, \
+    {     21, 7}, {     11, 6}, {     23, 7}, {     15, 6}, \
+    {     31, 7}, {     21, 8}, {     11, 7}, {     27, 8}, \
+    {     15, 7}, {     33, 8}, {     19, 7}, {     39, 8}, \
+    {     23, 7}, {     47, 8}, {     27, 9}, {     15, 8}, \
+    {     31, 7}, {     63, 8}, {     39, 9}, {     23, 8}, \
+    {     47,10}, {     15, 9}, {     31, 8}, {     67, 9}, \
+    {     39, 8}, {     79, 9}, {     47, 8}, {     95, 9}, \
+    {     55,10}, {     31, 9}, {     79,10}, {     47, 9}, \
+    {     95,11}, {     31,10}, {     63, 9}, {    135,10}, \
+    {     79, 9}, {    159, 8}, {    319, 9}, {    167,10}, \
+    {     95, 9}, {    191, 8}, {    383,11}, {     63,10}, \
+    {    127, 9}, {    255,10}, {    143, 9}, {    287,10}, \
+    {    159, 9}, {    319,11}, {     95,10}, {    191, 9}, \
+    {    383,12}, {     63,11}, {    127,10}, {    271, 9}, \
+    {    543,10}, {    287,11}, {    159,10}, {    351,11}, \
+    {    191,10}, {    415,11}, {    223,12}, {    127,11}, \
+    {    255,10}, {    511,11}, {    287,10}, {    575,11}, \
+    {    351,12}, {    191,11}, {    415,13}, {    127,12}, \
+    {    255,11}, {    575,12}, {    319,11}, {    703,12}, \
+    {    383,11}, {    831,12}, {    447,13}, {   8192,14}, \
+    {  16384,15}, {  32768,16} }
+#define MUL_FFT_TABLE3_SIZE 90
+#define MUL_FFT_THRESHOLD                 3520
+
+#define SQR_FFT_MODF_THRESHOLD             340  /* k = 5 */
+#define SQR_FFT_TABLE3                                      \
+  { {    340, 5}, {     17, 6}, {      9, 5}, {     19, 6}, \
+    {     17, 7}, {      9, 6}, {     21, 7}, {     11, 6}, \
+    {     23, 7}, {     15, 6}, {     31, 7}, {     21, 8}, \
+    {     11, 7}, {     29, 8}, {     15, 7}, {     33, 8}, \
+    {     19, 7}, {     39, 8}, {     27, 7}, {     55, 9}, \
+    {     15, 8}, {     31, 7}, {     65, 8}, {     43, 9}, \
+    {     23, 8}, {     47,10}, {     15, 9}, {     31, 8}, \
+    {     67, 9}, {     39, 8}, {     83, 9}, {     47, 8}, \
+    {     95,10}, {     31, 9}, {     63, 8}, {    127, 9}, \
+    {     79,10}, {     47, 9}, {     95,11}, {     31,10}, \
+    {     63, 9}, {    127, 8}, {    255, 9}, {    135,10}, \
+    {     79, 9}, {    159, 8}, {    319,10}, {     95, 9}, \
+    {    191,11}, {     63,10}, {    127, 9}, {    255, 8}, \
+    {    511, 9}, {    271,10}, {    143, 9}, {    287, 8}, \
+    {    575, 9}, {    303,10}, {    159, 9}, {    319,11}, \
+    {     95,10}, {    191, 9}, {    383,10}, {    207,12}, \
+    {     63,11}, {    127,10}, {    271, 9}, {    543,10}, \
+    {    287, 9}, {    575,10}, {    303,11}, {    159,10}, \
+    {    351,11}, {    191,10}, {    415,11}, {    223,10}, \
+    {    447,12}, {    127,11}, {    255,10}, {    543,11}, \
+    {    287,10}, {    607,11}, {    351,12}, {    191,11}, \
+    {    479,13}, {    127,12}, {    255,11}, {    575,12}, \
+    {    319,11}, {    703,12}, {    383,11}, {    767,12}, \
+    {    447,13}, {   8192,14}, {  16384,15}, {  32768,16} }
+#define SQR_FFT_TABLE3_SIZE 96
 #define SQR_FFT_THRESHOLD                 5504
 
 #define MULLO_BASECASE_THRESHOLD             0  /* always */
-#define MULLO_DC_THRESHOLD                  45
-#define MULLO_MUL_N_THRESHOLD             9174
+#define MULLO_DC_THRESHOLD                  48
+#define MULLO_MUL_N_THRESHOLD             6633
 
 #define DC_DIV_QR_THRESHOLD                 43
 #define DC_DIVAPPR_Q_THRESHOLD             170
 #define DC_BDIV_QR_THRESHOLD                43
-#define DC_BDIV_Q_THRESHOLD                113
+#define DC_BDIV_Q_THRESHOLD                110
 
-#define INV_MULMOD_BNM1_THRESHOLD           54
-#define INV_NEWTON_THRESHOLD               179
-#define INV_APPR_THRESHOLD                 173
+#define INV_MULMOD_BNM1_THRESHOLD           30
+#define INV_NEWTON_THRESHOLD               177
+#define INV_APPR_THRESHOLD                 171
 
-#define BINV_NEWTON_THRESHOLD              197
-#define REDC_1_TO_REDC_N_THRESHOLD          47
+#define BINV_NEWTON_THRESHOLD              194
+#define REDC_1_TO_REDC_N_THRESHOLD          50
 
 #define MU_DIV_QR_THRESHOLD               1142
 #define MU_DIVAPPR_Q_THRESHOLD            1142
@@ -91,13 +140,13 @@ along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
 #define MU_BDIV_QR_THRESHOLD               942
 #define MU_BDIV_Q_THRESHOLD               1017
 
-#define MATRIX22_STRASSEN_THRESHOLD         12
-#define HGCD_THRESHOLD                      88
-#define GCD_DC_THRESHOLD                   293
-#define GCDEXT_DC_THRESHOLD                233
+#define MATRIX22_STRASSEN_THRESHOLD         13
+#define HGCD_THRESHOLD                      92
+#define GCD_DC_THRESHOLD                   283
+#define GCDEXT_DC_THRESHOLD                221
 #define JACOBI_BASE_METHOD                   2
 
-#define GET_STR_DC_THRESHOLD                14
-#define GET_STR_PRECOMPUTE_THRESHOLD        26
-#define SET_STR_DC_THRESHOLD               272
-#define SET_STR_PRECOMPUTE_THRESHOLD       920
+#define GET_STR_DC_THRESHOLD                18
+#define GET_STR_PRECOMPUTE_THRESHOLD        31
+#define SET_STR_DC_THRESHOLD               490
+#define SET_STR_PRECOMPUTE_THRESHOLD       994
diff --git a/mpn/x86_64/gmp-mparam.h b/mpn/x86_64/gmp-mparam.h
index 8ebc943fc..b412f30f5 100644
--- a/mpn/x86_64/gmp-mparam.h
+++ b/mpn/x86_64/gmp-mparam.h
@@ -187,11 +187,11 @@ along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
 
 #define MATRIX22_STRASSEN_THRESHOLD         17
 #define HGCD_THRESHOLD                     139
-#define GCD_DC_THRESHOLD                   555
-#define GCDEXT_DC_THRESHOLD                496
+#define GCD_DC_THRESHOLD                   501
+#define GCDEXT_DC_THRESHOLD                474
 #define JACOBI_BASE_METHOD                   1
 
-#define GET_STR_DC_THRESHOLD                 9
+#define GET_STR_DC_THRESHOLD                17
 #define GET_STR_PRECOMPUTE_THRESHOLD        23
-#define SET_STR_DC_THRESHOLD               248
+#define SET_STR_DC_THRESHOLD               266
 #define SET_STR_PRECOMPUTE_THRESHOLD      1648
diff --git a/mpn/x86_64/pentium4/gmp-mparam.h b/mpn/x86_64/pentium4/gmp-mparam.h
index 9196e35e1..461633013 100644
--- a/mpn/x86_64/pentium4/gmp-mparam.h
+++ b/mpn/x86_64/pentium4/gmp-mparam.h
@@ -31,81 +31,187 @@ along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
 #define MOD_1_NORM_THRESHOLD                 0  /* always */
 #define MOD_1_UNNORM_THRESHOLD               0  /* always */
 #define MOD_1N_TO_MOD_1_1_THRESHOLD          6
-#define MOD_1U_TO_MOD_1_1_THRESHOLD          4
-#define MOD_1_1_TO_MOD_1_2_THRESHOLD         8
-#define MOD_1_2_TO_MOD_1_4_THRESHOLD        20
-#define PREINV_MOD_1_TO_MOD_1_THRESHOLD     10
+#define MOD_1U_TO_MOD_1_1_THRESHOLD          5
+#define MOD_1_1_TO_MOD_1_2_THRESHOLD        10
+#define MOD_1_2_TO_MOD_1_4_THRESHOLD        34
+#define PREINV_MOD_1_TO_MOD_1_THRESHOLD     16
 #define USE_PREINV_DIVREM_1                  1  /* native */
 #define DIVEXACT_1_THRESHOLD                 0  /* always (native) */
-#define BMOD_1_TO_MOD_1_THRESHOLD           21
+#define BMOD_1_TO_MOD_1_THRESHOLD           24
 
-#define MUL_TOOM22_THRESHOLD                12
+#define MUL_TOOM22_THRESHOLD                14
 #define MUL_TOOM33_THRESHOLD                81
-#define MUL_TOOM44_THRESHOLD               130
-#define MUL_TOOM6H_THRESHOLD               197
-#define MUL_TOOM8H_THRESHOLD               482
+#define MUL_TOOM44_THRESHOLD               214
+#define MUL_TOOM6H_THRESHOLD               286
+#define MUL_TOOM8H_THRESHOLD               430
 
-#define MUL_TOOM32_TO_TOOM43_THRESHOLD      89
-#define MUL_TOOM32_TO_TOOM53_THRESHOLD     154
-#define MUL_TOOM42_TO_TOOM53_THRESHOLD      94
-#define MUL_TOOM42_TO_TOOM63_THRESHOLD      96
+#define MUL_TOOM32_TO_TOOM43_THRESHOLD      81
+#define MUL_TOOM32_TO_TOOM53_THRESHOLD     138
+#define MUL_TOOM42_TO_TOOM53_THRESHOLD      82
+#define MUL_TOOM42_TO_TOOM63_THRESHOLD      80
 
 #define SQR_BASECASE_THRESHOLD               0  /* always (native) */
-#define SQR_TOOM2_THRESHOLD                 22
-#define SQR_TOOM3_THRESHOLD                 89
-#define SQR_TOOM4_THRESHOLD                244
-#define SQR_TOOM6_THRESHOLD                318
-#define SQR_TOOM8_THRESHOLD                502
+#define SQR_TOOM2_THRESHOLD                 20
+#define SQR_TOOM3_THRESHOLD                 81
+#define SQR_TOOM4_THRESHOLD                226
+#define SQR_TOOM6_THRESHOLD                303
+#define SQR_TOOM8_THRESHOLD                454
 
 #define MULMOD_BNM1_THRESHOLD                9
-#define SQRMOD_BNM1_THRESHOLD               13
-
-#define MUL_FFT_TABLE  { 240, 544, 1600, 2816, 7168, 20480, 49152, 327680, 0 }
-#define MUL_FFT_MODF_THRESHOLD             272
-#define MUL_FFT_THRESHOLD                 4864
-
-#define SQR_FFT_TABLE  { 272, 544, 1600, 2816, 7168, 20480, 49152, 196608, 0 }
-#define SQR_FFT_MODF_THRESHOLD             272
-#define SQR_FFT_THRESHOLD                 4224
+#define SQRMOD_BNM1_THRESHOLD               11
+
+
+#define MUL_FFT_MODF_THRESHOLD             240  /* k = 5 */
+#define MUL_FFT_TABLE3                                      \
+  { {    240, 5}, {      9, 4}, {     19, 5}, {     11, 6}, \
+    {      6, 5}, {     13, 6}, {      7, 5}, {     15, 6}, \
+    {      8, 5}, {     17, 6}, {      9, 5}, {     19, 6}, \
+    {     13, 7}, {      7, 6}, {     15, 7}, {      8, 6}, \
+    {     17, 7}, {      9, 6}, {     19, 7}, {     11, 6}, \
+    {     23, 7}, {     13, 8}, {      7, 7}, {     17, 8}, \
+    {      9, 7}, {     21, 8}, {     11, 7}, {     23, 8}, \
+    {     13, 9}, {      7, 8}, {     15, 7}, {     31, 8}, \
+    {     21, 9}, {     11, 8}, {     25,10}, {      7, 9}, \
+    {     15, 8}, {     33, 9}, {     19, 8}, {     39, 9}, \
+    {     23, 8}, {     47, 9}, {     27,10}, {     15, 9}, \
+    {     39,10}, {     23, 9}, {     51,11}, {     15,10}, \
+    {     31, 9}, {     63,10}, {     39, 9}, {     79,10}, \
+    {     47,11}, {     31,10}, {     63, 9}, {    127, 8}, \
+    {    255,10}, {     79, 9}, {    159,11}, {     47,10}, \
+    {     95,12}, {     31,11}, {     63,10}, {    127, 9}, \
+    {    287,11}, {     79,10}, {    159, 9}, {    319,10}, \
+    {    175,11}, {     95,10}, {    191, 9}, {    383,10}, \
+    {    207, 9}, {    415,11}, {    111,10}, {    223,12}, \
+    {     63,11}, {    127,10}, {    255,11}, {    143,10}, \
+    {    287,11}, {    159,10}, {    319,11}, {    175,12}, \
+    {     95,11}, {    223,13}, {     63,12}, {    127,11}, \
+    {    287,10}, {    575,12}, {    159,11}, {    319,10}, \
+    {    639,11}, {    351,12}, {    191,11}, {    383,12}, \
+    {    223,11}, {    447,13}, {    127,12}, {    255,11}, \
+    {    511,12}, {    287,11}, {    575,12}, {    319,11}, \
+    {    639,12}, {    351,13}, {    191,12}, {    415,11}, \
+    {    831,12}, {    447,14}, {    127,13}, {    255,12}, \
+    {    511,11}, {   1023,12}, {    543,11}, {   1087,10}, \
+    {   2175,12}, {    575,13}, {    319,12}, {    639,11}, \
+    {   1279,12}, {    703,11}, {   1407,13}, {    383,12}, \
+    {    767,11}, {   1535,12}, {    831,11}, {   1663,13}, \
+    {    447,14}, {    255,13}, {    511,12}, {   1023,11}, \
+    {   2047,12}, {   1087,11}, {   2175,13}, {    575,12}, \
+    {   1151,11}, {   2303,12}, {   1215,11}, {   2431,10}, \
+    {   4863,13}, {    639,12}, {   1279,11}, {   2559,13}, \
+    {    703,12}, {   1407,14}, {    383,13}, {    767,12}, \
+    {   1535,13}, {    831,12}, {   1663,13}, {    895,15}, \
+    {    255,14}, {    511,13}, {   1023,12}, {   2047,13}, \
+    {   1087,12}, {   2175,13}, {   1215,12}, {   2431,11}, \
+    {   4863,14}, {    639,13}, {   1407,12}, {   2815,13}, \
+    {   1471,14}, {    767,13}, {   1663,14}, {    895,13}, \
+    {   1791,12}, {   3583,13}, {   1919,12}, {   3839,15}, \
+    {    511,14}, {   1023,13}, {   2175,14}, {   1151,13}, \
+    {   2303,12}, {   4607,13}, {   2431,12}, {   4863,14}, \
+    {   1279,13}, {   2687,14}, {   1407,13}, {   2815,15}, \
+    {    767,14}, {   1791,13}, {   3583,14}, {   1919,13}, \
+    {   3839,12}, {   7679,16}, {    511,15}, {   1023,14}, \
+    {   2303,13}, {   4607,14}, {   2431,13}, {   4863,15}, \
+    {   1279,14}, {   2943,13}, {   5887,15}, {   1535,14}, \
+    {   3199,15}, {   1791,14}, {   3839,13}, {   7679,16}, \
+    {   1023,15}, {   2047,14}, {   4351,15}, {   2303,14}, \
+    {   4863,15}, {   2815,14}, {   5887,13}, {  11775,16}, \
+    {   1535,15}, {   3071,14}, {   6655,15}, {  32768,16}, \
+    {  65536,17}, { 131072,18}, { 262144,19}, { 524288,20}, \
+    {1048576,21}, {2097152,22}, {4194304,23}, {8388608,24} }
+#define MUL_FFT_TABLE3_SIZE 224
+#define MUL_FFT_THRESHOLD                 2752
+
+#define SQR_FFT_MODF_THRESHOLD             240  /* k = 5 */
+#define SQR_FFT_TABLE3                                      \
+  { {    240, 5}, {     11, 6}, {      6, 5}, {     13, 6}, \
+    {     15, 7}, {      8, 6}, {     19, 7}, {     10, 6}, \
+    {     21, 7}, {     13, 8}, {      7, 7}, {     21, 8}, \
+    {     11, 7}, {     25, 8}, {     13, 9}, {      7, 8}, \
+    {     15, 7}, {     31, 8}, {     21, 9}, {     11, 8}, \
+    {     25,10}, {      7, 9}, {     15, 8}, {     33, 9}, \
+    {     19, 8}, {     39, 9}, {     23, 8}, {     47, 9}, \
+    {     27,10}, {     15, 9}, {     39,10}, {     23, 9}, \
+    {     51,11}, {     15,10}, {     31, 9}, {     63, 8}, \
+    {    127,10}, {     39, 9}, {     79,10}, {     47,11}, \
+    {     31,10}, {     63, 9}, {    127, 8}, {    255,10}, \
+    {     71, 9}, {    143, 7}, {    575,10}, {     79,11}, \
+    {     47,12}, {     31,11}, {     63,10}, {    127, 9}, \
+    {    255,10}, {    143, 9}, {    287,11}, {     79, 9}, \
+    {    319,10}, {    191, 9}, {    383,10}, {    207,12}, \
+    {     63,11}, {    127,10}, {    255,11}, {    143,10}, \
+    {    287, 9}, {    575,11}, {    159,10}, {    319,11}, \
+    {    175,10}, {    351,12}, {     95,11}, {    191,10}, \
+    {    383,11}, {    223,13}, {     63,12}, {    127,11}, \
+    {    287,12}, {    159,11}, {    351,12}, {    191,11}, \
+    {    383,10}, {    767,11}, {    415,12}, {    223,11}, \
+    {    447,13}, {    127,12}, {    255,11}, {    511,12}, \
+    {    287,11}, {    575,12}, {    319,11}, {    639,12}, \
+    {    351,13}, {    191,12}, {    383,11}, {    767,12}, \
+    {    415,11}, {    831,12}, {    447,14}, {    127,13}, \
+    {    255,12}, {    511,11}, {   1023,12}, {    543,11}, \
+    {   1087,10}, {   2175,12}, {    575,13}, {    319,12}, \
+    {    639,11}, {   1279,12}, {    671,11}, {   1343,12}, \
+    {    703,13}, {    383,12}, {    767,11}, {   1535,12}, \
+    {    831,13}, {    447,14}, {    255,13}, {    511,12}, \
+    {   1023,11}, {   2047,12}, {   1087,11}, {   2175,13}, \
+    {    575,12}, {   1151,11}, {   2303,12}, {   1215,13}, \
+    {    639,12}, {   1279,11}, {   2559,12}, {   1343,13}, \
+    {    703,14}, {    383,13}, {    767,12}, {   1535,13}, \
+    {    831,12}, {   1663,15}, {    255,14}, {    511,13}, \
+    {   1023,12}, {   2047,13}, {   1087,12}, {   2175,13}, \
+    {   1151,12}, {   2303,13}, {   1215,14}, {    639,13}, \
+    {   1343,12}, {   2687,13}, {   1407,12}, {   2815,14}, \
+    {    767,13}, {   1663,14}, {    895,13}, {   1791,12}, \
+    {   3583,13}, {   1919,12}, {   3839,15}, {    511,14}, \
+    {   1023,13}, {   2175,14}, {   1151,13}, {   2303,12}, \
+    {   4607,13}, {   2431,12}, {   4863,14}, {   1279,13}, \
+    {   2687,14}, {   1407,13}, {   2815,15}, {    767,14}, \
+    {   1535,13}, {   3071,14}, {   1791,13}, {   3583,14}, \
+    {   1919,13}, {   3839,12}, {   7679,16}, {    511,15}, \
+    {   1023,14}, {   2175,13}, {   4351,14}, {   2303,13}, \
+    {   4607,14}, {   2431,13}, {   4863,15}, {   1279,14}, \
+    {   2815,13}, {   5631,14}, {   2943,13}, {   5887,12}, \
+    {  11775,15}, {   1535,14}, {   3199,15}, {   1791,14}, \
+    {   3583,13}, {   7167,14}, {   3839,13}, {   7679,16}, \
+    {   1023,15}, {   2047,14}, {   4351,15}, {   2303,14}, \
+    {   4863,15}, {   2815,14}, {   5887,13}, {  11775,16}, \
+    {   1535,15}, {   3071,14}, {   6655,15}, {  32768,16}, \
+    {  65536,17}, { 131072,18}, { 262144,19}, { 524288,20}, \
+    {1048576,21}, {2097152,22}, {4194304,23}, {8388608,24} }
+#define SQR_FFT_TABLE3_SIZE 220
+#define SQR_FFT_THRESHOLD                 2752
 
 #define MULLO_BASECASE_THRESHOLD             0  /* always */
-#define MULLO_DC_THRESHOLD                  28
-#define MULLO_MUL_N_THRESHOLD             8648
+#define MULLO_DC_THRESHOLD                  27
+#define MULLO_MUL_N_THRESHOLD             5240
 
-#define DC_DIV_QR_THRESHOLD                 32
-#define DC_DIVAPPR_Q_THRESHOLD              68
+#define DC_DIV_QR_THRESHOLD                 28
+#define DC_DIVAPPR_Q_THRESHOLD              60
 #define DC_BDIV_QR_THRESHOLD                31
-#define DC_BDIV_Q_THRESHOLD                 57
+#define DC_BDIV_Q_THRESHOLD                 60
 
-#define INV_MULMOD_BNM1_THRESHOLD          116
+#define INV_MULMOD_BNM1_THRESHOLD           99
 #define INV_NEWTON_THRESHOLD               266
-#define INV_APPR_THRESHOLD                 114
+#define INV_APPR_THRESHOLD                 110
 
-#define BINV_NEWTON_THRESHOLD              242
+#define BINV_NEWTON_THRESHOLD              262
 #define REDC_1_TO_REDC_2_THRESHOLD          15
-#define REDC_2_TO_REDC_N_THRESHOLD          50
-
-#define MU_DIV_QR_THRESHOLD               1589
-#define MU_DIVAPPR_Q_THRESHOLD            1528
-#define MUPI_DIV_QR_THRESHOLD              315
-#define MU_BDIV_QR_THRESHOLD              1499
-#define MU_BDIV_Q_THRESHOLD               1499
-
-#define MATRIX22_STRASSEN_THRESHOLD         19
-#define HGCD_THRESHOLD                     101
-#define GCD_DC_THRESHOLD                   242
-#define GCDEXT_DC_THRESHOLD                222
+#define REDC_2_TO_REDC_N_THRESHOLD          47
+
+#define MU_DIV_QR_THRESHOLD                979
+#define MU_DIVAPPR_Q_THRESHOLD            1078
+#define MUPI_DIV_QR_THRESHOLD              102
+#define MU_BDIV_QR_THRESHOLD               792
+#define MU_BDIV_Q_THRESHOLD                942
+
+#define MATRIX22_STRASSEN_THRESHOLD         21
+#define HGCD_THRESHOLD                      97
+#define GCD_DC_THRESHOLD                   217
+#define GCDEXT_DC_THRESHOLD                237
 #define JACOBI_BASE_METHOD                   1
 
-#define GET_STR_DC_THRESHOLD                13
-#define GET_STR_PRECOMPUTE_THRESHOLD        25
-#define SET_STR_DC_THRESHOLD               532
-#define SET_STR_PRECOMPUTE_THRESHOLD      1561
-
-/* These tables need updating.  */
-
-#define MUL_FFT_TABLE2 {{1,4}, {145,5}, {353,6}, {961,7}, {2689,8}, {6913,10}, {7169,9}, {7681,8}, {8449,9}, {13825,10}, {15361,9}, {19969,10}, {23553,9}, {26113,11}, {30721,10}, {31745,9}, {34561,10}, {48129,11}, {63489,10}, {81921,11}, {96257,10}, {97793,12}, {126977,11}, {133121,10}, {135169,11}, {137217,10}, {139777,9}, {141313,10}, {145409,11}, {161793,10}, {163841,11}, {165889,10}, {169985,11}, {172033,10}, {177153,11}, {206849,12}, {212993,11}, {217089,12}, {258049,11}, {358401,12}, {389121,11}, {391169,10}, {397313,11}, {410625,10}, {421889,11}, {450561,13}, {516097,12}, {520193,11}, {587777,12}, {651265,11}, {718849,12}, {790529,11}, {800769,12}, {815105,11}, {821249,12}, {833537,11}, {845825,12}, {915457,13}, {1040385,12}, {1437697,13}, {1564673,12}, {1830913,14}, {2088961,12}, {2355201,13}, {2613249,12}, {2879489,13}, {3137537,12}, {3405825,13}, {3661825,14}, {4186113,12}, {4454401,13}, {4714497,11}, {4979713,13}, {MP_SIZE_T_MAX, 0}}
-#define MUL_FFT_TABLE2_SIZE 73
-
-#define SQR_FFT_TABLE2 {{1,4}, {177,5}, {417,6}, {961,7}, {3073,8}, {6913,10}, {7169,9}, {7681,8}, {8449,9}, {13825,10}, {15361,9}, {19969,10}, {23553,9}, {26113,11}, {30721,10}, {48129,11}, {63489,10}, {65537,8}, {65793,10}, {80897,11}, {96257,12}, {126977,11}, {129025,10}, {136193,11}, {137217,10}, {146433,9}, {146945,11}, {161793,10}, {176129,11}, {195073,10}, {201729,11}, {202753,10}, {206849,11}, {219137,12}, {258049,11}, {260097,10}, {262145,11}, {270337,10}, {272385,11}, {279553,10}, {280577,11}, {286721,10}, {287745,11}, {359425,12}, {389121,11}, {423937,13}, {516097,12}, {520193,11}, {587777,12}, {651265,11}, {718849,12}, {782337,11}, {802817,12}, {806913,11}, {849921,12}, {915457,13}, {1040385,12}, {1437697,13}, {1564673,12}, {1830913,14}, {2080769,13}, {2088961,12}, {2355201,13}, {2613249,12}, {2752513,13}, {2785281,12}, {2801665,13}, {2818049,12}, {2838529,13}, {2863105,12}, {2867201,13}, {3137537,12}, {3403777,13}, {3661825,14}, {4177921,13}, {4186113,12}, {4452353,13}, {4714497,11}, {4979713,13}, {MP_SIZE_T_MAX, 0}}
-#define SQR_FFT_TABLE2_SIZE 79
+#define GET_STR_DC_THRESHOLD                12
+#define GET_STR_PRECOMPUTE_THRESHOLD        23
+#define SET_STR_DC_THRESHOLD               572
+#define SET_STR_PRECOMPUTE_THRESHOLD      1588