source: git/ntl/doc/tour-changes.html @ 6ce030f

spielwiese
Last change on this file since 6ce030f was 287cc8, checked in by Hans Schönemann <hannes@…>, 14 years ago
ntl 5.5.2 git-svn-id: file:///usr/local/Singular/svn/trunk@12402 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 35.0 KB
Line 
1<html>
2<head>
3<title>
4A Tour of NTL: Summary of Changes  </title>
5</head>
6
7<body bgcolor="#fff9e6">
8<center>
9<a href="tour-roadmap.html"><img src="arrow1.gif" alt="[Previous]" align=bottom></a>
10 <a href="tour.html"><img src="arrow2.gif" alt="[Up]" align=bottom></a> 
11<a href="tour-ack.html"> <img src="arrow3.gif" alt="[Next]" align=bottom></a>
12</center>
13
14<h1> 
15<p align=center>
16A Tour of NTL: Summary of Changes
17</p>
18</h1>
19
20<p> <hr> <p>
21<h3>
222009.08.14: Changes between NTL 5.5.1 and 5.5.2
23</h3>
24
25<ul>
26<li>
27New routines <tt>MulAddTo</tt> and <tt>MulSubFrom</tt>
28for computing <tt>x += a*b</tt> and <tt>x -= a*b</tt>,
29where <tt>x</tt> and <tt>a</tt> are <tt>ZZ</tt>'s and
30<tt>b</tt> is a <tt>ZZ</tt> or a <tt>long</tt>.
31In the case where <tt>b</tt> is a <tt>long</tt>,
32this may be much faster than writing
33<tt>mul(t, a, b); add(x, x, t)</tt>.
34See <a href="ZZ.txt">ZZ.txt</a> for details.
35
36These new routines are used in a number of places in
37NTL to get faster algorithms (for example, the <tt>LLL</tt> routine).
38
39<li>
40Fixed a relatively benign indexing bug in <tt>GF2EX</tt>
41discovered by Berend-Benjamin Tams using the <tt>valgrind</tt> tool.
42
43
44
45
46</ul>
47
48<p> <hr> <p>
49<h3>
502009.05.05: Changes between NTL 5.5 and 5.5.1
51</h3>
52
53<ul>
54<li> If using GMP (via either <tt>NTL_GMP_LIP</tt>
55or <tt>NTL_GMP_HACK</tt>), then the new version (4.3.0) of
56GMP implements the <tt>XGCD</tt> functionality differently,
57so that the coefficients do not always agree with those returned by
58the classical extended Euclidean algorithm.
59This version of NTL corrects the coefficients, so that the
60"classical" coefficients are always produced, regardless
61of GMP's implementation.
62This version of NTL also works
63around a bug in GMP 4.3.0's <tt>XGCD</tt> code
64(although that bug should be fixed in GMP 4.3.1).
65
66<li>
67The <tt>configure</tt> script has been slightly modified:
68there is a new configuration variable <tt>DEF_PREFIX</tt>,
69whose value can be used to set <tt>PREFIX</tt>, <tt>GMP_PREFIX</tt>,
70and <tt>GF2X_PREFIX</tt> in one stroke.
71Also, the (somewhat esoteric) <tt>configure</tt> variables
72<tt>GMP_LIBDIR</tt>, <tt>GMP_INCDIR</tt>,
73<tt>GF2X_LIBDIR</tt>, and <tt>GF2X_INCDIR</tt>
74have slightly different meanings now.
75
76</ul>
77</h3>
78
79<p> <hr> <p>
80<h3>
812009.04.08: Changes between NTL 5.4.2 and 5.5
82</h3>
83
84<ul>
85<li>
86Added the ability to generate a <i>shared</i> library
87(with help from Tim Abbott). <a href="tour-unix.html#shared">Details.</a>
88
89<li>
90Fixed some standardization issues
91(with help from Tim Abbot):
92default location of installed documentation files now conforms
93to standards; use of <tt>EOF</tt> now conforms to standards.
94
95<li>
96Added a callback mechanism to NTL's error reporting function.
97See <tt>ErrorCallback</tt> in <a href="tools.txt">tools.txt</a>.
98
99<li>
100Added support for the <tt>gf2x</tt> library for speeding up
101arithmetic in <tt>GF2X</tt> (with help from Emmanuel Thom&eacute;).
102<a href="tour-gf2x.html">Details.</a>
103
104<li>
105In conjuction with the above, I also changed the
106<tt>GF2X</tt> so that it works better with very large polynomials:
107large blocks of memory are released, recursive HalfGCD algorithms
108are used for large polynomials.
109
110
111<li>
112Fixed a bug in <tt>void TraceMod(zz_p&amp; x, const zz_pX&amp; a, const zz_pXModulus&amp; F)</tt> (reported by Luca De Feo).
113
114<li>
115Fixed a performance issue in various versions of <tt>SetCoeff</tt>
116(reported by Luca De Feo).
117
118<li>
119Fixed the declaration of  <tt>mat_zz_p transpose(const mat_zz_p&amp; a)</tt>
120(reported by Benoit Lacelle).
121</ul>
122
123
124<p> <hr> <p>
125<h3>
1262008.03.05: Changes between NTL 5.4.1 and 5.4.2
127</h3>
128
129<ul>
130<li>
131Fixed a bug in the <tt>sub(ZZ_pEX, ZZ_pE, ZZ_pEX)</tt>
132and  <tt>sub(zz_pEX, zz_pE, zz_pEX)</tt> routines (reported by Charanjit Jutla).
133Under certain circumstances, these could outout wrong answers.
134
135</ul>
136
137<p> <hr> <p>
138<h3>
1392007.05.09: Changes between NTL 5.4 and 5.4.1
140</h3>
141
142<ul>
143<li>
144Fixed rounding bug in <tt>expm1</tt> (reported by Paul Zimmermann).
145
146<li>
147Fixed memory leak in several LLL routines (reported by Friedrich Bahr).
148
149<li>
150Fixed infinite loop in several LLL routines
151(this only occurred on machines, like x86, with double rounding).
152
153<li>
154Improved <tt>GF2X</tt> timing tests (suggested by Paul Zimmermann).
155
156</ul>
157
158<p> <hr> <p>
159<h3>
1602005.03.24: Changes between NTL 5.3.2 and 5.4 
161</h3>
162
163<ul>
164<li>
165By default, NTL now compiles in ISO mode (using namespaces, etc.).
166You can always revert to traditional mode by unsetting
167the flag <tt>NTL_STD_CXX</tt> 
168(either pass <tt>NTL_STD_CXX=off</tt> to the configure script,
169or manually edit the <tt>config.h</tt> file).
170<p>
171
172<li>
173Some bug fixes:
174
175<ul>
176<li>
177The <tt>sqrt</tt> and <tt>log1p</tt> routines
178for the <tt>RR</tt> class would produce incorrectly rounded
179results in certain circumstances (although this only affected the relative
180error of the result very marginally).
181<li>
182The <tt>SqrRootPrec</tt> routine for the <tt>RR</tt> class
183could not be called, because it was defined incorrectly.
184</ul>
185
186<p>
187
188Thanks to Paul Zimmermann for finding (and fixing) these bugs!
189Paul has also validated NTL's <tt>RR</tt> class by cross-checking it with the
190<a href="http://www.mpfr.org">MPFR</a> library.
191
192<p>
193<li>
194Some performance enhancements:
195
196<ul>
197<li>
198Added a new <tt>MulModPrecon</tt> inline function for
199computing <tt>(a * b) % n</tt> for single precision numbers,
200when <tt>b</tt> and <tt>n</tt> are fixed for several computations.
201On some platforms this can be twice as fast or more than the
202old <tt>MulMod2</tt> routine.
203This indirectly affects a lot of computations that are done via
204homomorphic imaging (polynomial multiplication
205over <tt>zz_p</tt>, <tt>ZZ_p</tt>, and <tt>ZZ</tt>,
206matrix computations over <tt>zz_p</tt> and <tt>ZZ</tt>).
207
208<li>
209Rewrote the small prime FFT to take advantage of the new
210<tt>MulModPrecon</tt>, and to be more cache friendly.
211
212<li>
213Improved the performance of the <tt>GF2X</tt> multiplication routine.
214On some platforms, it can be twice as fast as the old one.
215Thanks (again) to Paul Zimmermann for suggesting some of these
216improvements and supplying some of the code.
217
218</ul>
219
220<p>
221<li>
222Miscellany:
223
224<ul>
225<li>
226Rewrote several of the installation scripts in Perl (the old shell
227scripts were getting too messy to maintain).
228However, the syntax for all of the command-line interfaces
229remains identical.
230
231</ul>
232 
233
234
235
236
237</ul>
238
239<p> <hr> <p>
240<h3>
2412004.05.21: Changes between NTL 5.3.1 and 5.3.2
242</h3>
243
244<ul>
245<li>
246Some bug fixes.
247
248<p>
249<li>
250Re-wrote <tt>SqrRootMod</tt> to make it run faster.
251
252</ul>
253
254
255
256<p> <hr> <p>
257<h3>
2582002.12.17: Changes between NTL 5.3 and 5.3.1
259</h3>
260
261<ul>
262<li>
263Fixed a bug affecting the <tt>BuildIrred</tt> routines
264for <tt>ZZ_pEX</tt> and <tt>zz_pEX</tt>.
265</ul>
266
267<p> <hr> <p>
268<h3>
2692002.07.05: Changes between NTL 5.2 and 5.3
270</h3>
271
272<ul>
273<li>
274Minimized and isolated constructs that do not adhere to <tt>C</tt>/<tt>C++</tt> 
275standards,
276and added flags <tt>NTL_CLEAN_INT</tt> and <tt>NTL_CLEAN_PTR</tt>
277which force stricter compliance with these standards
278<a href="tour-impl.html">[more details]</a>.
279
280<p>
281<li>
282Added functions <tt>IsWhiteSpace</tt>, <tt>CharToIntVal</tt>,
283and <tt>IntValToChar</tt>  to the <tt>tools</tt> module
284<a href="tools.txt">[more details]</a>.
285
286<p>
287<li>
288Added methods <tt>allocated</tt>, <tt>position1</tt> to generic vector classes
289<a href="vector.txt">[more details]</a>.
290
291<p>
292<li>
293Added method <tt>allocated</tt> to the class <tt>vec_GF2</tt>
294<a href="vec_GF2.txt">[more details]</a>.
295
296<p>
297<li>
298Added conversion routines from unsigned int/long to int, long, float, and double
299<a href="conversions.txt">[more details]</a>.
300
301<p>
302<li>
303Added routines <tt>AddPrec</tt>, <tt>SubPrec</tt>, etc., to the <tt>RR</tt>
304module, and declared the practice of directly  assigning to the variable
305<tt>RR::prec</tt> obsolete
306<a href="RR.txt">[more details]</a>.
307
308<p>
309<li>
310Fixed a number of minor bugs.
311
312</ul>
313
314
315
316<p> <hr> <p>
317<h3>
3182001.07.19: Changes between NTL 5.1a and 5.2
319</h3>
320
321<p>
322
323<ul>
324<li>
325Implemented Mark van Hoeij's new algorithm for factorining polynomials
326with rational coefficients.
327This new algorithm is much more efficient than the previous algorithm
328used by NTL, and is the default (one can switch back to the old algorithm
329with a run-time switch).
330<p>
331<a href="ZZXFactoring.txt">[documentation]</a>
332<p>
333<a href="tour-time.html">[performance measurements]</a>
334<p>
335
336<li>
337Added routines <tt>LLL_plus</tt> that are just like the all-integer
338<tt>LLL</tt> routines, except that they return the exact values of the
339squared lengths of the Gramm-Schmidt basis vectors.
340This is useful in implementing van Hoeij's algorithm.
341<a href="LLL.txt">[more details]</a>.
342<p>
343
344<li>
345Made a small change to <tt>quad_float.c</tt> to make it compile
346under  gcc version 3.0
347without errors.
348This is the <i>one</i> place in NTL where I resort to just a little
349assmebly code (but only on x86/Linux platforms), and wouldn't you know it,
350this is the <i>one</i> place where gcc 3.0 had problems.
351<p>
352
353<li>
354Made a small change to the procedure for generating a distribution,
355so that now all files in the "tar" file comprising the distribution
356come without any annoyingly excessive access control restrictions.
357<p>
358
359<li>
360Changed the version numbering scheme so that it is now closer to
361"standard practice".
362This is version "5.2".
363Any small bug fixes to this version will be named "5.2.1", "5.2.2", etc.
364Also, macros are now defined so that the numerical components
365of the version number are available to the programmer.
366<a href="version.txt">[more details]</a>.
367
368
369</ul>
370
371
372<p> <hr> <p>
373<h3>
3742001.06.08: Changes between NTL 5.0c and 5.1a
375</h3>
376
377<p>
378Some minor fixes and additions.
379<p>
380Completely backward compatible.
381<p>
382
383<ul>
384
385<li>
386Added a routine <tt>LatticeSolve()</tt> for finding integer
387solutions to linear systems of integer equations.
388<a href="LLL.txt">[more details]</a>
389
390<p>
391<li>
392Modified the stragey used by the <tt>LLL()</tt> and <tt>image()</tt>
393routines in the <a href="LLL.txt">LLL package</a> to deal
394with linear dependencies.
395The new strategy guarantees better worst-case bounds on the
396sizes of intermediate values.
397I'm not sure if it will have any serious practical impact, though.
398
399<p>
400<li>
401Added some "partial ISO modes" so that one can use
402some of the features of Standard <tt>C++</tt>,
403even if ones compiler does not yet support all of the features.
404<a href="tour-stdcxx.html">[more details]</a>
405
406<p>
407<li>
408Bug fix: routine <tt>determnant()</tt> in <tt>mat_GF2.h</tt>
409was not visible to the linker because of a typo in <tt>mat_GF2.c</tt>.
410
411<p>
412<li>
413Made a "smarter" script for selecting the <tt>GetTime()</tt>
414function.
415This fixes an installation problem on Cygwin/Windows 95 platforms.
416I hope it doesn't create more problems than it solves, though.
417
418<p>
419<li>
420Added some extra documentation for installation under
421Windows/MS Visual <tt>C++</tt>.
422<a href="tour-win.html">[more details]</a>
423
424<p>
425<li>
426Changed some names like <tt>c_lip.c</tt> to <tt>c_lip_impl.h</tt>.
427This should avoid some potential installation problems.
428
429<p>
430<li>
431Throw away first 256-bytes of arc4 streams to improve quality of
432the pseudo-random number generator.
433This may change the precise behavior of some  programs.
434
435<p>
436<li>
437Other minor, internal modifications.
438
439</ul>
440
441
442
443
444<p> <hr> <p>
445<h3>
4462001.02.19: Changes between NTL 5.0b and 5.0c
447</h3>
448
449<p>
450Fixed a naming problem in the Windows distribution.
451The Unix distribution is unaffected.
452
453
454<p> <hr> <p>
455<h3>
4562001.02.19: Changes between NTL 5.0a and 5.0b
457</h3>
458
459<p>
460Fixed a typo in <tt>vec_ulong.c</tt> that causes a compile error
461on some platforms.
462
463
464<p> <hr> <p>
465<h3>
4662001.02.19: Changes between NTL 4.3a and 5.0a
467</h3>
468
469<p>
470<ul>
471<li>
472I've now re-structured NTL so that one can use
473either 'traditional' LIP or GMP as the <i>primary</i> long integer package.
474Doing this introduced some (minor) backward incompatabilies in
475the programming interface, so there is also a 'third way' -- you
476can use GMP as a <i>supplemental</i> long integer package (as in NTL 4.3),
477getting
478many (but not all) of the performance benefits of GMP, while
479maintaining <i>complete</i> backward compatability with the traditional
480long integer package.
481This 'third way' is not highly recommended -- it is only intended
482as a backward compatabilty hack.
483
484<p>
485Even if you do not use GMP, you should
486<a href="tour-gmp.html">read about using NTL with GMP</a> so
487that you can write code that works with either the traditional or GMP
488long integer packages.
489<p>
490<li>
491Added a <tt>ZZ</tt> to unsigned long conversion routine.
492<a href="conversions.txt">[more details]</a>
493<li>
494Added new vector classes <tt>vec_ulong</tt> (vectors
495of unsigned longs) and <tt>vec_vec_ulong</tt>.
496<a href="tour-modules.html">[more details]</a>
497<li>
498Some minor bug fixes:  under some unusual circumstances, a memory
499allocation error could be erroneously raised; I also added a patch
500that works around a bug in v3.0.1 of GMP.
501<li>
502Some internal cleansing, minimizing the use of non-standard constructs.
503</ul>
504
505
506<p> <hr> <p>
507<h3>
508Changes between NTL 4.2a and 4.3a
509</h3>
510
511This is backward compatible with previous versions.
512
513<p>
514<ul>
515<li>
516Improved the performance of <tt>ZZ_pX</tt> arithmetic when using
517GMP.
518The GMP version is also more space efficient
519(the pre-computed tables are much smaller).
520These improvements are most marked for very large <tt>p</tt> (several
521thousand bits).
522
523<p>
524The only thing unsatisfactory about this state of affairs is that
525<i>vis a vis</i> the GMP version, the pure
526LIP code is asymptotically slower by <i>more</i> than a constant factor,
527and is is also less space efficient.
528Perhaps I'll get around to rectifying this imbalance someday.
529To do this, I need a sub-quadratic division with remainder routine for LIP.
530At any rate, the differences only become seriously noticible when
531<tt>p</tt> has more than a few thousand bits.
532
533<p>
534
535<li>
536Some other small adjustments here and there.
537
538</ul>
539
540<p> <hr> <p>
541<h3>
542Changes between NTL 4.1a and 4.2a
543</h3>
544
545This is backward compatible with previous versions.
546
547<p>
548<ul>
549<li>
550Hacked the big integer code so that NTL uses GMP
551(the GNU Multi-Precision library).
552This is done in such a way as to get most of the benefits of GMP
553with a reasonable amount of effort, and while maintaining complete backward
554compatability and minimizing the risk of introducing bugs.
555Some arithmetic operations
556on some platforms may execute two to three times
557faster if using GMP. <a href="tour-gmp.html">[more details]</a>
558<li>
559Simplified the installation procedure on Unix systems by
560providing a simple configuration script so that setting
561various configuration variables can be done without
562editing the <tt>makefile</tt> and  <tt>config.h</tt> file.
563<a href="tour-unix.html">[more details]</a>
564<li>
565Added function <tt>GenGermainPrime</tt>
566to efficiently generate random Germain primes, i.e., primes <i>p</i>
567such that <i>2p+1</i> is also prime. <a href="ZZ.txt">[more details]</a>
568<li>
569Added a function <tt>random</tt> to generate random <tt>quad_floats</tt>.
570<a href="quad_float.txt">[more details]</a>
571<li>
572Added an <tt>ifdef</tt> in <tt>tools.h</tt> that allows
573one to suppress the declaration of <tt>min</tt> and <tt>max</tt>
574functions in NTL client programs;
575these were causing problems when writing 'Windows applications'.
576<li>
577Implemented a faster algorithm for initializing the
578<tt>ZZ_p</tt> auxilliary data structures.
579<li>
580Polished up a few other minor things in the code and documentation.
581</ul>
582
583<p> <hr> <p>
584
585<p>
586<h3>
587Changes between NTL 4.0a and 4.1a
588</h3>
589<p>
590
591This is backward compatible with previous versions.
592
593<p>
594<ul>
595<li>
596Made some changes that should make NTL compile smoothly
597using any variation of the <tt>C++</tt> language between traditional and
598ISO Standard.
599These changes do not affect the documented NTL interface or the
600behaviour of NTL.
601
602<li>
603Added a flag <tt>NTL_STD_CXX</tt> in the <tt>config.h</tt> file.
604Setting this flag causes all of NTL to be "wrapped" in namespace <tt>NTL</tt>,
605and that part of the standard library used by NTL is "wrapped"
606in namespace <tt>std</tt>.
607This should greatly help with the <i>namespace pollution</i> problem.
608<a href="tour-stdcxx.html">Go here</a> for more details.
609
610</ul>
611
612
613
614<p> <hr> <p>
615
616<p>
617<h3>
618Changes between NTL 3.9b and 4.0a
619</h3>
620<p>
621
622This is backward compatible with previous version.
623
624<p>
625<ul>
626<li>
627Attached the GNU General Public License to NTL.
628
629<li>
630Fixed two bugs:
631<ul>
632<li>
633one in <tt>ReconstructRational</tt> which resulted in a crash on some inputs;
634<li>
635one in <tt>exp(RR)</tt> (and by implication in <tt>pow(RR,RR)</tt>),
636which led to wrong answers on 64-bit machines when computing <tt>exp(x)</tt>
637for <tt>x > 2^53</tt>.
638</ul>
639
640<li>
641Increased some inconvenient limiting bounds, including a restriction on the
642FFT.
643
644</ul>
645
646
647<p> <hr> <p>
648
649<p>
650<h3>
651Changes between NTL 3.9a and 3.9b
652</h3>
653<p>
654
655This is a minor revision of 3.9a.
656
657<ul>
658<li>
659Improved time and space efficiency of the HNF routine
660(see <a href="HNF.txt"><tt>HNF.txt</tt></a>).
661The old version was based on the description in Henri Cohen's book,
662which was not really properly optimized.
663</ul>
664
665
666
667<p> <hr> <p>
668
669<p>
670<h3>
671Changes between NTL 3.8b and 3.9a
672</h3>
673<p>
674
675This is backward compatible with previous versions.
676
677<ul>
678<li>
679Modified the installation script somewhat, adding
680a <i>configuration wizard</i> that sets the flags in
681<tt>config.h</tt> "automagically".
682This works for the <a href="tour-unix.html">Unix version</a> only.
683
684<li>
685Improved the <tt>xdouble</tt> input/output and ascii to <tt>xdouble</tt>
686conversion.
687The old version could be a bit flaky when reading/writing
688very large numbers.
689The new I/O routines also attain better accuracy.
690
691<li>
692Improved conversion routines between <tt>xdouble</tt>
693and <tt>ZZ</tt>/<tt>RR</tt>.
694
695<li>
696Improved the <tt>RR</tt> output routine.
697The new version should be more accurate and also
698completely platform independent.
699
700<li>
701Added the following routines to the <tt>RR</tt> package:
702<pre>
703   {Trunc,Floor,Ceil,Round}ToZZ, round
704   RoundToPrecision, MakeRR
705   random
706</pre>
707See <a href="RR.txt"><tt>RR.txt</tt></a> for details.
708
709<li>
710Improved the accuracy of <tt>quad_float</tt> input/output,
711and the accuracy of conversion between <tt>quad_float</tt> and <tt>RR</tt>.
712
713<li>
714Made the timing function somewhat more robust.
715
716<li>
717Hacked the Unix installation script so that it works
718more smoothly with Cygnus tools under Windows.
719
720<li>
721Fixed a few other, small problems.
722</ul>
723
724<p> <hr> <p>
725
726<p>
727<h3>
728Changes between NTL 3.8a and 3.8b
729</h3>
730<p>
731
732This is a minor revision of 3.8a.
733
734<ul>
735<li>
736Fixed a bug, a memory leak in routine <tt>gauss</tt> for <tt>mat_ZZ_pE</tt>
737and <tt>mat_zz_pE</tt>.
738<li>
739Fixed a minor problem in <tt>config.h</tt>.
740<li>
741Tightened up some size checks, so that now some nice "size invariants"
742are guaranteed, e.g., for a <tt>ZZ</tt> <tt>n</tt>,
743<pre>
744   NumBits(NumBits(n)) &lt;= NTL_BITS_PER_LONG-4
745</pre>
746Similarly for the type <tt>GF2X</tt>.
747Of course, on most platforms, one will run out of memory before
748these bounds are exceeded, but they are nevertheless convenient.
749</ul>
750
751
752<p> <hr> <p>
753
754<p>
755<h3>
756Changes between NTL 3.7a and 3.8a
757</h3>
758<p>
759
760This is backward compatible with previous versions.
761
762
763<ul>
764<li>
765Added conversion routines from <tt>unsigned</tt> <tt>int</tt>
766and <tt>unsigned</tt> <tt>long</tt> to
767<tt>ZZ</tt>, <tt>RR</tt>, <tt>xdouble</tt>, and <tt>quad_float</tt>.
768
769<li>
770Added routines <tt>GF2XFromBytes</tt> and <tt>BytesFromGF2X</tt>
771for conversion between byte vectors and polynomials over <tt>GF(2)</tt>,
772along with routines <tt>NumBits</tt> and <tt>NumBytes</tt>
773for such polynomials.
774See <a href="GF2X.txt"><tt>GF2X.txt</tt></a> for details.
775
776<li>
777Added a hack in the <tt>ZZX</tt> factorizer
778to exploit polynomials of the form <tt>g(x^k)</tt>.
779This can be disabled by setting the variable <tt>ZZXFac_PowerHack</tt>
780to zero.
781See <a href="ZZXFactoring.txt"><tt>ZZXFactoring.txt</tt></a>
782for details.
783
784<li>
785Improved the hensel system solver <tt>solve1</tt>.
786See <a href="mat_ZZ.txt"><tt>mat_ZZ.txt</tt></a> for details.
787
788<li>
789Changed documentation for <tt>RationalReconstruction</tt>
790to reflect the Wang, Guy, Davenport bounds.
791See <a href="ZZ.txt"><tt>ZZ.txt</tt></a> for details.
792
793<li>
794Improved the routine <tt>GenPrime</tt> a bit.
795
796<li>
797Some other small tweaks here and there.
798No real bug fixes.
799
800<li>
801Polished the documentation a bit, adding more examples.
802
803</ul>
804
805<p> <hr> <p>
806
807<p>
808<h3>
809Changes between NTL 3.6b and 3.7a
810</h3>
811<p>
812
813This is backward compatible with previous versions.
814
815<ul>
816<li>
817Added a "rational reconstruction" routine.
818See the routine <tt>ReconstructRational</tt> in <a href="ZZ.txt">ZZ.txt</a>.
819<li>
820Added another routine for solving linear systems over <tt>ZZ</tt>
821that is based on Hensel lifting, rather than Chinese Remaindering.
822It can be significantly faster in some cases.
823See the routine <tt>solve1</tt> in <a href="mat_ZZ.txt">mat_ZZ.txt</a>).
824<li>
825Some performace tuning, especially CRT and polynomial interpolation code.
826<li>
827Various documentation corrections.
828<li>
829Added more "overflow checks" here and there to ensure programs crash gracefully
830when certain things get too big.
831<li>
832Fixed a "benign" bug (i.e., it would never get triggered on any of today's
833machines).
834<li>
835Removed references to <tt>&lt;malloc.h&gt;</tt>, which were unnecessary,
836non-standard, and caused problems on some platforms.
837</ul>
838
839<p>
840<hr>
841
842<p>
843<h3>
844Changes between NTL 3.6a and 3.6b
845</h3>
846<p>
847
848Bug fixes.
849
850<p>
851<hr>
852
853<p>
854<h3>
855Changes between NTL 3.5a and 3.6a
856</h3>
857<p>
858
859This version is backward compatible with 3.5a.
860
861<p>
862
863<ul>
864
865<li>
866A few small bug fixes and performance enhancements.
867
868<li>
869Changes to the <tt>ZZX</tt> factoring routines that in some
870cases yield dramatic performance improvements
871(<a href="tour-time.html">more details</a>).
872
873</ul>
874
875<p>
876<hr>
877
878
879<p>
880<h3>
881Changes between NTL 3.1b and 3.5a
882</h3>
883<p>
884
885<b>Please note.</b> This version is <b>NOT</b> completely backward compatible.
886
887<p>
888
889Summary of changes:
890
891<ul>
892
893<li>
894Improved performance of the "all integer" LLL routine.
895
896<li>
897Put in a better pseudo-random number generator,
898and added ZZ/byte array conversions.
899
900<li>
901Improved performance of primality test, and added a
902more convenient routine <tt>GenPrime</tt>.
903
904<li>
905Overloaded NTL's vector placement "new" operator in a different
906way to avoid conflicts with standard <tt>C++</tt> library.
907
908<li>
909Renamed many macros.
910
911<li>
912Renamed header files.
913
914<li>
915Made some changes to the packaging
916the installation procedure.
917
918</ul>
919
920<p>
921<b>Renamed Macros.</b>
922I renamed many macros defined in NTL header files.
923
924<p>
925The reason is that I want to minimize namespace pollution.
926Someday, NTL will be wrapped in a namespace, and when that happens
927the only remaining namespace pollution problems will be caused by macros.
928Eliminating all macros from NTL is not feasible.
929Instead, all NTL defined macros now begin with the prefix "NTL_",
930which reduces the namespace pollution to an ecceptable level.
931You will probably not be affected by this, unless you
932do some low level hacking using a macro like <tt>ZZ_NBITS</tt>
933(now called <tt>NTL_NBITS</tt>), or unless you create your
934own NTL vectors using a macro like <tt>ntl_vector_decl</tt>
935(now called <tt>NTL_vector_decl</tt>).
936
937<p>
938For a complete list of affected names, see <a href="names.txt">names.txt</a>.
939
940<p>
941Adapting to this name change should be painless, as there is a
942program to translate source files from the old naming convention to the new.
943The file "newnames.c",
944can be compiled as either a <tt>C</tt> or <tt>C++</tt>
945program.
946The program is a "filter" that copies its input to its output,
947replacing all the old macro names by the new macro names.
948<p>
949In the WinNTL distribibution, "newnames.c" is called
950"newnames.cpp" and is located in the directory
951"newnames".
952
953
954<p>
955<b>Renamed header files.</b>
956The names of header files themeselves pollute another (extra-linguitsic) namespace.
957To alleviate this problem, the header files have been renamed.
958Instead of
959<pre>
960   #include "foo.h"
961</pre>
962one now should write
963<pre>
964   #include &lt;NTL/foo.h&gt;
965</pre>
966The only exceptions are the old header files "ntl_vector.h",
967"ntl_matrix.h", and "ntl_pair.h", which are now called
968<tt>&lt;NTL/vector.h&gt;</tt>, <tt>&lt;NTL/matrix.h&gt;</tt>, and
969<tt>&lt;NTL/pair.h&gt;</tt>.
970
971<p>
972<b>Installation procedure.</b>
973Now all
974NTL flags like NTL_LONG_LONG, NTL_AVOID_FLOAT, etc., can  now be set
975by editing the special file "include/NTL/config.h".
976See details in that file.
977The reason for this change is that this allows all of these settings
978to be made when NTL is configured and built.
979Clients of NTL will then automatically use consistent settings.
980One should not set these flags on the compiler command line as previously.
981
982
983<p>
984Pentium/Linux people should no longer have to worry
985about the NTL_X86_FIX flag. NTL now psychically deduces
986the "right thing to do", although if its psychic abilities fail,
987you can override it with flags in "include/NTL/config.h".
988
989<p>
990The "packaging" in the Unix distribution is slightly
991different, but hopefully nicer.
992Among other things, the tar file now unpacks into a sub-directory of the current directory.
993See <a href="tour-unix.html">the unix installation section</a>
994for more details.
995The Windows zip file now also
996unpacks into  sub-directory.
997
998
999<p>
1000<b>My apologies.</b>
1001Although these changes are minor, they will cause some NTL
1002users some inconvenience.
1003I apologize for this.
1004I really, really hope there are no more changes like this
1005(see my <a href="tour-roadmap.html">roadmap</a> of NTL's future).
1006
1007<p>
1008<hr>
1009
1010
1011<p>
1012<h3>
1013Changes between NTL 3.1a and 3.1b
1014</h3>
1015<p>
1016
1017Defined functions <tt>div(GF2X,GF2X,GF2)</tt> and <tt>div(GF2X,GF2X,long)</tt>,
1018which had not been defined in earlier versions.
1019Affected file: <tt>GF2X.c</tt>.
1020Most programs never use this, and most linkers do not complain
1021if these are missing (but some do).
1022
1023<p>
1024<hr>
1025
1026<p>
1027<h3>
1028Changes between NTL 3.0f and 3.1a
1029</h3>
1030<p>
1031
1032This version is backward compatible with previous versions.
1033
1034<p>
1035
1036<ul>
1037<li>
1038Added floating point LLL routines based on Givens rotations,
1039instead of classical Gramm-Schmidt orthogonalization.
1040This is a more stable, but somewhat slower, method.
1041See <a href="LLL.txt">LLL.txt</a> for details.
1042
1043<li>
1044Added support for irreducible trinomials and pentanomials
1045over GF(2). The <tt>GF2XModulus</tt> routines,
1046and by extension, the <tt>GF2E</tt> routines,
1047now exploit moduli of this special form.
1048The new routine <tt>BuildSparseIrred</tt> in <tt>GF2XFactoring</tt>
1049builds irreducibles of this form.
1050
1051<li>
1052Also implemented a faster modular inversion routine
1053for <tt>GF2X</tt>, and improved the performance of <tt>ZZ_pX</tt>
1054multiplication for small degree polynomials.
1055</ul>
1056
1057<p>
1058<hr>
1059
1060<p>
1061<h3>
1062Changes between NTL 3.0e and 3.0f
1063</h3>
1064<p>
1065
1066<ul>
1067<li>
1068Fixed a bug (another one) affecting routines
1069<pre>
1070   RandomBits, RandomBits_ZZ
1071</pre>
1072in module <tt>ZZ</tt>.
1073Affected source file: <tt>lip.c</tt>.
1074
1075<li>
1076Bug fix and performance tweak in <tt>ZZX</tt> factorizer.
1077Affected source file: <tt>ZZXFactoring.c</tt>.
1078   
1079</ul>
1080
1081<p>
1082<hr>
1083
1084<p>
1085<h3>
1086Changes between NTL 3.0 and 3.0e
1087</h3>
1088<p>
1089
1090<ul>
1091<li>
1092Fixed a bug affecting routines
1093<pre>
1094   RandomBits, RandomBits_ZZ, RandomBits_long
1095</pre>
1096in module <tt>ZZ</tt>.
1097The only source files that are affected and require re-compilation are
1098<pre>
1099   ZZ.c, lip.c
1100</pre>
1101
1102<li>
1103Note about names:
11043.0a-c were "pre-releases", which makes the "first release" 3.0d,
1105and hence this bug fix 3.0e.
1106   
1107</ul>
1108
1109<p>
1110<hr>
1111
1112
1113<p>
1114
1115<h3>
1116Changes between NTL 2.0 and 3.0
1117</h3>
1118<p>
1119
1120
1121<ul>
1122
1123<li>
1124Added functionality:
1125<p>
1126
1127<ul>
1128
1129<li>
1130Added classes vec_GF2 and mat_GF2 for fast linear algebra over GF(2).
1131
1132<li>
1133Added classes ZZ_pE, ZZ_pEX, zz_pE, zz_pEX, supporting polynomial
1134arithmetic over extension rings/fields over prime fields.
1135
1136<li>
1137Added John Abbott's pruning heuristic to the ZZX factoring routine.
1138
1139<li>
1140Speeded up multiplication in zz_pX for small p (this also helps
1141the ZZX factoring routine).
1142
1143<li>
1144Added some some transcendental functions (e.g., exp, log, pi) to RR.
1145
1146<li>
1147Added verbose mode and pruning to the XD and RR variants of LLL.
1148
1149</ul>
1150<p>
1151
1152<li>
1153Improved programming interface:
1154with this version, I've taken an the opportunity to
1155give the programming interface a "professional facelift".
1156In previous releases, I've tried to maintain backward compatability
1157as much as possible, but to make the badly needed improvements
1158to the interface that I've made with this release, this was not
1159possible.
1160<p>
1161NTL 3.0 is not backward compatable with NTL 2.0.
1162<p>
1163I apologize to NTL users for this, but it is a bit of painful
1164medicine that should only be necessary to take just this one time
1165(but then as a <tt>C++</tt> programmer, you must already
1166be used to suffering ;-).
1167Just about all of the incompatabilities are detectable by the compiler.
1168See below for a detailed list of the changes and
1169some tips on making the transition.
1170<p>
1171The new interface is much more enjoyable to work with,
1172and I don't foresee any changes to the interace in the future.
1173Here is a broad overview of the changes:
1174<p>
1175
1176<ul>
1177<li>
1178Added functional/operator notation consistently throughout NTL,
1179making it possible to write much more concise and readable code.
1180<li>
1181Got rid of automatic type conversions:  these cause just too
1182many problems.  But I've overloaded all of the basic arithmetic
1183operators and procedures so as to emulate a natural kind
1184of "type promotion" logic.  With these promotions, along with
1185a  full compliment of conversion functions, one hardly misses
1186the automatic conversions.
1187<li>
1188Got rid of the macros
1189<pre>
1190   vector(T), matrix(T), pair(T),
1191</pre>
1192which were causing too many name space problems.
1193
1194<li>
1195Made assignment operators have the "correct" return type.
1196<li>
1197Introduced a more powerful and flexible mechanism for modulus changing.
1198<li>
1199Cleaned up numerous other minor problems.
1200</ul>
1201
1202</ul>
1203
1204<p>
1205<h4>
1206Compatibility
1207</h4>
1208<p>
1209
1210Here is a detailed list of the changes to the programming
1211interface.
1212<p>
1213
1214
1215<ul>
1216
1217<li>
1218The names of the classes
1219<pre>
1220   BB, BB_p, BB_pX
1221</pre>
1222have been changed to
1223<pre>
1224   GF2X, GF2E, GF2EX
1225</pre>
1226
1227<li>
1228There is also a class <tt>GF2</tt> to represent GF(2).
1229Many of the functions relating to <tt>BB, BB_p, BB_pX</tt>
1230had argument and return-value types of type <tt>long</tt>
1231that are now of the more appropriate type <tt>GF2</tt>.
1232This change was needed so that the interface would be consistent
1233with that of the new classes
1234<pre>
1235   ZZ_pE, ZZ_pEX, zz_pE, zz_pEX.
1236</pre>
1237
1238<li>
1239The explicit conversion operator from <tt>GF2X</tt> 
1240(the new <tt>BB</tt>) to <tt>GF2EX</tt> (the new <tt>BB_pX</tt>)
1241has different semantics: it now performs a coefficient lift,
1242instead of creating a constant polynomial.
1243
1244<li>
1245The conversion operator "<tt>&lt;&lt;</tt>" has been retired.
1246Now instead of
1247<pre>
1248   x &lt;&lt; a;
1249</pre>
1250one writes
1251<pre>
1252   conv(x, a);
1253</pre>
1254<p>
1255Operator "<tt>&lt;&lt;</tt>" is now used for shift operations.
1256<li>
1257Every conversion routine now has a corresponding functional version
1258which has the name <tt>to_T</tt>, where <tt>T</tt> is the result type.
1259These new names replace old names that were less consistent.
1260So instead of
1261<pre>
1262   x = Long(a);
1263</pre>
1264one writes
1265<pre>
1266   x = to_long(a);
1267</pre>
1268
1269
1270<li>
1271The names of the routines
1272<pre>
1273   ZZ_pInit, zz_pInit, zz_pFFTInit, GF2EInit
1274</pre>
1275have been changed to
1276<pre>
1277   zz_p::init, zz_p::init, zz_p::FFTInit, GF2E::init
1278</pre>
1279
1280<li>
1281The names of the routines
1282<pre>
1283   and, or, xor
1284</pre>
1285for class <tt>ZZ</tt> have
1286changed to
1287<pre>
1288   bit_and, bit_or, bit_xor,
1289</pre>
1290because the new <tt>C++</tt>
1291standard defines these as reserved words.
1292
1293<li>
1294The function <tt>LowBits</tt> for <tt>ZZ</tt> is now called <tt>trunc</tt>.
1295
1296<li>
1297Polynomial inversion mod <tt>X^n</tt> has changed from <tt>inv</tt>
1298to <tt>InvTrunc</tt>.
1299
1300<li>
1301Modular trace, norm, minimum polynomial and characteristic
1302polynomial have changed from
1303<pre>
1304   trace, norm, MinPoly, IrredPoly, CharPoly
1305</pre>
1306to
1307<pre>
1308   TraceMod, NormMod, MinPolyMod, IrredPolyMod, CharPolyMod
1309</pre>
1310
1311
1312<li>
1313For the class <tt>ZZX</tt>, the functions
1314<pre>
1315   DivRem, div, rem, /, %, /=, %=
1316</pre>
1317have new semantics when dividing by non-monic polynomials.
1318The old semantics are provided by new routines
1319<pre>
1320   PseudoDivRem, PseudoDiv, PseudoRem.
1321</pre>
1322
1323<li>
1324The <tt>UpdateMap</tt> routines have slightly different semantics:
1325in versions &lt; 3.0, the output always had length n;
1326now high-order zeroes are stripped.
1327
1328<li>
1329The classes <tt>ZZ_pBak</tt>, <tt>zz_pBak,</tt> etc., 
1330have just slightly different semantics;  I can't imagine
1331any reasonable program detecting a difference.
1332
1333<li>
1334The assignment operator and copy constructor for the class <tt>RR</tt>
1335have different semantics: they now produce exact copies, instead
1336of rounding to current precision.
1337
1338<li>
1339All of the NTL compiler flags now start with <tt>NTL_</tt>
1340to avoid name space problems.
1341
1342<li>
1343All of the files "zz_p.h", vec_zz_p.h", etc., have been eliminated.
1344Use instead the names "lzz_p.h", "vec_lzz_p.h", etc.
1345
1346</ul>
1347
1348<p>
1349<h4>
1350Tips on making the transition
1351</h4>
1352<p>
1353
1354<ul>
1355
1356<li>
1357Apply this <a href="sedscript.txt">sed script</a> to make
1358most of the necessary syntactic changes.
1359
1360<li>
1361Re-compile old NTL programs with the flag
1362<pre>
1363   -DNTL_TRANSITION
1364</pre>
1365See <a href="flags.txt">flags.txt</a> for details on how
1366this will help your compiler detect remaining incompatabilities.
1367In particular, any uses of operator <tt>&lt;&lt;</tt>
1368in its old role as a conversion operator will cause the compiler
1369to raise an error.
1370You can then convert all of these to the new notation.
1371
1372</ul>
1373
1374
1375<p>
1376<hr>
1377
1378
1379<p>
1380<h3>
1381Changes between NTL 1.7 and 2.0
1382</h3>
1383<p>
1384
1385<ul>
1386<li>
1387Implementation of classes BB (polynomials over GF(2))
1388and BB_pX (polynomials over GF(2^n)).
1389
1390<li>
1391A more consistent and natural interface, including arithmetic operators
1392and a disciplined use of automatic conversion.
1393So now one can write
1394<pre>
1395   x = a * b + c;
1396</pre>
1397instead of
1398<pre>
1399   mul(x, a, b);
1400   add(x, x, c);
1401</pre>
1402as one must in older versions of NTL.
1403The operator notation leads to somewhat less efficient code,
1404and one can always use the old notation in situations
1405where efficiency is critical.
1406Despite the new programming interface,
1407care has been taken to ensure backward compitability;
1408pre-existing programs that use NTL should still work.
1409
1410<li>
1411Windows port.
1412
1413<li>
1414Added compile-time flag that allows one to exploit
1415"long long" data type if it exists (this especially helps on Pentium/Linux
1416platforms).
1417
1418<li>
1419Added compile-time flag to get better quad_float code on
1420Pentium/Linux platforms.
1421
1422<li>
1423A few bug fixes and performance tuning.
1424</ul>
1425
1426<p>
1427<hr>
1428
1429
1430<p>
1431<h3>
1432Changes between NTL 1.5 and NTL 1.7
1433</h3>
1434<p>
1435
1436<ul>
1437<li>
1438Incorporation of Keith Briggs' quadratic precision package.
1439
1440<li>
1441Much faster and more robust lattice basis reduction,
1442including Schnorr-Horner "volume heuristic" for Block Korkin
1443Zolotarev reductions, and a new quadratic precision LLL variant
1444that is much more robust.
1445
1446<li>
1447A few bug fixes.
1448
1449</ul>
1450
1451
1452<p>
1453<hr>
1454
1455<p>
1456<h3>
1457Changes between NTL 1.0 and NTL 1.5
1458</h3>
1459<p>
1460
1461
1462<ul>
1463<li>
1464Implementation of Schnorr-Euchner algorithms for
1465lattice basis reduction, including deep insertions and
1466block Korkin Zolotarev reduction.
1467These are significantly faster than the LLL algorithm
1468in NTL 1.0.
1469
1470<li>
1471Implementation of arbitrary-precision floating point.
1472
1473<li>
1474Implementation of double precision with extended exponent range,
1475which is useful for lattice basis reduction when the coefficients
1476are large.
1477
1478<li>
1479Faster polynomial multiplication over the integers,
1480incorporating the Schoenhagge-Strassen method.
1481
1482<li>
1483Compilation flags that increase performance on machines
1484with poor floating-point performance.
1485
1486<li>
1487Sundry performance tuning and a few bug fixes.
1488
1489</ul>
1490
1491<center>
1492<a href="tour-roadmap.html"><img src="arrow1.gif" alt="[Previous]" align=bottom></a>
1493 <a href="tour.html"><img src="arrow2.gif" alt="[Up]" align=bottom></a> 
1494<a href="tour-ack.html"> <img src="arrow3.gif" alt="[Next]" align=bottom></a>
1495</center>
1496
1497</body>
1498</html>
Note: See TracBrowser for help on using the repository browser.