1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2%%
3%%  polynomial.tex       LiDIA documentation
4%%
5%%  This file contains the documentation of the template class polynomial
6%%
7%%  Copyright   (c)   1996   by  LiDIA-Group
8%%
9%%  Authors: Stefan Neis, adding some own code to rewritten code of
10%%  Victor Shoup, Thomas Papanikolaou, Nigel Smart, Damian Weber who each
11%%  contributed some part of the original code.
12%%
13
14%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
15
16\NAME
17
18\CLASS{polynomial< T >}  \dotfill parameterized polynomials
19
20
21%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
22
23\ABSTRACT
24
25\code{polynomial< T >} is a class for doing elementary polynomial computations.  A variable of
26type \code{polynomial< T >} can hold polynomials of arbitrary degree.
27
28
29%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
30
31\DESCRIPTION
32
33A variable $f$ of type \code{polynomial< T >} is internally represented as a coefficient array
34with entries of type \code{T}.  The zero polynomial is a zero length array; otherwise, $f[0]$ is
35the constant-term, and $f[\deg(f)]$ is the leading coefficient, which must always be non-zero.
36
37
38%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
39
40\CONS
41
42\begin{fcode}{ct}{polynomial< T >}{}
43  initializes a zero polynomial.
44\end{fcode}
45
46\begin{fcode}{ct}{polynomial< T >}{T $x$}
47  initializes with the constant polynomial $x$.
48\end{fcode}
49
50\begin{fcode}{ct}{polynomial< T >}{const T * $v$, lidia_size_t $d$}
51  initializes with the polynomial $\sum_{i=0}^d v_i x^i$.  The behaviour of this constructor is
52  undefined if the array $v$ has less than $d + 1$ elements.
53\end{fcode}
54
55\begin{fcode}{ct}{polynomial< T >}{const vector< T > $v$}
56  initializes with the polynomial $\sum_{i=0}^{n-1} v_i x^i$ where
57  $n = v$\code{.get_size()}.
58\end{fcode}
59
60\begin{fcode}{ct}{polynomial< T >}{const polynomial< T > & $f$}
61  initializes with a copy of the polynomial $f$.
62\end{fcode}
63
64\begin{fcode}{dt}{~polynomial< T >}{}
65\end{fcode}
66
67
68%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
69
70\ASGN
71
72Let $f$ be of type \code{polynomial< T >}.
73
74The operator \code{=} is overloaded.  For efficiency reasons, the following functions are also
75implemented:
76
77\begin{fcode}{void}{$f$.assign_zero}{}
78  sets $f$ to the zero polynomial.
79\end{fcode}
80
81\begin{fcode}{void}{$f$.assign_one}{}
82  sets $f$ to the polynomial $1 \cdot x^0$.
83\end{fcode}
84
85\begin{fcode}{void}{$f$.assign_x}{}
86  sets $f$ to the polynomial $1 \cdot x^1+0 \cdot x^0$.
87\end{fcode}
88
89\begin{fcode}{void}{$f$.assign}{const T & $a$}
90  $f \assign a \cdot x^0$.
91\end{fcode}
92
93\begin{fcode}{void}{$f$.assign}{const polynomial< T > & $g$}
94  $f \assign g$.
95\end{fcode}
96
97
98%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
99
100\BASIC
101
102Let $f$ be of type \code{polynomial< T >}.
103
104\begin{fcode}{void}{$f$.remove_leading_zeros}{}
105  removes leading zeros.  Afterwards, if $f$ is not the zero polynomial,
106  $\code{$f$.lead_coeff()} \neq 0$.  Note that leading zeros will break the code, therefore,
107  this function is usually called automatically.  However, if you manipulate the coefficients by
108  hand or if you used \code{set_degree()}, you may need to explicitly call this function.
109\end{fcode}
110
111\begin{fcode}{void}{swap}{polynomial< T > & $a$, polynomial< T > & $b$}
112  exchanges the values of $a$ and $b$.
113\end{fcode}
114
115
116%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
117
118\ACCS
119
120Let $f$ be of type \code{polynomial< T >}.
121
122\begin{cfcode}{lidia_size_t}{$f$.degree}{}
123  returns the degree of $f$.  For the zero polynomial we return $-1$.
124\end{cfcode}
125
126\begin{fcode}{void}{$f$.set_degree}{lidia_size_t $n$}
127  sets the degree of the polynomial to $n$.  If the polynomial is not modified (by one of the
128  following functions) in such a way that it really has this pretended degree before doing
129  computations with the polynomial, this leads to undefined behaviour.  The value of $f$ is
130  always unchanged.
131\end{fcode}
132
133\begin{fcode}{bigint &}{$f$.operator[]}{lidia_size_t $i$}
134  returns a reference to the coefficient of $x^i$ of $f$.  $i$ must be non-negative and less
135  than or equal to the degree of $f$.  This operator may be used to assign a value to a
136  coefficient.
137\end{fcode}
138
139\begin{fcode}{int}{$f$.set_data}{const T * $d$, lidia_size_t $l$}
140  sets $f$ to the polynomial $\sum_{i=0}^{l-1} v_i x^i$.  The behaviour of this function is
141  undefined if the array $v$ has less than $l$ elements. The return value of
142  this function is always zero.
143\end{fcode}
144
145\begin{cfcode}{T *}{$f$.get_data}{}
146  returns a pointer to a copy of the array of coefficients of $f$.  If $f$ is the zero
147  polynomial it returns a pointer to an array with one element which is zero.
148\end{cfcode}
149
150\begin{cfcode}{bigint}{$f$.lead_coeff}{}
151  returns $f[\deg(f)]$, i.e.~the leading coefficient of $f$; returns zero if $f$ is the zero
152  polynomial.
153\end{cfcode}
154
155\begin{cfcode}{bigint}{$f$.const_term}{}
156  returns $f[0]$, i.e.~the constant term of $f$; returns zero if $f$ is the zero polynomial.
157\end{cfcode}
158
159
160%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
161
162\ARTH
163
164The following operators are overloaded:
165
166\begin{center}
167  \begin{tabular}{|c|rcl|l|}\hline
168    unary & & $op$ & \code{polynomial< T >} & $op\in\{\code{-}\}$ \\\hline
169    binary & \code{polynomial< T >} & $op$ & \code{polynomial< T >}
170    & $op\in\{\code{+},\code{-},\code{*}\}$\\\hline
171    binary with & \code{polynomial< T >} & $op$ & \code{polynomial< T >}
172    & $op\in\{\code{+=},\code{-=},\code{*=}\}$\\
173    assignment & & & &\\\hline
174    binary & \code{polynomial< T >} & $op$ & \code{T}
175    & $op \in\{\code{+},\code{-},\code{*}\}$\\\hline
176    binary & \code{T} & $op$ & \code{polynomial< T >}
177    & $op \in\{\code{+},\code{-},\code{*}\}$\\\hline
178    binary with & \code{polynomial< T >} & $op$ & \code{T}
179    & $op \in\{\code{+=},\code{-=},\code{*=}\}$\\
180    assignment & & & &\\\hline
181  \end{tabular}
182\end{center}
183
184To avoid copying, these operations can also be performed by
185the following functions (Let $f$ be of type \code{polynomial< T >}).
186
187%\begin{fcode}{void}{$f$.negate}{}
188%       $f \assign -f$.
189%\end{fcode}
190
191\begin{fcode}{void}{negate}{polynomial< T > & $g$, const polynomial< T > & $h$}
192  $g \assign -h$.
193\end{fcode}
194
195\begin{fcode}{void}{add}{polynomial< T > & $f$, const polynomial< T > & $g$, const polynomial< T > & $h$}
196  $f \assign g + h$.
197\end{fcode}
198
199\begin{fcode}{void}{add}{polynomial< T > & $f$, const polynomial< T > & $g$, const T & $a$}
200  $f \assign g + a$.
201\end{fcode}
202
203\begin{fcode}{void}{add}{polynomial< T > & $f$, const T & $a$, const polynomial< T > & $g$}
204  $f \assign g + a$.
205\end{fcode}
206
207\begin{fcode}{void}{subtract}{polynomial< T > & $f$, const polynomial< T > & $g$, const polynomial< T > & $h$}
208  $f \assign g - h$.
209\end{fcode}
210
211\begin{fcode}{void}{subtract}{polynomial< T > & $f$, const polynomial< T > & $g$, const T & $a$}
212  $f \assign g - a$.
213\end{fcode}
214
215\begin{fcode}{void}{subtract}{polynomial< T > & $f$, const T & $a$, const polynomial< T > & $g$}
216  $f \assign a - g$.
217\end{fcode}
218
219\begin{fcode}{void}{multiply}{polynomial< T > & $f$, const polynomial< T > & $g$, const polynomial< T > & $h$}
220  $f \assign g \cdot h$.
221\end{fcode}
222
223\begin{fcode}{void}{multiply}{polynomial< T > & $f$, const polynomial< T > & $g$, const T & $a$}
224  $f \assign g \cdot a$.
225\end{fcode}
226
227\begin{fcode}{void}{multiply}{polynomial< T > & $f$, const T & $a$, const polynomial< T > & $g$}
228  $f \assign g \cdot a$.
229\end{fcode}
230
231\begin{fcode}{void}{power}{polynomial< T > & $f$, const polynomial< T > & $g$, const bigint & $e$}
232  $f \assign g^e$.
233\end{fcode}
234
235
236%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
237
238\COMP
239
240The binary operators \code{==}, \code{!=} are overloaded.
241
242Let $f$ be an instance of type \code{polynomial< T >}.
243
244\begin{cfcode}{bool}{$f$.is_zero}{}
245  returns \TRUE if $f$ is the zero polynomial; \FALSE otherwise.
246\end{cfcode}
247
248\begin{cfcode}{bool}{$f$.is_one}{}
249  returns \TRUE if $f$ is a constant polynomial and the constant coefficient equals $1$; \FALSE
250  otherwise.
251\end{cfcode}
252
253\begin{cfcode}{bool}{$f$.is_x}{}
254  returns \TRUE if $f$ is a polynomial of degree $1$, the leading coefficient equals $1$ and the
255  constant coefficient equals $0$; \FALSE otherwise.
256\end{cfcode}
257
258%\begin{cfcode}{bool}{$f$.is_monic}{}
259%       returns \TRUE if $f$ is a monic polynomial, i.e.~if $f$ is not
260%       the zero polynomial and $f.lead_coeff() = 1$.
261%\end{cfcode}
262%
263
264
265%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
266
267\HIGH
268
269Let $f$ be an instance of type \code{polynomial< T >}.
270
271\begin{fcode}{void}{derivative}{polynomial< T > & $f$, const polynomial< T > & $g$}
272  $f \assign g'$, i.e.~the (formal) derivative of $g$.
273\end{fcode}
274
275\begin{fcode}{base_polynomial< T >}{derivative}{const base_polynomial< T > & $g$}
276  returns $g'$, i.e.~the (formal) derivative of $g$.
277\end{fcode}
278
279\begin{cfcode}{bigint}{$f$.operator()}{const bigint & $a$}
280  returns $\sum_{i=0}^{\deg(f)} f_i \cdot a^i$, where $f = \sum_{i=0}^{\deg(f)} f_i \cdot x^i$.
281\end{cfcode}
282
283%
284% \begin{fcode}{void}{swap}{polynomial< T > & $f$, polynomial< T > & $g$}
285%    swaps the values of $f$ and $g$.
286%\end{fcode}
287
288
289%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
290
291\IO
292
293The \code{istream} operator \code{>>} and the \code{ostream} operator \code{<<}
294are overloaded.\\
295Let $f = \sum_{i=0}^{n} f_{i} \cdot x^{i}$ where $n$ denotes the degree of the polynomial $f$.
296
297We support two different I/O-formats:
298\begin{itemize}
299\item The more simple format is
300\begin{verbatim}
301 [ f_0 f_1 ... f_n ]
302\end{verbatim}
303
304  with elements $f_i$ of type \code{T}.  Leading zeros will be removed at input.
305
306\item The more comfortable format (especially for sparse polynomials) is
307
308\begin{verbatim} f_n * x^n + ... + f_2 * x^2 + f_1 * x + f_0 \end{verbatim}
309At output, zero coefficients are omitted, as well as you may omit them at input.  In fact the
310input is even much less restrictive: you may ommit the ``*'' and you also may permute the
311monomials, writing e.g.~$a_0 + a_n x^n + a_1*x +\dots$.
312\end{itemize}
313
314Both formats may be used as input --- they are distiguished automatically by the first character
315of the input, being `[' or not `['.  The \code{ostream} operator \code{<<} always uses the
316second format.
317% The second output format can be obtained using the member function
318% \begin{cfcode}{void}{$f$.pretty_print}{ostream & os}
319% \end{cfcode}
320
321
322%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
323
324\SEEALSO
325
326\SEE{polynomial< bigint >},
327\SEE{polynomial< bigrational >},
328\SEE{polynomial< bigfloat >},
329\SEE{polynomial< bigcomplex >},
330\SEE{Fp_polynomial}
331
332
333%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
334
335\NOTES
336
337Special thanks to Victor Shoup and Thomas Papanikolaou, who gave permission to rewrite and
338include their code.
339
340
341%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
342
343\BUGS
344
345Since this is a template class, I have to rely on other classes for reading input and producing
346output.  Therefore I don't see, how to prevent ``ugly'' output like
347\begin{verbatim} 3 * x^4 + -5 * x^2 + -7 .\end{verbatim}
348
349
350%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
351
352\EXAMPLES
353
354\begin{quote}
355\begin{verbatim}
356#include <LiDIA/polynomial.h>
357
358int main()
359{
360    polynomial< bigfloat > f, g, h;
361
362    cout << "Please enter f : "; cin >> f;
363    cout << "Please enter g : "; cin >> g;
364
365    h = f * g;
366
367    cout << "f * g   =  " << h << endl;;
368
369    return 0;
370}
371\end{verbatim}
372\end{quote}
373
374
375%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
376
377\AUTHOR
378
379Stefan Neis, Thomas Papanikolaou, Victor Shoup
380