Since there is no single best algorithm to compute a particular function, in many cases NTTL implements several different algorithms for computing the same function. In the case of gcd, for instance, the standard Euclidean algorithm is implemented, as are the left and right binary algorithms (planned, as well as the left and right windowing algorithms).
Although the binary gcd algorithms are generally considered more efficient than the Euclidean algorithm, the binary algorithms assume that the operands can be represented in a certain form. This may not always be the case. For instance, if the operands are integers represented in CRR, then it may be very inefficient to extract the value of a particular bit. This renders the binary algorithms of little value.
For this reason (and others), it is important that the user be able to select a particular algorithms among those available. Traditionally, this requirement would have been handled by simply giving each of the algorithms a different name. If the user wanted to use the left-shift binary algorithm, then they would simply write their code to call that algorithm:
In another context, this is very inconvienient. Let us assume that the user does not know, a priori, which of the various algorithms is best suited to the current application. The user would like to run several trials, trying each of the algorithms in their application. With the previous solution, the user would be forced to replace every occurance of GCDLBS with GCDRBS, when changing from the left-shift binary algorithm, to the right-shift binary algorithm (for example). This can be very annoying. The user could, of course, minimize the changes by setting up a macro or an inline function, and using that in their application code. It would be far better, of course, if the library were setup so that this situation were handled by the library, not the user.
In NTTL, this issue is, in fact, handled in the library. The user codes the application using a generic function name. In the GCD case, for example, the name of the function is GCD( ). The algorithm used is determined by the header file #included:
#include <gcdLBS.h> main( ) { ... long d = GCD( u, v ); // left-shift binary algorithm ... }
By simply changing the header file that is #included, the user can change the algorithm used for the GCD calculation:
#include <gcdEuclid.h> main( ) { ... long d = GCD( u, v ); // now the Euclidean algorithm ... }
Multiple algorithms can be used in the same program, simply by #including multiple headers. The generic function (GCD( ), in this case) is defined by the first header file included (techniques are available to alter this, but this gets into the realm of the C++ guru). A generic header file, gcd.h, is also available. This header defines a generally acceptable default for the generic GCD function.
How is this technique implemented? Each header for an algorithm also contains a defintion of the generic function. The generic fuction is an inline template function that simply calls the specific function defined in that header. Since the generic function is inlined, there should be no runtime overhead. Macros prevent the generic function from being defined mutliple times, should multiple algorithms for the same function be included. This will probably be made more clear by looking at an example.
The following example shows the outline of three of the header files used to implement the GCD function. There are two different algorithms represented: the standard Euclidean algorithm, and the left-shift binary algorithm. Each of these algorithms is contained in a separate header file. The third header file is a generic header that implements a default for the GCD function. This is keeping with the idea that simple things should be simple to do; that only when the user is trying to optimize things should they have to worry about the ideas presented here. (learning curve increase with user sophistication, not the other way around).
The following is the outlline of the header for the Euclidean algorithm:
#ifndef __nttlHeader_gcdEuclid__
#define __nttlHeader_gcdEuclid__
tempate< class T >
T
GCDEuclid( T u, T v )
{
...
}
#ifndef __nttlAlgorithm_gcd__
#define __nttlAlgorithm_gcd__
template< class T >
T
GCD( T u, T v )
{
return GCDEuclid( u, v );
}
#endif // __nttlAlgorithm_gcd__
#endif // __nttlHeader_gcdEuclid__
|
Some things to note, here. The first #ifndef/#define pair is the standard idiom to prevent the contents of the header file from being declared multiple times within the same program scope. After this is the declaration of the Euclean GCD algorithm. Note that it has a unique name, GCDEuclid, so that it can be called directly.
Following the declaration of GCDEuclid is another #ifndef/#define pair. This time, it is preventing the generic GCD function from being declared twice. If multiple GCD headers are included in the same program scope, the library must prevent both headers from declaring the generic GCD function. Finally, there are the #endif statements for the two #ifndef/#define pairs already discussed.
The header file for the left-shift binary algorithm is very similar:
#ifndef __nttlHeader_gcdLBS__
#define __nttlHeader_gcdLBS__
template< class T >
T
GCDLBS( T u, T v )
{
...
}
#ifndef __nttlAlgorithm_gcd__
#define __nttlAlgorithm_gcd__
template< class T >
T
GCD( T u, T v )
{
return GCDLBS( u, v );
}
#endif // __nttlAlgorithm_gcd__
#endif // __nttlHeader_gcdLBS__
|
Note that this header also declares a GCD function. The #ifndef/#define pair immediately preceeding this declaration, however, will prevent it from actually being processed if another header has already declared it.
Finally, there is the default GCD header:
#ifndef __nttlHeader_gcd__
#define __nttlHeader_gcd__
#ifndef __nttlAlgorithm_gcd__
#define __nttlAlgorithm_gcd__
#include <nttl/gcdEuclid.h>
template< class T >
T
GCD( T u, T v )
{
return GCDEuclid( u, v );
}
#endif // __nttlAlgorithm_gcd__
#endif // __nttlHeader_gcd__
|
If another header has not already declared the generic GCD function, then this header #includes the header for the Euclidean algorithm (a good, general purpose choice for the default), and declares an inline template function that wraps the Euclidean function.
This technique provides a good solution to the problem outlined earlier. It is not without its drawbacks, however. Use of this method imposes an ordering on the headers. For instance, the Chinese Remainder Algorithm (CRA) uses the Extended GCD (EGCD) function. In order for the CRA to be usable by itself, it must include the header for EGCD. But this would declare the generic EGCD function. If the user wish to use one of the binary algorithms, then the header for the binary algorithm must be included before the header for the CRA:
#include <chineseRemainder.h> // also includes egcd.h #include <egcdLSB.h> // does not declare EGCD( ), since // that was done above main( ) { ... long d = EGCD( u, v, &a, &b ); // does not use the // left-shift binary // algorithm! ... }
The header dependency list, and the order in which headers should be included, are elsewhere in the documentation <include a link here>.
It may be desirable to implement compiler warning messages to let the NTTL user know that there is a possible conflict in the definition of the generic function. For instance, the declaration of the generic GCD function could be written as follows (from GCDEuclid.h):
#ifdef __nttlAlgorithm_gcd__ #warning (__FILE__) Default GCD fuction already defined. The \ Euclidean algorithm will *not* be used. #else #define __nttlAlgorithm_gcd__ template< class T > T GCD( T u, T v ) { return GCDEuclid( u, v ); } #endif // __nttlAlgorithm_gcd__
gcd.h would not be coded to emit such a warning. In this way, the user would be warned about the possible header ordering problem (the message text above should probably be reconsidered).