[Previous] [Up] [Next]

A Tour of NTL: Programming Interface

In this section, we give a general overview of the NTL's programming interface. The following section has links to detailed documentation on each and every class and function.

Note that only those classes and functions documented in these pages are a part of the "official API": all other interfaces are subject to change without notice.

Basic Ring Classes

The basic ring classes are:

All these classes all support basic arithmetic operators 

   +, -, (unary) -, +=, -=, ++, --, 
   *, *=, /, /=, %, %=.

However, the operations 

   %, %=
only exist for integer and polynomial classes, and do not exist for classes 
  ZZ_p, zz_p, GF2, ZZ_pE, zz_pE, GF2E.

The standard equality operators (== and !=) are provided for each class. In addition, the class ZZ supports the usual inequality operators.

The integer and polynomial classes also support "shift operators" for left and right shifting. For polynomial classes, this means multiplication or division by a power of X.

Floating Point Classes

In addition to the above ring classes, NTL also provides three different floating point classes:

Vectors and Matrices

There are also vectors and matrices over 

   ZZ ZZ_p zz_p GF2 ZZ_pE zz_pE GF2E RR
which support the usual arithmetic operations.

Functional and Procedural forms

Generally, for any function defined by NTL, there is a functional form, and a procedural form. For example:

   ZZ x, a, n;
   x = InvMod(a, n);  // functional form
   InvMod(x, a, n);   // procedural form

This example illustrates the normal way these two forms differ syntactically. However, there are exceptions. First, if there is a operator that can play the role of the functional form, that is the notation used:

   ZZ x, a, b;
   x = a + b;    // functional form
   add(x, a, b); // procedural form

Second, if the functional form's name would be ambiguous, the return type is simply appended to its name:

   ZZ_p x;
   x = random_ZZ_p();  // functional form
   random(x);          // procedural form

Third, there are a number of conversion functions (see below), whose name in procedural form is conv, but whose name in functional form is conv<T>, where T is the return type:

   ZZ x;  
   double a;

   x = conv<ZZ>(a);  // functional form
   conv(x, a);       // procedural form

The use of the procedural form may be more efficient, since it will generally avoid the creation of a temporary object to store its result. However, it is generally silly to get too worked up about such efficiencies, and the functional form is usually preferable because the resulting code is usually easier to understand.

The above rules governing procedural and functional forms apply to essentially all of the arithmetic classes supported by NTL, with the exception of xdouble and quad_float. These two classes only support the functional/operator notation for arithmetic operations (but do support both forms for conversion).

Conversions and Promotions

As mentioned above, there are numerous explicit conversion routines, which come in both functional and procedural forms. A complete list of these can be found in conversions.txt. This is the only place these are documented; they do not appear in the other ".txt" files.

It is worth mentioning here, however, that generic conversion operators are provided for vectors and matrices, which act component-wise. For example, since there is a conversion from ZZ to RR, there is automatically a conversion from Vec<ZZ> to Vec<RR>.

Even though there are no implicit conversions, users of NTL can still have most of their benefits. This is because all of the basic arithmetic operations (in both their functional and procedural forms), comparison operators, and assignment are overloaded to get the effect of automatic "promotions". For example:

   ZZ x, a;

   x = a + 1;
   if (x < 0) 
      mul(x, 2, a);
   else
      x = -1;

These promotions are documented in the ".txt" files, usually using a kind of "short hand" notation. For example:

ZZ operator+(const ZZ& a, const ZZ& b);

// PROMOTIONS: operator + promotes long to ZZ on (a, b).

This means that in addition to the declared function, there are two other functions that are logically equivalent to the following:

ZZ operator+(long a, const ZZ& b) { return ZZ(a) + b; }
ZZ operator+(const ZZ& a, long b) { return a + ZZ(b); }

Note that this is not how NTL actually implements these functions. It is in generally more efficient to write

   x = y + 2;

than it is to write

   x = y + ZZ(2);

The former notation avoids the creation and destruction of a temporary ZZ object to hold the value 2.

Also, don't have any inhibitions about writing tests like

   if (x == 0) ...

and assignments like

   x = 1; 

These are all optimized, and do not execute significaltly slower than the "lower level" (and much less natural)

   if (IsZero(x)) ...

and

   set(x);

