📄 tour-gmp.html
字号:
<html><head><title>A Tour of NTL: Using NTL with GMP </title></head><body bgcolor="#fff9e6"><center><a href="tour-impl.html"><img src="arrow1.gif" alt="[Previous]" align=bottom></a> <a href="tour.html"><img src="arrow2.gif" alt="[Up]" align=bottom></a> <a href="tour-time.html"> <img src="arrow3.gif" alt="[Next]" align=bottom></a></center><h1> <p align=center>A Tour of NTL: Using NTL with GMP</p></h1><p> <hr> <p>GMP is the GNU Multi-Precision library.You can get more information about it, as well as the latest versionfrom <a href="http://www.swox.com/gmp">here.</a><p>Briefly, GMP is a library for long integer arithmetic.It has hand-crafted assembly routines for a wide varietyof architectures.For basic operations, like integer multiplication, it can be two to three (and sometimes bit more) times faster than NTL'straditional long integer package.The speedup is most dramatic on x86 machines.<p>You can choose one of three different ways of implementinglong integer arithmetic in NTL:<p><ol><li>One can use the traditional NTL long integer arithmtic package,and avoid dealing with GMP entirely.<p><li>One can use traditional NTL long integer arithmtic package,but with GMP as a <i>supplemental</i> long integer package.This gives you many (though not all) of the performance benefits of GMP,but while still maintaining complete backward compatability.<p><li>One can use GMP as the primary long integer package.This gives you essentially all of the performance benefitsof GMP, but there are some minor backward incompatabilities <a href="#compat">(see below)</a>.</ol><p><p>The use of GMP as the primary long integer packageis the preferred method of using GMP.The use of GMP as a supplemental long integer package is intendedprimarily for backward compatability.<p>Building NTL with GMP (either as a supplemental or primary long integer package) takes a few extra minutes work,and you certainly do not need to use NTL with GMP if you don't want to.As far as I know, GMP is only available on Unix systemsand on Windows systems using Cygwin tools.<p>Even if you do not use GMP as the primary long integer package,you should still read the <a href="#compat">section belowon backward compatabilty</a>so that you can write portable code and avoid deprecated constructs.<p><h2>Downloading and building GMP</h2><p>To dowload and build GMP on your machine, do the following:<p><b> Step 1.</b>Download GMP from <a href="http://www.swox.com/gmp">here.</a>You will get a file <tt>gmp-XXX.tar.gz</tt>.<p><b>Step 2.</b>Unpack GMP as follows:<pre> % gunzip gmp-XXX.tar.gz % tar xf gmp-XXX.tar</pre>This creates a directory <tt>gmp-XXX</tt>.Go there now:<pre> % cd gmp-XXX</pre><p><b>Step 3.</b>Build GMP as follows:<pre> % ./configure --disable-shared --prefix=<gmp_prefix> % make % make install</pre>Here, <tt><gmp_prefix></tt> should be the name of a directory where you would like to store the GMP library components.This builds and installs GMP, creating files<tt><gmp_prefix>/include/gmp.h</tt> and <tt><gmp_prefix>/lib/libgmp.a</tt>.<p>The options <tt>--disable-shared</tt> and <tt>--prefix=<gmp_prefix></tt>to <tt>configure</tt>are both optional.The first option disables the creation of shared libraries,which simplifies things just a bit (in particular, this documentation).If you don't pass the second option, then <tt><gmp_prefix></tt> defaults to <tt>/usr/local</tt>, and and you have to have root permissions to run <tt>make install</tt>.<p>Executing <tt>make uninstall</tt> undoes the <tt>make install</tt>.<p>Executing <tt>make distclean</tt> removes everythingcreated by <tt>configure</tt> and <tt>make</tt>.<p><h2>Building and using NTL with GMP</h2><p>When building NTL with GMP, you have to tell NTL that you want touse GMP as the primary long integer package, and where the include files and library are.The easiest way to do this is by passing the argument <tt>NTL_GMP_LIP=on</tt> to the configuration scriptwhen you are <a href="tour-unix.html">installing NTL</a>.That is, you execute:<pre> % ./configure NTL_GMP_LIP=on GMP_PREFIX=<gmp_prefix></pre>where <tt><gmp_prefix></tt> is the name of the directory inwhich GMP was installed above.<p>If you need more fine-grained control, you can execute:<pre> % ./configure NTL_GMP_LIP=on GMP_INCDIR=-I<gmp_prefix>/include GMP_LIBDIR=-L<gmp_prefix>/lib</pre>Alternatively, the following achieves more or less the same thing:<pre> % ./configure NTL_GMP_LIP=on CPPFLAGS=-I<gmp_prefix>/include LDFLAGS=-L<gmp_prefix>/lib</pre><p>If you installed GMP in a standard system directory,then<pre> % ./configure NTL_GMP_LIP=on</pre>does the job.<p>If instead you want to use GMP as a supplemental long integer package,you should pass the argument <tt>NTL_GMP_HACK=on</tt> to the configure script,instead of <tt>NTL_GMP_LIP=on</tt>.One still has to specify where to find GMP using the <tt>GMP_PREFIX</tt>variable in the configuration script.<p>Instead of passing arguments to the configure script,you can also just edit the <tt>config.h</tt> and makefile by hand.The documentation in these files should be self-explanatory.<p>When compiling programs that use NTL with GMP,you need to link with the GMP library.If GMP is not installed in a standard place, this just means adding<tt>-L<gmp_prefix>/lib -lgmp</tt> to the compilation command.If you installed GMP in a standard system directory,then just <tt>-lgmp</tt> does the job.<p>NTL has been tested and works correctly with GMP versions 3.1 and 3.1.1as the primary long integer package.It is not possible to use versions of GMP prior to 3.1 as theprimary long integer package.<p>NTL has been tested and works correctlywith versions 2.0.2, 3.0.1, 3.1, and 3.1.1 of GMP as a supplemental long integer package.It is not recommended to use versions of GMP prior to 3.1.1,as these are generally more buggy and less efficient.<p>When using NTL with GMP as either primary or supplementallong integer package, as a user of NTL, you do not need toknow or understand anything about the the GMP library.So while there is detailed documentation available about howto use GMP, you do not have to read it.The programming interface to the long integer package completely hides implementation details.<p><h2>Some implementation details</h2><p>When using GMP as the primary long integer package, the code used by NTL is essentially a layer of <tt>C</tt> routinesthat call the low level <tt>mpn</tt> routines in the GMP package.These NTL wrapper routines provide essentially the same functionality of the higher level <tt>mpz</tt> routines in GMP,but while presenting an interface to the rest of NTL that is almost identicalto that of thetraditional NTL long integer package.There are, however, some very minor backward incompatabilities <a href="#compat">(see below)</a>.<p>When using GMP as a supplemental long integer package,the code employsa "quick and dirty", yet fairly effective hack.This quick and dirtyapproach converts "on the fly"between the classic LIP and GMP representations.This makes the use of GMP <i>completely</i> invisible to higher layer software.Of course, there is a penalty: converting between representations takestime.For operations like addition, conversion would take longerthan performing the operation, and so it is not done.However, for computationally expensiveoperations like multiplication, the "overhead" is not so bad,at least for numbers that are not too small.To multiply two 256-bit numbers on a Pentium-II, the extra timerequired for the data conversions is just 35% of the time todo the multiplication in GMP, i.e., the "overhead" is 35%.For 512-bit numbers, the corresponding opportunity cost is about 14%,and for 1024-bit numbers, it is less than 10%.For smaller numbers, the opportunity cost is greater, butnever much worse than about 50%.<p><h2><a name="compat">Backward compatbility</a></h2><p>With version 5.0 of NTL, some aspects of the programming interfaceare 'deprecated' so as to allow the use of another long integer package,such as GMP, as the primary long integer package.<p>Prior to version 5.0, the macro <tt>NTL_NBITS</tt> was defined,along with the macro <tt>NTL_RADIX</tt> defined to be <tt>(1L << NTL_NBITS)</tt>.While these macros are still available when using NTL's traditionallong integer package (i.e., when <tt>NTL_GMP_LIP</tt> is not set),they are not available when using the GMP as the primary long integerpackage (i.e., when <tt>NTL_GMP_LIP</tt> is set).Furthermore, when writing portable programs, one should avoid these macros.<p>Also, the static function <tt>long ZZ::digit(const ZZ &);</tt>is defined when using traditional long integer arithmetic,but is not available when using GMP as the primary long integer package,and in any case, its use should be avoided when writing portable programs. <p>Instead of the above macros, one should use the followng macros:<pre> NTL_ZZ_NBITS -- number of bits in a zzigit; a ZZ is represented as a sequence of zzigits. NTL_SP_NBITS -- max number of bits in a "single-precision" number NTL_WSP_NBITS -- max number of bits in a "wide single-precision" number</pre><p>The following relations hold:<pre> NTL_SP_NBITS <= NTL_WSP_NBITS <= NTL_ZZ_NBITS 26 <= NTL_SP_NBITS <= min(NTL_BITS_PER_LONG-2, NTL_DOUBLE_PRECISION-3) NTL_WSP_NBITS <= NTL_BITS_PER_LONG-2</pre><p>Note that <tt>NTL_ZZ_NBITS</tt> may be less than, equal to, or greater than<tt>NTL_BITS_PER_LONG</tt> -- no particular relationship should be assumed to hold.In particular, expressions like <tt>(1L << NTL_ZZ_BITS)</tt>might overflow.<p>"single-precision" numbers are meant to be used in conjunction with thesingle-precision modular arithmetic routines.<p>"wide single-precision" numbers are meant to be used in conjunctionwith the <tt>ZZ</tt> arithmetic routines for optimal efficiency.<p>Note that when using traditional long integer arithmetic, we have<pre> NTL_ZZ_NBITS = NTL_SP_NBITS = NTL_WSP_NBITS = NTL_NBITS.</pre><p>The following auxilliary macros are also defined:<pre>NTL_FRADIX -- double-precision value of <tt>2^NTL_ZZ_NBITS</tt>NTL_SP_BOUND -- (1L << NTL_SP_NBITS)NTL_WSP_BOUND -- (1L << NTL_WSP_NBITS)</pre><p>Note that for a <tt>ZZ</tt> <tt>n</tt>,<tt>n.size()</tt> returns the number of "zzigits" of <tt>n</tt>.This is supported with either traditional or GMP integer arithemtic.Note, however, that some old codes might write <tt>n.size() <= 1</tt>as a way to test if <tt>NumBits(n) <= NTL_NBITS</tt>.This is no longer the right thing to do, if one wants portable codethat works with either traditional or GMP long integer arithmetic.First, one has to decide whether one wants to test if<tt>NumBits(n)</tt> is bounded by <tt>NTL_ZZ_NBITS</tt>, <tt>NTL_SP_NBITS</tt>, or <tt>NTL_WSP_NBITS</tt>.In the first case, <tt>n.size() <= 1</tt> is still the right way to test this.In the second case, write this as <tt>n.SinglePrecision()</tt>.In the third case, write this as <tt>n.WideSinglePrecision()</tt>.The routines <tt>SinglePrecision</tt> and <tt>WideSinglePrecision</tt>are new to NTL version 5.0.<p>Most "high level" applications that use NTL should not be affectedby these changes to NTL's programming interface, and if they are,changing the programs should be quite easy.<p> <hr> <p><p><center><a href="tour-impl.html"><img src="arrow1.gif" alt="[Previous]" align=bottom></a> <a href="tour.html"><img src="arrow2.gif" alt="[Up]" align=bottom></a> <a href="tour-time.html"> <img src="arrow3.gif" alt="[Next]" align=bottom></a></center></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -