| 1 | <html> |
|---|
| 2 | <head> |
|---|
| 3 | <title> |
|---|
| 4 | A Tour of NTL: Using NTL with GMP </title> |
|---|
| 5 | </head> |
|---|
| 6 | |
|---|
| 7 | <body bgcolor="#fff9e6"> |
|---|
| 8 | |
|---|
| 9 | <center> |
|---|
| 10 | <a href="tour-impl.html"><img src="arrow1.gif" alt="[Previous]" align=bottom></a> |
|---|
| 11 | <a href="tour.html"><img src="arrow2.gif" alt="[Up]" align=bottom></a> |
|---|
| 12 | <a href="tour-gf2x.html"> <img src="arrow3.gif" alt="[Next]" align=bottom></a> |
|---|
| 13 | </center> |
|---|
| 14 | |
|---|
| 15 | <h1> |
|---|
| 16 | <p align=center> |
|---|
| 17 | A Tour of NTL: Using NTL with GMP |
|---|
| 18 | </p> |
|---|
| 19 | </h1> |
|---|
| 20 | |
|---|
| 21 | <p> <hr> <p> |
|---|
| 22 | |
|---|
| 23 | GMP is the GNU Multi-Precision library. |
|---|
| 24 | You can get more information about it, as well as the latest version |
|---|
| 25 | from <a href="http://gmplib.org">here.</a> |
|---|
| 26 | |
|---|
| 27 | <p> |
|---|
| 28 | |
|---|
| 29 | Briefly, GMP is a library for long integer arithmetic. |
|---|
| 30 | It has hand-crafted assembly routines for a wide variety |
|---|
| 31 | of architectures. |
|---|
| 32 | For basic operations, like integer multiplication, it can be |
|---|
| 33 | two to three (and sometimes bit more) times faster than NTL's |
|---|
| 34 | traditional long integer package. |
|---|
| 35 | The speedup is most dramatic on x86 machines. |
|---|
| 36 | |
|---|
| 37 | <p> |
|---|
| 38 | You can choose one of three different ways of implementing |
|---|
| 39 | long integer arithmetic in NTL: |
|---|
| 40 | <p> |
|---|
| 41 | <ol> |
|---|
| 42 | <li> |
|---|
| 43 | One can use the traditional NTL long integer arithmtic package, |
|---|
| 44 | and avoid dealing with GMP entirely. |
|---|
| 45 | |
|---|
| 46 | <p> |
|---|
| 47 | <li> |
|---|
| 48 | One can use traditional NTL long integer arithmtic package, |
|---|
| 49 | but with GMP as a <i>supplemental</i> long integer package. |
|---|
| 50 | This gives you many (though not all) of the performance benefits of GMP, |
|---|
| 51 | but while still maintaining complete backward compatability. |
|---|
| 52 | |
|---|
| 53 | <p> |
|---|
| 54 | <li> |
|---|
| 55 | One can use GMP as the primary long integer package. |
|---|
| 56 | This gives you essentially all of the performance benefits |
|---|
| 57 | of GMP, but there are some minor backward incompatabilities |
|---|
| 58 | <a href="#compat">(see below)</a>. |
|---|
| 59 | |
|---|
| 60 | </ol> |
|---|
| 61 | |
|---|
| 62 | <p> |
|---|
| 63 | |
|---|
| 64 | <p> |
|---|
| 65 | The use of GMP as the primary long integer package |
|---|
| 66 | is the preferred method of using GMP. |
|---|
| 67 | The use of GMP as a supplemental long integer package is intended |
|---|
| 68 | primarily for backward compatability. |
|---|
| 69 | |
|---|
| 70 | <p> |
|---|
| 71 | Building NTL with GMP (either as a supplemental or primary |
|---|
| 72 | long integer package) takes a few extra minutes work, |
|---|
| 73 | and you certainly do not need to use NTL with GMP if you don't want to. |
|---|
| 74 | As far as I know, GMP is only available on Unix systems |
|---|
| 75 | and on Windows systems using Cygwin tools. |
|---|
| 76 | |
|---|
| 77 | <p> |
|---|
| 78 | Even if you do not use GMP as the primary long integer package, |
|---|
| 79 | you should still read the <a href="#compat">section below |
|---|
| 80 | on backward compatabilty</a> |
|---|
| 81 | so that you can write portable code and avoid deprecated constructs. |
|---|
| 82 | |
|---|
| 83 | <p> |
|---|
| 84 | <h2> |
|---|
| 85 | Downloading and building GMP |
|---|
| 86 | </h2> |
|---|
| 87 | <p> |
|---|
| 88 | |
|---|
| 89 | Download GMP from <a href="http://gmplib.org">here.</a> |
|---|
| 90 | You will get a file <tt>gmp-XXX.tar.gz</tt>. |
|---|
| 91 | <p> |
|---|
| 92 | Now do the following: |
|---|
| 93 | <pre> |
|---|
| 94 | % gunzip gmp-XXX.tar.gz |
|---|
| 95 | % tar xf gmp-XXX.tar |
|---|
| 96 | % cd gmp-XXX |
|---|
| 97 | % ./configure --prefix=$HOME/sw |
|---|
| 98 | % make |
|---|
| 99 | % make check |
|---|
| 100 | % make install |
|---|
| 101 | </pre> |
|---|
| 102 | This will build, test, and install GMP in <tt>$HOME/sw</tt>. |
|---|
| 103 | Of course, change $HOME/sw to whatever you want (the default is |
|---|
| 104 | <tt>/usr/local</tt>). |
|---|
| 105 | You will find the GMP header files in <tt>$HOME/sw/include</tt> |
|---|
| 106 | and the compiled binaries in <tt>$HOME/sw/lib</tt>. |
|---|
| 107 | |
|---|
| 108 | <p> |
|---|
| 109 | You can also supply the option |
|---|
| 110 | <tt>--disable-shared</tt> to the <tt>configure</tt> script, |
|---|
| 111 | if you only want static libraries. |
|---|
| 112 | However, if you ultimately want to build NTL as a shared |
|---|
| 113 | library, then you must also buld GMP as a shared library. |
|---|
| 114 | |
|---|
| 115 | <p> |
|---|
| 116 | You must ensure that NTL and GMP have the same |
|---|
| 117 | <a href="tour-unix.html#abi">ABI</a>. |
|---|
| 118 | Usually, GMP's configure script will automatically |
|---|
| 119 | choose a 64-bit ABI if available. |
|---|
| 120 | |
|---|
| 121 | |
|---|
| 122 | <p> |
|---|
| 123 | <h2> |
|---|
| 124 | Building and using NTL with GMP |
|---|
| 125 | </h2> |
|---|
| 126 | <p> |
|---|
| 127 | |
|---|
| 128 | When building NTL with GMP, you have to tell NTL that you want to |
|---|
| 129 | use GMP as the primary long integer package, |
|---|
| 130 | and where the include files and library are. |
|---|
| 131 | The easiest way to do this is by passing the argument |
|---|
| 132 | <tt>NTL_GMP_LIP=on</tt> to the NTL configuration script |
|---|
| 133 | when you are <a href="tour-unix.html">installing NTL</a>. |
|---|
| 134 | Assuming you installed GMP in <tt>$HOME/sw</tt> as above, |
|---|
| 135 | and you also want to install NTL in <tt>$HOME/sw</tt>, |
|---|
| 136 | you execute: |
|---|
| 137 | <pre> |
|---|
| 138 | % ./configure PREFIX=$HOME/sw NTL_GMP_LIP=on GMP_PREFIX=$HOME/sw |
|---|
| 139 | </pre> |
|---|
| 140 | You can write this more simply as |
|---|
| 141 | <pre> |
|---|
| 142 | % ./configure DEF_PREFIX=$HOME/sw NTL_GMP_LIP=on |
|---|
| 143 | </pre> |
|---|
| 144 | Here, <tt>DEF_PREFIX</tt> is a variable that is used |
|---|
| 145 | to specify the location of all software, |
|---|
| 146 | and it defaults to <tt>/usr/local</tt>. |
|---|
| 147 | |
|---|
| 148 | |
|---|
| 149 | <p> |
|---|
| 150 | If you installed GMP in <tt>/usr/local</tt> (or some other |
|---|
| 151 | standard system directory where your compiler will look by default) |
|---|
| 152 | then simply |
|---|
| 153 | <pre> |
|---|
| 154 | % ./configure PREFIX=$HOME/sw NTL_GMP_LIP=on |
|---|
| 155 | </pre> |
|---|
| 156 | does the job. |
|---|
| 157 | Moreover, if NTL is also to be installed in <tt>/usr/local</tt>, |
|---|
| 158 | then |
|---|
| 159 | <pre> |
|---|
| 160 | % ./configure NTL_GMP_LIP=on |
|---|
| 161 | </pre> |
|---|
| 162 | does the job. |
|---|
| 163 | |
|---|
| 164 | <p> |
|---|
| 165 | If instead you want to use GMP as a supplemental long integer package, |
|---|
| 166 | you should pass the argument <tt>NTL_GMP_HACK=on</tt> to the configure script, |
|---|
| 167 | instead of <tt>NTL_GMP_LIP=on</tt>. |
|---|
| 168 | One still has to specify where to find GMP using the <tt>GMP_PREFIX</tt> |
|---|
| 169 | variable in the configuration script. |
|---|
| 170 | |
|---|
| 171 | <p> |
|---|
| 172 | Instead of passing arguments to the configure script, |
|---|
| 173 | you can also just edit the <tt>config.h</tt> and <tt>makefile</tt> by hand. |
|---|
| 174 | The documentation in these files should be self-explanatory. |
|---|
| 175 | |
|---|
| 176 | |
|---|
| 177 | <p> |
|---|
| 178 | When compiling programs that use NTL with GMP, |
|---|
| 179 | you need to link with the GMP library. |
|---|
| 180 | If GMP is installed as above in |
|---|
| 181 | <tt>$HOME/sw</tt>, rather than in a standard system directory, |
|---|
| 182 | this just means adding |
|---|
| 183 | <tt>-L$HOME/sw/lib -lgmp</tt> to the compilation command. |
|---|
| 184 | If you installed GMP in a standard system directory, |
|---|
| 185 | then just <tt>-lgmp</tt> does the job. |
|---|
| 186 | Note that <tt>-lgmp</tt> must come <i>after</i> <tt>-lntl</tt> |
|---|
| 187 | on the command line. |
|---|
| 188 | Finally, if NTL and GF2X are installed as |
|---|
| 189 | shared libraries, then you don't even need <tt>-lgmp</tt>. |
|---|
| 190 | |
|---|
| 191 | |
|---|
| 192 | <p> |
|---|
| 193 | NTL has been tested and works correctly with GMP versions 3.1, 3.1.1, |
|---|
| 194 | and 4.1.4 (among others) |
|---|
| 195 | as the primary long integer package. |
|---|
| 196 | It is not possible to use versions of GMP prior to 3.1 as the |
|---|
| 197 | primary long integer package. |
|---|
| 198 | |
|---|
| 199 | <p> |
|---|
| 200 | |
|---|
| 201 | NTL has been tested and works correctly |
|---|
| 202 | with versions 2.0.2, 3.0.1, 3.1, 3.1.1, and 4.1.4 |
|---|
| 203 | (among otheers) of GMP as a supplemental |
|---|
| 204 | long integer package. |
|---|
| 205 | It is not recommended to use versions of GMP prior to 3.1.1, |
|---|
| 206 | as these are generally more buggy and less efficient. |
|---|
| 207 | |
|---|
| 208 | <p> |
|---|
| 209 | When using NTL with GMP as either primary or supplemental |
|---|
| 210 | long integer package, as a user of NTL, you do not need to |
|---|
| 211 | know or understand anything about the the GMP library. |
|---|
| 212 | So while there is detailed documentation available about how |
|---|
| 213 | to use GMP, you do not have to read it. |
|---|
| 214 | The programming interface to the long integer package |
|---|
| 215 | completely hides implementation details. |
|---|
| 216 | |
|---|
| 217 | |
|---|
| 218 | |
|---|
| 219 | |
|---|
| 220 | <p> |
|---|
| 221 | <h2> |
|---|
| 222 | Some implementation details |
|---|
| 223 | </h2> |
|---|
| 224 | <p> |
|---|
| 225 | |
|---|
| 226 | When using GMP as the primary long integer package, |
|---|
| 227 | the code used by NTL is essentially a layer of <tt>C</tt> routines |
|---|
| 228 | that call the low level <tt>mpn</tt> routines in the GMP package. |
|---|
| 229 | These NTL wrapper routines provide essentially the same |
|---|
| 230 | functionality of the higher level <tt>mpz</tt> routines in GMP, |
|---|
| 231 | but while presenting an interface to the rest of NTL that is almost identical |
|---|
| 232 | to that of the |
|---|
| 233 | traditional NTL long integer package. |
|---|
| 234 | There are, however, some very minor backward incompatabilities |
|---|
| 235 | <a href="#compat">(see below)</a>. |
|---|
| 236 | |
|---|
| 237 | <p> |
|---|
| 238 | When using GMP as a supplemental long integer package, |
|---|
| 239 | the code employs |
|---|
| 240 | a "quick and dirty", yet fairly effective hack. |
|---|
| 241 | This quick and dirty |
|---|
| 242 | approach converts "on the fly" |
|---|
| 243 | between the classic LIP and GMP representations. |
|---|
| 244 | This makes the use of GMP <i>completely</i> invisible to higher layer software. |
|---|
| 245 | Of course, there is a penalty: converting between representations takes |
|---|
| 246 | time. |
|---|
| 247 | For operations like addition, conversion would take longer |
|---|
| 248 | than performing the operation, and so it is not done. |
|---|
| 249 | However, for computationally expensive |
|---|
| 250 | operations like multiplication, the "overhead" is not so bad, |
|---|
| 251 | at least for numbers that are not too small. |
|---|
| 252 | To multiply two 256-bit numbers on a Pentium-II, the extra time |
|---|
| 253 | required for the data conversions is just 35% of the time to |
|---|
| 254 | do the multiplication in GMP, i.e., the "overhead" is 35%. |
|---|
| 255 | For 512-bit numbers, the corresponding opportunity cost is about 14%, |
|---|
| 256 | and for 1024-bit numbers, it is less than 10%. |
|---|
| 257 | For smaller numbers, the opportunity cost is greater, but |
|---|
| 258 | never much worse than about 50%. |
|---|
| 259 | |
|---|
| 260 | <p> |
|---|
| 261 | <h2> |
|---|
| 262 | <a name="compat"> |
|---|
| 263 | Backward compatbility |
|---|
| 264 | </a> |
|---|
| 265 | </h2> |
|---|
| 266 | <p> |
|---|
| 267 | |
|---|
| 268 | With version 5.0 of NTL, some aspects of the programming interface |
|---|
| 269 | are 'deprecated' so as to allow the use of another long integer package, |
|---|
| 270 | such as GMP, as the primary long integer package. |
|---|
| 271 | |
|---|
| 272 | <p> |
|---|
| 273 | Prior to version 5.0, the macro <tt>NTL_NBITS</tt> was defined, |
|---|
| 274 | along with the macro <tt>NTL_RADIX</tt> defined to be |
|---|
| 275 | <tt>(1L << NTL_NBITS)</tt>. |
|---|
| 276 | While these macros are still available when using NTL's traditional |
|---|
| 277 | long integer package (i.e., when <tt>NTL_GMP_LIP</tt> is not set), |
|---|
| 278 | they are not available when using the GMP as the primary long integer |
|---|
| 279 | package (i.e., when <tt>NTL_GMP_LIP</tt> is set). |
|---|
| 280 | Furthermore, when writing portable programs, one should avoid these macros. |
|---|
| 281 | |
|---|
| 282 | <p> |
|---|
| 283 | |
|---|
| 284 | |
|---|
| 285 | Also, the static function <tt>long ZZ::digit(const ZZ &);</tt> |
|---|
| 286 | is defined when using traditional long integer arithmetic, |
|---|
| 287 | but is not available when using GMP as the primary long integer package, |
|---|
| 288 | and in any case, its use should be avoided when writing portable programs. |
|---|
| 289 | |
|---|
| 290 | |
|---|
| 291 | <p> |
|---|
| 292 | Instead of the above macros, one should use the followng macros: |
|---|
| 293 | |
|---|
| 294 | <pre> |
|---|
| 295 | NTL_ZZ_NBITS -- number of bits in a zzigit; |
|---|
| 296 | a ZZ is represented as a sequence of zzigits. |
|---|
| 297 | |
|---|
| 298 | NTL_SP_NBITS -- max number of bits in a "single-precision" number |
|---|
| 299 | |
|---|
| 300 | NTL_WSP_NBITS -- max number of bits in a "wide single-precision" number |
|---|
| 301 | </pre> |
|---|
| 302 | <p> |
|---|
| 303 | The following relations hold: |
|---|
| 304 | <pre> |
|---|
| 305 | NTL_SP_NBITS <= NTL_WSP_NBITS <= NTL_ZZ_NBITS |
|---|
| 306 | 26 <= NTL_SP_NBITS <= min(NTL_BITS_PER_LONG-2, NTL_DOUBLE_PRECISION-3) |
|---|
| 307 | NTL_WSP_NBITS <= NTL_BITS_PER_LONG-2 |
|---|
| 308 | </pre> |
|---|
| 309 | |
|---|
| 310 | <p> |
|---|
| 311 | |
|---|
| 312 | Note that <tt>NTL_ZZ_NBITS</tt> may be less than, equal to, or greater than |
|---|
| 313 | <tt>NTL_BITS_PER_LONG</tt> -- no particular relationship |
|---|
| 314 | should be assumed to hold. |
|---|
| 315 | In particular, expressions like <tt>(1L << NTL_ZZ_BITS)</tt> |
|---|
| 316 | might overflow. |
|---|
| 317 | |
|---|
| 318 | <p> |
|---|
| 319 | "single-precision" numbers are meant to be used in conjunction with the |
|---|
| 320 | single-precision modular arithmetic routines. |
|---|
| 321 | |
|---|
| 322 | <p> |
|---|
| 323 | "wide single-precision" numbers are meant to be used in conjunction |
|---|
| 324 | with the <tt>ZZ</tt> arithmetic routines for optimal efficiency. |
|---|
| 325 | |
|---|
| 326 | <p> |
|---|
| 327 | Note that when using traditional long integer arithmetic, we have |
|---|
| 328 | <pre> |
|---|
| 329 | NTL_ZZ_NBITS = NTL_SP_NBITS = NTL_WSP_NBITS = NTL_NBITS. |
|---|
| 330 | </pre> |
|---|
| 331 | |
|---|
| 332 | <p> |
|---|
| 333 | The following auxilliary macros are also defined: |
|---|
| 334 | |
|---|
| 335 | <pre> |
|---|
| 336 | NTL_FRADIX -- double-precision value of <tt>2^NTL_ZZ_NBITS</tt> |
|---|
| 337 | NTL_SP_BOUND -- (1L << NTL_SP_NBITS) |
|---|
| 338 | NTL_WSP_BOUND -- (1L << NTL_WSP_NBITS) |
|---|
| 339 | </pre> |
|---|
| 340 | |
|---|
| 341 | <p> |
|---|
| 342 | |
|---|
| 343 | Note that for a <tt>ZZ</tt> <tt>n</tt>, |
|---|
| 344 | <tt>n.size()</tt> returns the number of "zzigits" of <tt>n</tt>. |
|---|
| 345 | This is supported with either traditional or GMP integer arithemtic. |
|---|
| 346 | Note, however, that some old codes might write <tt>n.size() <= 1</tt> |
|---|
| 347 | as a way to test if <tt>NumBits(n) <= NTL_NBITS</tt>. |
|---|
| 348 | This is no longer the right thing to do, if one wants portable code |
|---|
| 349 | that works with either traditional or GMP long integer arithmetic. |
|---|
| 350 | First, one has to decide whether one wants to test if |
|---|
| 351 | <tt>NumBits(n)</tt> is bounded by <tt>NTL_ZZ_NBITS</tt>, |
|---|
| 352 | <tt>NTL_SP_NBITS</tt>, or <tt>NTL_WSP_NBITS</tt>. |
|---|
| 353 | In the first case, <tt>n.size() <= 1</tt> is still |
|---|
| 354 | the right way to test this. |
|---|
| 355 | In the second case, write this as <tt>n.SinglePrecision()</tt>. |
|---|
| 356 | In the third case, write this as <tt>n.WideSinglePrecision()</tt>. |
|---|
| 357 | The routines <tt>SinglePrecision</tt> and <tt>WideSinglePrecision</tt> |
|---|
| 358 | are new to NTL version 5.0. |
|---|
| 359 | |
|---|
| 360 | <p> |
|---|
| 361 | |
|---|
| 362 | Most "high level" applications that use NTL should not be affected |
|---|
| 363 | by these changes to NTL's programming interface, and if they are, |
|---|
| 364 | changing the programs should be quite easy. |
|---|
| 365 | |
|---|
| 366 | |
|---|
| 367 | <p> <hr> <p> |
|---|
| 368 | |
|---|
| 369 | |
|---|
| 370 | <p> |
|---|
| 371 | |
|---|
| 372 | <center> |
|---|
| 373 | <a href="tour-impl.html"><img src="arrow1.gif" alt="[Previous]" align=bottom></a> |
|---|
| 374 | <a href="tour.html"><img src="arrow2.gif" alt="[Up]" align=bottom></a> |
|---|
| 375 | <a href="tour-gf2x.html"> <img src="arrow3.gif" alt="[Next]" align=bottom></a> |
|---|
| 376 | </center> |
|---|
| 377 | |
|---|
| 378 | |
|---|
| 379 | |
|---|
| 380 | </body> |
|---|
| 381 | </html> |
|---|
