doc/tour-gmp.html

<html>
<head>
<title>
A Tour of NTL: Using NTL with GMP  </title>
</head>


<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-gf2x.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 version
from <a href="http://gmplib.org">here.</a>

<p>

Briefly, GMP is a library for long integer arithmetic.
It has hand-crafted assembly routines for a wide variety
of architectures.
For basic operations, like integer multiplication, it can be 
two to three (and sometimes bit more) times faster than NTL's
traditional long integer package.
The speedup is most dramatic on x86 machines.

<p>
By default, NTL uses a long integer package derived
from Arjen Lenstra's LIP package.
However, for extra speed, it is recommended to use GMP.
Building NTL with GMP 
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 systems
and on Windows systems using Cygwin tools.

<p>
Even if you do not use GMP,
you should still read the <a href="#compat">section below
on backward compatabilty</a>
so that you can write portable code and avoid deprecated constructs.

<p>
<b>Note:</b> GMP is thread safe, so you should feel free to use it
in a thread-safe build of NTL.
However, the current version (v6) 
is <i>not</i> entirely exception friendly (it may
abort a running program, but only in some very extreme and
unusal circumstances).


<p>
<h2>
Downloading and building GMP
</h2>
<p>

Download GMP from <a href="http://gmplib.org">here.</a>
You will get a file <tt>gmp-XXX.tar.gz</tt>.
<p>
Now do the following:
<pre>
   % gunzip gmp-XXX.tar.gz
   % tar xf gmp-XXX.tar
   % cd gmp-XXX
   % ./configure --prefix=$HOME/sw
   % make
   % make check
   % make install
</pre>
This will build, test, and install GMP in <tt>$HOME/sw</tt>.
Of course, change $HOME/sw to whatever you want (the default is 
<tt>/usr/local</tt>).
You will find the GMP header files in <tt>$HOME/sw/include</tt> 
and the compiled binaries in <tt>$HOME/sw/lib</tt>.

<p>
You can also supply the option
<tt>--disable-shared</tt> to the <tt>configure</tt> script,
if you only want static libraries.
However, if you ultimately want to build NTL as a shared
library, then you must also buld GMP as a shared library.

<p>
You must ensure that NTL and GMP have the same 
<a href="tour-unix.html#abi">ABI</a>.
Usually, GMP's configure script will automatically
choose a 64-bit ABI if available.


<p>
<h2>
Building and using NTL with GMP
</h2>
<p>

When building NTL with GMP, you have to tell NTL that you want to
use GMP as the 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 NTL configuration script
when you are <a href="tour-unix.html">installing NTL</a>.
Assuming you installed GMP in <tt>$HOME/sw</tt> as above,
and you also want to install NTL in <tt>$HOME/sw</tt>,
you execute:
<pre>
   % ./configure PREFIX=$HOME/sw NTL_GMP_LIP=on  GMP_PREFIX=$HOME/sw
</pre>
You can write this more simply as 
<pre>
   % ./configure DEF_PREFIX=$HOME/sw NTL_GMP_LIP=on 
</pre>
Here, <tt>DEF_PREFIX</tt> is a variable that is used
to specify the location of all software,
and it defaults to <tt>/usr/local</tt>.


<p>
If you installed GMP in <tt>/usr/local</tt> (or some other
standard system directory where your compiler will look by default)
then simply
<pre>
   % ./configure PREFIX=$HOME/sw NTL_GMP_LIP=on
</pre>
does the job.
Moreover, if NTL is also to be installed in <tt>/usr/local</tt>,
then
<pre>
   % ./configure NTL_GMP_LIP=on
</pre>
does the job.

<p>
Instead of passing arguments to the configure script,
you can also just edit the <tt>config.h</tt> and <tt>makefile</tt> 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 installed as above in 
<tt>$HOME/sw</tt>, rather than in a standard system directory,
 this just means adding
<tt>-L$HOME/sw/lib -lgmp</tt> to the compilation command.
If you installed GMP in a standard system directory,
then just <tt>-lgmp</tt> does the job.
Note that <tt>-lgmp</tt> must come <i>after</i> <tt>-lntl</tt>
on the command line.
Finally, if NTL is installed 
a shared libraries, then you don't even need <tt>-lgmp</tt>.


<p>
NTL has been tested and works correctly with GMP versions 3.1,  3.1.1,
4.1.4, and 5.1 (among others).
It is not possible to use versions of GMP prior to 3.1 with NTL.

<p>
When using NTL with GMP, 
as a user of NTL, you do not need to
know or understand anything about the the GMP library.
So while there is detailed documentation available about how
to use GMP, you do not have to read it.
The programming interface to the long integer package 
completely hides implementation details.


<p>
<h2>
<a name="compat">
Backward compatbility
</a>
</h2>
<p>

With version 5.0 of NTL, some aspects of the programming interface
are 'deprecated' so as to allow the use of another long integer package,
such as GMP, as the 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 &lt;&lt; NTL_NBITS)</tt>.
While these macros are still available when using NTL's traditional
long integer package (i.e., when <tt>NTL_GMP_LIP</tt> is not set),
they are not available when using the GMP as the long integer
package (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 &amp;, long);</tt>
is defined when using traditional long integer arithmetic,
but is not available when using GMP as the 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 &lt;= NTL_WSP_NBITS &lt;= NTL_ZZ_NBITS
   26 &lt;= NTL_SP_NBITS &lt;= min(NTL_BITS_PER_LONG-2, NTL_DOUBLE_PRECISION-3)
   NTL_WSP_NBITS &lt;= 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 &lt;&lt; NTL_ZZ_BITS)</tt>
might overflow.

<p>
"single-precision" numbers are meant to be used in conjunction with the
single-precision modular arithmetic routines.

<p>
"wide single-precision" numbers are meant to be used in conjunction
with 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 &lt;&lt; NTL_SP_NBITS)
NTL_WSP_BOUND -- (1L &lt;&lt; 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() &lt;= 1</tt>
as a way to test if <tt>NumBits(n) &lt;= NTL_NBITS</tt>.
This is no longer the right thing to do, if one wants portable code
that 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() &lt;= 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 affected
by 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-gf2x.html"> <img src="arrow3.gif" alt="[Next]" align=bottom></a>
</center>


</body>
</html>