<html>
<head>
<title>
A Tour of NTL: Examples: Vectors and Matrices </title>
</head>
<center>
<a href="tour-ex1.html"><img src="arrow1.gif" alt="[Previous]" align=bottom></a>
<a href="tour-examples.html"><img src="arrow2.gif" alt="[Up]" align=bottom></a>
<a href="tour-ex3.html"> <img src="arrow3.gif" alt="[Next]" align=bottom></a>
</center>
<h1>
<p align=center>
A Tour of NTL: Examples: Vectors and Matrices
</p>
</h1>
<p> <hr> <p>
<p>
The following routine sums up the
numbers in a vector of <tt>ZZ</tt>'s.
<!-- STARTPLAIN
#include <NTL/ZZ.h>
#include <NTL/vector.h>
using namespace std;
using namespace NTL;
ZZ sum(const Vec<ZZ>& v)
{
ZZ acc;
acc = 0;
for (long i = 0; i < v.length(); i++)
acc += v[i];
return acc;
}
ENDPLAIN -->
<!-- STARTPRETTY {{{ -->
<p><p><table cellPadding=10px><tr><td><font color="#000000"><font face="monospace">
<font color="#1773cc">#include </font><font color="#4a6f8b"><NTL/ZZ.h></font><br>
<font color="#1773cc">#include </font><font color="#4a6f8b"><NTL/vector.h></font><br>
<br>
<font color="#b02f60"><b>using</b></font> <font color="#008b00"><b>namespace</b></font> std;<br>
<font color="#b02f60"><b>using</b></font> <font color="#008b00"><b>namespace</b></font> NTL;<br>
<br>
ZZ sum(<font color="#008b00"><b>const</b></font> Vec<ZZ>& v)<br>
{<br>
ZZ acc;<br>
<br>
acc = <font color="#ff8b00">0</font>;<br>
<br>
<font color="#b02f60"><b>for</b></font> (<font color="#008b00"><b>long</b></font> i = <font color="#ff8b00">0</font>; i < v.length(); i++)<br>
acc += v[i];<br>
<br>
<font color="#b02f60"><b>return</b></font> acc;<br>
}<br>
</font></font></td></tr></table><p><p>
<!-- }}} ENDPRETTY -->
<p>
The class <tt>Vec<ZZ></tt> is a dynamic-length array of <tt>ZZ</tt>s;
more generally, NTL provides a template class <tt>Vec<T></tt>
for
dynamic-length
vectors over any type <tt>T</tt>.
Some history is in order here.
NTL predates the STL and the <tt>vector</tt> template
found in modern <tt>C++</tt>.
Older versions of NTL (prior to v6) did not use templates, but instead
defined generic vectors using macros.
By convention, NTL named these <tt>vec_T</tt>.
For backward compatibility, NTL now provides typedefs
all these "legacy" vector types.
<p>
Vectors in NTL are indexed from 0, but in many situations
it is convenient or more natural to index from 1.
The generic vector class allows for this;
the above example could be written as follows.
<!-- STARTPLAIN
#include <NTL/ZZ.h>
#include <NTL/vector.h>
using namespace std;
using namespace NTL;
ZZ sum(ZZ& s, const Vec<ZZ>& v)
{
ZZ acc;
acc = 0;
for (long i = 1; i <= v.length(); i++)
acc += v(i);
return acc;
}
ENDPLAIN -->
<!-- STARTPRETTY {{{ -->
<p><p><table cellPadding=10px><tr><td><font color="#000000"><font face="monospace">
<font color="#1773cc">#include </font><font color="#4a6f8b"><NTL/ZZ.h></font><br>
<font color="#1773cc">#include </font><font color="#4a6f8b"><NTL/vector.h></font><br>
<br>
<font color="#b02f60"><b>using</b></font> <font color="#008b00"><b>namespace</b></font> std;<br>
<font color="#b02f60"><b>using</b></font> <font color="#008b00"><b>namespace</b></font> NTL;<br>
<br>
ZZ sum(ZZ& s, <font color="#008b00"><b>const</b></font> Vec<ZZ>& v)<br>
{<br>
ZZ acc;<br>
<br>
acc = <font color="#ff8b00">0</font>;<br>
<br>
<font color="#b02f60"><b>for</b></font> (<font color="#008b00"><b>long</b></font> i = <font color="#ff8b00">1</font>; i <= v.length(); i++)<br>
acc += v(i); <br>
<br>
<font color="#b02f60"><b>return</b></font> acc;<br>
}<br>
</font></font></td></tr></table><p><p>
<!-- }}} ENDPRETTY -->
<p>
Note that by default, NTL does not perform range checks on
vector indices.
However, there is a compile-time flag that activates range checking.
Therefore, it is good practice to always assume that range checking
may be activated, and to not access elements that are out of range.
<p> <hr> <p>
The following example illustrates vector I/O,
as well as changing the length of a vector.
This program reads a <tt>Vec<ZZ></tt>,
and then creates and prints a "palindrome".
<!-- STARTPLAIN
#include <NTL/ZZ.h>
#include <NTL/vector.h>
using namespace std;
using namespace NTL;
int main()
{
Vec<ZZ> v;
cin >> v;
long n = v.length();
v.SetLength(2*n);
long i;
for (i = 0 ; i < n; i++)
v[n+i] = v[n-1-i];
cout << v << "\n";
}
ENDPLAIN -->
<!-- STARTPRETTY {{{ -->
<p><p><table cellPadding=10px><tr><td><font color="#000000"><font face="monospace">
<font color="#1773cc">#include </font><font color="#4a6f8b"><NTL/ZZ.h></font><br>
<font color="#1773cc">#include </font><font color="#4a6f8b"><NTL/vector.h></font><br>
<br>
<font color="#b02f60"><b>using</b></font> <font color="#008b00"><b>namespace</b></font> std;<br>
<font color="#b02f60"><b>using</b></font> <font color="#008b00"><b>namespace</b></font> NTL;<br>
<br>
<font color="#008b00"><b>int</b></font> main()<br>
{<br>
Vec<ZZ> v;<br>
cin >> v;<br>
<br>
<font color="#008b00"><b>long</b></font> n = v.length();<br>
v.SetLength(<font color="#ff8b00">2</font>*n);<br>
<br>
<font color="#008b00"><b>long</b></font> i;<br>
<font color="#b02f60"><b>for</b></font> (i = <font color="#ff8b00">0</font> ; i < n; i++)<br>
v[n+i] = v[n-<font color="#ff8b00">1</font>-i];<br>
<br>
cout << v << <font color="#4a6f8b">"</font><font color="#8a2ae2">\n</font><font color="#4a6f8b">"</font>;<br>
}<br>
</font></font></td></tr></table><p><p>
<!-- }}} ENDPRETTY -->
<p>
Notice that changing the length of a vector does not change
its contents.
<p>
When we compile and run this program,
if we type in
<pre>
[1 -2 3]
</pre>
as input, the output is
<pre>
[1 -2 3 3 -2 1]
</pre>
<p>
See <a href="vector.cpp.html"><tt>vector.txt</tt></a> for
complete details of NTL's generic vector mechanism.
Also note that for several fundamental vector types, such as
<tt>Vec<ZZ>.txt</tt>, there is a corresponding header file
<tt><NTL/vec_ZZ.h></tt> that defines
a number of basic arithmetic operations,
as well as provides the typedef
typedef <tt>vec_ZZ</tt> for backward compatibilty.
See <a href="vec_ZZ.cpp.html"><tt>vec_ZZ.txt</tt></a> for
complete details on the arithmetic operations for <tt>Vec<ZZ></tt>'s
provided by NTL.
<p> <hr> <p>
There is also basic support for matrices
in NTL.
In general, the class <tt>Mat<T></tt> is a special
kind of <tt>Vec< Vec< T > ></tt>, where each row is
a vector of the same length.
Row <tt>i</tt> of matrix <tt>M</tt>
can be accessed as <tt>M[i]</tt> (indexing from 0)
or as <tt>M(i)</tt> (indexing from 1).
Column <tt>j</tt> of row <tt>i</tt> can be accessed
as <tt>M[i][j]</tt> or <tt>M(i)(j)</tt>;
for notational convenience, the latter is equivalent to <tt>M(i,j)</tt>.
<p>
Here is a matrix multiplication routine,
which in fact is already provided by NTL.
<!-- STARTPLAIN
#include <NTL/ZZ.h>
#include <NTL/matrix.h>
using namespace std;
using namespace NTL;
void mul(Mat<ZZ>& X, const Mat<ZZ>& A, const Mat<ZZ>& B)
{
long n = A.NumRows();
long l = A.NumCols();
long m = B.NumCols();
if (l != B.NumRows())
Error("matrix mul: dimension mismatch");
X.SetDims(n, m); // make X have n rows and m columns
long i, j, k;
ZZ acc, tmp;
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
acc = 0;
for(k = 1; k <= l; k++) {
mul(tmp, A(i,k), B(k,j));
add(acc, acc, tmp);
}
X(i,j) = acc;
}
}
}
ENDPLAIN -->
<!-- STARTPRETTY {{{ -->
<p><p><table cellPadding=10px><tr><td><font color="#000000"><font face="monospace">
<font color="#1773cc">#include </font><font color="#4a6f8b"><NTL/ZZ.h></font><br>
<font color="#1773cc">#include </font><font color="#4a6f8b"><NTL/matrix.h></font><br>
<br>
<font color="#b02f60"><b>using</b></font> <font color="#008b00"><b>namespace</b></font> std;<br>
<font color="#b02f60"><b>using</b></font> <font color="#008b00"><b>namespace</b></font> NTL;<br>
<br>
<font color="#008b00"><b>void</b></font> mul(Mat<ZZ>& X, <font color="#008b00"><b>const</b></font> Mat<ZZ>& A, <font color="#008b00"><b>const</b></font> Mat<ZZ>& B)<br>
{<br>
<font color="#008b00"><b>long</b></font> n = A.NumRows();<br>
<font color="#008b00"><b>long</b></font> l = A.NumCols();<br>
<font color="#008b00"><b>long</b></font> m = B.NumCols();<br>
<br>
<font color="#b02f60"><b>if</b></font> (l != B.NumRows())<br>
Error(<font color="#4a6f8b">"matrix mul: dimension mismatch"</font>);<br>
<br>
X.SetDims(n, m); <font color="#0000ed"><i>// make X have n rows and m columns</i></font><br>
<br>
<font color="#008b00"><b>long</b></font> i, j, k;<br>
ZZ acc, tmp;<br>
<br>
<font color="#b02f60"><b>for</b></font> (i = <font color="#ff8b00">1</font>; i <= n; i++) {<br>
<font color="#b02f60"><b>for</b></font> (j = <font color="#ff8b00">1</font>; j <= m; j++) {<br>
acc = <font color="#ff8b00">0</font>;<br>
<font color="#b02f60"><b>for</b></font>(k = <font color="#ff8b00">1</font>; k <= l; k++) {<br>
mul(tmp, A(i,k), B(k,j));<br>
add(acc, acc, tmp);<br>
}<br>
X(i,j) = acc;<br>
}<br>
}<br>
}<br>
</font></font></td></tr></table><p><p>
<!-- }}} ENDPRETTY -->
<p>
In case of a dimension mismatch, the routine calls the
<tt>Error</tt> function, which is a part of NTL and which simply
prints the message and aborts.
That is generally how NTL deals with errors.
<p>
This routine will not work properly if <tt>X</tt> aliases
<tt>A</tt> or <tt>B</tt>.
The actual matrix multiplication routine in NTL takes care of this.
In fact, all of NTL's routines allow outputs to alias inputs.
<p>
To call NTL's built-in multiplication routine
(declared in <tt><NTL/mat_ZZ.h></tt>), one can write
<pre>
mul(X, A, B);
</pre>
or one can also use the operator notation
<pre>
X = A * B;
</pre>
<p>
NTL provides several matrix types.
See <a href="matrix.cpp.html"><tt>matrix.txt</tt></a>
for complete details on NTL's generic matrix mechanism.
Also see <a href="mat_ZZ.cpp.html"><tt>mat_ZZ.txt</tt></a> for
complete details on the arithmetic operations for <tt>Mat<ZZ></tt>'s
provideed by NTL (including basic linear algebra).
Also see <a href="LLL.cpp.html"><tt>LLL.txt</tt></a>
for details on routines for lattice basis reduction
(as well as routines for finding the kernel and image of a matrix).
<p>
One thing you may have noticed by now is that
NTL code generally avoids the type
<tt>int</tt>, preferring instead to use <tt>long</tt>.
This seems to go against what most "style" books preach,
but nevertheless seems to make the most sense in today's world.
Although <tt>int</tt> was originally meant to represent the
"natural" word size, this seems to no longer be the case.
On 32-bit machines, <tt>int</tt> and <tt>long</tt>
are the same,
but on 64-bit machines, they are often different, with
<tt>int</tt>'s having 32 bits and <tt>long</tt>'s having 64 bits.
Indeed, there is a standard, called "LP64", which is being adopted
by all Unix-like systems, and which specifies that on 64-bit machines,
<tt>int</tt>'s have 32 bits, and <tt>long</tt>'s and pointers have 64 bits.
Moreover, on such 64-bit machines,
the "natural" word size is usually 64-bits;
indeed, it is often more expensive to manipulate 32-bit integers.
Thus, for simplicity, efficiency, and safety, NTL uses <tt>long</tt>
for all integer values.
If you are used to writing <tt>int</tt> all the time,
it takes a little while to get used to this.
<p>
<center>
<a href="tour-ex1.html"><img src="arrow1.gif" alt="[Previous]" align=bottom></a>
<a href="tour-examples.html"><img src="arrow2.gif" alt="[Up]" align=bottom></a>
<a href="tour-ex3.html"> <img src="arrow3.gif" alt="[Next]" align=bottom></a>
</center>
</body>
</html>
