tour-changes.html

数值算法库for Windows

and added ZZ/byte array conversions.

<li>
Improved performance of primality test, and added a 
more convenient routine <tt>GenPrime</tt>.

<li>
Overloaded NTL's vector placement "new" operator in a different
way to avoid conflicts with standard <tt>C++</tt> library.

<li>
Renamed many macros.

<li>
Renamed header files.

<li>
Made some changes to the packaging
the installation procedure.

</ul>

<p>
<b>Renamed Macros.</b>
I renamed many macros defined in NTL header files.

<p>
The reason is that I want to minimize namespace pollution.
Someday, NTL will be wrapped in a namespace, and when that happens
the only remaining namespace pollution problems will be caused by macros.
Eliminating all macros from NTL is not feasible.
Instead, all NTL defined macros now begin with the prefix "NTL_",
which reduces the namespace pollution to an ecceptable level.
You will probably not be affected by this, unless you
do some low level hacking using a macro like <tt>ZZ_NBITS</tt>
(now called <tt>NTL_NBITS</tt>), or unless you create your
own NTL vectors using a macro like <tt>ntl_vector_decl</tt>
(now called <tt>NTL_vector_decl</tt>).

<p>
For a complete list of affected names, see <a href="names.txt">names.txt</a>.

<p>
Adapting to this name change should be painless, as there is a 
program to translate source files from the old naming convention to the new.
The file "newnames.c", 
can be compiled as either a <tt>C</tt> or <tt>C++</tt>
program. 
The program is a "filter" that copies its input to its output,
replacing all the old macro names by the new macro names.
<p>
In the WinNTL distribibution, "newnames.c" is called 
"newnames.cpp" and is located in the directory
"newnames".


<p>
<b>Renamed header files.</b>
The names of header files themeselves pollute another (extra-linguitsic) namespace.
To alleviate this problem, the header files have been renamed.
Instead of
<pre>
   #include "foo.h"
</pre>
one now should write
<pre>
   #include &lt;NTL/foo.h&gt;
</pre>
The only exceptions are the old header files "ntl_vector.h",
"ntl_matrix.h", and "ntl_pair.h", which are now called
<tt>&lt;NTL/vector.h&gt;</tt>, <tt>&lt;NTL/matrix.h&gt;</tt>, and 
<tt>&lt;NTL/pair.h&gt;</tt>.

<p>
<b>Installation procedure.</b>
Now all
NTL flags like NTL_LONG_LONG, NTL_AVOID_FLOAT, etc., can  now be set
by editing the special file "include/NTL/config.h".
See details in that file.
The reason for this change is that this allows all of these settings
to be made when NTL is configured and built.
Clients of NTL will then automatically use consistent settings.
One should not set these flags on the compiler command line as previously.


<p>
Pentium/Linux people should no longer have to worry
about the NTL_X86_FIX flag. NTL now psychically deduces
the "right thing to do", although if its psychic abilities fail,
you can override it with flags in "include/NTL/config.h".

<p>
The "packaging" in the Unix distribution is slightly
different, but hopefully nicer.
Among other things, the tar file now unpacks into a sub-directory of the current directory.
See <a href="tour-unix.html">the unix installation section</a>
for more details.
The Windows zip file now also 
unpacks into  sub-directory.