Some types have even more promotions. For example, the type ZZ_pX has promotions from long and ZZ_p. Thus, the add function for ZZ_pX takes the following argument types: 

   (ZZ_pX, ZZ_pX), (ZZ_pX, ZZ_p), (ZZ_pX, long), (ZZ_p, ZZ_pX), (long, ZZ_pX)
Each of these functions effectively converts the argument to be promoted to a ZZ_pX.

Note that when promoting a pair of arguments, at least one of the arguments must be of the target type.

I have tried to be very consistent with these promotions so that one usually won't need to hunt through the documentation. For a given type, there is a natural, fixed set of types that promote to it. Here is the complete list:

   destination  source
   
   xdouble      double
   quad_float   double
   RR           double
   ZZ           long
   ZZ_p         long
   ZZ_pX        long, ZZ_p
   zz_p         long
   zz_pX        long, zz_p
   ZZX          long, ZZ
   GF2          long
   GF2X         long, GF2
   GF2E         long, GF2
   GF2EX        long, GF2, GF2E
   ZZ_pE        long, ZZ_p
   ZZ_pEX       long, ZZ_p, ZZ_pE
   zz_pE        long, zz_p
   zz_pEX       long, zz_p, zz_pE

All the promotions are documented, but here are a few general rules describing the available promotions:

Some Conversion and Promotion Technicalities

Usually, conversions and promotions are semantically equivalent. There are three exceptions, however.

One exception is conversion of floating point double to ZZ. The safest way to do this is to apply an explicit conversion operator, and not to rely on promotions. For example, consider

   ZZ a; double x;

   a = a + x;

This is equivialent to

   a = a + long(x);

and to

   a = a + ZZ(x);

One could also use an explicit conversion function:

   a = a + conv<ZZ>(x);

This last version guarantees that there is no loss of precision, and also guarantees that the floor of x is computed. With the first version, one may lose precision when x is converted to a long, and also the direction of truncation for negative numbers is implementation dependent (usually truncating towards zero, instead of computing the floor).

The second exception is conversion of unsigned int or unsigned long to ZZ. Again, the safest way to do this is with an explicit conversion operator. As above, if one relies on promotions, the unsigned integer will be first converted to a signed long, which is most likely not what was intended.

The third exception can occur on 64-bit machines when converting a signed or unsigned long to one of NTL's extended precision floating-point types (RR or quad_float). These types only provide promotions from double, and converting a long to a double on a 64-bit machine can lead to a loss of precision. Again, if one uses the appropriate NTL conversion routine, no loss of precision will occur.

Another pitfall too avoid is initialzing ZZ's with integer constants that are too big. Consider the following:

   ZZ x;
   x = 1234567890123456789012;

This integer constant is too big, and this overflow condition may or may not cause your compiler to give you a warning or an error. The easiest way to introduce such large constants into your program is as follows:

   ZZ x;
   x = conv<ZZ>("1234567890123456789012");

Conversion functions are provided for converting C character strings to the types ZZ, RR, quad_float, and xdouble.

One should also be careful when converting to RR. All of these conversions round to the current working precision, which is usually, but not always, what one wants.

Input and Output

NTL provides input and output operators for all types, using the usual conventions for input and output streams. If an input error occurs, the "fail bit" of the input stream is set, and the input variable remains unchanged.

Although conversions from C-style character strings to the types ZZ, xdouble, quad_float, and RR are provided, one can always read and write to C++ character streams using the stringstream class from the standard library, in conjunction with the input and output operators provided by NTL.

Aliasing

An important feature of NTL is that aliasing of input and output parameters is generally allowed. For example, if you write mul(x, a, b), then a or b may alias (have the same address as) x (or any object that x contains, e.g., scalar/vector or scalar/polynomial multiplication).

One exception to this rule: the generic conversions provided for vectors and matrices assume that their inputs do not alias their outputs.

Constructors, Destructors, and Memory Management

NTL generally takes care of managing the space occupied by large, dynamically sized objects, like objects of class ZZ or any of NTL's dynamic vectors. However, it is helpful to understand a little of what is happening behind the scenes.

Almost all classes are implemented as a pointer, and the default constructor just sets this pointer to 0. Space is allocated for the object as needed, and when the object's destructor is called, the space is freed.

