D. J. Bernstein
Fast arithmetic
Integer multiplication benchmarks

NTL LIP

NTL LIP is my name for the variant of LIP included in NTL. NTL was written by Victor Shoup. The NTL home page is www.shoup.net/ntl. Sample code using NTL:
     #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