<p>
<b>My apologies.</b>
Although these changes are minor, they will cause some NTL
users some inconvenience.
I apologize for this.
I really, really hope there are no more changes like this
(see my <a href="tour-roadmap.html">roadmap</a> of NTL's future).

<p>
<hr>


<p>
<h3>
Changes between NTL 3.1a and 3.1b
</h3>
<p>

Defined functions <tt>div(GF2X,GF2X,GF2)</tt> and <tt>div(GF2X,GF2X,long)</tt>,
which had not been defined in earlier versions.
Affected file: <tt>GF2X.c</tt>.
Most programs never use this, and most linkers do not complain
if these are missing (but some do).

<p>
<hr>

<p>
<h3>
Changes between NTL 3.0f and 3.1a
</h3>
<p>

This version is backward compatible with previous versions.

<p>

<ul>
<li>
Added floating point LLL routines based on Givens rotations,
instead of classical Gramm-Schmidt orthogonalization.
This is a more stable, but somewhat slower, method.
See <a href="LLL.txt">LLL.txt</a> for details.

<li>
Added support for irreducible trinomials and pentanomials
over GF(2). The <tt>GF2XModulus</tt> routines,
and by extension, the <tt>GF2E</tt> routines,
now exploit moduli of this special form.
The new routine <tt>BuildSparseIrred</tt> in <tt>GF2XFactoring</tt>
builds irreducibles of this form.

<li>
Also implemented a faster modular inversion routine
for <tt>GF2X</tt>, and improved the performance of <tt>ZZ_pX</tt>
multiplication for small degree polynomials.
</ul>

<p>
<hr>

<p>
<h3>
Changes between NTL 3.0e and 3.0f
</h3>
<p>

<ul>
<li>
Fixed a bug (another one) affecting routines
<pre>
   RandomBits, RandomBits_ZZ
</pre>
in module <tt>ZZ</tt>.
Affected source file: <tt>lip.c</tt>.

<li>
Bug fix and performance tweak in <tt>ZZX</tt> factorizer.
Affected source file: <tt>ZZXFactoring.c</tt>.
   
</ul>

<p>
<hr>

<p>
<h3>
Changes between NTL 3.0 and 3.0e
</h3>
<p>

<ul>
<li>
Fixed a bug affecting routines 
<pre>
   RandomBits, RandomBits_ZZ, RandomBits_long
</pre>
in module <tt>ZZ</tt>.
The only source files that are affected and require re-compilation are
<pre>
   ZZ.c, lip.c
</pre>

<li>
Note about names:
3.0a-c were "pre-releases", which makes the "first release" 3.0d,
and hence this bug fix 3.0e.
   
</ul>

<p>
<hr>


<p>

<h3>
Changes between NTL 2.0 and 3.0
</h3>
<p>


<ul>

<li>
Added functionality:
<p>

<ul>

<li>
Added classes vec_GF2 and mat_GF2 for fast linear algebra over GF(2).

<li>
Added classes ZZ_pE, ZZ_pEX, zz_pE, zz_pEX, supporting polynomial
arithmetic over extension rings/fields over prime fields.

<li>
Added John Abbott's pruning heuristic to the ZZX factoring routine.

<li>
Speeded up multiplication in zz_pX for small p (this also helps
the ZZX factoring routine).

<li>
Added some some transcendental functions (e.g., exp, log, pi) to RR.

<li>
Added verbose mode and pruning to the XD and RR variants of LLL.

</ul>
<p>

<li>
Improved programming interface:
with this version, I've taken an the opportunity to 
give the programming interface a "professional facelift".
In previous releases, I've tried to maintain backward compatability
as much as possible, but to make the badly needed improvements
to the interface that I've made with this release, this was not
possible.
<p>
NTL 3.0 is not backward compatable with NTL 2.0.
<p>
I apologize to NTL users for this, but it is a bit of painful
medicine that should only be necessary to take just this one time
(but then as a <tt>C++</tt> programmer, you must already
be used to suffering ;-).
Just about all of the incompatabilities are detectable by the compiler.
See below for a detailed list of the changes and
some tips on making the transition.
<p>
The new interface is much more enjoyable to work with,
and I don't foresee any changes to the interace in the future.
Here is a broad overview of the changes:
<p>

<ul>
<li>
Added functional/operator notation consistently throughout NTL,
making it possible to write much more concise and readable code.
<li>
Got rid of automatic type conversions:  these cause just too
many problems.  But I've overloaded all of the basic arithmetic
operators and procedures so as to emulate a natural kind
of "type promotion" logic.  With these promotions, along with
a  full compliment of conversion functions, one hardly misses
the automatic conversions.
<li>
Got rid of the macros
<pre>
   vector(T), matrix(T), pair(T),
</pre>
which were causing too many name space problems.

<li>
Made assignment operators have the "correct" return type.
<li>
Introduced a more powerful and flexible mechanism for modulus changing.
<li>
Cleaned up numerous other minor problems.
</ul>

</ul>

<p>
<h4>
Compatibility
</h4>
<p>

Here is a detailed list of the changes to the programming 
interface.
<p>


<ul>

<li>
The names of the classes 
<pre>
   BB, BB_p, BB_pX
</pre>
have been changed to
<pre>
   GF2X, GF2E, GF2EX
</pre>

<li>
There is also a class <tt>GF2</tt> to represent GF(2).
Many of the functions relating to <tt>BB, BB_p, BB_pX</tt>
had argument and return-value types of type <tt>long</tt>
that are now of the more appropriate type <tt>GF2</tt>.
This change was needed so that the interface would be consistent
with that of the new classes
<pre>
   ZZ_pE, ZZ_pEX, zz_pE, zz_pEX.
</pre>

<li>
The explicit conversion operator from <tt>GF2X</tt> 
(the new <tt>BB</tt>) to <tt>GF2EX</tt> (the new <tt>BB_pX</tt>)
has different semantics: it now performs a coefficient lift,
instead of creating a constant polynomial.

<li>
The conversion operator "<tt>&lt;&lt;</tt>" has been retired.
Now instead of
<pre>
   x &lt;&lt; a; 
</pre>
one writes
<pre>
   conv(x, a);
</pre>
<p>
Operator "<tt>&lt;&lt;</tt>" is now used for shift operations.
<li>
Every conversion routine now has a corresponding functional version
which has the name <tt>to_T</tt>, where <tt>T</tt> is the result type.
These new names replace old names that were less consistent.
So instead of
<pre>
   x = Long(a);
</pre>
one writes
<pre>
   x = to_long(a);
</pre>


<li>
The names of the routines
<pre>
   ZZ_pInit, zz_pInit, zz_pFFTInit, GF2EInit
</pre>
have been changed to
<pre>
   zz_p::init, zz_p::init, zz_p::FFTInit, GF2E::init
</pre>

<li>
The names of the routines 
<pre>
   and, or, xor 
</pre>
for class <tt>ZZ</tt> have
changed to 
<pre>
   bit_and, bit_or, bit_xor, 
</pre>
because the new <tt>C++</tt>
standard defines these as reserved words.

<li>
The function <tt>LowBits</tt> for <tt>ZZ</tt> is now called <tt>trunc</tt>.

<li>
Polynomial inversion mod <tt>X^n</tt> has changed from <tt>inv</tt>
to <tt>InvTrunc</tt>.

<li>
Modular trace, norm, minimum polynomial and characteristic
polynomial have changed from
<pre>
   trace, norm, MinPoly, IrredPoly, CharPoly
</pre>
to
<pre>
   TraceMod, NormMod, MinPolyMod, IrredPolyMod, CharPolyMod
</pre>


<li>
For the class <tt>ZZX</tt>, the functions 
<pre>
   DivRem, div, rem, /, %, /=, %=
</pre>
have new semantics when dividing by non-monic polynomials.
The old semantics are provided by new routines 
<pre>
   PseudoDivRem, PseudoDiv, PseudoRem.
</pre>

<li>
The <tt>UpdateMap</tt> routines have slightly different semantics:
in versions &lt; 3.0, the output always had length n;
now high-order zeroes are stripped.

<li>
The classes <tt>ZZ_pBak</tt>, <tt>zz_pBak,</tt> etc.,  
have just slightly different semantics;  I can't imagine
any reasonable program detecting a difference.

<li>
The assignment operator and copy constructor for the class <tt>RR</tt>
have different semantics: they now produce exact copies, instead
of rounding to current precision.

<li>
All of the NTL compiler flags now start with <tt>NTL_</tt>
to avoid name space problems.

<li>
All of the files "zz_p.h", vec_zz_p.h", etc., have been eliminated.
Use instead the names "lzz_p.h", "vec_lzz_p.h", etc.

</ul>

<p>
<h4>
Tips on making the transition
</h4>
<p>

<ul>

<li>
Apply this <a href="sedscript.txt">sed script</a> to make
most of the necessary syntactic changes.

<li>
Re-compile old NTL programs with the flag 
<pre>
   -DNTL_TRANSITION
</pre>
See <a href="flags.txt">flags.txt</a> for details on how
this will help your compiler detect remaining incompatabilities.
In particular, any uses of operator <tt>&lt;&lt;</tt>
in its old role as a conversion operator will cause the compiler
to raise an error.
You can then convert all of these to the new notation.

</ul>


<p>
<hr>


<p>
<h3>
Changes between NTL 1.7 and 2.0
</h3>
<p>

<ul>
<li>
Implementation of classes BB (polynomials over GF(2))
and BB_pX (polynomials over GF(2^n)).

<li>
A more consistent and natural interface, including arithmetic operators
and a disciplined use of automatic conversion.
So now one can write
<pre>
   x = a * b + c;
</pre>
instead of 
<pre>
   mul(x, a, b);
   add(x, x, c);
</pre>
as one must in older versions of NTL.
The operator notation leads to somewhat less efficient code,
and one can always use the old notation in situations
where efficiency is critical.
Despite the new programming interface,
care has been taken to ensure backward compitability;
pre-existing programs that use NTL should still work.

<li>
Windows port.

<li>
Added compile-time flag that allows one to exploit 
"long long" data type if it exists (this especially helps on Pentium/Linux 
platforms).

<li>
Added compile-time flag to get better quad_float code on
Pentium/Linux platforms.

<li>
A few bug fixes and performance tuning.
</ul>

<p>
<hr>


<p>
<h3>
Changes between NTL 1.5 and NTL 1.7
</h3>
<p>

<ul>
<li>
Incorporation of Keith Briggs' quadratic precision package.

<li>
Much faster and more robust lattice basis reduction,
including Schnorr-Horner "volume heuristic" for Block Korkin
Zolotarev reductions, and a new quadratic precision LLL variant
that is much more robust.

<li>
A few bug fixes.

</ul>


<p>
<hr>

<p>
<h3>
Changes between NTL 1.0 and NTL 1.5
</h3>
<p>


<ul>
<li>
Implementation of Schnorr-Euchner algorithms for
lattice basis reduction, including deep insertions and
block Korkin Zolotarev reduction.
These are significantly faster than the LLL algorithm
in NTL 1.0.

<li>
Implementation of arbitrary-precision floating point.

<li>
Implementation of double precision with extended exponent range,
which is useful for lattice basis reduction when the coefficients
are large.

<li>
Faster polynomial multiplication over the integers,
incorporating the Schoenhagge-Strassen method.

<li>
Compilation flags that increase performance on machines
with poor floating-point performance.

<li>
Sundry performance tuning and a few bug fixes.

</ul>

<center>
<a href="tour-roadmap.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-ack.html"> <img src="arrow3.gif" alt="[Next]" align=bottom></a>
</center>

</body>
</html>