Copies are "deep" rather than "shallow". This means the data itself is copied, and not just a pointer to the data. If the destination object does not have enough space to hold the source data, then the space held by the destination object is "grown". This is done using the C routine realloc(). Note, however, that if the source object is smaller than the destination object, the space held by the destination object is retained. This strategy usually yields reasonable behaviour; however, one can take explicit control of the situation if necessary, since almost all NTL classes have a method kill() which frees all space held by the object, and sets its state to the default initial state (a value 0 or a zero-length vector).

The only exception to the above is the class ZZ_pContext, and the analogous classes for zz_p, ZZ_pE, zz_pE, and GF2E. These objects are implemented as referenced-counted pointers, and copies are "shallow".

While we are discussing initialization, there is one technical point worth mentioning. It is safe to declare global objects of any NTL type as long as one uses only the default constructor. For example, the global declarations

   ZZ global_integer;
   Vec<ZZ_p> global_vector;

should always work, since their initialization only involves setting a pointer to 0. However, one should avoid initializing global objects with non-default constructors, and should avoid doing anything that would lead to non-trivial computations with NTL objects prior to the beginning of the execution of routine main(). The reasons for this are quite esoteric and can only be appreciated by a true C++ afficianado. Actually, most such initializations and computations probably will work, but it is somewhat platform dependant.

Normal people usually do none of these things, so all of this should not matter too much. There is, however, one possible exception to this. A programmer might want to have a global constant initialized like this:

   const quad_float Pi = conv<quad_float>("3.1415926535897932384626433832795029");

While this probably will work fine on most platforms, it may not be an entirely portable construction, since it will involve a non-trivial computation before execution of main() begins. A more portable strategy is to define a function returning a read-only reference:

   const quad_float& Pi()
   {
      static quad_float pi = 
         conv<quad_float>("3.1415926535897932384626433832795029");
      return pi;
   }

and then call the function Pi() to get a read-only reference to this constant value:

   area = Pi()*r*r;

The initialization will then take place the first time Pi() is called, which is presumably after main() starts, and so everything should work fine. This is a very simple and general strategy that most C++ experts recommend using whenever the initialization of a non-global object requires non-trivial computation.

Residue class rings and modulus switching

NTL provides a number of classes to represent residue class rings: 

   ZZ_p, zz_p, GF2, ZZ_pE, lzz_pE, GF2E.
For each such class, except GF2, there is a global, current modulus.

We focus on the class ZZ_p, but similar comments apply to the other residue class types. For example, for ZZ_p, you can set the current modulus to p as follows:

   ZZ_p::init(p);

The current modulus must be initialized before any operations on ZZ_p's are performed. The modulus may be changed, and a mechanism is provided for saving and restoring a modulus.

Here is what you do to save the current modulus, temporarily set it to p, and automatically restore it:

   { 
      ZZ_pPush push(p); 

      ...

   }

The constructor for push will save the current modulus, and install p as the current modulus. The destructor for push will restore the old modulus when the scope enclosing it exits. This is the so-called RAII (resource acquisition is initialization) paradigm.

You could also do the following:

   {
      ZZ_pPush push; // just backup current modulus

        ...

      ZZ_p::init(p1); // install p1

        ...

      ZZ_p::init(p2); // install p2

      // reinstall original modulus at close of scope
   }

Warning: C++ syntax can be rather unfriendly sometimes. When using RAII objects like ZZ_pPush, watch out for the following errors:

   ZZ_pPush push();  // ERROR: local declaration of a function!!
   ZZ_pPush(p);      // ERROR: temporary RAII-object created and
                     //        immediately destroyed!!

Unfortunately, most compilers do not issue any warnings in these situations. I have fallen into both traps myself.

The ZZ_pPush interface is good for implementing simple stack-like "context switching". For more general context switching, use the class ZZ_pContext:

   ZZ_p::init(p);     // set current modulus to p

      ...

   ZZ_pContext context;
   context.save();    // save the current modulus p

      ...

   ZZ_p::init(q);     // set current modulus to q

      ...
  
   context.restore(); // restore p as the current modulus

Note that ZZ_pContext's are essentially "smart pointers", and they may be copied. Generally speaking, saving, restoring, and copying ZZ_pContext's are very cheap operations. Likewise, saving and restoring contexts using ZZ_pPush objects are very cheap operations.

