?? tour-changes.html
字號:
<html>
<head>
<title>
A Tour of NTL: Summary of Changes </title>
</head>
<body bgcolor="#fff9e6">
<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>
<h1>
<p align=center>
A Tour of NTL: Summary of Changes
</p>
</h1>
<p> <hr> <p>
<h3>
2005.03.24: Changes between NTL 5.3.2 and 5.4
</h3>
<ul>
<li>
By default, NTL now compiles in ISO mode (using namespaces, etc.).
You can always revert to traditional mode by unsetting
the flag <tt>NTL_STD_CXX</tt>
(either pass <tt>NTL_STD_CXX=off</tt> to the configure script,
or manually edit the <tt>config.h</tt> file).
<p>
<li>
Some bug fixes:
<ul>
<li>
The <tt>sqrt</tt> and <tt>log1p</tt> routines
for the <tt>RR</tt> class would produce incorrectly rounded
results in certain circumstances (although this only affected the relative
error of the result very marginally).
<li>
The <tt>SqrRootPrec</tt> routine for the <tt>RR</tt> class
could not be called, because it was defined incorrectly.
</ul>
<p>
Thanks to Paul Zimmermann for finding (and fixing) these bugs!
Paul has also validated NTL's <tt>RR</tt> class by cross-checking it with the
<a href="http://www.mpfr.org">MPFR</a> library.
<p>
<li>
Some performance enhancements:
<ul>
<li>
Added a new <tt>MulModPrecon</tt> inline function for
computing <tt>(a * b) % n</tt> for single precision numbers,
when <tt>b</tt> and <tt>n</tt> are fixed for several computations.
On some platforms this can be twice as fast or more than the
old <tt>MulMod2</tt> routine.
This indirectly affects a lot of computations that are done via
homomorphic imaging (polynomial multiplication
over <tt>zz_p</tt>, <tt>ZZ_p</tt>, and <tt>ZZ</tt>,
matrix computations over <tt>zz_p</tt> and <tt>ZZ</tt>).
<li>
Rewrote the small prime FFT to take advantage of the new
<tt>MulModPrecon</tt>, and to be more cache friendly.
<li>
Improved the performance of the <tt>GF2X</tt> multiplication routine.
On some platforms, it can be twice as fast as the old one.
Thanks (again) to Paul Zimmermann for suggesting some of these
improvements and supplying some of the code.
</ul>
<p>
<li>
Miscellany:
<ul>
<li>
Rewrote several of the installation scripts in Perl (the old shell
scripts were getting too messy to maintain).
However, the syntax for all of the command-line interfaces
remains identical.
</ul>
</ul>
<p> <hr> <p>
<h3>
2004.05.21: Changes between NTL 5.3.1 and 5.3.2
</h3>
<ul>
<li>
Some bug fixes.
<p>
<li>
Re-wrote <tt>SqrRootMod</tt> to make it run faster.
</ul>
<p> <hr> <p>
<h3>
2002.12.17: Changes between NTL 5.3 and 5.3.1
</h3>
<ul>
<li>
Fixed a bug affecting the <tt>BuildIrred</tt> routines
for <tt>ZZ_pEX</tt> and <tt>zz_pEX</tt>.
</ul>
<p> <hr> <p>
<h3>
2002.07.05: Changes between NTL 5.2 and 5.3
</h3>
<ul>
<li>
Minimized and isolated constructs that do not adhere to <tt>C</tt>/<tt>C++</tt>
standards,
and added flags <tt>NTL_CLEAN_INT</tt> and <tt>NTL_CLEAN_PTR</tt>
which force stricter compliance with these standards
<a href="tour-impl.html">[more details]</a>.
<p>
<li>
Added functions <tt>IsWhiteSpace</tt>, <tt>CharToIntVal</tt>,
and <tt>IntValToChar</tt> to the <tt>tools</tt> module
<a href="tools.txt">[more details]</a>.
<p>
<li>
Added methods <tt>allocated</tt>, <tt>position1</tt> to generic vector classes
<a href="vector.txt">[more details]</a>.
<p>
<li>
Added method <tt>allocated</tt> to the class <tt>vec_GF2</tt>
<a href="vec_GF2.txt">[more details]</a>.
<p>
<li>
Added conversion routines from unsigned int/long to int, long, float, and double
<a href="conversions.txt">[more details]</a>.
<p>
<li>
Added routines <tt>AddPrec</tt>, <tt>SubPrec</tt>, etc., to the <tt>RR</tt>
module, and declared the practice of directly assigning to the variable
<tt>RR::prec</tt> obsolete
<a href="RR.txt">[more details]</a>.
<p>
<li>
Fixed a number of minor bugs.
</ul>
<p> <hr> <p>
<h3>
2001.07.19: Changes between NTL 5.1a and 5.2
</h3>
<p>
<ul>
<li>
Implemented Mark van Hoeij's new algorithm for factorining polynomials
with rational coefficients.
This new algorithm is much more efficient than the previous algorithm
used by NTL, and is the default (one can switch back to the old algorithm
with a run-time switch).
<p>
<a href="ZZXFactoring.txt">[documentation]</a>
<p>
<a href="tour-time.html">[performance measurements]</a>
<p>
<li>
Added routines <tt>LLL_plus</tt> that are just like the all-integer
<tt>LLL</tt> routines, except that they return the exact values of the
squared lengths of the Gramm-Schmidt basis vectors.
This is useful in implementing van Hoeij's algorithm.
<a href="LLL.txt">[more details]</a>.
<p>
<li>
Made a small change to <tt>quad_float.c</tt> to make it compile
under gcc version 3.0
without errors.
This is the <i>one</i> place in NTL where I resort to just a little
assmebly code (but only on x86/Linux platforms), and wouldn't you know it,
this is the <i>one</i> place where gcc 3.0 had problems.
<p>
<li>
Made a small change to the procedure for generating a distribution,
so that now all files in the "tar" file comprising the distribution
come without any annoyingly excessive access control restrictions.
<p>
<li>
Changed the version numbering scheme so that it is now closer to
"standard practice".
This is version "5.2".
Any small bug fixes to this version will be named "5.2.1", "5.2.2", etc.
Also, macros are now defined so that the numerical components
of the version number are available to the programmer.
<a href="version.txt">[more details]</a>.
</ul>
<p> <hr> <p>
<h3>
2001.06.08: Changes between NTL 5.0c and 5.1a
</h3>
<p>
Some minor fixes and additions.
<p>
Completely backward compatible.
<p>
<ul>
<li>
Added a routine <tt>LatticeSolve()</tt> for finding integer
solutions to linear systems of integer equations.
<a href="LLL.txt">[more details]</a>
<p>
<li>
Modified the stragey used by the <tt>LLL()</tt> and <tt>image()</tt>
routines in the <a href="LLL.txt">LLL package</a> to deal
with linear dependencies.
The new strategy guarantees better worst-case bounds on the
sizes of intermediate values.
I'm not sure if it will have any serious practical impact, though.
<p>
<li>
Added some "partial ISO modes" so that one can use
some of the features of Standard <tt>C++</tt>,
even if ones compiler does not yet support all of the features.
<a href="tour-stdcxx.html">[more details]</a>
<p>
<li>
Bug fix: routine <tt>determnant()</tt> in <tt>mat_GF2.h</tt>
was not visible to the linker because of a typo in <tt>mat_GF2.c</tt>.
<p>
<li>
Made a "smarter" script for selecting the <tt>GetTime()</tt>
function.
This fixes an installation problem on Cygwin/Windows 95 platforms.
I hope it doesn't create more problems than it solves, though.
<p>
<li>
Added some extra documentation for installation under
Windows/MS Visual <tt>C++</tt>.
<a href="tour-win.html">[more details]</a>
<p>
<li>
Changed some names like <tt>c_lip.c</tt> to <tt>c_lip_impl.h</tt>.
This should avoid some potential installation problems.
<p>
<li>
Throw away first 256-bytes of arc4 streams to improve quality of
the pseudo-random number generator.
This may change the precise behavior of some programs.
<p>
<li>
Other minor, internal modifications.
</ul>
<p> <hr> <p>
<h3>
2001.02.19: Changes between NTL 5.0b and 5.0c
</h3>
<p>
Fixed a naming problem in the Windows distribution.
The Unix distribution is unaffected.
<p> <hr> <p>
<h3>
2001.02.19: Changes between NTL 5.0a and 5.0b
</h3>
<p>
Fixed a typo in <tt>vec_ulong.c</tt> that causes a compile error
on some platforms.
<p> <hr> <p>
<h3>
2001.02.19: Changes between NTL 4.3a and 5.0a
</h3>
<p>
<ul>
<li>
I've now re-structured NTL so that one can use
either 'traditional' LIP or GMP as the <i>primary</i> long integer package.
Doing this introduced some (minor) backward incompatabilies in
the programming interface, so there is also a 'third way' -- you
can use GMP as a <i>supplemental</i> long integer package (as in NTL 4.3),
getting
many (but not all) of the performance benefits of GMP, while
maintaining <i>complete</i> backward compatability with the traditional
long integer package.
This 'third way' is not highly recommended -- it is only intended
as a backward compatabilty hack.
<p>
Even if you do not use GMP, you should
<a href="tour-gmp.html">read about using NTL with GMP</a> so
that you can write code that works with either the traditional or GMP
long integer packages.
<p>
<li>
Added a <tt>ZZ</tt> to unsigned long conversion routine.
<a href="conversions.txt">[more details]</a>
<li>
Added new vector classes <tt>vec_ulong</tt> (vectors
of unsigned longs) and <tt>vec_vec_ulong</tt>.
<a href="tour-modules.html">[more details]</a>
<li>
Some minor bug fixes: under some unusual circumstances, a memory
allocation error could be erroneously raised; I also added a patch
that works around a bug in v3.0.1 of GMP.
<li>
Some internal cleansing, minimizing the use of non-standard constructs.
</ul>
<p> <hr> <p>
<h3>
Changes between NTL 4.2a and 4.3a
</h3>
This is backward compatible with previous versions.
<p>
<ul>
<li>
Improved the performance of <tt>ZZ_pX</tt> arithmetic when using
GMP.
The GMP version is also more space efficient
(the pre-computed tables are much smaller).
These improvements are most marked for very large <tt>p</tt> (several
thousand bits).
<p>
The only thing unsatisfactory about this state of affairs is that
<i>vis a vis</i> the GMP version, the pure
LIP code is asymptotically slower by <i>more</i> than a constant factor,
and is is also less space efficient.
Perhaps I'll get around to rectifying this imbalance someday.
To do this, I need a sub-quadratic division with remainder routine for LIP.
At any rate, the differences only become seriously noticible when
<tt>p</tt> has more than a few thousand bits.
<p>
<li>
Some other small adjustments here and there.
</ul>
<p> <hr> <p>
<h3>
Changes between NTL 4.1a and 4.2a
</h3>
This is backward compatible with previous versions.
<p>
<ul>
<li>
Hacked the big integer code so that NTL uses GMP
(the GNU Multi-Precision library).
This is done in such a way as to get most of the benefits of GMP
with a reasonable amount of effort, and while maintaining complete backward
compatability and minimizing the risk of introducing bugs.
Some arithmetic operations
on some platforms may execute two to three times
faster if using GMP. <a href="tour-gmp.html">[more details]</a>
<li>
Simplified the installation procedure on Unix systems by
providing a simple configuration script so that setting
various configuration variables can be done without
editing the <tt>makefile</tt> and <tt>config.h</tt> file.
<a href="tour-unix.html">[more details]</a>
<li>
Added function <tt>GenGermainPrime</tt>
to efficiently generate random Germain primes, i.e., primes <i>p</i>
such that <i>2p+1</i> is also prime. <a href="ZZ.txt">[more details]</a>
<li>
Added a function <tt>random</tt> to generate random <tt>quad_floats</tt>.
<a href="quad_float.txt">[more details]</a>
<li>
Added an <tt>ifdef</tt> in <tt>tools.h</tt> that allows
one to suppress the declaration of <tt>min</tt> and <tt>max</tt>
functions in NTL client programs;
these were causing problems when writing 'Windows applications'.
<li>
Implemented a faster algorithm for initializing the
<tt>ZZ_p</tt> auxilliary data structures.
<li>
Polished up a few other minor things in the code and documentation.
</ul>
<p> <hr> <p>
<p>
<h3>
Changes between NTL 4.0a and 4.1a
</h3>
<p>
This is backward compatible with previous versions.
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -