#include "NTL/ZZ.h"
main()
{
ZZ a;
ZZ b;
ZZ c;
cin >> a;
cin >> b;
mul(c,a,b); /* c = a * b works but does extra copying */
cout << c << "\n";
}
Note that NTL can use
GMP instead of NTL LIP.
I compiled NTL 5.2 on thoth on 2002.02.23:
lynx -source www.shoup.net/ntl/ntl-5.2.tar.gz > ntl-5.2.tar.gz
gunzip < ntl-5.2.tar.gz | tar -xf -
cd ntl-5.2/src
./configure
make
# about 250 seconds
cd ..
lynx -source cr.yp.to/speed/mult/ntl-bench.c > bench.c
g++ -O3 -o bench bench.c -I include src/ntl.a -fno-exceptions
./bench > bench.out
# about 130 seconds
Results:
1: 2916 145 111 93 232 106
2: 93 120 120 107 245 106
3: 93 107 93 107 321 93
4: 93 93 93 93 284 93
5: 93 93 93 93 230 93
6: 93 93 93 93 230 93
7: 93 93 93 93 230 93
8: 93 93 93 93 338 93
10: 93 93 93 93 230 93
12: 93 93 93 93 230 93
14: 93 93 93 93 230 93
16: 116 91 91 91 337 91
20: 91 91 91 91 339 91
24: 91 91 91 91 228 91
28: 91 91 91 91 114 91
32: 1670 188 184 184 284 150
40: 169 184 184 150 285 150
48: 149 179 164 149 171 149
56: 149 164 164 149 284 149
64: 21746 322 272 254 389 254
80: 295 292 283 254 391 254
96: 1870 613 582 552 572 552
112: 581 550 550 550 684 550
128: 1183 817 788 770 904 770
160: 1070 1029 1014 1014 1147 1014
192: 10023 1384 1316 1316 1448 1316
224: 1725 1659 1659 1659 1679 1659
256: 2393 2090 2046 2046 2179 2046
320: 3465 3177 3147 3147 3281 3147
384: 4590 4322 4275 4275 4514 4275
448: 6902 5628 5579 5579 5597 5579
512: 10616 7718 7514 7435 7442 7420
640: 11609 10862 10833 10821 10958 10821
768: 14859 14444 14383 14333 14354 14333
896: 19457 18414 18354 18354 18439 18315
1024: 26276 24261 24150 24150 24176 24150
1280: 44393 34188 34070 34070 34294 34070
1536: 46543 45538 45479 45479 45602 45465
1792: 61223 58068 57997 57997 58022 57982
2048: 75396 73550 73467 73468 73495 73452
2560: 106755 105545 105523 105523 105511 105489
3072: 161257 141096 141040 141040 141178 141040
3584: 185755 179185 179113 179113 179221 179098
4096: 226116 223230 223158 223158 223265 223143
5120: 323609 321368 341219 321331 321400 321278
6144: 429317 427499 427430 427430 443833 427430
7168: 549651 547069 547038 547020 547131 546994
8192: 704215 679188 721576 679352 695965 679098
10240: 980497 976324 976308 976308 976409 992395
12288: 1491960 1298766 1296647 1296647 1296784 1313097
14336: 1682155 1684071 1652416 1668706 1652525 1652388
16384: 2109518 2065901 2075804 2049665 2077817 2049623
20480: 2937480 2945729 2942906 2945538 2929634 2941531
24576: 3979971 3915842 3919610 3919829 3914260 3919741
28672: 5022411 5000139 5010936 5012164 4982540 5027846
32768: 6268433 6217868 6208851 6195690 6263965 6207387
40960: 9013542 8883338 8882039 8882389 8902323 8899917
49152: 11933349 11798913 11827280 11815365 11797699 11826886
57344: 15182571 15134885 15113894 15117283 15114440 15112861
65536: 18768967 18676361 18694641 18693830 18679026 18702732
81920: 27087962 26768082 26749326 26782526 26762902 26762634
98304: 35838300 35624010 35611663 35638161 35620871 35616853
114688: 45823943 45532420 45513669 45511591 45576490 45509252
131072: 56514311 56255261 56242278 56232918 56255103 56245005
163840: 81417236 80842593 80778546 80748282 80754678 80827660
196608: 107651780 107080860 107077107 107063985 107142002 107091981
229376: 137433507 136418719 136310241 136298910 136338333 136358774
262144: 169693536 168984910 168949225 168881215 168932787 169007937
327680: 244158511 242444799 242422821 242418873 242446470 242379403
393216: 323577851 322221229 322097669 322133973 322194225 322138946
458752: 412438937 410072628 410094483 409998684 409981569 410070135
524288: 511532150 509245245 509117994 509126661 509114667 509066247
655360: 732710293 731160177 730995249 730665063 730658637 730598574
786432: 971112214 967751985 967720887 967634421 967701144 967721877
917504: 1242072400 1235184785 1234892476 1234791990 1234909803 1234872006
1048576: 1536520126 1533597867 1533558144 1533538266 1533315162 1533660864
1310720: 2201091139 2195648181 2195699910 2195530026 2195868321 2199389568
1572864: 2924296832 2919318279 2919860040 2920402857 2920021899 2923146549
1835008: 3723091904 3715295787 3718622733 3715215687 3715589295 3715376340
2097152: 4618476286 4608546696 4608425286 4610735118 4608479703 4608814194
Older timings of NTL 3.9b on a Pentium-II:
1: 2764 286 209 198 193 180
2: 199 180 198 180 180 180
4: 187 180 180 180 180 180
8: 191 180 180 180 200 180
16: 199 196 175 175 175 175
32: 395 350 359 279 279 279
64: 8650 538 468 459 454 454
128: 5572 988 918 918 946 918
256: 3333 2633 2624 2608 2608 2636
512: 25659 9327 9244 9225 9225 9217
1024: 31553 29685 29649 29622 29623 29623
2048: 101916 90755 90623 90568 90569 90568
4096: 287356 275655 275559 275515 287147 275610
8192: 853849 933509 840604 840326 840296 845944
16384: 2578731 2542333 2536159 2541439 2541500 2536203
32768: 7749844 7674841 7675722 7681206 7674466 7674468