Context Navigation

source: git/ntl/doc/tour-struct.html @ 2cfffe

spielwiese

Last change on this file since 2cfffe was 2cfffe, checked in by Hans Schönemann <hannes@…>, 21 years ago
This commit was generated by cvs2svn to compensate for changes in r6316, which included commits to RCS files with non-trunk default branches. git-svn-id: file:///usr/local/Singular/svn/trunk@6317 2c84dea3-7e68-4137-9b89-c4e89433aadc
Property mode set to `100644`
File size: 18.0 KB

Line
1	<html>
2	<head>
3	<title>
4	A Tour of NTL: Programming Interface </title>
5	</head>
6
7	<body bgcolor="#fff9e6">
8	<center>
9	<a href="tour-examples.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-modules.html"> <img src="arrow3.gif" alt="[Next]" align=bottom></a>
12	</center>
13
14	<h1>
15	<p align=center>
16	A Tour of NTL: Programming Interface
17	</p>
18	</h1>
19
20	<p> <hr> <p>
21
22	In this section, we give a general overview of the
23	NTL's programming interface.
24
25	<p>
26	<p>
27	<h3>
28	Basic Ring Classes
29	</h3>
30	<p>
31
32	The basic ring classes are:
33	<ul>
34	<li>
35	<tt>ZZ</tt>: big integers
36	<li>
37	<tt>ZZ_p</tt>: big integers modulo <tt>p</tt>
38	<li>
39	<tt>zz_p</tt>: integers mod "single precision" <tt>p</tt>
40	<li>
41	<tt>GF2</tt>: integers mod 2
42	<li>
43	<tt>ZZX</tt>: univariate polynomials over <tt>ZZ</tt>
44	<li>
45	<tt>ZZ_pX</tt>: univariate polynomials over <tt>ZZ_p</tt>
46	<li>
47	<tt>zz_pX</tt>: univariate polynomials over <tt>zz_p</tt>
48	<li>
49	<tt>GF2X</tt>: polynomials over GF2
50	<li>
51	<tt>ZZ_pE</tt>: ring/field extension over ZZ_p
52	<li>
53	<tt>zz_pE</tt>: ring/field extension over zz_p
54	<li>
55	<tt>GF2E</tt>: ring/field extension over GF2
56	<li>
57	<tt>ZZ_pEX</tt>: univariate polynomials over <tt>ZZ_pE</tt>
58	<li>
59	<tt>zz_pEX</tt>: univariate polynomials over <tt>zz_pE</tt>
60	<li>
61	<tt>GF2EX</tt>: univariate polynomials over <tt>GF2E</tt>
62	</ul>
63
64	<p>
65	All these classes all support basic
66	arithmetic operators
67	<pre>
68	+, -, (unary) -, +=, -=, ++, --,
69	, =, /, /=, %, %=.
70	</pre>
71
72	<p>
73	However, the operations
74	<pre>
75	%, %=
76	</pre>
77	only exist for integer and polynomial classes, and
78	do not exist
79	for classes
80	<pre>
81	ZZ_p, zz_p, GF2, ZZ_pE, zz_pE, GF2E.
82	</pre>
83
84	<p>
85	The standard equality operators (<tt>==</tt> and <tt>!=</tt>)
86	are provided for each class.
87	In addition, the class <tt>ZZ</tt>
88	supports the usual inequality
89	operators.
90
91	<p>
92	The integer and polynomial classes also support "shift operators"
93	for left and right shifting.
94	For polynomial classes, this means multiplication or division
95	by a power of <tt>X</tt>.
96
97	<p>
98	<p>
99	<h3>
100	Floating Point Classes
101	</h3>
102	<p>
103
104	In addition to the above ring classes, NTL also provides three
105	different floating point classes:
106	<ul>
107	<li>
108	<tt>xdouble</tt>: "double precision" floating point with
109	extended exponent range (for very large numbers);
110	<li>
111	<tt>quad_float</tt>: "quasi" quadruple-precision floating point;
112	<li>
113	<tt>RR</tt>: aribitrary precision floating point.
114	</ul>
115
116
117	<p>
118	<p>
119	<h3>
120	Vectors and Matrices
121	</h3>
122	<p>
123
124	There are also vectors and matrices over
125	<pre>
126	ZZ ZZ_p zz_p GF2 ZZ_pE zz_pE GF2E RR
127	</pre>
128	which support the usual arithmetic operations.
129
130	<p>
131	<p>
132	<h3>
133	Functional and Procedural forms
134	</h3>
135	<p>
136
137	Generally, for any function defined by NTL, there is
138	a functional form, and a procedural form.
139	For example:
140
141	<pre>
142	ZZ x, a, n;
143	x = InvMod(a, n); // functional form
144	InvMod(x, a, n); // procedural form
145	</pre>
146
147	<p>
148	This example illustrates the normal way these two forms differ
149	syntactically.
150	However, there are exceptions.
151
152	First, if there is a operator that can play the role of the
153	functional form, that is the notation used:
154
155	<pre>
156	ZZ x, a, b;
157	x = a + b; // functional form
158	add(x, a, b); // procedural form
159	</pre>
160
161	Second, if the functional form's name would be ambiguous,
162	the return type is simply appended to its name:
163
164	<pre>
165	ZZ_p x;
166	x = random_ZZ_p(); // functional form
167	random(x); // procedural form
168	</pre>
169
170	Third, there are a number of conversion functions (see below), whose name
171	in procedural form is <tt>conv</tt>, but whose name in
172	functioanl form is <tt>to_T</tt>, where <tt>T</tt> is the return type:
173
174	<pre>
175	ZZ x;
176	double a;
177
178	x = to_ZZ(a); // functional form
179	conv(x, a); // procedural form
180	</pre>
181
182
183
184	<p>
185	The use of the procedural form may be more efficient,
186	since it will generally avoid the creation of a temporary object
187	to store its result.
188	However, it is generally silly to get too worked up about
189	such efficiencies, and the functional form is usually preferable
190	because the resulting code is usually easier to understand.
191
192	<p>
193	The above rules converning procedural and functional forms apply
194	to essentially all of the arithmetic classes supported by NTL,
195	with the exception of
196	<tt>xdouble</tt> and <tt>quad_float</tt>.
197	These two classes only support the functional/operator notation
198	for arithmetic operations (but do support both forms for conversion).
199
200
201
202
203	<p>
204	<p>
205	<h3>
206	Conversions and Promotions
207	</h3>
208	<p>
209
210	NTL does not provide automatic conversions from, say,
211	<tt>int</tt> to <tt>ZZ</tt>.
212	Most <tt>C++</tt> experts consider such automatic conversions
213	bad form in library design, and I would agree with them.
214	Some earlier versions of NTL had automatic conversions,
215	but they caused too much trouble, so I took them out.
216	Indeed, combining function overloading and automatic conversions
217	is generally considered by programming language experts
218	to be a bad idea (but that did not stop
219	the designers of <tt>C++</tt> from doing it).
220	It makes it very difficult to figure out which function
221	ought to be called.
222	<tt>C++</tt> has an incredibly complex set of rules for doing this;
223	moreover, these rules have been changing over time,
224	and no two compilers seem to implement exactly the same
225	set of rules.
226	And if a compiler has a hard time doing this, imagine what it
227	is like for a programmer.
228	In fact, the rules have become so complicated, that the latest
229	edition of Stroustrup's <tt>C++</tt> book does not even explain them,
230	although
231	earlier verisons did.
232	Possible explanations:
233	<em>(a)</em> Stroustrup thinks his readers are
234	too stupid to understand the rules, or
235	<em>(b)</em> Stroustrup does not understand the rules, or
236	<em>(c)</em> the rules are so complicated that Stroustrup finds it embarassing
237	to talk about them.
238
239	<p>
240	Now it should be more clear why I didn't just implement,
241	say, the <tt>int</tt> to <tt>ZZ</tt> conversion function
242	as a <tt>ZZ</tt> constructor taking an argument of type <tt>int</tt>,
243	instead of calling it <tt>to_ZZ</tt>.
244	This would have introduced an automatic conversion, which I
245	wanted to avoid for the reasons explained above.
246	"OK. But why not make the constructor <tt>explict</tt>?" you ask.
247	The main reason is that this is a fairly recently introduced
248	language feature that is not universally available.
249	And even if it were, what about, say, the <tt>ZZ</tt> to <tt>int</tt>
250	conversion routine?
251	How would you name <em>that</em>?
252	The strategy I chose is simple, consistent, and portable.
253
254
255	<p>
256
257	As mentioned above, there are numerous explicit conversion routines,
258	which come in both functional and procedural forms.
259	A complete list of these can be found in
260	<a href="conversions.txt">conversions.txt</a>.
261	This is the only place these are documented; they do not appear
262	in the ".txt" files.
263
264	<p>
265
266	Even though there are no automatic conversions, users
267	of NTL can still have most of their benefits, while
268	avoiding their pitfalls.
269	This is because all of the basic arithmetic operations
270	(in both their functional and procedural forms),
271	comparison operators, and assignment are overloaded
272	to get the effect of automatic "promotions".
273	For example:
274
275	<pre>
276	ZZ x, a;
277
278	x = a + 1;
279	if (x < 0)
280	mul(x, 2, a);
281	else
282	x = -1;
283	</pre>
284
285	<p>
286
287	These promotions are documented in the ".txt" files,
288	usually using a kind of "short hand" notation.
289	For example:
290
291	<pre>
292	ZZ operator+(const ZZ& a, const ZZ& b);
293
294	// PROMOTIONS: operator + promotes long to ZZ on (a, b).
295	</pre>
296
297	This means that in addition to the declared function, there
298	are two other functions that are logically equivalent to the following:
299	<pre>
300	ZZ operator+(long a, const ZZ& b) { return to_ZZ(a) + b; }
301	ZZ operator+(const ZZ& a, long b) { return a + to_ZZ(b); }
302	</pre>
303
304	<p>
305	Note that this is not how NTL actually implements these functions.
306	It is in generally more efficient to write
307	<pre>
308	x = y + 2;
309	</pre>
310	than it is to write
311	<pre>
312	x = y + to_ZZ(2);
313	</pre>
314	The former notation avoids the creation and destruction
315	of a temporary <tt>ZZ</tt>
316	object to hold the value 2.
317
318	<p>
319	Also, don't have any inhibitions about writing tests like
320	<pre>
321	if (x == 0) ...
322	</pre>
323	and assignments like
324	<pre>
325	x = 1;
326	</pre>
327	These are all optimized, and do not execute significaltly slower
328	than the "lower level" (and much less natural)
329	<pre>
330	if (IsZero(x)) ...
331	</pre>
332	and
333	<pre>
334	set(x);
335	</pre>
336
337	<p>
338	Some types have even more promotions.
339	For example, the type <tt>ZZ_pX</tt> has promotions
340	from <tt>long</tt> and <tt>ZZ_p</tt>.
341	Thus, the <tt>add</tt> function for <tt>ZZ_pX</tt> takes the following
342	argument types:
343	<pre>
344	(ZZ_pX, ZZ_pX), (ZZ_pX, ZZ_p), (ZZ_pX, long), (ZZ_p, ZZ_pX), (long, ZZ_pX)
345	</pre>
346	Each of these functions effectively converts the argument to be promoted
347	to a <tt>ZZ_pX</tt>.
348
349	<p>
350	Note that when promoting a pair of arguments, at least one
351	of the arguments must be of the target type.
352
353	<p>
354	I have tried to be very consistent with these promotions so
355	that one usually won't need to hunt through the documentation.
356	For a given type, there is a natural, fixed set of types
357	that promote to it.
358	Here is the complete list:
359	<pre>
360	destination: source
361
362	xdouble: double
363	quad_float: double
364	RR: double
365	ZZ: long
366	ZZ_p: long
367	ZZ_pX: long, ZZ_p
368	zz_p: long
369	ZZ_pX: long, zz_p
370	ZZX: long, ZZ
371	GF2: long
372	GF2X: long, GF2
373	GF2E: long, GF2
374	GF2EX: long, GF2, GF2E
375	ZZ_pE: long, ZZ_p
376	ZZ_pEX: long, ZZ_p, ZZ_pE
377	zz_pE: long, zz_p
378	zz_pEX: long, zz_p, zz_pE
379	</pre>
380
381	<p>
382	All the promotions are documented, but here
383	are a few general rules describing the available promotions:
384
385	<ul>
386
387	<li>
388	Promotions apply uniformly to both procedural and functional
389	forms, as well as to the corresponding assignment operator forms.
390	E.g.,
391	<pre>
392	x = x + 2;
393	add(x, x, 2);
394	x += 2;
395	</pre>
396
397	<li>
398	The addition, subtraction, multiplication, equality and comparison
399	routines always promote both arguments. E.g.,
400	<pre>
401	x = 2 + y;
402	add(x, 2, y);
403	if (3 > x \|\| y == 5) ...
404	</pre>
405
406	<li>
407	The assignment operator always promotes the right-hand side.
408	E.g.,
409	<pre>
410	x = 2;
411	</pre>
412
413	<li>
414	For non-integer, non-polynomial types, the division routine
415	promotes both arguments.
416	E.g.,
417	<pre>
418	RR x, y, z;
419	...
420	x = 1.0/y;
421	z = y/2.0;
422	</pre>
423
424	For integer or polynomial types, the division routine
425	promotes the denominator only. E.g.,
426	<pre>
427	ZZ x, y;
428	...
429	y = x/2;
430	</pre>
431
432
433	<li>
434	Matrix by scalar and vector by scalar multiplication promote the scalar.
435	E.g.,
436	<pre>
437	vec_ZZ v, w;
438	...
439	v = w*2;
440	v = 2*w;
441	v *= 2;
442	</pre>
443
444
445	<li>
446	The monomial constructors for polynomials
447	and the corresponding <tt>SetCoeff</tt> routines
448	promote the coefficient argument.
449	E.g.,
450	<pre>
451	ZZX f;
452	f = ZZX(3, 5); // f == 5*X^3
453	SetCoeff(f, 0, 2); // f == 5*x^3 + 2;
454	</pre>
455
456	<li>
457	In module <tt>ZZ</tt>, the modular arithmetic routines, as well as
458	the bit-wise <i>and</i>, <i>or</i>, and <i>xor</i> routines promote their arguments.
459	There are also several other routines in module <tt>ZZ</tt>
460	that have both <tt>ZZ</tt> and <tt>long</tt> versions, e.g.,
461	<tt>NumBits</tt>, <tt>bit</tt>, <tt>weight</tt>.
462	Check the documentation in <a href="ZZ.txt"><tt>ZZ.txt</tt></a>
463	for complete details.
464
465	</ul>
466
467	<p>
468
469
470	<p>
471	<p>
472	<h3>
473	Some Conversion and Promotion Technicalities
474	</h3>
475	<p>
476
477	<p>
478	Usually, conversions and promotions are semantically equivalent.
479	There are three exceptions, however.
480
481	<p>
482	One exception
483	is conversion of floating point <tt>double</tt> to
484	<tt>ZZ</tt>.
485	The safest way to do this is to apply an explicit conversion operator,
486	and not to rely on promotions.
487	For example, consider
488	<pre>
489	ZZ a; double x;
490
491	a = a + x;
492	</pre>
493	This is equivialent to
494	<pre>
495	a = a + long(x);
496	</pre>
497	One could also use an explicit conversion function:
498	<pre>
499	a = a + to_ZZ(x);
500	</pre>
501	The second version guarantees that there is no loss of precision,
502	and also guarantees that the floor of <tt>x</tt> is computed.
503	With the first version, one may lose precision when <tt>x</tt>
504	is converted to a <tt>long</tt>, and also the direction of truncation
505	for negative numbers is implementation dependent
506	(usually truncating towards zero, instead of computing the floor).
507	<p>
508	The second exception is conversion of <tt>unsigned int</tt>
509	or <tt>unsigned long</tt> to <tt>ZZ</tt>.
510	Again, the safest way to do this is with an explicit conversion operator.
511	As above, if one relies on promotions, the unsigned integer
512	will be first converted to a <i>signed</i> <tt>long</tt>, which is most
513	likely not what was intended.
514	<p>
515	The third exception can occur
516	on 64-bit machines when
517	converting a signed or unsigned <tt>long</tt> to one of NTL's
518	extended precision floating-point types (<tt>RR</tt> or <tt>quad_float</tt>).
519	These types only provide promotions from <tt>double</tt>,
520	and converting a <tt>long</tt> to a <tt>double</tt> on a 64-bit machine
521	can lead to a loss of precision.
522	Again, if one uses the appropriate NTL conversion routine,
523	no loss of precision will occur.
524
525	<p>
526
527	Another pitfall too avoid is initialzing <tt>ZZ</tt>s
528	with integer constants that are too big.
529	Consider the following:
530	<pre>
531	ZZ x;
532	x = 1234567890123456789012;
533	</pre>
534	This integer constant is too big, and this overflow
535	condition may or may not cause your compiler to give
536	you a warning or an error.
537	The easiest way to introduce such large constants into your
538	program is as follows:
539	<pre>
540	ZZ x;
541	x = to_ZZ("1234567890123456789012");
542	</pre>
543	Conversion functions are provided for converting <tt>C</tt> character strings
544	to the types <tt>ZZ</tt>, <tt>RR</tt>, <tt>quad_float</tt>,
545	and <tt>xdouble</tt>.
546
547	<p>
548	One should also be careful when converting to <tt>RR</tt>.
549	All of these conversions round to the current working precision, which is
550	usually, but not always what one wants.
551
552	<p>
553	<p>
554	<h3>
555	Aliasing
556	</h3>
557	<p>
558
559	An important feature of NTL is that aliasing of input and output
560	parameters is <i>always</i> allowed. For example, if you
561	write <tt>mul(x, a, b)</tt>, then <tt>a</tt> or <tt>b</tt>
562	may alias (have the same address as) <tt>x</tt>
563	(or any object that <tt>x</tt> contains, e.g., scalar/vector
564	or scalar/polynomial multiplication).
565
566
567	<p>
568	<p>
569	<h3>
570	Constructors, Destructors, and Memory Management
571	</h3>
572	<p>
573
574	NTL generally takes care of managing the space occupied by large,
575	dynamically sized objects, like objects of class <tt>ZZ</tt> or any of
576	NTL's dynamic vectors.
577	However, it is helpful to understand a little of what is happening behind the scenes.
578
579	<p>
580	Most classes are implemented as a pointer, and the default constructor
581	just sets this pointer to 0.
582	Space is allocated for the object as needed, and when the object's
583	destructor is called, the space is freed.
584	Exceptions to this are the "modular" classes <tt>ZZ_p</tt>, <tt>ZZ_pE</tt>, <tt>zz_pE</tt>,
585	and <tt>GF2E</tt>.
586	Since, for a given modulus, the sizes of these objects are fixed, the default constructor
587	allocates the appropriate amount of space.
588
589	<p>
590	Copies are "deep" rather than "shallow".
591	This means the data itself is copied, and not just a pointer to the data.
592	If the destination object does not have enough space to hold the source data,
593	then the space held by the destination object is "grown".
594	This is done using the <tt>C</tt> routine <tt>realloc()</tt>.
595	Note, however, that if the source object is smaller than the destination
596	object, the space held by the destination object is retained.
597	This strategy usually yields reasonable behaviour;
598	however, one can take explicit control of the situation if necessary, since
599	almost all NTL classes have a method <tt>kill()</tt>
600	which frees all space held by the object, and sets its state to
601	the default initial state (a value 0 or a zero-length vector).
602
603	<p>
604	The only exception to the above are the special classes <tt>ZZ_pBak</tt>,
605	<tt>ZZ_pContext</tt>, and the analogous classes for <tt>zz_p</tt>,
606	<tt>ZZ_pE</tt>, <tt>zz_pE</tt>, and <tt>GF2E</tt>.
607	These objects are implemented as referenced-counted pointers,
608	and copies are "shallow".
609
610	<p>
611	While we are discussing initialization, there is one technical point
612	worth mentioning.
613	It is safe to declare global objects of any NTL type (except modular types),
614	as long as one uses only the default constructor.
615	For example, the global declarations
616	<pre>
617	ZZ global_integer;
618	vec_ZZ_p global_vector;
619	</pre>
620	should always work, since their initialization only involves
621	setting a pointer to 0.
622	However,
623	one should avoid initializing global objects with
624	non-default constructors, and should avoid doing anything that would lead to
625	non-trivial computations with NTL objects
626	prior to the beginning of the execution of routine <tt>main()</tt>.
627	The reasons for this are quite esoteric and can only be appreciated
628	by a true
629	<tt>C++</tt> afficianado.
630	Actually, most such initializations and computations probably will work,
631	but it is somewhat platform dependant.
632
633	<p>
634	Normal people usually do none of these things, so all of this
635	should not matter too much.
636	There is, however, one possible exception to this.
637	A programmer might want to have a global constant initialized like this:
638	<pre>
639	const quad_float Pi = to_quad_float("3.1415926535897932384626433832795029");
640	</pre>
641	While this probably will work fine on most platforms,
642	it may not be an entirely portable construction,
643	since it will involve a non-trivial computation before
644	execution of <tt>main()</tt> begins.
645	A more portable strategy
646	is to define a function returning a read-only
647	reference:
648	<pre>
649	const quad_float& Pi()
650	{
651	static quad_float pi =
652	to_quad_float("3.1415926535897932384626433832795029");
653	return pi;
654	}
655	</pre>
656	and then call the function <tt>Pi()</tt> to get a read-only reference
657	to this constant value:
658	<pre>
659	area = Pi()rr;
660	</pre>
661	The initialization will then take place the first time <tt>Pi()</tt>
662	is called, which is presumably after <tt>main()</tt> starts,
663	and so everything should work fine.
664	This is a very simple and general strategy that most <tt>C++</tt>
665	experts recommend using whenever the initialization of a non-global
666	object requires non-trivial computation.
667
668
669
670
671
672
673	<p>
674
675	<center>
676	<a href="tour-examples.html"><img src="arrow1.gif" alt="[Previous]" align=bottom></a>
677	<a href="tour.html"><img src="arrow2.gif" alt="[Up]" align=bottom></a>
678	<a href="tour-modules.html"> <img src="arrow3.gif" alt="[Next]" align=bottom></a>
679	</center>
680
681
682	</body>
683	</html>

Note: See TracBrowser for help on using the repository browser.

Download in other formats: