\input texinfo @setfilename mpfrcx.info @documentencoding UTF-8 @include version.texi @settitle MPFRCX @value{VERSION} @synindex tp fn @set MINMPC 1.0 @set AUTHORS Andreas Enge @copying This manual is for MPFRCX, a library for the arithmetic of polynomials with multiple precision real or complex floating point coefficients, version @value{VERSION} of @value{UPDATED-MONTH}. Copyright @copyright{} 2007, 2008, 2009, 2010, 2011, 2012, 2017, 2018, 2020 Andreas Enge @quotation Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.3 or any later version published by the Free Software Foundation; with no Invariant Sections. A copy of the license is included in the section entitled ``GNU Free Documentation License.'' @end quotation @end copying @iftex @afourpaper @end iftex @tex \global\parindent=0pt \global\parskip=8pt \global\baselineskip=13pt @end tex @direntry * mpfrcx: (mpfrcx)Multiple Precision Real and Complex Polynomial Library. @end direntry @titlepage @title MPFRCX @subtitle Multiple Precision Real and Complex Polynomial Library @subtitle Edition @value{VERSION} @subtitle @value{UPDATED-MONTH} @author @value{AUTHORS} @page @vskip 0pt plus 1filll @insertcopying @end titlepage @ifnottex @node Top @top MPFRCX This manual documents how to install and use the Multiple Precision Real and Complex Polynomial Library, version @value{VERSION} as of @value{UPDATED-MONTH}. @end ifnottex @menu * Copying:: MPFRCX Copying Conditions. * Introduction to MPFRCX:: Brief introduction to MPFRCX. * Installing MPFRCX:: How to configure and compile the MPFRCX library. * Reporting Bugs:: How to usefully report bugs. * MPFRCX Basics:: What every MPFRCX user should now. * Functions:: Functions for arithmetic on real and complex polynomials. * Contributors:: * References:: * Concept Index:: * Function Index:: * GNU Free Documentation License:: @end menu @c @times{} made available as a "x" in info and html (already works in tex). @ifnottex @macro times x @end macro @end ifnottex @node Copying @unnumbered MPFRCX Copying Conditions @cindex Copying conditions @cindex Conditions for copying MPFRCX The MPFRCX Library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version, see the file COPYING.LESSER. The MPFRCX Library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. @node Introduction to MPFRCX @chapter Introduction to MPFRCX MPFRCX is a portable library written in C for arithmetic of polynomials with arbitrary precision real or complex floating point coefficients. It is based on the GNU MP, the MPFR and the MPC libraries. @node Installing MPFRCX @chapter Installing MPFRCX @cindex Installation To build MPFRCX, you first have to install GNU MP, MPFR and MPC on your computer. For MPC, the minimal supported version is @value{MINMPC}; the minimally required versions of GNU MP and MPFR depend on the MPC version used. You need a C compiler, preferably GCC, but any reasonable compiler should work. And you need a standard Unix @samp{make} program, plus some other standard Unix utility programs. Here are the steps needed to install the library on Unix systems: @enumerate @item @samp{tar xzf mpfrcx-@value{VERSION}.tar.gz} @item @samp{cd mpfrcx-@value{VERSION}} @item @samp{./configure} if GMP, MPFR and MPC are installed into standard directories, that is, directories that are searched by default by the compiler and the linking tools. @samp{./configure --with-gmp=} is used to indicate a different location where GMP is installed. @samp{./configure --with-mpfr=} is used to indicate a different location where MPFR is installed. @samp{./configure --with-mpc=} is used to indicate a different location where MPC is installed. @samp{./configure --with-gmp= --with-mpfr= --with-mpc=} is used to indicate different locations of GMP, MPFR and MPC. @emph{Warning!} Do not use these options if you have CPPFLAGS and/or LDFLAGS containing a -I or -L option with a directory that contains a GMP header or library file, as these options just add -I and -L options to CPPFLAGS and LDFLAGS @emph{after} the ones that are currently declared, so that DIR will have a lower precedence. Also, this may not work if DIR is a system directory. @item @samp{make} This compiles MPFRCX in the working directory. @item @samp{make check} This will make sure MPFRCX was built correctly. If you get error messages, please report them to @samp{andreas.enge@@inria.fr} (@xref{Reporting Bugs}, for information on what to include in useful bug reports). @item @samp{make install} This will copy the file @file{mpfrcx.h} to the directory @file{/usr/local/include}, the file @file{libmpfrcx.a} to the directory @file{/usr/local/lib}, and the file @file{mpfrcx.info} to the directory @file{/usr/local/share/info} (or if you passed the @samp{--prefix} option to @file{configure}, using the prefix directory given as argument to @samp{--prefix} instead of @file{/usr/local}). Note: you need write permissions on these directories. @end enumerate @section Other `make' Targets There are some other useful make targets: @itemize @bullet @item @samp{mpfrcx.pdf} or @samp{pdf} inside the @file{doc}subdirectory Create a PDF version of the manual, in @file{mpfrcx.pdf}. @item @samp{mpfrcx.html} or @samp{html} inside the @file{doc}subdirectory Create an HTML version of the manual, in several pages in the directory @file{mpfrcx.html}; if you want only one output HTML file, then type @samp{makeinfo --html --no-split mpfrcx.texi} instead. @item @samp{clean} Delete all object files and archive files, but not the configuration files. @item @samp{distclean} Delete all files not included in the distribution. @item @samp{uninstall} Delete all files copied by @samp{make install}. @end itemize @node Reporting Bugs @chapter Reporting Bugs @cindex Reporting bugs If you think you have found a bug in the MPFRCX library, please investigate and report it. There are a few things you should take into account when you compose your bug report. Please send us a minimal test case that makes it possible for us to reproduce the bug. Include instructions on how to run the test case, and why the result differs from what you would expect. Please include compiler version information in your bug report. This can be extracted using @samp{cc -V} on some machines, or, if you are using gcc, @samp{gcc -v}. Also, include the output from @samp{uname -a}. Send your bug report to: @samp{andreas.enge@@inria.fr}. Beware that the MPFRCX library is in a very early development stage, and some functions, while working correctly, may be terribly inefficient. You might want to send an e-mail to the above address if you are interested in one of the more exotic functions to enquire about its status. @node MPFRCX Basics @chapter MPFRCX Basics @cindex @file{libmpfrcx.a} @cindex @file{mpfrcx.h} MPFRCX provides types and functions for working with univariate polynomials, taking as coefficients either real or complex floating point numbers of arbitrary precision. The functions are collected in the library @file{libmpfrcx.a} and declared in the header file @file{mpfrcx.h}. @section Nomenclature and Types @cindex Real polynomial @tindex @code{mpfrx_t} @noindent A @dfn{real polynomial} is a polynomial whose coefficients are of type @code{mpfr_t}. The C data type for such objects is @code{mpfrx_t}. All coefficients are supposed to have the same floating point precision. Besides its list of coefficients, a variable of type @code{mpfrx_t} contains the degree of the polynomial as an @code{int} and the precision of its coefficients as an @code{mp_prec_t}. If the degree of a polynomial increases, its list of coefficients is lengthened accordingly; on the other hand, if the degree decreases, the memory allocated to the now superfluous coefficients is not freed, unless explicitly requested by a call to @code{mpfrx_realloc}, @pxref{Initialisation Functions}. @cindex Complex polynomial @tindex @code{mpcx_t} @noindent A @dfn{complex polynomial} is a polynomial whose coefficients are of type @code{mpc_t}. The C data type for such objects is @code{mpcx_t}. All coefficients are supposed to have the same floating point precision, and this both for their real and their imaginary parts. Otherwise, complex polynomials behave like real ones. When calling the functions described in the following, arguments of type @code{mpfrx_ptr} or @code{mpfrx_srcptr} stand for arbitrary variables of type @code{mpfrx_t}; the former may be modified by the function, the latter not. The same holds for @code{mpcx_ptr} and @code{mpcx_srcptr}. Notice that unlike for operations with real numbers of type @code{mpfr_t} and complex numbers of type @code{mpc_t}, there are no rounding modes for operations with polynomials and no precise semantics; polynomial arithmetic is realised by calls to functions on the coefficients, which may accumulate rounding errors. @section Function Classes Functions and macros working with real polynomials begin with @code{mpfrx_}, those treating complex polynomials begin with @code{mpcx_}. For the time being, there are no mixed operations. @section MPFRCX Variable Conventions As a general rule, all MPFRCX functions expect output arguments before input arguments, in analogy with GMP, MPFR and MPC. MPFRCX allows you to use the same variable for both input and output in the same expression. For example, the main function for multiplication of real polynomials, @code{mpfrx_mul}, can be used like this: @code{mpfrx_mul (f, f, f)} to replace @var{f} by its square. Before you can assign to an MPFRCX variable, you need to initialise it by calling one of the special initialisation functions. When you are done with a variable, you need to clear it out, using one of the functions for that purpose. A variable should be initialised only once; after a variable has been initialised, values may be assigned to it any number of times. @node Functions @chapter Functions @cindex Functions All publicly visible functions exist with the same behaviour for real or complex polynomials; their names start with @code{mpfrx_} resp. @code{mpcx_}. For the time being, the only specific functions concern the fast Fourier transform and are internal to the library. @menu * Initialisation Functions:: * Assignment Functions:: * Simultaneous Init & Assign:: * Access Functions:: * Comparison and Miscellaneous Functions:: * I/O Functions:: * Basic Polynomial Arithmetic:: * Higher Level Functions:: * Tree Based Functions:: * Functions for Galois Field Towers:: @end menu @node Initialisation Functions @section Initialisation Functions @cindex Initialisation Functions An @code{mpfrx_t} or @code{mpcx_t} object must be initialised before storing the first value in it, using the function @code{mpfrx_init} or @code{mpcx_init}. @deftypefun void mpfrx_init (mpfrx_ptr @var{f}, const int @var{size}, const mp_prec_t @var{prec}) @deftypefunx void mpcx_init (mpcx_ptr @var{f}, const int @var{size}, const mp_prec_t @var{prec}) Initialise @var{f} with initial space for @var{size} coefficients of precision @var{prec}, and set it to zero. It is possible to assign a polynomial with more than @var{size} coefficients to @var{f} later on; the size of @var{f} is then increased automatically. Beware that @var{size}@math{=d+1} coefficients are needed to store a polynomial of degree @math{d}. @end deftypefun @deftypefun void mpfrx_clear (mpfrx_ptr @var{z}) @deftypefunx void mpcx_clear (mpcx_ptr @var{z}) Free the space currently occupied by @var{z}. Make sure to call this function on each variable precisely once. @end deftypefun @deftypefun void mpfrx_realloc (mpfrx_ptr @var{f}, const int @var{size}) @deftypefunx void mpcx_realloc (mpcx_ptr @var{f}, const int @var{size}) Changes the number of coefficients stored in @var{f} to @var{size}, which may be more or less than (or equal to) the previous size, while preserving the precision of the coefficients. If @var{f} still fits (that is, its degree is at most @var{size}@math{-1}), its value is preserved, otherwise, it is replaced by 0. @end deftypefun @node Assignment Functions @section Assignment Functions @cindex Assignment Functions These functions assign new values to already initialised polynomials (@pxref{Initialisation Functions}). @deftypefun void mpfrx_set (mpfrx_ptr @var{h}, mpfrx_srcptr @var{f}) @deftypefunx void mpcx_set (mpcx_ptr @var{h}, mpcx_srcptr @var{f}) @deftypefunx void mpcx_set_frx (mpcx_ptr @var{h}, mpfrx_srcptr @var{f}) Set the value of @var{h} from @var{f}. The precision of @var{h} is preserved, and the coefficients of @var{f} are rounded if the target precision is lower. @end deftypefun @deftypefun void mpfrx_swap (mpfrx_ptr @var{f}, mpfrx_ptr @var{g}) @deftypefunx void mpcx_swap (mpcx_ptr @var{f}, mpcx_ptr @var{g}) Swap the contents of the variables @var{f} and @var{g}. If their coefficients do not have the same precision, precisions are swapped as well. The effect is thus not the same as obtained by several calls to @code{mpfrx_set} or @code{mpcx_set}, respectively, with an additional temporary variable, which would keep the respective precisions of @var{f} and @var{g} unchanged. @end deftypefun @node Simultaneous Init & Assign @section Combined Initialisation and Assignment Functions @cindex Combined Initialisation and Assignment Functions @deftypefun void mpfrx_init_set (mpfrx_ptr @var{h}, mpfrx_srcptr @var{f}) @deftypefunx void mpcx_init_set (mpcx_ptr @var{h}, mpcx_srcptr @var{f}) Initialise @var{h} with the same precision as @var{f} and set its value from @var{f}. @end deftypefun @node Access Functions @section Access Functions @cindex Access Functions @defmac {int mpfrx_get_prec} (mpfrx_srcptr @var{f}) @defmacx {int mpcx_get_prec} (mpcx_srcptr @var{f}) Return the common precision of the coefficients of @var{f}. @end defmac @deftypefun void mpfrx_set_prec (mpfrx_ptr @var{f}, const mp_prec_t @var{prec}) @deftypefunx void mpcx_set_prec (mpcx_ptr @var{f}, const mp_prc_t @var{prec}) Set the precision of the coefficients of @var{f} to @var{prec} and replace @var{f} by the zero polynomial. The effect is similar to a call to @code{mpfrx_clear} resp. @code{mpcx_clear} followed by a call to @code{mpfrx_init} resp. @code{mpcx_init}, but the number of coefficients in the polynomial is kept. @end deftypefun @defmac {int mpfrx_get_deg} (mpfrx_srcptr @var{f}) @defmacx {int mpcx_get_deg} (mpcx_srcptr @var{f}) Return the degree of @var{f}, which is -1 for the zero polynomial. @end defmac @deftypefun void mpfrx_set_deg (mpfrx_ptr @var{f}, const int @var{deg}) @deftypefunx void mpcx_set_deg (mpcx_ptr @var{f}, const int @var{deg}) Set the degree of @var{f} to @var{deg} while preserving the coefficients. If the degree increases, the new coefficients are set to NaN and need to be set manually before computing with the variable, see @code{mpfrx_set_coeff} and @code{mpcx_set_coeff}. If necessary, new coefficients are allocated. @end deftypefun @deftypefun mpfr_ptr mpfrx_get_coeff (mpfrx_srcptr @var{f}, const unsigned int @var{i}) @deftypefunx mpc_ptr mpcx_get_coeff (mpcx_srcptr @var{f}, const unsigned int @var{i}) Return a pointer to coefficient @var{i} of @var{f}, or NULL if the degree of @var{f} is less than @var{i}. @end deftypefun @deftypefun void mpfrx_set_coeff (mpfrx_ptr @var{f}, const unsigned int @var{i}, mpfr_srcptr @var{coeff}) @deftypefunx void mpcx_set_coeff (mpcx_ptr @var{f}, const unsigned int @var{i}, mpc_scrptr @var{coeff}) Set the coefficient @var{i} of @var{f} to @var{coeff}. If the current degree of @var{f} is smaller than @var{i}, then the degree of @var{f} is set to @var{i}; intermediate coefficients are set to NaN. @end deftypefun @node Comparison and Miscellaneous Functions @section Comparison and Miscellaneous Functions @cindex Comparison Functions @cindex Miscellaneous Functions @deftypefun int mpfrx_cmp (mpfrx_srcptr @var{f}, mpfrx_srcptr @var{g}) @deftypefunx int mpcx_cmp (mpcx_srcptr @var{f}, mpcx_srcptr @var{g}) Return 0 if @var{f} equals @var{g} and -1 if not. The coefficients of @var{f} and @var{g} are compared one by one; so even if the two polynomials have different precisions, they may be recognised as equal. @end deftypefun @deftypefun void mpfrx_urandom (mpfrx_ptr @var{f}, int @var{deg}, gmp_rand_state_t @var{state}) @deftypefunx void mpcx_urandom (mpcx_ptr @var{f}, int @var{deg}, gmp_rand_state_t @var{state}) If @var{deg}<0, set @var{f} to be the 0 polynomial. Otherwise, generate a uniformly distributed random degree between 0 and @var{deg} (inclusive), and a random polynomial of this degree. Each coefficient is chosen uniformly at random in the unit interval @math{[0, 1]} resp. the unit square @math{[0, 1] @times [0, 1]}; except for the leading coefficient, which cannot be 0. @var{state} is a @code{gmp_randstate_t} structure which should be created using the GMP @code{rand_init} function, see the GMP manual. @end deftypefun @defmac {const int MPFRCX_VERSION_MAJOR} @defmacx {const int MPFRCX_VERSION_MINOR} @defmacx {const int MPFRCX_VERSION_PATCHLEVEL} @defmacx {const char* MPFRCX_VERSION_STRING} @end defmac The major, minor and patchlevel version number of the library. These are concatenated and separated by '.' to form the version string; '-dev' is added to the version string of development snapshots. @deftypefun {const char *} mpfrcx_get_version (void) Return the MPFRCX version as a null-terminated string. @end deftypefun @node I/O Functions @section Input and Output Functions @cindex Input functions @cindex Output functions @cindex I/O functions The following function writes a polynomial to an output stream. When using it, you need to include @file{stdio.h} @emph{before} @file{mpfrcx.h}. @deftypefun size_t mpfrx_out_str (FILE* @var{stream}, int @var{base}, size_t @var{n_digits}, mpfrx_srcptr @var{f}) @deftypefunx size_t mpcx_out_str (FILE* @var{stream}, int @var{base}, size_t @var{n_digits}, mpcx_srcptr @var{f}) Output @var{f} to @var{stream} using the given @var{base} and the given number of digits @var{n_digits} for the coefficients. If @var{n_digits} is 0, then a suitable number of digits is chosen so that reading the polynomial into a variable of the same precision as @var{f} yields the same polynomial again (this input function needs yet to be written...). The output starts with an opening bracket @code{'('}, followed by the degree and a list of coefficients in decreasing order of degree (separated by spaces) and a closing bracket @code{')'}. Return the number of written characters. @end deftypefun @node Basic Polynomial Arithmetic @section Basic Polynomial Arithmetic @cindex Basic Polynomial Arithmetic @deftypefun void mpfrx_add (mpfrx_ptr @var{h}, mpfrx_srcptr @var{f}, mpfrx_srcptr @var{g}) @deftypefunx void mpcx_add (mpcx_ptr @var{h}, mpcx_srcptr @var{f}, mpcx_srcptr @var{g}) Set @var{h} to @var{f} @math{+} @var{g}. @end deftypefun @deftypefun void mpfrx_sub (mpfrx_ptr @var{h}, mpfrx_srcptr @var{f}, mpfrx_srcptr @var{g}) @deftypefunx void mpfrx_si_sub (mpfrx_ptr @var{h}, const long int @var{f}, mpfrx_srcptr @var{g}) @deftypefunx void mpcx_sub (mpcx_ptr @var{h}, mpcx_srcptr @var{f}, mpcx_srcptr @var{g}) @deftypefunx void mpcx_si_sub (mpcx_ptr @var{h}, const long int @var{f}, mpcx_srcptr @var{g}) Set @var{h} to @var{f} @math{-} @var{g}. @end deftypefun @deftypefun void mpfrx_neg (mpfrx_ptr @var{h}, mpfrx_srcptr @var{f}) @deftypefunx void mpcx_neg (mpcx_ptr @var{h}, mpcx_srcptr @var{f}) Set @var{h} to @minus{}@var{f}. @end deftypefun @deftypefun void mpfrx_mul (mpfrx_ptr @var{h}, mpfrx_srcptr @var{f}, mpfrx_srcptr @var{g}) @deftypefunx void mpfrx_mul_fr (mpfrx_ptr @var{h}, mpfrx_srcptr @var{f}, mpfr_srcptr @var{g}) @deftypefunx void mpfrx_mul_si (mpfrx_ptr @var{h}, mpfrx_srcptr @var{f}, const long int @var{g}) @deftypefunx void mpfrx_mul_ui (mpfrx_ptr @var{h}, mpfrx_srcptr @var{f}, const unsigned long int @var{g}) @deftypefunx void mpcx_mul (mpcx_ptr @var{h}, mpcx_srcptr @var{f}, mpcx_srcptr @var{g}) @deftypefunx void mpcx_mul_c (mpcx_ptr @var{h}, mpcx_srcptr @var{f}, mpc_srcptr @var{g}) @deftypefunx void mpcx_mul_fr (mpcx_ptr @var{h}, mpcx_srcptr @var{f}, mpfr_srcptr @var{g}) @deftypefunx void mpcx_mul_si (mpcx_ptr @var{h}, mpcx_srcptr @var{f}, const long int @var{g}) @deftypefunx void mpcx_mul_ui (mpcx_ptr @var{h}, mpcx_srcptr @var{f}, const unsigned long int @var{g}) Set @var{h} to @var{f} @math{*} @var{g}. @end deftypefun @deftypefun void mpfrx_mul_x (mpfrx_ptr @var{h}, mpfrx_srcptr @var{f}, const unsigned int @var{n}) @deftypefunx void mpcx_mul_x (mpcx_ptr @var{h}, mpcx_srcptr @var{f}, const unsigned int @var{n}) Set @var{h} to @var{f} @math{*} @var{x}@sup{@var{n}} @end deftypefun @deftypefun void mpfrx_rem (mpfrx_ptr @var{r}, mpfrx_srcptr @var{f}, mpfrx_srcptr @var{g}) @deftypefunx void mpcx_rem (mpcx_ptr @var{r}, mpcx_srcptr @var{f}, mpcx_srcptr @var{g}) Set @var{r} to the remainder of @var{f} divided by @var{g}. @end deftypefun @deftypefun void mpfrcx_real (mpfrx_ptr @var{h}, mpcx_srcptr @var{f}) @deftypefunx void mpfrcx_imag (mpfrx_ptr @var{h}, mpcx_srcptr @var{f}) Set @var{h} to the real or the imaginary part of @var{f}, respectively. The prefix @code{mpfrcx} indicates the mixed type of the operations, with an @code{mpcx} argument and an @code{mpfrx} result. @end deftypefun @node Higher Level Functions @section Higher Level Functions @cindex Higher Level Functions @deftypefun void mpfrx_eval (mpfr_ptr @var{r}, mpfrx_srcptr @var{f}, mpfr_srcptr @var{x}) @deftypefunx void mpcx_eval (mpc_ptr @var{r}, mpcx_srcptr @var{f}, mpc_srcptr @var{x}) Set @var{r} to the value f(x) of @var{f} at @var{x}, obtained using a Horner scheme. @end deftypefun @deftypefun void mpfrx_derive (mpfrx_ptr @var{h}, mpfrx_srcptr @var{f}) @deftypefunx void mpcx_derive (mpcx_ptr @var{h}, mpcx_srcptr @var{f}) Set @var{h} to the derivative of @var{f}. @end deftypefun @deftypefun void mpfrx_root (mpfr_ptr @var{root}, mpfrx_srcptr @var{f}) @deftypefunx void mpcx_root (mpc_ptr @var{root}, mpcx_srcptr @var{f}) Computes a root of @var{f}. The variable @var{root} is supposed to contain an initial approximation, that is refined via Newton iterations until it does not change any more. No special care is taken to avoid infinite loops. @end deftypefun @node Tree Based Functions @section Tree Based Functions @cindex Tree Based Functions The following functions implement asymptotically fast operations on arrays of polynomials, usually through the use of subproduct trees. @cindex Subproduct tree Such a tree is a binary tree constructed from an array of polynomials by storing these polynomials in the leaves of the tree. Each parent node contains the product of the child nodes, so that the root of the tree contains the product of all the leaves. Internally, subproduct trees are variables of types @code{mpfrx_tree_t} and @code{mpcx_tree_t}. (Analogously to the situation with polynomials, in the following, @code{mpfrx_tree_ptr} and @code{mpfcx_tree_ptr} are used for variables of type @code{mpfrx_tree_t} and @code{mpcx_tree_t} that may be modified by the function, and @code{mpfrx_tree_srcptr} and @code{mpfcx_tree_srcptr} for variables that are not modified.) @deftypefun void mpfrx_tree_init (mpfrx_tree_ptr @var{t}, int @var{no}, mpfr_prec_t @var{prec}) @deftypefunx void mpcx_tree_init (mpcx_tree_ptr @var{t}, int @var{no}, mpfr_prec_t @var{prec}) Initialises @var{t} as a subproduct tree with @var{no} leaves in which all polynomials stored in the nodes will have precision @var{prec}. All nodes are initialised by a call to @code{mpfrx_init} or @code{mpcx_init}, respectively. @end deftypefun @deftypefun void mpfrx_tree_clear (mpfrx_tree_ptr @var{t}) @deftypefunx void mpcx_tree_clear (mpcx_tree_ptr @var{t}) Frees the subproduct tree referenced by @var{t}, and all the polynomials stored in its nodes by calls to @code{mpfrx_clear} or @code{mpcx_clear}, respectively. @end deftypefun @deftypefun void mpfrx_subproducttree (mpfrx_tree_ptr @var{t}, mpfrx_t *@var{factors}) @deftypefunx void mpcx_subproducttree (mpcx_tree_ptr @var{t}, mpcx_t *@var{factors}) Computes the subproduct tree @var{t} whose leaves contains the polynomials in the array @var{factors}. The variable @var{t} needs to have been initialised by a call to @code{mpfrx_tree_init} or @code{mpcx_tree_init}, respectively, and @var{factors} needs to contain at least as many elements as there are leaves in @var{t}. (If there are more elements in @var{factors}, the last ones are ignored.) So a typical usage is a call to @code{mpfrx_tree_init}, followed by a call to @code{mpfrx_subproducttree}, and finally a call to @code{mpfrcx_tree_clear}. @var{factors} is not modified by the function. @end deftypefun @deftypefun void mpfrx_tree_get_root (mpfrx_ptr @var{f}, mpfrx_tree_srcptr @var{t}) @deftypefunx void mpcx_tree_get_root (mpcx_ptr @var{f}, mpcx_tree_srcptr @var{t}) Assigns the root of the tree @var{t} to @var{f}. For instance, if @var{t} has been obtained by a call to @code{mpfrx_subproducttree} or @code{mpcx_subproducttree}, this retrieves the product of all polynomials on the leaves. @end deftypefun @deftypefun void mpfrx_reconstruct (mpfrx_ptr @var{h}, mpfrx_t* @var{factors}, int @var{no}) @deftypefunx void mpcx_reconstruct (mpcx_ptr @var{h}, mpcx_t* @var{factors}, int @var{no}) Computes the product of the first @var{no} polynomials in the array @var{factors} and stores it in @var{h} (which may be one of the elements of @var{factors}; apart from that, @var{factors} is not modified). The same effect could be obtained by a call to @code{mpfrx_subproducttree} or @code{mpcx_subproducttree}, respectively, followed by @code{mpfrx_tree_get_root} or @code{mpcx_tree_get_root}, respectively. But to save space by a factor of O(log(@code{no})), this function uses a separate implementation. @end deftypefun @deftypefun void mpfrx_hecke (mpfrx_ptr @var{rop}, mpfrx_tree_srcptr @var{subproducts}, mpfrx_t *@var{vals}) @deftypefunx void mpcx_hecke (mpcx_ptr @var{rop}, mpcx_tree_srcptr @var{subproducts}, mpcx_t *@var{vals}) Assume that @var{t} has been created (by a call to @code{mpfrx_subproducttree} or @code{mpcx_subproducttree}, respectively) with the elements of the array @var{factors} on its leaves, and let @var{f} be the product of all the elements in @var{factors} (or, equivalently, the polynomial at the root of @var{subproducttree}). Then the function computes Σ @var{vals}[i]*@var{f}/@var{factors}[i] and returns the result in @var{rop}. It can be used to compute the Hecke representation of algebraic numbers, whence its name. @end deftypefun @deftypefun void mpfrx_product_and_hecke (mpfrx_t *@var{rop}, mpfrx_t **@var{vals}, int @var{no_pols}, int @var{no_factors}) @deftypefunx void mpcx_product_and_hecke (mpcx_t *@var{rop}, mpcx_t **@var{vals}, int @var{no_pols}, int @var{no_factors}) Combines one call to @code{mpfrx_subproducttree} (resp. @code{mpcx_subproducttree}) and one or more calls to @code{mpfrx_hecke} (resp. @code{mpcx_hecke}) into one function, which allows to not store the subproduct tree and thus to conserve memory without computational overhead. The function behaves as if a subproduct tree were created from @var{vals}[0], which needs to contain @var{no_factors} elements; the root of the tree is returned in @var{rop}[0]. For @var{i} from 1 to @var{no_pols-1}, it then behaves as if it called @code{mpfrx_hecke} (resp. @code{mpcx_hecke}) with this subproduct tree and @var{vals}[i], which needs to also contain @var{no_factors} values; the result of the operation is stored in @var{rop}[i]. @end deftypefun @deftypefun void mpfrx_multieval (mpfr_t* @var{values}, mpfr_t* @var{args}, int @var{no}, mpfrx_t @var{f}) @deftypefunx void mpcx_multieval (mpc_t* @var{values}, mpc_t* @var{args}, int @var{no}, mpcx_t @var{f}) Evaluates the polynomial @var{f} in the first @var{no} elements of the array @var{args}, and store the values in the first @var{no} entries of @var{values} (that must exist and already be initalised). @end deftypefun The following functions are convenience functions; they operate more or less like their counterparts without the suffix @code{_from_roots} (see the individual functions for small differences), but instead of a list of polynomials, they take as input a list of roots, which are interpreted as linear polynomials with this root. @deftypefun void mpfrx_reconstruct_from_roots (mpfrx_ptr @var{h}, mpfr_t* @var{roots}, int @var{no}) @deftypefunx void mpcx_reconstruct_from_roots (mpcx_ptr @var{h}, mpc_t* @var{roots}, int @var{no}) Compute the polynomial @var{h} of degree @var{no} that has the elements of @var{roots} as roots (potentially with multiplicity). @end deftypefun @deftypefun void mpfrx_subproducttree_from_roots (mpfrx_tree_ptr @var{t}, mpfr_t *@var{roots}, int @var{no}) @deftypefunx void mpcx_subproducttree_from_roots (mpcx_tree_ptr @var{t}, mpc_t *@var{roots}, int @var{no}) Unlike their counterparts without the @code{_from_roots} suffix, these functions also initialise the subproduct tree to the correct size @var{no}; so they should be called with an uninitialised argument @var{t}, which needs to be cleared explicitly later. This inconsistency is motivated by the corresponding behaviour of @code{mpfrcx_subproducttree_from_roots}, described below. @end deftypefun @deftypefun void mpfrx_hecke_from_roots (mpfrx_ptr @var{rop}, mpfrx_tree_srcptr @var{subproducts}, mpfr_t *@var{vals}) @deftypefunx void mpcx_hecke_from_roots (mpcx_ptr @var{rop}, mpcx_tree_srcptr @var{subproducts}, mpc_t *@var{vals}) The functions assume that @var{subproducts} has been generated (for instance by a call to @code{mpfrx_subproducttree_from_roots} or @code{mpcx_subproducttree_from_roots}) from monic linear polynomials; then @var{vals} corresponds to an array of constant polynomials, which are simply passed as complex numbers. @end deftypefun @deftypefun void mpfrx_product_and_hecke_from_roots (mpfrx_t *@var{rop}, mpfr_t **@var{vals}, int @var{no_pols}, int @var{no_factors}) @deftypefunx void mpcx_product_and_hecke_from_roots (mpcx_t *@var{rop}, mpc_t **@var{vals}, int @var{no_pols}, int @var{no_factors}) The functions work in the same way as @code{mpfrx_products_and_hecke} and @code{mpcx_products_and_hecke}, except that the elements in @code{vals[0]} are interpreted as linear polynomials with the elements as roots, and the other elements in @code{vals} as constant polynomials. Otherwise said, they work like a call to @code{mpcx_subproducttree_from_roots} or @code{mpfrx_subproducttree_from_roots} with @code{vals [0]}, followed by calls to @code{mpcx_hecke_from_roots} or @code{mpfrx_hecke_from_roots} with @code{vals [i]} for @var{i} from 1 to @var{no_pols}@math{-1}. @end deftypefun The following functions go one step further: They work with real polynomials given by their complex roots; this ``mixed'' nature of the operations is indicated by the prefix @code{mpfrcx} instead of @code{mpfrx} or @code{mpcx}. To use these functions, one needs to indicate whether a root is real or complex, and in the latter case, how the roots are paired. So together with an array @var{roots} of elements of type @code{mpc_t}, one needs to pass an array of integers @var{conjugates} of the same length, where @code{conjugates [i] == j} if and only if @code {roots [j]} is the complex conjugate of @code {roots [i]}. In particular, @code {conjugates [i] == i} if and only if @code {roots [i]} is in fact real. To save memory space, only the first element of each complex-conjugate pair needs to be set, that is, the one with @code {conjugates [i] >= i}. Internally, the functions work with linear or quadratic real polynomials obtained by regrouping the roots. For a numerical example, see the following function description. @deftypefun void mpfrcx_reconstruct_from_roots (mpfrx_ptr @var{h}, mpc_t* @var{roots}, int* @var{conjugates}, int @var{no}) Compute the polynomial @var{h} of degree @var{no} from its roots given in @var{roots} and paired, as seen above, through @var{conjugates}. For instance, the function may be called with @code{no == 3}, @code{roots == @{ (1.2599 0), (-0.6299 1.0911), NULL @} } and @code{conjugates == @{ 1, 3, 2 @} }; it then computes the result @math{X^3-2} (modulo some rounding errors) as the product of the linear real polynomial @math{X - 1.2599} and the quadratic real polynomial @math{X^2 + 1.2599 X + 1.5874}. @end deftypefun @deftypefun void mpfrcx_subproducttree_from_roots (mpfrx_ptr @var{h}, mpc_t* @var{roots}, int* @var{conjugates}, int @var{no}) The function initialises the subproducttree to the correct size, which depends not only on @var{no}, but on the exact number @math{n_1} of real roots and @math{n_2} of pairs of complex-conjugate roots. The tree has @math{n_1+n_2} leaves, with @math{n_1} linear and @math{n_2} quadratic polynomials. The function then computes the subproduct tree, with a polynomial of degree @var{no}@math{= n_1+2n_2} at its root. @end deftypefun @deftypefun void mpfrcx_hecke_from_roots (mpfrx_ptr @var{h}, mpfrx_tree_srcptr @var{subproducts}, mpc_t *@var{vals}, mpc_t *@var{roots}, int *@var{conjugates}) The function works like @code{mpcx_hecke_from_roots}, returning a real polynomial in @var{h}, assuming that @var{vals} is an array of real values and pairs of complex-conjugate values corresponding to the roots in @var{roots}, paired according to the same array @var{conjugates}. It is necessary to pass @var{roots} again for constructing the linear real interpolation polynomial for a pair of complex-conjugate values without factoring the corresponding quadratic polynomial on a leaf of @var{subproducts}. @end deftypefun @deftypefun void mpfrcx_product_and_hecke_from_roots (mpfrx_t *@var{rop}, mpc_t **@var{vals}, int *@var{conjugates}, int @var{no_pols}, int @var{no_factors}) The function works exactly like @code{mpcx_product_and_hecke_from_roots}, except that the result is known to be real since all elements of @var{vals} are paired up into complex-conjugate pairs according to @var{conjugates}. @end deftypefun @node Functions for Galois Field Towers @section Functions for Galois Field Towers @cindex Galois field @cindex Field tower The functions in this section decompose a solvable Galois number field extension into a tower of extensions, following @cite {Andreas Enge and François Morain: Fast Decomposition of Polynomials with Known Galois Group}. They have been written in the context of complex multiplication of elliptic curves, for either Hilbert or ray class fields of imaginary-quadratic number fields, or their real subfields, but could be applied in other contexts; abelian extensions of the rationals come to mind, but in principle also Galois extensions of higher degree number fields can be handled. The general setting is as follows: Let @math{L/Q}, where @math{Q} is the field of rational numbers, be a Galois number field with Galois group @math{G = (g_0, ..., g_{h-1})}. We assume that a fixed complex embedding of @math{L} has been chosen, and that @math{L} is given by the corresponding embedding of a generating element @math{x} and the action of the Galois group on this element; in other words, by an ordered list @math{(x_0, ..., x_{h-1})} of complex numbers such that @math{x_i = x^{g_i}}. Moreover, we assume the knowledge of a normal series for @math{G}, that is, @math{1 = H_{l-1} < H_{l-2} < ... < H_0 < H_{-1} = G} such that each subgroup @math{H_i} is normal in @math{H_{i-1}}. Let @math{L_i} be the fixed field of @math{H_i}, such that @math{L_{l-1} = L} and @math{L_{-1} = Q}. Then we obtain a Galois tower in which @math {L/L_i} has group @math{H_i}, the extension @math{L_i/Q} has group @math{G/H_i}, and the extension @math{L_i/L_{i-1}} has group @math{H_{i-1}/H_i}. For instance, in the abelian case, such a normal series exists such that each quotient @math{H_{i-1}/H_i} is cyclic of prime order. In the case of a ray class field @math{L} over an imaginary-quadratic number field @math{K}, the Galois group @math{G} is a semi-direct product of the (abelian) ray class group and the group of order 2 generated by the complex conjugation automorphism. One may then choose all the @math{H_i} down to @math{H_0} such that they do not contain complex conjugation, that is, as subgroups of the ray class group; then @math{L_0=K}, so that alongside the extension @math{L/Q}, we have also decomposed the Galois extension @math{L/K}. Galois field towers are stored in variables of type @code{mpcx_tower_t}; again, pointers to modifiable or unmodifiable towers exist, of types @code{mpcx_tower_ptr} and @code{mpcx_tower_srcptr}, respectively. The type is defined as a (one-dimensional array of a) C @code{struct} containing the following fields: @verbatim typedef struct { int levels; int* d; int deg; mpcx_t** W; } @end verbatim Here, @code{levels} is the length of the normal series (called @math{l} above). The array entry @code{d[i]} stores the relative degree of @math{L_i/L_{i-1}}. The variable @code{deg} stores the total degree of the extension @math{L/Q} (called @math{h} above), which is also the product of all the @code{d[i]}. Finally @code{W[i]} for @code{i} from @code{1} up to @code{levels-1} holds (after computation) the relative minimal polynomial of a generator of @math{L_i/L_{i-1}}, given by its Hecke representation. Otherwise said, if the absolute extension @math{L_{i-1}/Q} has the minimal polynomial @math{V_{i-1}} in the variable @math{X_{i-1}}, then @code{W[i]} stores the minimal polynomial of @math{X_i}, multiplied by the derivative @math{V_{i-1}'}. It is thus a (non-monic, with leading coefficient @math{V_{i-1}'}) polynomial of degree @code{d[i]} in the variable @math{X_i}, the coefficients of which are polynomials in the variable @math{X_{i-1}}, stored in @code{W[i][0]} up to @code{W[i][d[i]]}. To be consistent with this, the variable @code{W[0]} would have to hold @math{V_0} as an array of @code{d[0]} constant polynomials in the variable @math{X_0}; instead, we chose to use an array of length 1 for @code{W[0]} and to let its unique entry @code{W[0][0]} directly hold @math{V_0}. @deftypefun void mpcx_tower_init (mpcx_tower_ptr @var{twr}, int @var{l}, int* @var{d}, mpfr_prec_t @var{prec}) Initialises @var{twr} to hold a Galois tower, where @var{l} as above is the length of the Galois group decomposition, @var{d} the sequence of relative degress as explained above, and @var{prec} is the common precision used for all subsequent computations. @end deftypefun @deftypefun void mpcx_tower_clear (mpcx_tower_ptr @var{twr}) Clears @var{twr} and all its components. @end deftypefun @deftypefun void mpcx_tower_decomposition (mpcx_tower_ptr @var{twr}, mpc_t *@var{roots}) Given an initialised Galois tower @var{twr}, and a generating element of the extension @math{L/Q} together with its conjugates under the Galois group in an order compatible with the normal series as explained above in @var{roots}, computes absolute and relative extensions corresponding to the subfield tower and stores them in @var{twr}. The precisions of the elements in @var{roots} should match the precision with which @var{twr} has been initialised. The function chooses as generators ``small'' elementary-symmetric expressions under the action of the relative Galois groups; for instance, if possible the relative trace is preferred, then sums of products of two roots, and so on. The question whether an element generates a subfield is answered on a heuristic basis, since equality of elements cannot be rigorously determined in the presence of rounding errors; so there is a very small risk of the function not finding a generator of a subfield. Notice that the defining polynomials of all field extensions should have rational coefficients (or even integral rational coefficients if the generating element in @code{roots[0]} is an algebraic integer), but that the identification is not carried out by the function, and that all polynomials are stored with complex coefficients. So this function may in fact also be called when the base field @math{L_{-1}} is not the field of rational numbers, as long as a suitable function is called afterwards that obtains the symbolic expressions in @math{L_{-1}} of the coefficients of the generated polynomials from their image under the fixed complex embedding of @math{L}, which also induces a fixed embedding of @math{L_{-1}}. @end deftypefun The following variants of the data structures and functions treat a generalisation to an important non-Galois case, that of the real subfields of class fields of imaginary-quadratic number fields. These fields do not form Galois towers, but being the ``projection'' under complex conjugation, they behave very similarly to extensions of @math{Q} that have subgroups of the class group as Galois groups. The mathematical and algorithmic details are described in @cite {Andreas Enge and François Morain: Fast Decomposition of Polynomials with Known Galois Group}. Roughly speaking, all occurring polynomials are real, and their roots split into real roots and complex-conjugate pairs of complex roots. Since comparison of floating point numbers with rounding errors is a thorny problem, the user is expected to provide the functions with an indication of which roots are paired up; in the targeted application, this information can generally be derived symbolically from the class group. Such field towers are stored in variables of type @code{mpfrx_tower_t}, with pointers @code{mpfrx_ptr} to modifiable and @code{mpfrx_srcptr} to unmodifiable towers. The type is defined as a (one-dimensional array of a) C @code{struct} containing the following fields: @verbatim typedef struct { int levels; int* d; int deg; mpfrx_t** W; } @end verbatim The only difference to @code{mpcx_tower_t} is that the polynomials are real instead of complex. @deftypefun void mpfrx_tower_init (mpfrx_tower_ptr @var{twr}, int @var{l}, int* @var{d}, mpfr_prec_t @var{prec}) @deftypefunx void mpfrx_tower_clear (mpfrx_tower_ptr @var{twr}) These functions behave exactly like their complex counterparts. @end deftypefun @deftypefun void mpfrcx_tower_decomposition (mpfrx_tower_ptr @var{twr}, mpc_t *@var{roots}, int *@var{conjugates}) The function behaves exactly like its complex counterpart @code{mpcx_tower_decomposition}. Together with the list @var{roots} of complex roots of the class polynomial, in an order compatible with the tower field structure, it expects an array @var{conjugates} that designates the pairing of the roots: @code{conjugates [i] == j} if and only if @code {roots [j]} is the complex conjugate of @code {roots [i]}. In particular, @code {conjugates [i] == i} if and only if @code {roots [i]} is in fact real. To save memory space, only the first element of each complex-conjugate pair needs to be set, that is, the one with @code {conjugates [i] >= i}. The prefix @code{mpfrcx} of the function name indicates the ``mixed'' nature of the operation: While the results are real, the input values are still of complex type (reflecting that the number fields @math{L_i} all have at least one real embedding, but need not be totally real). @end deftypefun @node Contributors @unnumbered Contributors The main developer of the MPFRCX library is Andreas Enge. The functions for Galois field towers are co-authored by Jared Asuncion. @node References @unnumbered References @itemize @bullet @item Torbj@"orn Granlund et al. @code{gmp} -- GNU multiprecision library. Version 5.0.2, @url{http://gmplib.org/} @item Guillaume Hanrot, Vincent Lef@`evre, Patrick P@'elissier, Philippe Th@'eveny and Paul Zimmermann. @code{mpfr} -- A library for multiple-precision floating-point computations with exact rounding. Version 3.1.0, @url{http://www.mpfr.org/} @item Andreas Enge, Micka@"el Gastineau, Philippe Th@'eveny and Paul Zimmermann. @code{mpc} -- A library for multiprecision complex arithmetic with exact rounding. Version 0.9, @url{http://mpc.multiprecision.org/} @item Andreas Enge and François Morain. Fast Decomposition of Polynomials with Known Galois Group. In Marc Fossorier, Tom Høholdt and Alain Poli (eds.): Applied Algebra, Algebraic Algorithms and Error-Correcting Codes — AAECC-15, vol. 2643 of Lecture Notes in Computer Science, Springer-Verlag, Berlin 2003, pp. 254–264 Extended version: @url{https://www.math.u-bordeaux.fr/~aenge/papers/galois_long.ps.gz} @end itemize @node Concept Index @unnumbered Concept Index @printindex cp @node Function Index @unnumbered Function Index @printindex fn @node GNU Free Documentation License @appendix GNU Free Documentation License @include fdl-1.3.texi @ifnothtml @contents @end ifnothtml @bye