It is critical that ZZ_p objects created under one ZZ_p modulus are not used in any non-trivial way "out of context", i.e., under a different (or undefined) ZZ_p modulus. However, for ease-of-use, some operations may be safely performed out of context. These safe operations include: the default and copy constructor, the destructor, and the assignment operator. In addition it is generally safe to read any ZZ_p object out of context (i.e., printing it out, or fetching its underlying representive using the rep() function).

Any unsafe uses out of context are not in general checked, and may lead to unpredictable behavior.

The implementations of Vec<ZZ_p>, Vec<GF2E>, and Vec<GF2> are specialized to manage memory more efficiently than in the default implementation of Vec<T>:

C+11 Support

As of version 10.4, NTL supports a number of C++11 specific features. To enable this support, you must build NTL with NTL_STD_CXX11=on. This build flag is automatically turned on by a number of other NTL features that require NTL support.

The most important of these is "move semantics". Most of the important classes are now equipped with "move" constructors and "move" assignment operators. Where possible, these are declared noexcept. NTL's Vec class and STL's vector class can take advantage of noexcept move constructors in certain situations. See below for more details regarding exceptions and move semantics.

Error Handling and Exceptions

Prior to version 8.0 of NTL, errors were dealt with in a simlple way: print an error message and abort. As of version 8.0, NTL provides error handling with exceptions. To use this feature, you will need to configure NTL with the NTL_EXCEPTIONS flag turned on. You will also need a C++11 compiler.

The exceptions thrown by NTL are either a std::bad_alloc exception (in case of memory allocation error), or a class (defined in namespace NTL) derived from std::runtime_error:

All of these error objects override the what() method of std::exception with an appropriate error message.

There is also a special exception class InvModErrorObject, which is derived from ArithmeticErrorObject, and is thrown when a modular inverse computation over ZZ fails (either directly, or indirectly through PowerMod computation, or via an inverse computation in ZZ_p). The InvModErrorObject provides two methods, get_a() and get_n(), which provide read-only references to the offending objects a and n (so GCD(a, n) != 1).

The generic class ErrorObject is not thrown directly by any NTL routines, except for the legacy function Error, which is no longer called by any NTL routines. New functions 

   MemoryError, LogicError, ArithmeticError, ResourceError, FileError, InputError
are used to throw exceptions derived from ErrorObject.

Efficiency considerations: Because of a bunch of design decsions that were made long before C++11 came along, most of the important NTL classes do not have noexcept move constructors if you enable exceptions in NTL, which can reduce performance somewhat. Therefore, if you do not really need to have NTL handle errors by throwing exceptions, and you do want to maximize performance, you should not enable exceptions in NTL. But even with exceptions enabled, the performance penalty should not be terrible.

Issues with GMP: GMP itself (at least as of version 6.1.2) provides only the very crude print-message-then-abort error handling. Note that NTL only uses low-level GMP routines (the mpn-level routines), and these routines should only abort if they cannot allocate space for temporary big integers within GMP itself. So this should only be an issue of you are working with some very large integers. The GMP developers are working on improving their error handling. When that happens, NTL will inherit these improvements. If you really need proper error handling, and are willing to pay a certain performance penalty, then you should configure and build NTL without GMP.

Issues with gf2x: Similar comments apply to NTL builds that use the gf2x library.

Exception safety: I have tried to carefully document exception safety characterstics for just a few, critical, low-level classes: vectors and matrices (vector.txt and matrix.txt), smart pointer classes (SmartPtr.txt), thread-safe lazy initialization classes (Lazy.txt and LazyTable.txt). Otherwise, it is only safe to assume that NTL functions provide a weak exception-safety guarantee: if an exception is thrown, the stack unwinding process will will not leak any resources and will leave all modified objects in a reasonable state: at least, such objects may be safely destroyed, and may also be assigned to or reset; however, they may not necessarily be safely used as inputs to other functions. When stronger exception safety is required, you can always compute results into dynamically allocated objects pointed to by "smart pointers", and then move or swap these pointers into place after all computations have succeeded.

As NTL provides swap functions for all its major classes, and as swap functions have evolved to play a critical role in writing exception-safe code, they deserve a special mention here:

These rules are unfortunatley a bit complicated, due to NTL's historical legacy, and to its special memory management of ZZVec, Vec<ZZ_p>, GF2XVec, and Vec<GF2E> types.

[Previous] [Up] [Next]