- // 1000 0.36 0.54 0.08 0.10
- // 5000 4.66 2.48 1.01 0.51
- // 25000 61.1 13.22 13.23 2.73
- // 32500 91.0 27.5 20.0 5.8
- // 35000 102.1 27.5 21.5 5.6
- // 50000 183 27.6 40.7 5.6
- // Multiplikation zweier N-Wort-Zahlen unter
- // Linux mit einem 80486: Solaris, Sparc 10/20:
- // N kara fftm (time in sec.) kara fftm
- // 1000 0.36 0.54 0.08 0.10
- // 1260 0.52 0.50 0.11 0.10
- // 1590 0.79 0.51 0.16 0.10
- // 2000 1.09 1.07 0.23 0.21
- // 2520 1.57 1.08 0.33 0.21
- // 3180 2.32 1.08 0.50 0.21
- // 4000 3.29 2.22 0.70 0.41
- // 5040 4.74 2.44 0.99 0.50
- // N1 N2 kara fftm (time in sec.) kara fftm
- // 1250 1250 0.51 0.50 0.11 0.10
- // 1250 1580 0.70 0.50 0.15 0.10
- // 1250 2000 0.89 0.51 0.18 0.10
- // 1250 2250 0.99 0.51 0.21 0.10
- // 1250 2500 1.08 1.03 <--- 0.22 0.21
- // 1250 2800 1.20 1.07 0.26 0.21
- // 1250 3100 1.35 1.07 0.28 0.21
- // Es gibt also noch Werte von (len1,len2) mit 1250 <= len1 <= len2, bei
- // denen "kara" schneller ist als "fftm", aber nicht viele und dort auch
- // nur um 5%. Darum wählen wir ab hier die FFT-Multiplikation.
- const unsigned int cl_fftm_threshold = 1250; // muß stets >= 6 sein (sonst Endlosrekursion!)
+ // 1000 0.005 0.016 0.018 0.028
+ // 1500 0.009 0.012 0.032 0.028
+ // 2000 0.015 0.025 0.053 0.052 <-
+ // 2500 0.022 0.026 0.067 0.052
+ // 3000 0.029 0.027 <- 0.093 0.053
+ // 3500 0.035 0.037 0.12 0.031
+ // 4000 0.045 0.028 0.16 0.12
+ // 5000 0.064 0.050 0.20 0.11
+ // 7000 0.110 0.051 0.37 0.20
+ // 10000 0.19 0.11 0.61 0.26
+ // 20000 0.59 0.23 1.85 0.55
+ // 30000 1.10 0.25 3.79 0.56
+ // 50000 2.52 1.76 8.15 1.37
+ // 70000 4.41 2.30 14.09 2.94
+ // 100000 7.55 1.53 24.48 2.96
+ // More playing around with timings reveals that there are some values where
+ // FFT multiplication is somewhat slower than Karatsuba, both for len1==len2
+ // and also if len1<len2.
+ // Here are the timigs from CLN version <= 1.0.3:
+ // // Linux mit einem 80486: Solaris, Sparc 10/20:
+ // // N kara fftm (time in sec.) kara fftm
+ // // 1000 0.36 0.54 0.08 0.10
+ // // 5000 4.66 2.48 1.01 0.51
+ // // 25000 61.1 13.22 13.23 2.73
+ // // 32500 91.0 27.5 20.0 5.8
+ // // 35000 102.1 27.5 21.5 5.6
+ // // 50000 183 27.6 40.7 5.6
+ // // Multiplikation zweier N-Wort-Zahlen unter
+ // // Linux mit einem 80486: Solaris, Sparc 10/20:
+ // // N kara fftm (time in sec.) kara fftm
+ // // 1000 0.36 0.54 0.08 0.10
+ // // 1260 0.52 0.50 0.11 0.10
+ // // 1590 0.79 0.51 0.16 0.10
+ // // 2000 1.09 1.07 0.23 0.21
+ // // 2520 1.57 1.08 0.33 0.21
+ // // 3180 2.32 1.08 0.50 0.21
+ // // 4000 3.29 2.22 0.70 0.41
+ // // 5040 4.74 2.44 0.99 0.50
+ // // N1 N2 kara fftm (time in sec.) kara fftm
+ // // 1250 1250 0.51 0.50 0.11 0.10
+ // // 1250 1580 0.70 0.50 0.15 0.10
+ // // 1250 2000 0.89 0.51 0.18 0.10
+ // // 1250 2250 0.99 0.51 0.21 0.10
+ // // 1250 2500 1.08 1.03 <--- 0.22 0.21
+ // // 1250 2800 1.20 1.07 0.26 0.21
+ // // 1250 3100 1.35 1.07 0.28 0.21
+ // // Es gibt also noch Werte von (len1,len2) mit 1250 <= len1 <= len2, bei
+ // // denen "kara" schneller ist als "fftm", aber nicht viele und dort auch
+ // // nur um 5%. Darum wählen wir ab hier die FFT-Multiplikation.
+ // // 140000: 4.15s 12.53 23.7
+ // // 14000: 4.16s
+ // // 11000: 4.16s
+ // // 9000: 1.47s
+ // // 7000: 1.48s
+ // // 1400: 1.42s 2.80 6.5
+#if CL_USE_GMP
+ const unsigned int cl_fftm_threshold = 2500;
+ // must be >= 6 (else infinite recursion)
+#else
+ // Use the old default value from CLN version <= 1.0.3 as a crude estimate.
+ const unsigned int cl_fftm_threshold = 1250;
+#endif