doc/cln_9.html

   1 <HTML>
   2 <HEAD>
   3 <!-- Created by texi2html 1.56k from cln.texi on 14 January 2000 -->
   4
   5 <TITLE>CLN, a Class Library for Numbers - 9. Univariate polynomials</TITLE>
   6 </HEAD>
   7 <BODY>
   8 Go to the <A HREF="cln_1.html">first</A>, <A HREF="cln_8.html">previous</A>, <A HREF="cln_10.html">next</A>, <A HREF="cln_13.html">last</A> section, <A HREF="cln_toc.html">table of contents</A>.
   9 <P><HR><P>
  10
  11
  12 <H1><A NAME="SEC54" HREF="cln_toc.html#TOC54">9. Univariate polynomials</A></H1>
  13
  14
  15
  16 <H2><A NAME="SEC55" HREF="cln_toc.html#TOC55">9.1 Univariate polynomial rings</A></H2>
  17
  18 <P>
  19 CLN implements univariate polynomials (polynomials in one variable) over an
  20 arbitrary ring. The indeterminate variable may be either unnamed (and will be
  21 printed according to <CODE>cl_default_print_flags.univpoly_varname</CODE>, which
  22 defaults to <SAMP>`x'</SAMP>) or carry a given name. The base ring and the
  23 indeterminate are explicitly part of every polynomial. CLN doesn't allow you to
  24 (accidentally) mix elements of different polynomial rings, e.g.
  25 <CODE>(a^2+1) * (b^3-1)</CODE> will result in a runtime error. (Ideally this should
  26 return a multivariate polynomial, but they are not yet implemented in CLN.)
  27
  28
  29 <P>
  30 The classes of univariate polynomial rings are
  31
  32
  33
  34 <PRE>
  35                            Ring
  36                          cl_ring
  37                         &#60;cl_ring.h&#62;
  38                             |
  39                             |
  40                  Univariate polynomial ring
  41                       cl_univpoly_ring
  42                       &#60;cl_univpoly.h&#62;
  43                             |
  44            +----------------+-------------------+
  45            |                |                   |
  46  Complex polynomial ring    |    Modular integer polynomial ring
  47  cl_univpoly_complex_ring   |        cl_univpoly_modint_ring
  48   &#60;cl_univpoly_complex.h&#62;   |        &#60;cl_univpoly_modint.h&#62;
  49                             |
  50            +----------------+
  51            |                |
  52    Real polynomial ring     |
  53    cl_univpoly_real_ring    |
  54     &#60;cl_univpoly_real.h&#62;    |
  55                             |
  56            +----------------+
  57            |                |
  58  Rational polynomial ring   |
  59  cl_univpoly_rational_ring  |
  60   &#60;cl_univpoly_rational.h&#62;  |
  61                             |
  62            +----------------+
  63            |
  64  Integer polynomial ring
  65  cl_univpoly_integer_ring
  66   &#60;cl_univpoly_integer.h&#62;
  67 </PRE>
  68
  69 <P>
  70 and the corresponding classes of univariate polynomials are
  71
  72
  73
  74 <PRE>
  75                    Univariate polynomial
  76                           cl_UP
  77                       &#60;cl_univpoly.h&#62;
  78                             |
  79            +----------------+-------------------+
  80            |                |                   |
  81    Complex polynomial       |      Modular integer polynomial
  82         cl_UP_N             |                cl_UP_MI
  83   &#60;cl_univpoly_complex.h&#62;   |        &#60;cl_univpoly_modint.h&#62;
  84                             |
  85            +----------------+
  86            |                |
  87      Real polynomial        |
  88         cl_UP_R             |
  89     &#60;cl_univpoly_real.h&#62;    |
  90                             |
  91            +----------------+
  92            |                |
  93    Rational polynomial      |
  94         cl_UP_RA            |
  95   &#60;cl_univpoly_rational.h&#62;  |
  96                             |
  97            +----------------+
  98            |
  99    Integer polynomial
 100         cl_UP_I
 101   &#60;cl_univpoly_integer.h&#62;
 102 </PRE>
 103
 104 <P>
 105 Univariate polynomial rings are constructed using the functions
 106
 107
 108 <DL COMPACT>
 109
 110 <DT><CODE>cl_univpoly_ring cl_find_univpoly_ring (const cl_ring&#38; R)</CODE>
 111 <DD>
 112 <DT><CODE>cl_univpoly_ring cl_find_univpoly_ring (const cl_ring&#38; R, const cl_symbol&#38; varname)</CODE>
 113 <DD>
 114 This function returns the polynomial ring <SAMP>`R[X]'</SAMP>, unnamed or named.
 115 <CODE>R</CODE> may be an arbitrary ring. This function takes care of finding out
 116 about special cases of <CODE>R</CODE>, such as the rings of complex numbers,
 117 real numbers, rational numbers, integers, or modular integer rings.
 118 There is a cache table of rings, indexed by <CODE>R</CODE> and <CODE>varname</CODE>.
 119 This ensures that two calls of this function with the same arguments will
 120 return the same polynomial ring.
 121
 122 <DT><CODE>cl_univpoly_complex_ring cl_find_univpoly_ring (const cl_complex_ring&#38; R)</CODE>
 123 <DD>
 124 <DT><CODE>cl_univpoly_complex_ring cl_find_univpoly_ring (const cl_complex_ring&#38; R, const cl_symbol&#38; varname)</CODE>
 125 <DD>
 126 <DT><CODE>cl_univpoly_real_ring cl_find_univpoly_ring (const cl_real_ring&#38; R)</CODE>
 127 <DD>
 128 <DT><CODE>cl_univpoly_real_ring cl_find_univpoly_ring (const cl_real_ring&#38; R, const cl_symbol&#38; varname)</CODE>
 129 <DD>
 130 <DT><CODE>cl_univpoly_rational_ring cl_find_univpoly_ring (const cl_rational_ring&#38; R)</CODE>
 131 <DD>
 132 <DT><CODE>cl_univpoly_rational_ring cl_find_univpoly_ring (const cl_rational_ring&#38; R, const cl_symbol&#38; varname)</CODE>
 133 <DD>
 134 <DT><CODE>cl_univpoly_integer_ring cl_find_univpoly_ring (const cl_integer_ring&#38; R)</CODE>
 135 <DD>
 136 <DT><CODE>cl_univpoly_integer_ring cl_find_univpoly_ring (const cl_integer_ring&#38; R, const cl_symbol&#38; varname)</CODE>
 137 <DD>
 138 <DT><CODE>cl_univpoly_modint_ring cl_find_univpoly_ring (const cl_modint_ring&#38; R)</CODE>
 139 <DD>
 140 <DT><CODE>cl_univpoly_modint_ring cl_find_univpoly_ring (const cl_modint_ring&#38; R, const cl_symbol&#38; varname)</CODE>
 141 <DD>
 142 These functions are equivalent to the general <CODE>cl_find_univpoly_ring</CODE>,
 143 only the return type is more specific, according to the base ring's type.
 144 </DL>
 145
 146
 147
 148 <H2><A NAME="SEC56" HREF="cln_toc.html#TOC56">9.2 Functions on univariate polynomials</A></H2>
 149
 150 <P>
 151 Given a univariate polynomial ring <CODE>R</CODE>, the following members can be used.
 152
 153
 154 <DL COMPACT>
 155
 156 <DT><CODE>cl_ring R-&#62;basering()</CODE>
 157 <DD>
 158 This returns the base ring, as passed to <SAMP>`cl_find_univpoly_ring'</SAMP>.
 159
 160 <DT><CODE>cl_UP R-&#62;zero()</CODE>
 161 <DD>
 162 This returns <CODE>0 in R</CODE>, a polynomial of degree -1.
 163
 164 <DT><CODE>cl_UP R-&#62;one()</CODE>
 165 <DD>
 166 This returns <CODE>1 in R</CODE>, a polynomial of degree &#60;= 0.
 167
 168 <DT><CODE>cl_UP R-&#62;canonhom (const cl_I&#38; x)</CODE>
 169 <DD>
 170 This returns <CODE>x in R</CODE>, a polynomial of degree &#60;= 0.
 171
 172 <DT><CODE>cl_UP R-&#62;monomial (const cl_ring_element&#38; x, uintL e)</CODE>
 173 <DD>
 174 This returns a sparse polynomial: <CODE>x * X^e</CODE>, where <CODE>X</CODE> is the
 175 indeterminate.
 176
 177 <DT><CODE>cl_UP R-&#62;create (sintL degree)</CODE>
 178 <DD>
 179 Creates a new polynomial with a given degree. The zero polynomial has degree
 180 <CODE>-1</CODE>. After creating the polynomial, you should put in the coefficients,
 181 using the <CODE>set_coeff</CODE> member function, and then call the <CODE>finalize</CODE>
 182 member function.
 183 </DL>
 184
 185 <P>
 186 The following are the only destructive operations on univariate polynomials.
 187
 188
 189 <DL COMPACT>
 190
 191 <DT><CODE>void set_coeff (cl_UP&#38; x, uintL index, const cl_ring_element&#38; y)</CODE>
 192 <DD>
 193 This changes the coefficient of <CODE>X^index</CODE> in <CODE>x</CODE> to be <CODE>y</CODE>.
 194 After changing a polynomial and before applying any "normal" operation on it,
 195 you should call its <CODE>finalize</CODE> member function.
 196
 197 <DT><CODE>void finalize (cl_UP&#38; x)</CODE>
 198 <DD>
 199 This function marks the endpoint of destructive modifications of a polynomial.
 200 It normalizes the internal representation so that subsequent computations have
 201 less overhead. Doing normal computations on unnormalized polynomials may
 202 produce wrong results or crash the program.
 203 </DL>
 204
 205 <P>
 206 The following operations are defined on univariate polynomials.
 207
 208
 209 <DL COMPACT>
 210
 211 <DT><CODE>cl_univpoly_ring x.ring ()</CODE>
 212 <DD>
 213 Returns the ring to which the univariate polynomial <CODE>x</CODE> belongs.
 214
 215 <DT><CODE>cl_UP operator+ (const cl_UP&#38;, const cl_UP&#38;)</CODE>
 216 <DD>
 217 Returns the sum of two univariate polynomials.
 218
 219 <DT><CODE>cl_UP operator- (const cl_UP&#38;, const cl_UP&#38;)</CODE>
 220 <DD>
 221 Returns the difference of two univariate polynomials.
 222
 223 <DT><CODE>cl_UP operator- (const cl_UP&#38;)</CODE>
 224 <DD>
 225 Returns the negative of a univariate polynomial.
 226
 227 <DT><CODE>cl_UP operator* (const cl_UP&#38;, const cl_UP&#38;)</CODE>
 228 <DD>
 229 Returns the product of two univariate polynomials. One of the arguments may
 230 also be a plain integer or an element of the base ring.
 231
 232 <DT><CODE>cl_UP square (const cl_UP&#38;)</CODE>
 233 <DD>
 234 Returns the square of a univariate polynomial.
 235
 236 <DT><CODE>cl_UP expt_pos (const cl_UP&#38; x, const cl_I&#38; y)</CODE>
 237 <DD>
 238 <CODE>y</CODE> must be &#62; 0. Returns <CODE>x^y</CODE>.
 239
 240 <DT><CODE>bool operator== (const cl_UP&#38;, const cl_UP&#38;)</CODE>
 241 <DD>
 242 <DT><CODE>bool operator!= (const cl_UP&#38;, const cl_UP&#38;)</CODE>
 243 <DD>
 244 Compares two univariate polynomials, belonging to the same univariate
 245 polynomial ring, for equality.
 246
 247 <DT><CODE>cl_boolean zerop (const cl_UP&#38; x)</CODE>
 248 <DD>
 249 Returns true if <CODE>x</CODE> is <CODE>0 in R</CODE>.
 250
 251 <DT><CODE>sintL degree (const cl_UP&#38; x)</CODE>
 252 <DD>
 253 Returns the degree of the polynomial. The zero polynomial has degree <CODE>-1</CODE>.
 254
 255 <DT><CODE>cl_ring_element coeff (const cl_UP&#38; x, uintL index)</CODE>
 256 <DD>
 257 Returns the coefficient of <CODE>X^index</CODE> in the polynomial <CODE>x</CODE>.
 258
 259 <DT><CODE>cl_ring_element x (const cl_ring_element&#38; y)</CODE>
 260 <DD>
 261 Evaluation: If <CODE>x</CODE> is a polynomial and <CODE>y</CODE> belongs to the base ring,
 262 then <SAMP>`x(y)'</SAMP> returns the value of the substitution of <CODE>y</CODE> into
 263 <CODE>x</CODE>.
 264
 265 <DT><CODE>cl_UP deriv (const cl_UP&#38; x)</CODE>
 266 <DD>
 267 Returns the derivative of the polynomial <CODE>x</CODE> with respect to the
 268 indeterminate <CODE>X</CODE>.
 269 </DL>
 270
 271 <P>
 272 The following output functions are defined (see also the chapter on
 273 input/output).
 274
 275
 276 <DL COMPACT>
 277
 278 <DT><CODE>void fprint (cl_ostream stream, const cl_UP&#38; x)</CODE>
 279 <DD>
 280 <DT><CODE>cl_ostream operator&#60;&#60; (cl_ostream stream, const cl_UP&#38; x)</CODE>
 281 <DD>
 282 Prints the univariate polynomial <CODE>x</CODE> on the <CODE>stream</CODE>. The output may
 283 depend on the global printer settings in the variable
 284 <CODE>cl_default_print_flags</CODE>.
 285 </DL>
 286
 287
 288
 289 <H2><A NAME="SEC57" HREF="cln_toc.html#TOC57">9.3 Special polynomials</A></H2>
 290
 291 <P>
 292 The following functions return special polynomials.
 293
 294
 295 <DL COMPACT>
 296
 297 <DT><CODE>cl_UP_I cl_tschebychev (sintL n)</CODE>
 298 <DD>
 299 Returns the n-th Tchebychev polynomial (n &#62;= 0).
 300
 301 <DT><CODE>cl_UP_I cl_hermite (sintL n)</CODE>
 302 <DD>
 303 Returns the n-th Hermite polynomial (n &#62;= 0).
 304
 305 <DT><CODE>cl_UP_RA cl_legendre (sintL n)</CODE>
 306 <DD>
 307 Returns the n-th Legendre polynomial (n &#62;= 0).
 308
 309 <DT><CODE>cl_UP_I cl_laguerre (sintL n)</CODE>
 310 <DD>
 311 Returns the n-th Laguerre polynomial (n &#62;= 0).
 312 </DL>
 313
 314 <P>
 315 Information how to derive the differential equation satisfied by each
 316 of these polynomials from their definition can be found in the
 317 <CODE>doc/polynomial/</CODE> directory.
 318
 319
 320 <P><HR><P>
 321 Go to the <A HREF="cln_1.html">first</A>, <A HREF="cln_8.html">previous</A>, <A HREF="cln_10.html">next</A>, <A HREF="cln_13.html">last</A> section, <A HREF="cln_toc.html">table of contents</A>.
 322 </BODY>
 323 </HTML>