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