📄 tour-struct.html
字号:
<html><head><title>A Tour of NTL: Programming Interface </title></head><body bgcolor="#fff9e6"><center><a href="tour-examples.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-modules.html"> <img src="arrow3.gif" alt="[Next]" align=bottom></a></center><h1> <p align=center>A Tour of NTL: Programming Interface </p></h1><p> <hr> <p>In this section, we give a general overview of the NTL's programming interface.<p><p><h3>Basic Ring Classes</h3><p>The basic ring classes are:<ul><li><tt>ZZ</tt>: big integers<li><tt>ZZ_p</tt>: big integers modulo <tt>p</tt><li><tt>zz_p</tt>: integers mod "single precision" <tt>p</tt><li><tt>GF2</tt>: integers mod 2<li><tt>ZZX</tt>: univariate polynomials over <tt>ZZ</tt><li><tt>ZZ_pX</tt>: univariate polynomials over <tt>ZZ_p</tt><li><tt>zz_pX</tt>: univariate polynomials over <tt>zz_p</tt><li><tt>GF2X</tt>: polynomials over GF2<li><tt>ZZ_pE</tt>: ring/field extension over ZZ_p<li><tt>zz_pE</tt>: ring/field extension over zz_p<li><tt>GF2E</tt>: ring/field extension over GF2<li><tt>ZZ_pEX</tt>: univariate polynomials over <tt>ZZ_pE</tt><li><tt>zz_pEX</tt>: univariate polynomials over <tt>zz_pE</tt><li><tt>GF2EX</tt>: univariate polynomials over <tt>GF2E</tt></ul><p>All these classes all support basicarithmetic operators<pre> +, -, (unary) -, +=, -=, ++, --, *, *=, /, /=, %, %=.</pre><p>However, the operations <pre> %, %=</pre>only exist for integer and polynomial classes, and do not existfor classes <pre> ZZ_p, zz_p, GF2, ZZ_pE, zz_pE, GF2E.</pre><p>The standard equality operators (<tt>==</tt> and <tt>!=</tt>)are provided for each class.In addition, the class <tt>ZZ</tt>supports the usual inequalityoperators.<p>The integer and polynomial classes also support "shift operators"for left and right shifting.For polynomial classes, this means multiplication or divisionby a power of <tt>X</tt>.<p><p><h3>Floating Point Classes</h3><p>In addition to the above ring classes, NTL also provides threedifferent floating point classes: <ul><li><tt>xdouble</tt>: "double precision" floating point withextended exponent range (for very large numbers);<li><tt>quad_float</tt>: "quasi" quadruple-precision floating point;<li><tt>RR</tt>: aribitrary precision floating point.</ul><p><p><h3>Vectors and Matrices</h3><p>There are also vectors and matrices over <pre> ZZ ZZ_p zz_p GF2 ZZ_pE zz_pE GF2E RR</pre>which support the usual arithmetic operations.<p><p><h3>Functional and Procedural forms</h3><p>Generally, for any function defined by NTL, there is a functional form, and a procedural form.For example:<pre> ZZ x, a, n; x = InvMod(a, n); // functional form InvMod(x, a, n); // procedural form</pre><p>This example illustrates the normal way these two forms differsyntactically.However, there are exceptions.First, if there is a operator that can play the role of thefunctional form, that is the notation used:<pre> ZZ x, a, b; x = a + b; // functional form add(x, a, b); // procedural form</pre>Second, if the functional form's name would be ambiguous,the return type is simply appended to its name:<pre> ZZ_p x; x = random_ZZ_p(); // functional form random(x); // procedural form</pre>Third, there are a number of conversion functions (see below), whose namein procedural form is <tt>conv</tt>, but whose name in functioanl form is <tt>to_T</tt>, where <tt>T</tt> is the return type:<pre> ZZ x; double a; x = to_ZZ(a); // functional form conv(x, a); // procedural form</pre><p>The use of the procedural form may be more efficient,since it will generally avoid the creation of a temporary objectto store its result.However, it is generally silly to get too worked up aboutsuch efficiencies, and the functional form is usually preferablebecause the resulting code is usually easier to understand.<p>The above rules converning procedural and functional forms applyto essentially all of the arithmetic classes supported by NTL,with the exception of<tt>xdouble</tt> and <tt>quad_float</tt>.These two classes only support the functional/operator notationfor arithmetic operations (but do support both forms for conversion).<p><p><h3>Conversions and Promotions</h3><p>NTL does not provide automatic conversions from, say,<tt>int</tt> to <tt>ZZ</tt>.Most <tt>C++</tt> experts consider such automatic conversionsbad form in library design, and I would agree with them.Some earlier versions of NTL had automatic conversions,but they caused too much trouble, so I took them out.Indeed, combining function overloading and automatic conversionsis generally considered by programming language expertsto be a bad idea (but that did not stopthe designers of <tt>C++</tt> from doing it).It makes it very difficult to figure out which functionought to be called.<tt>C++</tt> has an incredibly complex set of rules for doing this;moreover, these rules have been changing over time,and no two compilers seem to implement exactly the sameset of rules.And if a compiler has a hard time doing this, imagine what itis like for a programmer.In fact, the rules have become so complicated, that the latestedition of Stroustrup's <tt>C++</tt> book does not even explain them,althoughearlier verisons did.Possible explanations:<em>(a)</em> Stroustrup thinks his readers are too stupid to understand the rules, or<em>(b)</em> Stroustrup does not understand the rules, or<em>(c)</em> the rules are so complicated that Stroustrup finds it embarassingto talk about them.<p>Now it should be more clear why I didn't just implement,say, the <tt>int</tt> to <tt>ZZ</tt> conversion functionas a <tt>ZZ</tt> constructor taking an argument of type <tt>int</tt>,instead of calling it <tt>to_ZZ</tt>.This would have introduced an automatic conversion, which Iwanted to avoid for the reasons explained above."OK. But why not make the constructor <tt>explict</tt>?" you ask.The main reason is that this is a fairly recently introducedlanguage feature that is not universally available.And even if it were, what about, say, the <tt>ZZ</tt> to <tt>int</tt>conversion routine?How would you name <em>that</em>?The strategy I chose is simple, consistent, and portable.<p>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 <a href="conversions.txt">conversions.txt</a>.This is the only place these are documented; they do not appearin the ".txt" files.<p>Even though there are no automatic conversions, usersof NTL can still have most of their benefits, whileavoiding their pitfalls.This is because all of the basic arithmetic operations (in both their functional and procedural forms),comparison operators, and assignment are overloadedto get the effect of automatic "promotions".For example:<pre> ZZ x, a; x = a + 1; if (x < 0) mul(x, 2, a); else x = -1;</pre><p>These promotions are documented in the ".txt" files, usually using a kind of "short hand" notation.For example:<pre>ZZ operator+(const ZZ& a, const ZZ& b);// PROMOTIONS: operator + promotes long to ZZ on (a, b).</pre>This means that in addition to the declared function, thereare two other functions that are logically equivalent to the following:<pre>ZZ operator+(long a, const ZZ& b) { return to_ZZ(a) + b; }ZZ operator+(const ZZ& a, long b) { return a + to_ZZ(b); }</pre><p>Note that this is not how NTL actually implements these functions.It is in generally more efficient to write<pre> x = y + 2;</pre>than it is to write<pre> x = y + to_ZZ(2);</pre>The former notation avoids the creation and destructionof a temporary <tt>ZZ</tt>object to hold the value 2.<p>Also, don't have any inhibitions about writing tests like<pre> if (x == 0) ...</pre>and assignments like<pre> x = 1; </pre>These are all optimized, and do not execute significaltly slowerthan the "lower level" (and much less natural) <pre> if (IsZero(x)) ...</pre>and<pre> set(x);</pre><p>Some types have even more promotions.For example, the type <tt>ZZ_pX</tt> has promotionsfrom <tt>long</tt> and <tt>ZZ_p</tt>.Thus, the <tt>add</tt> function for <tt>ZZ_pX</tt> takes the following argument types:⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -