?? 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>Changes between NTL 5.1a and 5.2</h3><p><ul><li>Implemented Mark van Hoeij's new algorithm for factorining polynomialswith rational coefficients.This new algorithm is much more efficient than the previous algorithmused by NTL, and is the default (one can switch back to the old algorithmwith 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 thesquared 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 compileunder gcc version 3.0without errors.This is the <i>one</i> place in NTL where I resort to just a littleassmebly 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 distributioncome 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 componentsof the version number are available to the programmer.<a href="version.txt">[more details]</a>.</ul><p> <hr> <p><h3>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 integersolutions 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 dealwith linear dependencies.The new strategy guarantees better worst-case bounds on thesizes 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 usesome 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 underWindows/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 ofthe pseudo-random number generator.This may change the precise behavior of some programs.<p><li>Other minor, internal modifications.</ul><p> <hr> <p><h3>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>Changes between NTL 5.0a and 5.0b</h3><p>Fixed a typo in <tt>vec_ulong.c</tt> that causes a compile erroron some platforms.<p> <hr> <p><h3>Changes between NTL 4.3a and 5.0a</h3><p><ul><li>I've now re-structured NTL so that one can useeither 'traditional' LIP or GMP as the <i>primary</i> long integer package.Doing this introduced some (minor) backward incompatabilies inthe programming interface, so there is also a 'third way' -- youcan use GMP as a <i>supplemental</i> long integer package (as in NTL 4.3), gettingmany (but not all) of the performance benefits of GMP, whilemaintaining <i>complete</i> backward compatability with the traditionallong integer package.This 'third way' is not highly recommended -- it is only intendedas 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> sothat you can write code that works with either the traditional or GMPlong 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> (vectorsof 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 memoryallocation 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> (severalthousand bits).<p>The only thing unsatisfactory about this state of affairs is that <i>vis a vis</i> the GMP version, the pureLIP 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 GMPwith a reasonable amount of effort, and while maintaining complete backwardcompatability and minimizing the risk of introducing bugs.Some arithmetic operations on some platforms may execute two to three timesfaster if using GMP. <a href="tour-gmp.html">[more details]</a><li>Simplified the installation procedure on Unix systems byproviding a simple configuration script so that setting various configuration variables can be done withoutediting 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 allowsone 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.<p><ul><li>Made some changes that should make NTL compile smoothlyusing any variation of the <tt>C++</tt> language between traditional and ISO Standard.These changes do not affect the documented NTL interface or thebehaviour of NTL.<li>Added a flag <tt>NTL_STD_CXX</tt> in the <tt>config.h</tt> file.Setting this flag causes all of NTL to be "wrapped" in namespace <tt>NTL</tt>,and that part of the standard library used by NTL is "wrapped"in namespace <tt>std</tt>.This should greatly help with the <i>namespace pollution</i> problem.<a href="tour-stdcxx.html">Go here</a> for more details.</ul><p> <hr> <p><p><h3>Changes between NTL 3.9b and 4.0a</h3><p>This is backward compatible with previous version.<p><ul><li>Attached the GNU General Public License to NTL.<li>Fixed two bugs:<ul><li>one in <tt>ReconstructRational</tt> which resulted in a crash on some inputs;<li>one in <tt>exp(RR)</tt> (and by implication in <tt>pow(RR,RR)</tt>),which led to wrong answers on 64-bit machines when computing <tt>exp(x)</tt>for <tt>x > 2^53</tt>.</ul><li>Increased some inconvenient limiting bounds, including a restriction on the FFT.</ul><p> <hr> <p><p><h3>Changes between NTL 3.9a and 3.9b</h3><p>This is a minor revision of 3.9a.<ul><li>Improved time and space efficiency of the HNF routine(see <a href="HNF.txt"><tt>HNF.txt</tt></a>).The old version was based on the description in Henri Cohen's book,which was not really properly optimized.</ul><p> <hr> <p><p><h3>Changes between NTL 3.8b and 3.9a</h3><p>This is backward compatible with previous versions.<ul><li>Modified the installation script somewhat, addinga <i>configuration wizard</i> that sets the flags in<tt>config.h</tt> "automagically".This works for the <a href="tour-unix.html">Unix version</a> only.<li>Improved the <tt>xdouble</tt> input/output and ascii to <tt>xdouble</tt>conversion.The old version could be a bit flaky when reading/writingvery large numbers.The new I/O routines also attain better accuracy.<li>Improved conversion routines between <tt>xdouble</tt>and <tt>ZZ</tt>/<tt>RR</tt>. <li>Improved the <tt>RR</tt> output routine.The new version should be more accurate and also completely platform independent.<li>Added the following routines to the <tt>RR</tt> package:<pre> {Trunc,Floor,Ceil,Round}ToZZ, round RoundToPrecision, MakeRR random</pre>See <a href="RR.txt"><tt>RR.txt</tt></a> for details.<li>Improved the accuracy of <tt>quad_float</tt> input/output,and the accuracy of conversion between <tt>quad_float</tt> and <tt>RR</tt>.<li>Made the timing function somewhat more robust.<li>Hacked the Unix installation script so that it works more smoothly with Cygnus tools under Windows.<li>Fixed a few other, small problems.</ul><p> <hr> <p><p><h3>Changes between NTL 3.8a and 3.8b</h3><p>This is a minor revision of 3.8a.<ul><li>Fixed a bug, a memory leak in routine <tt>gauss</tt> for <tt>mat_ZZ_pE</tt>and <tt>mat_zz_pE</tt>.<li>Fixed a minor problem in <tt>config.h</tt>.<li>Tightened up some size checks, so that now some nice "size invariants"are guaranteed, e.g., for a <tt>ZZ</tt> <tt>n</tt>,<pre> NumBits(NumBits(n)) <= NTL_BITS_PER_LONG-4</pre>Similarly for the type <tt>GF2X</tt>.Of course, on most platforms, one will run out of memory beforethese bounds are exceeded, but they are nevertheless convenient.</ul><p> <hr> <p><p><h3>Changes between NTL 3.7a and 3.8a</h3><p>This is backward compatible with previous versions.<ul><li>Added conversion routines from <tt>unsigned</tt> <tt>int</tt>and <tt>unsigned</tt> <tt>long</tt> to <tt>ZZ</tt>, <tt>RR</tt>, <tt>xdouble</tt>, and <tt>quad_float</tt>.<li>Added routines <tt>GF2XFromBytes</tt> and <tt>BytesFromGF2X</tt>for conversion between byte vectors and polynomials over <tt>GF(2)</tt>,along with routines <tt>NumBits</tt> and <tt>NumBytes</tt>for such polynomials.See <a href="GF2X.txt"><tt>GF2X.txt</tt></a> for details.<li>Added a hack in the <tt>ZZX</tt> factorizerto exploit polynomials of the form <tt>g(x^k)</tt>.This can be disabled by setting the variable <tt>ZZXFac_PowerHack</tt>to zero.See <a href="ZZXFactoring.txt"><tt>ZZXFactoring.txt</tt></a>for details.<li>Improved the hensel system solver <tt>solve1</tt>.See <a href="mat_ZZ.txt"><tt>mat_ZZ.txt</tt></a> for details.<li>Changed documentation for <tt>RationalReconstruction</tt>to reflect the Wang, Guy, Davenport bounds.See <a href="ZZ.txt"><tt>ZZ.txt</tt></a> for details.<li>Improved the routine <tt>GenPrime</tt> a bit. <li>Some other small tweaks here and there.No real bug fixes.<li>Polished the documentation a bit, adding more examples.</ul><p> <hr> <p><p><h3>Changes between NTL 3.6b and 3.7a</h3><p>This is backward compatible with previous versions.<ul><li>Added a "rational reconstruction" routine. See the routine <tt>ReconstructRational</tt> in <a href="ZZ.txt">ZZ.txt</a>.<li>Added another routine for solving linear systems over <tt>ZZ</tt>that is based on Hensel lifting, rather than Chinese Remaindering.It can be significantly faster in some cases.See the routine <tt>solve1</tt> in <a href="mat_ZZ.txt">mat_ZZ.txt</a>).<li>Some performace tuning, especially CRT and polynomial interpolation code.<li>Various documentation corrections.<li>Added more "overflow checks" here and there to ensure programs crash gracefullywhen certain things get too big.<li>Fixed a "benign" bug (i.e., it would never get triggered on any of today'smachines).<li>Removed references to <tt><malloc.h></tt>, which were unnecessary,non-standard, and caused problems on some platforms.</ul><p><hr><p><h3>Changes between NTL 3.6a and 3.6b</h3><p>Bug fixes.<p><hr><p><h3>Changes between NTL 3.5a and 3.6a</h3><p>This version is backward compatible with 3.5a.<p><ul><li>A few small bug fixes and performance enhancements.<li>Changes to the <tt>ZZX</tt> factoring routines that in somecases yield dramatic performance improvements(<a href="tour-time.html">more details</a>).</ul><p><hr><p><h3>Changes between NTL 3.1b and 3.5a</h3><p><b>Please note.</b> This version is <b>NOT</b> completely backward compatible.<p>Summary of changes:<ul><li>Improved performance of the "all integer" LLL routine.<li>Put in a better pseudo-random number generator,?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -