path: root/Master/texmf-dist/source/latex/polynom/polynom.dtx

% \iffalse
%
% The files  polynom.dtx  and  polynom.ins  and all files generated
% from these two files are referred to as `this work'.
%
% This work is copyright 2000-2004 Carsten Heinz.
%
% This work may be distributed and/or modified under the conditions
% of the LaTeX Project Public License, either version 1.3 of this
% license or (at your option) any later version.
% The latest version of this license is in
%   http://www.latex-project.org/lppl.txt
% and version 1.3 or later is part of all distributions of LaTeX
% version 2003/12/01 or later.
%
% This work has the LPPL maintenance status "maintained".
%
% The Current Maintainer of this work is Carsten Heinz <cheinz@gmx.de>.
%
%<*driver>
\documentclass{ltxdoc}
\usepackage{hyperref,polynom}

\DisableCrossrefs
\OnlyDescription

\begin{document}
    \DocInput{polynom.dtx}
\end{document}
%</driver>
% \fi
%
%^^A
%^^A  Some definitions used for documentation.
%^^A
% \let\packagename\textsf
% \newenvironment{describe}{\trivlist\item[]}{\endtrivlist}
% \makeatletter
% \def\fps@figure{htbp}
% \let\c@table\c@figure
% \let\fps@table\fps@figure
% \makeatother
%^^A
%^^A  end of these definitions
%^^A
%
%\newbox\abstractbox
%\setbox\abstractbox=\vbox{
%	\begin{abstract}
%   The \packagename{polynom} package implements macros for manipulating
%   polynomials. For example, it can typeset polynomial long divisions and
%   synthetic divisions (Horner's scheme), which can be shown step by step.
%   The main test case and application is the polynomial ring in one variable
%   with rational coefficients.
%   \emph{Please note that this is work in progress. Multivariate polynomials
%   are \emph{currently} not supported.}
%	\end{abstract}}
%
% \title{The \packagename{Polynom} Package}
% \author{Copyright 2000--2004\\ Carsten Heinz \texttt{<\,cheinz@gmx.de\,>}}
% \date{2004/08/12\enspace Version 0.16\\ \box\abstractbox}
% \maketitle
%
%
% \section{Introduction}
%
% Donald Arseneau has contributed a lot of packages to the \TeX\ community.
% In particular, he posted macros for long division on \texttt{comp.text.tex},
% which were also published in the TUGboat \cite{TUGboat} and eventually as
% \texttt{longdiv.tex} on CTAN. The \packagename{polynom} package allows to do
% the job with polynomials, see figure~\ref{division}. There you can also
% see an example of Horner's scheme for synthetic division.
% \begin{figure}
% \centering
% \begin{minipage}{.42\linewidth}
%   \[\polylongdiv{(X-1)(X^2+2X+2)+1}{X-1}\]
% \end{minipage}
% \hfil
% \begin{minipage}{.5\linewidth}
%   \[\polyhornerscheme[x=1]{x^3+x^2-1}\]
% \end{minipage}
%
% \begin{minipage}{.42\linewidth}
% \centering |\polylongdiv{X^3+X^2-1}{X-1}|
% \end{minipage}
% \hfil
% \begin{minipage}{.5\linewidth}
% \centering |\polyhornerscheme[x=1]{x^3+x^2-1}|
% \end{minipage}
% \caption{Polynomial long division and synthetic division. The commands both
%  are able to generate partial output, see \href{polydemo.pdf}{polydemo.pdf}
%  in fullscreen mode.}
% \label{division}
% \end{figure}
%
% \begin{figure}
%   \[\polylonggcd {(X-1)(X-1)(X^2+1)} {(X-1)(X+1)(X+1)}\]
% \centering |\polylonggcd {(X-1)(X-1)(X^2+1)} {(X-1)(X+1)(X+1)}|
% \caption{Euclidean algorithm with polynomials; the last nonzero remainder
%          is a greatest common divisor. In the case here, it is uniquely
%          determined up to a scalar factor, so \(X-1\) and \(\frac49X-\frac49\)
%          are both greatest common divisors}\label{euclidean}
% \end{figure}
%
% \begin{figure}
% \centering
% \begin{tabular}{ll}
% |\polyfactorize {(X-1)(X-1)(X^2+1)}|&\polyfactorize{(X-1)(X-1)(X^2+1)}\\ \\
% |\polyfactorize {2X^3+X^2-7X+3}|\\
% \multicolumn{2}{l}{\hspace*{.3\linewidth}\polyfactorize{2X^3+X^2-7X+3}}\\ \\
% \multicolumn{2}{l}{\makeatletter\ttfamily
%    \def\temp{\polyfactorize{120X^5-274X^4+225X^3-85X^2+15X-1}}^^A
%    \csname strip@prefix\expandafter\endcsname\meaning\temp}\\
% \multicolumn{2}{l}{\hspace*{.3\linewidth}^^A
%                    \polyfactorize{120X^5-274X^4+225X^3-85X^2+15X-1}}\\
% \end{tabular}
% \caption{Factorizations of some polynomials}\label{factorize}
% \end{figure}
%
% Figures~\ref{euclidean} and \ref{factorize} show applications of polynomial
% division. On the one hand the Euclidean algorithm to determine a greatest
% common divisor of two polynomials, and on the other the factorization of
% a polynomial with at most two nonrational zeros. This should suffice for many
% teaching aids.
%
%
% \section{Hints}
%
% As the examples show, the commands get their data through mandatory and
% optional arguments. Polynomials are entered as you would type them in math
% mode:\footnote{The scanner is based on the scanner of the \texttt{calc}
% package \cite{calc}. Read its documentation and the implementation part here
% if you want to know more.} you may use |+|, |-|, |*|, |\cdot|, |/|, |\frac|,
% |(|, |)|, natural numbers, symbols like |e|, |\pi|, |\chi|, |\lambda|, and
% variables; the power operator |^| with integer exponents can be used on
% symbols, variables, and parenthesized expressions.
% Never use variables in a nominator, denominator or divisor.
%
% The support of symbols is very limited and there is neither support of
% functions like \(\sin(x)\) or \(\exp(x)\), nor of roots or exponents other
% than integers, for example \(\sqrt\pi\) or \(e^x\). For teaching purposes
% this shouldn't be a major drawback. Particularly because there is a simple
% workaround in some cases: the package doesn't look at symbols closely,
% so define a function like \(e^x\) or `composed symbol' like \(\sqrt\pi\)
% as a symbol. Take a look at figure~\ref{epowerx} for an example.
% \begin{figure}
% \newcommand\epowerx{e^x}
% \[\polylongdiv[style=C,div=/]{\epowerx x^3-\epowerx x^2+\epowerx x-\epowerx}{x-1}\]
% \begin{verbatim}
%    \newcommand\epowerx{e^x}
%    \[\polylongdiv{\epowerx x^3-\epowerx x^2+\epowerx x-\epowerx}{x-1}\]\end{verbatim}
% \caption{Avoiding problems with \(e^x\). Be particularly careful in such
% cases. \emph{You} have to take care of the correct result \emph{since} the
% package does the computation. And by the way, it's always good to keep an
% eye on plausibility of the results}
% \label{epowerx}
% \end{figure}
%
% \medbreak
%
% Optional arguments are used to specify more general options (and also for
% the evaluation point for Horner's scheme). The options are entered in
% key=value fashion using the \packagename{keyval} package \cite{keyval}.
% The available options are listed in the respective sections below.
%
%
% \section{Commands}
%
%
% \subsection[\texttt{\textbackslash polyset}]
% {\normalfont\texttt{\textbackslash polyset}\marg{key=value list}}
%
% Keys and values in optional arguments affect only that particular operation.
% |\polyset| changes the settings for the rest of the current environment or
% group. This could be a single figure or the whole document. Almost every key
% described in this manual is allowed\,---\,just try it and you'll see.
% Table~\ref{keys} lists all keys, which are not connected to a particular
% command. An example is
% \begin{verbatim}
%    \polyset{vars=XYZ\xi,  % make X, Y, Z, and \xi into variables
%             delims={[}{]}}% nongrowing brackets\end{verbatim}
% Note that is essential to use \texttt{vars}-declared variables only.
% The package can't guess your intention and
% |\polylongdiv{\zeta^3+\zeta^2-1}{\zeta-1}|
% would divide a constant by a constant without the information $\zeta$ being
% a variable.
%
% \begin{table}
% \centering
% \begin{tabular}{p{.4\textwidth}p{.5\textwidth}}
% \texttt{vars=}\meta{token string}
%       & make each token a variable\\
%       &\\
% \texttt{delims=}\marg{left}\marg{right}
%       & define delimiters used for printing\\
%       & parenthesized expressions\\
% \end{tabular}
% \caption{General keys. Default for \texttt{vars} is \texttt{Xx}. The key
%          \texttt{delims} has in fact an optional argument which takes
%          invisible versions of the left and right delimiter. The default is
%          \texttt{delims=[\{\textbackslash left.\}\{\textbackslash right.\}]\{\textbackslash left(\}\{\textbackslash right)\}}
%          }\label{keys}
% \end{table}
%
%
% \subsection[\texttt{\textbackslash polylongdiv}]
% {\normalfont\texttt{\textbackslash polylongdiv}\oarg{key=value list}\meta{polynomial \(a\)}\meta{polynomial \(b\)}}
%
% The command prints the polynomial long division of $a/b$. Applicable keys
% are listed in table~\ref{keys:longdiv}. Of course, \texttt{vars} and
% \texttt{delims} can be used, too.
%
% \begin{table}
% \centering
% \begin{tabular}{p{.4\textwidth}p{.5\textwidth}}
% \texttt{stage=}\meta{number}
%       & print long division up to stage \meta{number} (starting with 1)\\
%       &\\
% \texttt{style=}\texttt{A$\vert$B$\vert$C}
%       & define output scheme for long division, refer \href{polydemo.pdf}{polydemo.pdf}\\
%       &\\
% \texttt{div=}\meta{token}
%       & define division sign for \texttt{style=C}, default is $\div$\\
% \end{tabular}
% \caption{Keys and values for polynomial long division. \texttt{style=A}
%          requires \texttt{stage=}\({}3\times(\#\)quotient's summands\()+1\)
%          to be carried out fully. The other styles \texttt{B} and \texttt{C}
%          need one more stage if the remainder is nonzero}
% \label{keys:longdiv}
% \end{table}
%
%
% \subsection[\texttt{\textbackslash polyhornerscheme}]
% {\normalfont\texttt{\textbackslash polyhornerscheme}\oarg{key=value list}\meta{polynomial}}
%
% The command prints Horner's scheme for the given polynomial with respect to
% the specified evaluation point. Note that the latter one is entered as a
% key=value pair in the form \meta{variable}\texttt{=}\meta{value}.
% Table~\ref{keys:horner} lists other keys and their respective values.
%
% \begin{table}
% \centering
% \begin{tabular}{p{.4\textwidth}p{.5\textwidth}}
% \meta{variable}\texttt{=}\meta{value}
%       & The definition of the evaluation point is \emph{mandatory}!\\
%       &\\
% \texttt{stage=}\meta{number}
%       & print Horner's scheme up to stage \meta{number} (starting with 1)\\
%       &\\
% \texttt{tutor=}\texttt{true$\vert$false}
%       &turn on and off tutorial comments\\
% \texttt{tutorlimit=}\meta{number}
%       & illustrate the recent \meta{number} steps\\
% \texttt{tutorstyle=}\meta{font selection}
%       & define appearance of tutorial comments\\
%       &\\
% \texttt{resultstyle=}\meta{font selection}
%       & define appearance of the result\\
% \texttt{resultleftrule=}\texttt{true$\vert$false}\newline
% \texttt{resultrightrule=}\texttt{true$\vert$false}\newline
% \texttt{resultbottomrule=}\texttt{true$\vert$false}
%       & control rules left to, right to, and at the bottom of the result\\
%       &\\
% \texttt{showbase=}\texttt{false$\vert$}\newline\phantom{\texttt{showbase=}}\texttt{top$\vert$middle$\vert$bottom}
%       & define whether and in which row the base (the value) is printed\\
% \texttt{showvar=}\texttt{true$\vert$false}
%       & print or suppress the variable name (additionally to the base)\\
% \texttt{showbasesep=}\texttt{true$\vert$false}
%       & print or suppress the vertical rule\\
%       &\\
% \texttt{equalcolwidth=}\texttt{true$\vert$false}
%       & use the same width for all columns or use their individual widths\\
% \texttt{arraycolsep=}\meta{dimension}
%       & space between columns\\
% \texttt{arrayrowsep=}\meta{dimension}
%       & space between rows\\
%       &\\
% \texttt{showmiddlerow=}\texttt{true$\vert$false}
%       & print or suppress the middle row\\
% \end{tabular}
% \caption{Keys and values for Horner's scheme. Don't use \texttt{showmiddlerow=false}
%          with \texttt{tutor=true}.}
% \label{keys:horner}
% \end{table}
%
% \iffalse
% The following key are not listed above:
%
%           mul=<math tokens>                           \cdot
%           plusface=left|right                         right
%           plusyoffset=<dimension>                     0pt
%
%           downarrow=<picture tokens>                  {\vector(0,-1){2.5}}
%           diagarrow=<picture tokens>                  {\vector(2,1){1.6}}
%           downarrowxoffset=<dimension>                0pt
%           diagarrowxoffset=<dimension>                0pt
% \fi
%
%
% \subsection[\texttt{\textbackslash polylonggcd}]
% {\normalfont\texttt{\textbackslash polylonggcd}\oarg{key=value list}\meta{polynomial \(a\)}\meta{polynomial \(b\)}}
%
% The command prints equations of the Euclidean algorithm used to determine
% the greatest common divisor of the polynomials \(a\) and \(b\), refer
% figure~\ref{euclidean}.
%
%
% \subsection[\texttt{\textbackslash polyfactorize}]
% {\normalfont\texttt{\textbackslash polyfactorize}\oarg{key=value list}\meta{polynomial}}
%
% The command prints a factorization of the polynomial as long as all except
% two roots are rational, see figure \ref{factorize}.
%
%
% \subsection{Low-level commands}
%
% To tell the whole truth, the commands above don't need the polynomials typed
% in verbatim. The internal representation of polynomials can be stored as
% replacement texts of control sequences and such control sequences can take
% the role of verbatim polynomials. This is also the case for \meta{\(a\)} and
% \meta{\(b\)} in table~\ref{low}, but each \meta{cs$_{\ldots}$} must be a
% control sequence, in which the result is saved.
% 
% The command in table~\ref{low} can be used for low level calculations, and in
% particular to store polynomials for later use with the high-level commands.
% For example one could write the following.
% \begin{verbatim}
%    \polyadd\polya {(X^2+X+1)(X-1)-\frac\pi2}{0}% trick
%    \polymul\polyb {X-1}{1}             % another trick
%    Let's see how to divide \polyprint\polya{} by \polyprint\polyb.
%      \[\polylongdiv\polya\polyb\]\end{verbatim}
%
% \begin{table}
% \centering
% \begin{tabular}{r@{\enspace}ll}
% \meta{cs$_{a+b}$}&$\gets a+b$
%       & \cs{polyadd}\meta{cs$_{a+b}$}\meta{\(a\)}\meta{\(b\)}\\
%       &&\\
% \meta{cs$_{a-b}$}&$\gets a-b$
%       & \cs{polysub}\meta{cs$_{a-b}$}\meta{\(a\)}\meta{\(b\)}\\
%       &&\\
% \meta{cs$_{ab}$}&$\gets a\cdot b$
%       & \cs{polymul}\meta{cs$_{ab}$}\meta{\(a\)}\meta{\(b\)}\\
%       &&\\
% \meta{cs$_{a/b}$}&$\gets \lfloor a/b\rfloor$
%       & \cs{polydiv}\meta{cs$_{a/b}$}\meta{\(a\)}\meta{\(b\)}\\
% \cs{polyremainder}&$\gets a\bmod b$
%       &\\
%       &&\\
% \meta{cs$_{\gcd}$}&$\gets \gcd(a,b)$
%       & \cs{polygcd}\meta{cs$_{\gcd}$}\meta{\(a\)}\meta{\(b\)}\\
%       &&\\
% \multicolumn{2}{r}{print polynomial $a$}
%       & \cs{polyprint}\meta{\(a\)}\\
% \end{tabular}
% \caption{Low-level user commands}\label{low}
% \end{table}
%
%
% \section{Acknowledgments}
%
% I wish to thank
%   Ludger Humbert,
%   Karl Heinz Marbaise, and
%   Elke Niedermair
% for their tests and error reports.
%
%
% \StopEventually{^^A
% \begin{thebibliography}{1}
% \bibitem{TUGboat}
%   \textsc{Barbara Beeton} and \textsc{Donald Arseneau}.
%
%   \textit{Long division}.
%
%   In Jeremy Gibbons' \textit{Hey --- it works!},
%   TUGboat 18(2), June 1997, p.~75.
%
% \bibitem{calc}
%   \textsc{Kresten Krab Thorup}, \textsc{Frank Jensen}, and \textsc{Chris Rowley}.
%
%   \textit{The \texttt{calc} package, Infix notation arithmetic in \LaTeX}, 1998/07/07.
%
%   Available from \texttt{CTAN:} \texttt{macros/latex/required/tools}.
%
% \bibitem{keyval}
%   \textsc{David Carlisle}.
%
%   \textit{The \textsf{keyval} package}, 1999/03/16.
%
%   Available from \texttt{CTAN:} \texttt{macros/latex/required/graphics}.
%\end{thebibliography}}
%
%
% \CheckSum{4559}
%
%
% \section{Preliminaries}
%
% Let's start with identification.
%    \begin{macrocode}
%<*package>
\NeedsTeXFormat{LaTeX2e}
\ProvidesPackage{polynom}[2004/08/12 0.16 (Carsten Heinz)]
%    \end{macrocode}
% Now follow two frequently used definitions.
%
% \begin{macro}{\pld@AddTo}
% \begin{macro}{\pld@Extend}
% \meta{macro}\marg{contents}
% \begin{describe}
% adds \meta{contents} to the macro respectively does an |\expandafter| on the
% first token of \meta{contents} before doing so.
% \end{describe}
%    \begin{macrocode}
\def\pld@AddTo#1#2{\expandafter\def\expandafter#1\expandafter{#1#2}}
\def\pld@Extend#1#2{%
    \expandafter\pld@AddTo\expandafter#1\expandafter{#2}}
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\pld@ExpandTwo}
% expands the respectively first tokens of |#2| and |#3| and puts all as
% argument after |#1|. Note that |#2| and |#3| need not to be single tokens.
%    \begin{macrocode}
\def\pld@ExpandTwo#1#2#3{%
    \expandafter\def\expandafter\pld@temp\expandafter{#2}%
    \pld@Extend\pld@temp{#3}%
    \expandafter#1\pld@temp}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@if}
% is used as a temporary and local switch.
%    \begin{macrocode}
\def\pld@true{\let\pld@if\iftrue}
\def\pld@false{\let\pld@if\iffalse}
\pld@false
%    \end{macrocode}
% \end{macro}
%
%
% \section{The user interface}
%
% \begin{macro}{\polyset}
% This command just `inserts' the family name |pld| and requires the
% \packagename{keyval} package.
%    \begin{macrocode}
\RequirePackage{keyval}[1997/11/10]
\newcommand\polyset[1]{\ifx\@empty#1\@empty\else \setkeys{pld}{#1}\fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@IfVar}
% The variables are stored in a comma separated list. Here we look after
% |#1| being an element and execute the second argument \meta{then} or the
% third argument \meta{else}.
%    \begin{macrocode}
\def\pld@IfVar#1{%
    \def\pld@temp##1,#1,##2##3\relax{%
        \ifx\@empty##3\@empty \expandafter\@secondoftwo
                        \else \expandafter\@firstoftwo \fi}%
    \expandafter\pld@temp\pld@variables,#1,\@empty\relax}
%    \end{macrocode}
% The key iterates down the tokens and expand the list.
%    \begin{macrocode}
\define@key{pld}{vars}
    {\let\pld@variables\@empty
     \@tfor\pld@temp:=#1\do
         {\pld@Extend\pld@variables{\expandafter,\pld@temp}}}
%    \end{macrocode}
%    \begin{macrocode}
\polyset{vars=Xx}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@iftopresult}
% determines the printing style for long divisions. The key checks for the
% macro definition |\pld@style|\meta{name}, \ldots
%    \begin{macrocode}
\define@key{pld}{style}
    {\@ifundefined{pld@style#1}%
         {\PackageError{polynom}{Unknown style `#1'}%
          {Arguments can be `A' or `B' or `C'.}}%
         {\let\pld@style=#1%
          \@nameuse{pld@style#1}}}
%    \end{macrocode}
% which are defined here.
%    \begin{macrocode}
\def\pld@styleA{\let\pld@iftopresult\iftrue}
\def\pld@styleB{\let\pld@iftopresult\iffalse}
\let\pld@styleC\pld@styleB
%    \end{macrocode}
%    \begin{macrocode}
\polyset{style=A}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@leftdelim}
% \begin{macro}{\pld@rightdelim}
% \begin{macro}{\pld@leftxdelim}
% \begin{macro}{\pld@rightxdelim}
% We make left and right delimiters definable.
%    \begin{macrocode}
\define@key{pld}{delims}
    {\@ifnextchar[\pld@delims
                  {\pld@delims[{}{}]}#1{}{}}
\def\pld@delims[#1#2]#3#4{%
    \def\pld@leftxdelim{#1}\def\pld@rightxdelim{#2}%
    \def\pld@leftdelim{#3}\def\pld@rightdelim{#4}}
\polyset{delims=[{\left.}{\right.}]{\left(}{\right)}}
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\pld@div}
% Moreover one can customize the division sign for the C style.
%    \begin{macrocode}
\define@key{pld}{div}{\def\pld@div{#1}}
\polyset{div=\div}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@stage}
% \begin{macro}{\pld@currstage}
% Ensure a positive value.
%    \begin{macrocode}
\define@key{pld}{stage}{%
    \@tempcnta#1\relax \ifnum\@tempcnta<\@ne \@tempcnta\@ne \fi
    \edef\pld@stage{\the\@tempcnta}}
%    \end{macrocode}
%    \begin{macrocode}
\newcount\pld@currstage
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% The following definitions all have the same scheme: get the polynomial(s),
% do the operation, and assign or print the result. And they all use macros
% which are defined in later sections.
%
% \begin{macro}{\polymul}
% Just the things stated.
%    \begin{macrocode}
\newcommand*\polymul[1]{%
    \pld@GetPoly{\pld@polya\pld@polyb}%
                {\pld@MultiplyPoly#1\pld@polya\pld@polyb
                 \ignorespaces}}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\polydiv}
% Ditto.
%    \begin{macrocode}
\newcommand*\polydiv[1]{%
    \begingroup
    \let\pld@stage\maxdimen
    \pld@GetPoly{\pld@polya\pld@polyb}%
                {\pld@DividePoly\pld@polya\pld@polyb
                 \let#1\pld@quotient
                 \let\polyremainder\pld@remainder
                 \pld@RestoreAftergroup#1\polyremainder\relax
    \endgroup\ignorespaces}}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\polylongdiv}
% Ditto.
%    \begin{macrocode}
\newcommand*\polylongdiv[1][]{%
    \begingroup
    \let\pld@stage\maxdimen \polyset{#1}%
    \pld@GetPoly{\pld@polya\pld@polyb}%
                {\pld@LongDividePoly\pld@polya\pld@polyb
                 \pld@PrintLongDiv
    \endgroup \ignorespaces}}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\polylonggcd}
% Ditto.
%    \begin{macrocode}
\newcommand*\polylonggcd[1][]{%
    \begingroup
    \let\pld@stage\maxdimen \polyset{#1}%
    \pld@GetPoly{\pld@polya\pld@polyb}%
                {\pld@LongEuclideanPoly\pld@polya\pld@polyb
                 \pld@PrintLongEuclidean
    \endgroup \ignorespaces}}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\polygcd}
% Ditto.
%    \begin{macrocode}
\newcommand*\polygcd[1]{%
    \begingroup
    \let\pld@stage\maxdimen
    \pld@GetPoly{\pld@polya\pld@polyb}%
                {\pld@LongEuclideanPoly\pld@polya\pld@polyb
                 \global\let\@gtempa\pld@vb
    \endgroup \let#1\@gtempa \ignorespaces}}
%    \end{macrocode}
% A bug report by Elke Niedermair ^^A {e.a.n@gmx.de}{2002/10/29}{undefined control sequence \pld@stage}
% led to the initialization of |\pld@stage| -- and the surrounding
%|\begingroup| and |\endgroup|.
% \end{macro}
%
% \begin{macro}{\polyfactorize}
% Ditto.
%    \begin{macrocode}
\newcommand*\polyfactorize{%
    \pld@GetPoly\pld@current
                {\pld@Factorize\pld@current \ensuremath{\pld@allines}}}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\polyprint}
% Ditto.
%    \begin{macrocode}
\newcommand*\polyprint{%
    \pld@GetPoly{\pld@polya}%
                {\ensuremath{\pld@PrintPoly\pld@polya}}}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\polyadd}
% Get the polynomials, add them via appending the representation, and
% normalize the result via simplification.
%    \begin{macrocode}
\newcommand*\polyadd[1]{%
    \pld@GetPoly{\pld@polya\pld@polyb}%
                {\let#1\pld@polya \pld@ExtendPoly#1\pld@polyb
                 \pld@Simplify#1%
                 \ignorespaces}}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\polysub}
% Ditto.
%    \begin{macrocode}
\newcommand*\polysub[1]{%
    \pld@GetPoly{\pld@polya\pld@polyb}%
                {\def\pld@tempoly{\pld@R{-1}1}%
                 \pld@MultiplyPoly\pld@polyb\pld@polyb\pld@tempoly
                 \let#1\pld@polya \pld@ExtendPoly#1\pld@polyb
                 \pld@Simplify#1%
                 \ignorespaces}}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@RestoreAftergroup}
% We just iterate down the control sequences, add |\def#1{|\meta{contents of
% \texttt{\#1}}|}| to |\@gtempa|, and execute it \cs{aftergroup}.
%    \begin{macrocode}
\def\pld@RestoreAftergroup{%
    \global\let\@gtempa\@empty
    \pld@RestoreAfter@}
\def\pld@RestoreAfter@#1{%
    \ifx\relax#1%
        \aftergroup\@gtempa
    \else
        \global\pld@Extend\@gtempa{\expandafter\def\expandafter#1%
                                   \expandafter{#1}}%
        \expandafter\pld@RestoreAfter@
    \fi}
%    \end{macrocode}
% \end{macro}
%
%
% \section{Internal data format}\label{sInternalDataFormat}
%
% A polynomial is a finite sum $\meta{$\mathrm{monomial}_1$}+\ldots+
% \meta{$\mathrm{monomial}_n$}$ of monomials. In the internal data format, the
% monomials will be sorted by degree---in the multivariate case not by the
% total degree but by the degree of the first variable, then by the degree of
% the second variable, and so on.
%
% Each monomial is a product of \emph{rationals}, general \emph{fractions},
% \emph{symbolic factors}, and \emph{variables}. The factors are represented
% in the following format.
% \begin{enumerate}
% \item |\pld@R|\marg{integer nominator}\marg{integer denominator} for rationals,
% \item |\pld@F|\marg{nominator}\marg{denominator} for general fractions,
% \item |\pld@S|\marg{symbol}\marg{exponent} for symbolic factors, and
% \item |\pld@V|\marg{symbol}\marg{exponent} for variables.
% \end{enumerate}
% As a special case \meta{nominator} and/or \meta{denominator} may be empty,
% which stands for a factor $1={}$|\pld@R{1}{1}|.
%
% \begin{table}[tp]
% \begin{tabular}{cl}
% \emph{mathematians write}&\multicolumn{1}{c}{\emph{internal representation}}\\[1ex]
% $X^2-1$      & |\pld@V{X}{2}+\pld@R{-1}{1}|\\[1ex]
% $\frac1e X$  & |\pld@F{\pld@R{1}{1}}{\pld@S{e}{1}}\pld@V{X}{1}|\\
%              & |\pld@S{e}{-1}\pld@V{X}{1}|\\[1ex]
% $\frac1{10}$ & |\pld@F{\pld@R{1}{1}}{\pld@R{10}{1}}|\\
%              & |\pld@R{1}{10}|
% \end{tabular}
% \caption{Mathematical notation versus internal representation}\label{mvi}
% \end{table}
% Table \ref{mvi} shows examples of the internal data format. As you can see,
% sometimes there are various ways to represent the same polynomial. The 
% exact internal data depends on how you enter the factors and which state has
% been reached in the division algorithm, for example.
%
% And now some definitions which work on representations of polynomials, first
% macros to `look at' polynomials and then macros to build them.
%
% \begin{macro}{\pld@SplitMonom}
% \meta{|\#1\#2| submacro}\marg{monomial representation}
% \begin{describe}
% calls the given macro with the `nonvariable' part as first and the `variable'
% part as second argument. Each of them can be empty. Note that this definition
% makes an assumption on the order of the factors in the representation, namely
% that the variable part comes at the end.
% \end{describe}
%    \begin{macrocode}
\def\pld@SplitMonom#1#2{%
    \pld@SplitMonom@#2\pld@V\relax {\pld@SplitMonom@V#1#2\relax}%
                                   {#1{#2}{}}}
\def\pld@SplitMonom@#1\pld@V#2\relax{%
    \ifx\@empty#2\@empty \expandafter\@secondoftwo
                   \else \expandafter\@firstoftwo \fi}
\def\pld@SplitMonom@V#1#2\pld@V#3\relax{#1{#2}{\pld@V#3}}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@SplitMonomS}
% \meta{|\#1\#2| submacro}\marg{`monomial representation'}
% \begin{describe}
% does the same but splits at |\pld@S| to separate numerals and symbols.
% \end{describe}
%    \begin{macrocode}
\def\pld@SplitMonomS#1#2{%
    \pld@SplitMonomS@#2\pld@S\relax {\pld@SplitMonomS@S#1#2\relax}%
                                   {#1{#2}{}}}
\def\pld@SplitMonomS@#1\pld@S#2\relax{%
    \ifx\@empty#2\@empty \expandafter\@secondoftwo
                   \else \expandafter\@firstoftwo \fi}
\def\pld@SplitMonomS@S#1#2\pld@S#3\relax{#1{#2}{\pld@S#3}}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@IfSum}
% \marg{polynomial representation}\marg{then}\marg{else}
% \begin{describe}
% executes \meta{then} if and only if the polynomial is a sum (of more than
% one monomial).
% \end{describe}
%    \begin{macrocode}
\def\pld@IfSum#1{\pld@IfSum@#1+\@empty+\relax+}
\def\pld@IfSum@#1+#2+\relax+{%
    \ifx\@empty#2\@empty \expandafter\@secondoftwo
                   \else \expandafter\@firstoftwo \fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@DefNegative}
% \meta{macro}\marg{monomial representation}
% \begin{describe}
% negates the monomial and puts it into the macro.
% \end{describe}
%    \begin{macrocode}
\def\pld@DefNegative#1#2{\pld@DefNegative@#1#2\@empty}
\def\pld@DefNegative@#1#2#3#4#5\@empty{%
    \ifx #2\pld@R\def#1{\pld@R{-#3}{#4}#5}%
           \else \def#1{\pld@R{-1}1#2{#3}{#4}#5}\fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@DefInverse}
% \meta{inverse macro}\marg{monomial representation}
% \begin{describe}
% puts a representation of the monomials' reciprocal into the macro.
% \end{describe}
%    \begin{macrocode}
\def\pld@DefInverse#1#2{%
    \let#1\@empty
    \pld@DefInverse@#1#2\relax\@empty\@empty}
%    \end{macrocode}
% Here we just interchange nominator and denominator or negate the exponent.
%    \begin{macrocode}
\def\pld@DefInverse@#1#2#3#4{%
    \ifx\relax#2\relax \expandafter\@gobbletwo \else
        \ifx #2\pld@R \pld@AddTo#1{\pld@R{#4}{#3}}\else
        \ifx #2\pld@F \pld@AddTo#1{\pld@F{#4}{#3}}\else
        \ifx #2\pld@S \pld@AddTo#1{\pld@S{#3}{-#4}}\else
        \ifx #2\pld@V \pld@AddTo#1{\pld@V{#3}{-#4}}\else
            \pld@DIError
        \fi \fi \fi \fi
    \fi
    \pld@DefInverse@#1}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@AddToPoly}
% \begin{macro}{\pld@ExtendPoly}
% \meta{polynomial}\marg{monomial}
% \begin{describe}
% adds \meta{monomial} as a new summand to \meta{polynomial} or does an
% |\expandafter| on the first token before doing so.
% \end{describe}
%    \begin{macrocode}
\def\pld@AddToPoly#1#2{%
    \ifx #1\@empty \def#1{#2}\else
                   \pld@AddTo#1{+#2}\fi}
\def\pld@ExtendPoly#1#2{%
    \ifx #1\@empty \pld@Extend#1{#2}\else
    \ifx #2\@empty
             \else \pld@Extend#1{\expandafter+#2}\fi \fi}
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\pld@R}
% \begin{macro}{\pld@F}
% \begin{macro}{\pld@S}
% \begin{macro}{\pld@V}
% These macros just contain distinct single characters. We will change the
% definitions locally when we output a polynomial, for example.
%    \begin{macrocode}
\def\pld@R{r}
\def\pld@F{f}
\def\pld@S{s}
\def\pld@V{v}
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
%
%
% \section{Scanning input}
%
% \begin{macro}{\pld@GetPoly}
% |{|\meta{macro$_1$}\ldots\meta{macro$_k$}|}| \marg{do after} \marg{polynomial$_1$}\ldots\marg{polynomial$_k$}
% \begin{describe}
% This definition parses all user supplied polynomials. For $i=1,\ldots,k$,
% it assigns the internal representation of \meta{polynomial$_i$} to
% \meta{macro$_i$} and executes \meta{do after}wards. `\marg{polynomial$_i$}'
% may be a stored polynomial---that means a control sequence---in which case
% the argument braces \emph{must} be omitted.
% \end{describe}
% First we initialize data and check whether the user provides an explicit
% polynomial.
%    \begin{macrocode}
\def\pld@GetPoly#1#2{%
    \def\pld@pool{#1}\def\pld@aftermacro{#2}%
    \pld@GetPoly@}
\def\pld@GetPoly@{%
    \@ifnextchar\bgroup \pld@GetPolyArg\pld@GetPolyLet}
%    \end{macrocode}
% Such a polynomial is scanned and then assigned to a macro from the pool.
%    \begin{macrocode}
\def\pld@GetPolyArg#1{%
    \pld@Scan{#1}%
    \pld@GetPolyLet\pld@tempoly}
%    \end{macrocode}
% Here we get one macro from the pool, assign the polynomial, and continue if
% the pool isn't empty.
%    \begin{macrocode}
\def\pld@GetPolyLet{\expandafter\pld@GetPolyLet@\pld@pool\relax}
\def\pld@GetPolyLet@#1#2\relax#3{%
    \let#1#3\def\pld@pool{#2}%
    \pld@Simplify#1%
    \ifx\pld@pool\@empty \expandafter\pld@aftermacro
                   \else \expandafter\pld@GetPoly@ \fi}
%    \end{macrocode}
% \end{macro}
%
% Now we actually scan the input. Section \emph{4 The evaluation scheme} of
% the \texttt{calc} package \cite{calc} explains how this is done in general.
% Together with the implementation part of the that package, it's an excellent
% introduction---if you are familiar with \TeX. However, some things are
% different:
% \begin{itemize}
% \item We additionally detect |\frac|, |\cdot|, symbols, and variables.
% \item To write $XY$ instead of $X\cdot Y$ or $X*Y$, we provide an implicit
%       multiplication.
% \item |\pld@ScanIt| does what |\calc@pre@scan| and |\calc@post@scan| do.
% \item In terms of the \texttt{calc} package, we clear the local `register B'
%       |\pld@tempoly| after each |\begingroup| (for providing a faster
%       multiplication, see below) and we assign the value of that register
%       to the global `register A' |\@gtempa| before each |\endgroup|.
% \item Multiplication with a single factor (symbol, variable, fraction,
%       number) makes group level changes only if the current term is a sum.
%       Otherwise it just adds the factor to |\pld@tempoly|. This saves many
%       multiplications of polynomials.
% \end{itemize}
% We begin with basic definitions.
%
% \begin{macro}{\pld@ScanBegingroup}
% \begin{macro}{\pld@ScanEndgruop}
% Just what was stated above.
%    \begin{macrocode}
\def\pld@ScanBegingroup{\begingroup \let\pld@tempoly\@empty}
\def\pld@ScanEndgroup{\pld@ScanSetA \endgroup}
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\pld@ScanSetA}
% \begin{macro}{\pld@ScanSetB}
% In the \texttt{calc} package the second routine is called |\scan@initB| (but
% with registers instead of macros, of course)
%    \begin{macrocode}
\def\pld@ScanSetA{\global\let\@gtempa\pld@tempoly}
\def\pld@ScanSetB{\let\pld@tempoly\@gtempa}
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\pld@Scan}
% corresponds to |\calc@assign@generic|.
%    \begin{macrocode}
\def\pld@Scan#1{%
    \let\pld@tempoly\@empty
      \pld@ScanOpen(#1\relax
    \pld@ScanEndgroup \pld@ScanEndgroup}
%    \end{macrocode}
% The brake |\relax| terminates the main scanning loop.
%    \begin{macrocode}
\def\pld@ScanIt#1{%
    \ifx \relax#1\let\pld@next\@gobble \else
%    \end{macrocode}
% The tokens |+|, |-|, |*|, |\cdot|, |/|, and |)| let us make the according
% translations.
%    \begin{macrocode}
    \ifx +#1\let\pld@next\pld@ScanAdd\else
    \ifx -#1\let\pld@next\pld@ScanSubtract\else
    \ifx *#1\let\pld@next\pld@ScanMultiply\else
    \ifx \cdot#1\let\pld@next\pld@ScanMultiply\else
    \ifx /#1\let\pld@next\pld@ScanDivide\else
    \ifx )#1\let\pld@next\pld@ScanClose\else
    \ifx ^#1\let\pld@next\pld@ScanPower\else
%    \end{macrocode}
% Other tokens are `preceeded' by an implicit multiplication, as you will see
% below.
%    \begin{macrocode}
        \ifx \frac#1\let\pld@next\pld@ScanFrac\else
        \ifx (#1\let\pld@next\pld@ScanOpen\else
%    \end{macrocode}
% Now we check for a digit and a variable, respectively. If none of them is
% given, we treat the argument as a symbol.
%    \begin{macrocode}
            \pld@IfNumber{#1}%
                {\let\pld@next\pld@ScanNumeric}%
                {\pld@IfVar{#1}{\let\pld@next\pld@ScanVar}%
                               {\let\pld@next\pld@ScanSymbol}}%
        \fi \fi
    \fi \fi \fi \fi \fi \fi \fi \fi
    \pld@next #1}
%    \end{macrocode}
% For speedy scanning we could alternatively define
% \begin{verbatim}
%    \def\pld@ScanIt#1{%
%        \expandafter\let\expandafter\pld@next\csname
%                                 pld@Scan@\string#1\endcsname
%        \ifx\relax\pld@next
%            \pld@IfVar{#1}{\let\pld@next\pld@ScanVar}%
%                          {\let\pld@next\pld@ScanSymbol}%
%        \fi
%        \pld@next #1}\end{verbatim}
% and make appropriate definitions |\pld@Scan@\relax| (one single control
% sequence), |\pld@Scan@|$\langle$\texttt{+$\vert$-$\vert$*$\vert$\bslash
% cdot$\vert$/$\vert$)$\vert$\textasciicircum$\vert$\bslash frac$\vert$($\vert
% $0$\vert\ldots\vert$9}$\rangle$ instead of |\pld@ScanAdd| and all the other
% definitions below.
% \end{macro}
%
% \begin{macro}{\pld@IfNumber}
% execute the first or second argument depending on whether |#1| is found in
% |0123456789|.
%    \begin{macrocode}
\def\pld@IfNumber#1{%
    \def\pld@temp##1#1##2##3\relax{%
        \ifx\@empty##2\@empty \expandafter\@secondoftwo
                        \else \expandafter\@firstoftwo \fi}%
    \pld@temp 0123456789#1\@empty\relax}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@ScanOpen}
% \begin{macro}{\pld@ScanClose}
% correspond to |\calc@open| and |\calc@close|. A left parentheses implicitly
% inserts a multiplication in many (or even most) cases since the parenthesized
% expression must be viewed as a potential sum.
% The simple |\pld@ScanImplicitMultiply| in version 0.11 didn't insert a
% multiplication when scanning |2(X+1)|, for example.
%    \begin{macrocode}
\def\pld@ScanOpen({%
    \ifx\@empty\pld@tempoly\else
        \pld@ScanMultiplyBase\pld@ScanBbyA
    \fi
    \pld@ScanBegingroup \aftergroup\pld@ScanSetB
    \pld@ScanBegingroup \aftergroup\pld@ScanSetB
    \pld@ScanIt}
%    \end{macrocode}
%    \begin{macrocode}
\def\pld@ScanClose){%
    \pld@ScanEndgroup \pld@ScanEndgroup \pld@ScanSetA
    \pld@ScanIt}
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\pld@ScanAdd}
% \begin{macro}{\pld@ScanSubtract}
% correspond to |\calc@add| and |\calc@subtract|.
%    \begin{macrocode}
\def\pld@ScanAdd+{\pld@ScanAddBase\pld@ScanAtoB}
\def\pld@ScanSubtract-{\pld@ScanAddBase\pld@ScanAfromB}
\def\pld@ScanAddBase#1{%
    \pld@ScanEndgroup \pld@ScanEndgroup
    \pld@ScanBegingroup \aftergroup#1%
    \pld@ScanBegingroup \aftergroup\pld@ScanSetB
    \pld@ScanIt}
%    \end{macrocode}
% For a subtraction we just add a factor |\pld@R{-1}{1}|.
%    \begin{macrocode}
\def\pld@ScanAtoB{\pld@ExtendPoly\pld@tempoly\@gtempa}
\def\pld@ScanAfromB{\pld@ExtendPoly\pld@tempoly{\@gtempa\pld@R{-1}1}}
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\pld@ScanMultiply}
% \begin{macro}{\pld@ScanDivide}
% instead of |\calc@multiply| and |\calc@divide|.
%    \begin{macrocode}
\def\pld@ScanMultiply#1{\pld@ScanMultiplyBase\pld@ScanBbyA \pld@ScanIt}
\def\pld@ScanDivide/{\pld@ScanMultiplyBase\pld@ScanDivBbyA \pld@ScanIt}
\def\pld@ScanMultiplyBase{%
    \pld@ScanEndgroup \pld@ScanBegingroup \aftergroup}
%    \end{macrocode}
% Division is here adding a fraction, thus this is limited to numbers and
% symbols. No variables should appear in the expression after |/|.
%    \begin{macrocode}
\def\pld@ScanBbyA{\pld@MultiplyPoly\pld@tempoly\pld@tempoly\@gtempa}
\def\pld@ScanDivBbyA{%
    \def\pld@temp{\pld@F{}}%
    \pld@Extend\pld@temp{\expandafter{\@gtempa}}%
    \pld@Extend\pld@tempoly\pld@temp}
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\pld@ScanPower}
% We calculate the |#1|-th power of |\pld@tempoly| by successive
% multiplication. Note that this code---as most code of this package---is not
% optimized for speed.
%    \begin{macrocode}
\def\pld@ScanPower^#1{%
    \let\pld@polya\pld@tempoly
    \@multicnt#1\relax
    \loop \ifnum\@multicnt>\@ne
        \advance\@multicnt\m@ne
        \pld@MultiplyPoly\pld@tempoly\pld@tempoly\pld@polya
    \repeat
    \pld@ScanIt}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@ScanImplicitMultiply}
% inserts a multiplication if and only if the local register B is a sum.
%    \begin{macrocode}
\def\pld@ScanImplicitMultiply{%
    \expandafter\pld@IfSum\expandafter{\pld@tempoly}%
        {\pld@ScanMultiplyBase\pld@ScanBbyA}%
        {}}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@ScanNumeric}
% We assign the integer to a count register and issue an error if it's
% fractional.
%    \begin{macrocode}
\def\pld@ScanNumeric{%
    \pld@ScanImplicitMultiply
    \let\pld@temp\frac \let\frac\relax
    \afterassignment\pld@ScanNumeric@ \@tempcnta}
\def\pld@ScanNumeric@#1{%
    \let\frac\pld@temp
    \ifx #1.%
        \PackageError{polynom}{noninteger constants not supported}%
        {Constants must be integers in TeX's word range.\MessageBreak
         The fractional part will be lost.}%
        \def\pld@next##1{\afterassignment\pld@ScanIt\@tempcnta}%
    \else
        \let\pld@next\pld@ScanIt
    \fi
%    \end{macrocode}
% We add the integer to the polynomial and continue the scan.
%    \begin{macrocode}
    \pld@Extend\pld@tempoly
        {\expandafter\pld@R\expandafter{\the\@tempcnta}1}%
    \pld@next #1}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@ScanVar}
% \begin{macro}{\pld@ScanSymbol}
% are defined in terms of a submacro.
%    \begin{macrocode}
\def\pld@ScanVar{\pld@ScanImplicitMultiply \pld@ScanVS\pld@V}
\def\pld@ScanSymbol{\pld@ScanImplicitMultiply \pld@ScanVS\pld@S}
%    \end{macrocode}
% The submacro checks all super- and subscript variations and adds
% the data to the polynomial. The suffixes |u| and |l| stand for
% upper and lower.
%    \begin{macrocode}
\def\pld@ScanVS#1#2{%
    \@ifnextchar^{\pld@ScanVS@u#1{#2}}%
                 {\@ifnextchar_{\pld@ScanVar@l#1{#2}}%
                               {\pld@AddTo\pld@tempoly{#1{#2}1}%
                                \pld@ScanIt}}}
%    \end{macrocode}
%    \begin{macrocode}
\def\pld@ScanVS@u#1#2^#3{%
    \@ifnextchar_{\pld@ScanVS@ul#1{#2}{#3}}%
                 {\pld@AddTo\pld@tempoly{#1{#2}{#3}}\pld@ScanIt}}
\def\pld@ScanVS@l#1#2_#3{%
    \@ifnextchar^{\pld@ScanVS@lu#1{#2}{#3}}%
                 {\pld@AddTo\pld@tempoly{#1{#2_{#3}}1}\pld@ScanIt}}
%    \end{macrocode}
%    \begin{macrocode}
\def\pld@ScanVS@ul#1#2#3_#4{%
    \pld@AddTo\pld@tempoly{#1{#2_{#4}}{#3}}\pld@ScanIt}
\def\pld@ScanVS@lu#1#2#3^#4{%
    \pld@AddTo\pld@tempoly{#1{#2_{#3}}{#4}}\pld@ScanIt}
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\pld@ScanFrac}
% A fraction scans nominator and denominator seperately and add them to the
% current |\pld@tempoly|.
%    \begin{macrocode}
\def\pld@ScanFrac#1#2#3{%
    \pld@ScanImplicitMultiply
    \begingroup
      \pld@Scan{#2}\pld@AddTo\pld@tempoly\relax
      \global\let\@gtempa\pld@tempoly
    \endgroup
    \pld@Extend\pld@tempoly{\expandafter\pld@F\expandafter{\@gtempa}}%
%    \end{macrocode}
%    \begin{macrocode}
    \begingroup
      \pld@Scan{#3}\pld@AddTo\pld@tempoly\relax
      \global\let\@gtempa\pld@tempoly
    \endgroup
    \pld@Extend\pld@tempoly{\expandafter{\@gtempa}}%
%    \end{macrocode}
%    \begin{macrocode}
    \pld@ScanIt}
%    \end{macrocode}
% \end{macro}
%
%
% \section{Basic printing}
%
% \begin{macro}{\pld@PrintPoly}
% \meta{polynomial macro}
% \begin{describe}
% prints the polynomial represented by the macro contents. An empty macro
% stands for `0'.
% \end{describe}
% The implementation follows that description and uses |\pld@PrintMonoms|.
%    \begin{macrocode}
\def\pld@PrintPolyArg#1{%
    \def\pld@temp{#1}\pld@PrintPoly\pld@temp}
\def\pld@PrintPoly#1{%
    \ifx\@empty#1\@empty 0\else
        \pld@firsttrue \expandafter\pld@PrintMonoms#1+\relax+%
    \fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@PrintPolyWithDelims}
% \meta{polynomial macro}
% \begin{describe}
% prints the polynomial represented by the macro contents. The polynomial is
% enclosed in the user defined delimiters except when the polynomial is a
% single summand. Then just that summand is printed.
% \end{describe}
% According to the result of |\pld@IfSum| we insert the delimiters.
%    \begin{macrocode}
\def\pld@PrintPolyWithDelimsArg#1{%
    \def\pld@temp{#1}\pld@PrintPolyWithDelims\pld@temp}
\def\pld@PrintPolyWithDelims#1{%
    \ifx\@empty#1\@empty 0\else
        \pld@firsttrue
        \expandafter\pld@IfSum\expandafter{#1}\pld@true\pld@false
        \pld@if \pld@leftdelim
                \expandafter\pld@PrintMonoms#1+\relax+%
                \pld@rightdelim
          \else \expandafter\pld@PrintMonoms#1+\relax+\fi
    \fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@PrintInit}
% is called before we print a factor of a monomial. First we have to `reset'
% |\pld@R| to its primary definition. Its special definition below suppresses
% the output of a factor `1' if this factor is not required.
%    \begin{macrocode}
\def\pld@PrintInit{%
    \let\pld@R\pld@PrintRational \strut
%    \end{macrocode}
% The switch |\pld@iffirst| indicates whether we are working on the first
% summand of a polynomial, that means whether or not we can omit a plus.
% According to the value of the accumulator, we print its sign and/or value.
%    \begin{macrocode}
    \pld@AccuIfNegative
       {\pld@AccuNegate \pld@iffirst\pld@minustrue\else{}\fi -}%
                       {\pld@iffirst\pld@minusfalse\else{}+\fi}%
    \pld@firstfalse
    \pld@AccuIfAbsOne{}{\pld@AccuPrint \pld@true}%
%    \end{macrocode}
% The switch |\pld@if| is set true if and only if we have printed something
% for the monomial (except the sign). So we know when to insert the omitted
% factor `1'.
%
% At the end of |\pld@PrintInit|, the macro throws away itself since all the
% `initialisation' done here is necessary only once for a summand. Note that
% this is done inside a group below, thus the meaning is not lost.
%    \begin{macrocode}
    \let\pld@PrintInit\@empty}
%    \end{macrocode}
%    \begin{macrocode}
\def\pld@minustrue{\global\let\pld@ifminus\iftrue}
\def\pld@minusfalse{\global\let\pld@ifminus\iffalse}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@iffirst}
% from above.
%    \begin{macrocode}
\def\pld@firsttrue{\global\let\pld@iffirst\iftrue}
\def\pld@firstfalse{\global\let\pld@iffirst\iffalse}
\pld@firstfalse
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@PrintMonoms}
% While not reaching the end of the polynomial, the accumulator gets `1' and
% we redefine |\pld@R|,\ldots,|\pld@V|. For example, a rational is just saved
% by multiplying it with the current accumulator.
%    \begin{macrocode}
\def\pld@PrintMonoms#1+{%
    \ifx\relax#1\else
        \begingroup
          \pld@AccuSetX11%
          \let\pld@R\pld@AccuMul
          \let\pld@F\pld@PrintFrac
          \let\pld@S\pld@PrintSymbol
          \let\pld@V\pld@PrintSymbol
%    \end{macrocode}
% Then we indicate that nothing has been printed so far, print the factors (if
% any) by executing the code, and finally print the accumulator if necessary.
%    \begin{macrocode}
          \pld@false
          #1%
          \pld@PrintInit
          \pld@if\else \pld@AccuPrint \fi
        \endgroup
        \expandafter\pld@PrintMonoms
    \fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@PrintRational}
% is |\pld@R|: indicate that we print something, load the accumulator, and
% print it. Note that we don't need to call |\pld@PrintInit| since it has
% already been done!
%    \begin{macrocode}
\def\pld@PrintRational#1#2{%
    \pld@true \pld@AccuSetX{#1}{#2}\pld@AccuPrint}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@PrintSymbol}
% is |\pld@S| or |\pld@V|: init, indicate, and print the symbol with exponent.
%    \begin{macrocode}
\def\pld@PrintSymbol#1#2{%
    \pld@PrintInit \pld@true #1\ifnum#2=\@ne\else^{#2}\fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@PrintFrac}
% is |\pld@F|: init, indicate, and print the fraction \ldots\space no, wait!
% First we check whether the denominator is `1'. In that case we don't use a
% fraction; we enclose the nominator in delimiters if necessary.
%    \begin{macrocode}
\def\pld@PrintFrac#1#2{%
    \pld@PrintInit \pld@true
    \ifx\@empty#2\@empty
        \begingroup
          \pld@IfSum{#1}\pld@true\pld@false
          \pld@if\pld@leftdelim #1\pld@rightdelim\else #1\fi
        \endgroup
        \expandafter\@gobbletwo
    \else
        \expandafter\pld@PrintFrac@
    \fi
    {#1}{#2}}
%    \end{macrocode}
% Otherwise we check the nominator.
%    \begin{macrocode}
\def\pld@PrintFrac@#1#2{%
    \ifx\@empty#1\@empty \frac1{#2}\else \frac{#1}{#2}\fi}
%    \end{macrocode}
% \end{macro}
%
% These printing routines do \emph{not} handle all representations which are
% legal in the sense of section \ref{sInternalDataFormat}. For example,
% |\pld@R{1}{1}\pld@V{X}{1}\pld@R{-1}{1}| would be printed as $X-1$.
% A correct output is guaranteed if there is at most one rational at the
% very beginning of the representation. Thus we normalize the internal data:
% condense, sort and simplify factors and summands. This will keep us busy
% for the next (p)ages.
%
%
% \section{Simplifying}
%
%
% \subsection{Phase I: Condense factors of summands}
%
% \begin{macro}{\pld@CondenseFactors}
% \meta{polynomial macro}
% \begin{describe}
% Here we condense rationals, fractions, and the exponents of symbolic factors
% and variables of each monomial in \meta{polynomial macro}. Afterwards the
% factors appear exactly in this order: if present a rational number comes
% first, then fractions if any, then symbols, and finally the variables.
% For example, the representation of
% {\makeatletter\pld@Scan{\frac23\frac1e5X^3\frac32X}
%         $\pld@PrintPoly\pld@tempoly$
% becomes  \pld@CondenseFactors\pld@tempoly
%         $\pld@PrintPoly\pld@tempoly$}.
% \end{describe}
% As for printing, we redefine |\pld@R|,\ldots,|\pld@V| and iterate through
% the monomials.
%    \begin{macrocode}
\def\pld@CondenseFactors#1{%
    \ifx\@empty#1\else
        \begingroup
          \let\pld@R\pld@AccuMul
          \let\pld@F\pld@CondenseFrac
          \let\pld@S\pld@CFSymbol
          \let\pld@V\pld@CFVar
%    \end{macrocode}
% The following two assignments allow |#1| to be |\pld@temp| or |\pld@tempoly|.
%    \begin{macrocode}
          \let\pld@temp#1\let\pld@tempoly\@empty
          \expandafter\pld@CF@loop\pld@temp+\relax+%
          \global\let\@gtempa\pld@tempoly
        \endgroup
        \let#1\@gtempa
    \fi}
%    \end{macrocode}
% For each monomial the factors are kept in separate `registers': rationals in
% the accumulator, fractions in |\pld@frac|, symbols in |\pld@symbols|, and
% variables in |\pld@vars|. |\pld@if| is set true if and only if there is a
% `general' fraction.
%    \begin{macrocode}
\def\pld@CF@loop#1+{%
    \ifx\relax#1\else
        \begingroup
          \pld@AccuSetX11%
          \def\pld@frac{{}{}}\let\pld@symbols\@empty\let\pld@vars\@empty
          \pld@false
          #1%
          \let\pld@temp\@empty
%    \end{macrocode}
% Now we put together the collected data (if the rational constant is not
% zero): If the rational constant does not equal one, we place it in front of
% all other factors.
%    \begin{macrocode}
          \pld@AccuIfZero{}%
          {\pld@AccuIfOne{}{\pld@AccuGet\pld@temp
                            \edef\pld@temp{\noexpand\pld@R\pld@temp}}%
%    \end{macrocode}
% Then follow fractions, symbols and variables.^^A
% \footnote{This is the right place to \emph{simplify} general fractions and
%       symbols. Here we are in the special case that they don't contain
%       any rationals as `over all' factors except `$1=|\{\}|={}$ empty
%       argument' in the nominator or denominator, e.g.~$\frac{a+b}{b+a}$ is
%       now represented as $\frac{a+b}1\frac1{b+a}$.}
%    \begin{macrocode}
           \pld@if \pld@Extend\pld@temp{\expandafter\pld@F\pld@frac}\fi
           \expandafter\pld@CF@loop@\pld@symbols\relax\@empty
           \expandafter\pld@CF@loop@\pld@vars\relax\@empty
%    \end{macrocode}
% Finally we add the result to |\pld@tempoly|. Note that |\endgroup| destroys
% all temporary garbage, for example the exponents of symbols and variables.
%    \begin{macrocode}
           \ifx\@empty\pld@temp
               \def\pld@temp{\pld@R11}%
           \fi}%
          \global\let\@gtempa\pld@temp
        \endgroup
        \ifx\@empty\@gtempa\else
            \pld@ExtendPoly\pld@tempoly\@gtempa
        \fi
        \expandafter\pld@CF@loop
    \fi}
%    \end{macrocode}
% For each symbol or variable, we look up the exponent |\pld@@|\meta{symbol}
% and add it together with |\pld@|\meta{\textup{\texttt{S}$\vert$\texttt{V}}}
% and the symbol to the summand |\pld@temp|.
%    \begin{macrocode}
\def\pld@CF@loop@#1#2{%
    \ifx\relax#1\else
        \xdef\@gtempa{\csname pld@@\string#2\endcsname}%
        \ifnum \@gtempa=\z@ \else
            \pld@AddTo\pld@temp{#1{#2}}%
            \pld@Extend\pld@temp{\expandafter{\@gtempa}}%
        \fi
        \expandafter\pld@CF@loop@
    \fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@CFSymbol}
% \begin{macro}{\pld@CFVar}
% These definitions collect the exponents. Here we only insert type arguments.
%    \begin{macrocode}
\def\pld@CFSymbol{\pld@CFSV\pld@symbols\pld@S}
\def\pld@CFVar{\pld@CFSV\pld@vars\pld@V}
%    \end{macrocode}
% A new symbol initializes |\pld@@|\meta{symbol} to the current exponent and
% adds the symbol to the list, whereas \ldots
%    \begin{macrocode}
\def\pld@CFSV#1#2#3#4{%
    \@ifundefined{pld@@\string#3}%
    {\@namedef{pld@@\string#3}{#4}%
     \pld@AddTo#1{#2{#3}}}%
%    \end{macrocode}
% an existing one increases |\pld@@|\meta{symbol}.
%    \begin{macrocode}
    {\@tempcnta\csname pld@@\string#3\endcsname\relax
     \advance\@tempcnta#4\relax
     \expandafter\edef\csname pld@@\string#3\endcsname{\the\@tempcnta}}}
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\pld@CondenseFrac}
% For a fraction, we work on the nominator and denominator separately: a sum
% is added to |\pld@frac|, otherwise we `execute' the code---but of course the
% reciprocal of the denominator. This adds the appropriate data.
%    \begin{macrocode}
\def\pld@CondenseFrac#1#2{%
    \pld@IfSum{#1}{\pld@CFFracAdd{\pld@F{#1}{}}{}}%
                  {#1}%
    \pld@IfSum{#2}{\pld@CFFracAdd{}{\pld@F{}{#2}}}%
                  {\begingroup
                     \pld@DefInverse\pld@temp{#2}%
                     \global\let\@gtempa\pld@temp
                   \endgroup
                   \@gtempa}}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@CFFracAdd}
% We just add the nominator and denominator to |\pld@frac| and indicate this
% by setting |\pld@if| true.
%    \begin{macrocode}
\def\pld@CFFracAdd{\pld@true \expandafter\pld@CFFracAdd@\pld@frac}
\def\pld@CFFracAdd@#1#2#3#4{\def\pld@frac{{#1#3}{#2#4}}}
%    \end{macrocode}
% \end{macro}
%
%
% \subsection{Phase III: Condense monomials of same type}
%
% \begin{macro}{\pld@CondenseMonomials}
% $\langle$|\pld@true|$\vert$|pld@false|$\rangle$\meta{polynomial macro}
% \begin{describe}
% This definition sums up the monomials of \meta{polynomial macro}.
% For example, the representation of
% {\makeatletter\pld@Scan{X^2+e^{-1}X^2}^^A
%         $\pld@PrintPoly\pld@tempoly$
% becomes  \pld@CondenseMonomials\pld@true\pld@tempoly
%         $\pld@PrintPoly\pld@tempoly$}.
% If and only if the first argument is |\pld@false|, the macro works on
% symbols instead of variables, for example
% {\makeatletter\pld@Scan{1-\pi+2\pi+e^{-1}+e^{-1}}^^A
%               \pld@CondenseFactors\pld@tempoly
%         $\pld@PrintPoly\pld@tempoly$
% becomes  \pld@CondenseMonomials\pld@false\pld@tempoly
%         $\pld@PrintPoly\pld@tempoly$}.
% \end{describe}
% Again we redefine |\pld@R|,\ldots,|\pld@V|. Here they will add their
% arguments to the current summand. To condense a sum of constants, i.e.~to
% work on symbols, we need to redefine two more macros and sort the constants
% first. To understand this, read ahead and notice the paragraph  at the end
% of this subsection.
%    \begin{macrocode}
\def\pld@CondenseMonomials#1#2{%
    \ifx\@empty#2\else
        \begingroup
          #1%
          \pld@if\else
              \let\pld@SortVars@V\pld@SortVars@S
              \let\pld@SplitMonom\pld@SplitMonomS
              \pld@SortMonomials#2%
          \fi
          \let\pld@R\pld@CMRational
          \let\pld@F\pld@CMFrac
          \let\pld@S\pld@CMSymbol
          \let\pld@V\pld@CMError
%    \end{macrocode}
% Initialize temporary macros, expand the polynomial and work on it, and
% assign the result back to |#1|.
%    \begin{macrocode}
          \let\pld@temp#2\let\pld@tempoly\@empty
          \pld@AccuSetX01\let\pld@symbols\@empty \let\pld@monom\relax
          \expandafter\pld@CM@\pld@temp+\relax+%
          \global\let\@gtempa\pld@tempoly
        \endgroup
        \let#2\@gtempa
    \fi}
%    \end{macrocode}
% Reaching the end of the polynomial, we just add the last summand to the
% temporary polynomial. Otherwise the monomial is split into `factors' and
% `variables', which are handled by |\pld@CM@do|. Afterwards we proceed to
% the next summand.
%    \begin{macrocode}
\def\pld@CM@#1+{%
    \ifx\relax#1\relax
        \pld@CMAddToTempoly
    \else
        \pld@SplitMonom\pld@CM@do{#1}%
        \expandafter\pld@CM@
    \fi}
%    \end{macrocode}
% The following macro gets the nonvariable and variable part as arguments. If
% we haven't worked on a summand yet, we don't need to do anything special. At
% the end of the macro we will add the nonvariable part to the currently empty
% nonvariable part.
%    \begin{macrocode}
\def\pld@CM@do#1#2{%
    \ifx\pld@monom\relax \else
%    \end{macrocode}
% Otherwise we check whether the last and current monomials are of same type.
% Note that this simple |\ifx| requires the variables being in the same order.^^A
% \footnote{It's better to use |\bslash pld@IfMonomE|, but even this requires
%       the mentioned restriction.}
% If the monomials are different, we add the last monomial to the temporary
% polynomial and initialize some macros again.
%    \begin{macrocode}
        \def\pld@temp{#2}%
        \ifx\pld@temp\pld@monom \else
            \pld@CMAddToTempoly
            \pld@AccuSetX01\let\pld@symbols\@empty \let\pld@monom\relax
        \fi
    \fi
%    \end{macrocode}
% In any case we add the nonvariable part to the current (possibly cleared)
% one.
%    \begin{macrocode}
    \let\pld@op+%
    \ifx\@empty#1\@empty \pld@R11\relax \else #1\relax \fi
    \def\pld@monom{#2}}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@CMAddToTempoly}
% According to whether the accumulator is zero, we save the value in
% |\pld@temp| or just empty that macro.
%    \begin{macrocode}
\def\pld@CMAddToTempoly{%
    \pld@AccuIfZero{\let\pld@temp\@empty}%
                   {\pld@AccuGet\pld@temp
                    \edef\pld@temp{\noexpand\pld@R\pld@temp}}%
%    \end{macrocode}
% Then we we simplify the (possible) sum of symbols by calling the main
% definition of this section with |\pld@false|. Afterwards we append the
% symbols if necessary.
%    \begin{macrocode}
    \pld@CondenseMonomials\pld@false\pld@symbols
    \ifx\pld@symbols\@empty \else
        \pld@ExtendPoly\pld@temp\pld@symbols
    \fi
%    \end{macrocode}
% Now depending on the contents of |\pld@temp|, we do nothing---the sum of the
% monomials is zero---or add the factors together with the `variable part' to
% the polynomial. Note that we put |\pld@F{| and |}{}| around a sum if and
% only if |\pld@if| is true.\footnote{Why we don't need a fraction and also
% don't want it in the other case? We don't want it since it would make things
% more complex. We don't need it since, if we strip off both variables and
% symbols, there are only rationals left and these are evaluated completely
% and condensed in one single rational---no sum, no need for a fraction.}
%    \begin{macrocode}
    \ifx\pld@temp\@empty \else
        \pld@if
            \expandafter\pld@IfSum\expandafter{\pld@temp}%
                {\expandafter\def\expandafter\pld@temp\expandafter
                    {\expandafter\pld@F\expandafter{\pld@temp}{}}}%
                {}%
        \fi
        \pld@ExtendPoly\pld@tempoly\pld@temp
        \pld@Extend\pld@tempoly{\pld@monom}%
    \fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@CMFracAdd}
% Depending on the current operator |\pld@op|, we add a new summand to
% |\pld@symbols| or extend the last summand by another factor.
%    \begin{macrocode}
\def\pld@CMFracAdd{%
    \ifx +\pld@op \let\pld@op\@empty
                  \expandafter\pld@AddToPoly
            \else \expandafter\pld@AddTo \fi
    \pld@symbols}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@CMRational}
% We add the rational to the accumulator if and only if there is no other
% (symbolic or fractional) factor. This is the reason for some |\relax|es
% above and below.
%    \begin{macrocode}
\def\pld@CMRational#1#2#3{%
    \ifx\relax#3%
        \pld@AccuAdd{#1}{#2}%
    \else
%    \end{macrocode}
% If the rational belongs to a more complex factor, we add it to
% |\pld@symbols|. Note that the used macro was redefined above.
%    \begin{macrocode}
        \pld@CMFracAdd{\pld@R{#1}{#2}}%
        \expandafter#3%
    \fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@CMSymbol}
% A symbol is just copied.
%    \begin{macrocode}
\def\pld@CMSymbol#1#2{\pld@CMFracAdd{\pld@S{#1}{#2}}}%
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@CMFrac}
% Here we remove a possibly inserted |\pld@F{| and |}{}| around a sum and
% execute the nominator---or we add the (condensed) fraction.
%    \begin{macrocode}
\def\pld@CMFrac#1#2{%
    \ifx\@empty#2\@empty
        \pld@CMFrac@nom#1+\relax+%
    \else
        \pld@CMFrac@{#1}{#2}%
    \fi}
%    \end{macrocode}
%    \begin{macrocode}
\def\pld@CMFrac@#1#2{%
    \pld@IfSum{#1}{\pld@CMFracAdd{\pld@F{#1}{}}}%
                  {#1}%
    \pld@IfSum{#2}{\pld@CMFracAdd{\pld@F{}{#2}}}%
                  {\begingroup
                     \pld@DefInverse\pld@temp{#2}%
                     \global\let\@gtempa\pld@temp
                   \endgroup
                   \@gtempa}}
%    \end{macrocode}
% A nominator is executed summand by summand.
%    \begin{macrocode}
\def\pld@CMFrac@nom#1+{%
    \ifx\relax#1\else
        #1\relax
        \expandafter\pld@CMFrac@nom
    \fi}
%    \end{macrocode}
% \end{macro}
%
% In this section we have made two assumptions: (a) \emph{variables have
% always the same order in monomials} and (b) \emph{monomials of the same
% type}---that means at most different in the nonvariable part---\emph{must
% follow each other}. The first condition has already been mentioned, the
% second is necessary for looking only at the next monomial to check whether
% we have to summarize their preceeding factors. Both are established in the
% following section.
%
%
% \subsection{Phase II: Sort monomials by type}
%
% \begin{macro}{\pld@SortMonomials}
% We first sort the variables of each monomial and then the monomials.
%    \begin{macrocode}
\def\pld@SortMonomials#1{%
    \ifx #1\@empty \else
        \begingroup
%    \end{macrocode}
%    \begin{macrocode}
          \let\pld@temp#1\let\pld@tempoly\@empty
          \expandafter\pld@SortVars\pld@temp+\relax+%
%    \end{macrocode}
%    \begin{macrocode}
          \let\pld@temp\pld@tempoly \let\pld@tempoly\@empty
          \expandafter\pld@SortSummands\pld@temp+\relax+%
%    \end{macrocode}
%    \begin{macrocode}
          \global\let\@gtempa\pld@tempoly
        \endgroup
        \let#1\@gtempa
    \fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@SortVars}
% While not reaching the end \ldots
%    \begin{macrocode}
\def\pld@SortVars#1+{%
    \ifx\relax#1\relax\else
        \pld@SplitMonom\pld@SortVars@{#1}%
        \expandafter\pld@SortVars
    \fi}
%    \end{macrocode}
% we sort the variables if necessary---note the redefinitions of |\pld@V| and
% |\pld@S|---
%    \begin{macrocode}
\def\pld@SortVars@#1#2{%
    \begingroup
      \def\pld@monom{#2}%
      \ifx\@empty\pld@monom\else
          \let\pld@V\pld@SVVar
          \let\pld@S\pld@SVSymbol
          \pld@SortVars@V
      \fi
      \global\let\@gtempa\pld@monom
    \endgroup
%    \end{macrocode}
% and put the things together again.
%    \begin{macrocode}
    \def\pld@factor{#1}%
    \pld@Extend\pld@factor\@gtempa
    \pld@ExtendPoly\pld@tempoly\pld@factor}
%    \end{macrocode}
% We use good old bubble sort on the contents of |\pld@monom|. This macro
% terminates if no items have been interchanged.
%    \begin{macrocode}
\def\pld@SortVars@V{%
    \pld@false \let\pld@temp\pld@monom \let\pld@monom\@empty
    \pld@temp\pld@V\relax\relax
    \pld@if \expandafter\pld@SortVars@V \fi}
%    \end{macrocode}
% The redefinition of |\pld@V| first checks whether the end of the variables
% has been reached. If this is not the case, we either add the current
% variable to |\pld@monom| and continue with the next one, or we interchange
% the variables and indicate this by |\pld@true|.
%    \begin{macrocode}
\def\pld@SVVar#1#2\pld@V#3#4{%
    \ifx\relax#3\relax
        \pld@AddTo\pld@monom{\pld@V{#1}{#2}}%
    \else
        \pld@IfVarL{#1}{#3}{\pld@AddTo\pld@monom{\pld@V{#1}{#2}}%
                            \def\pld@next{\pld@V{#3}{#4}}}%
                           {\pld@true
                            \pld@AddTo\pld@monom{\pld@V{#3}{#4}}%
                            \def\pld@next{\pld@V{#1}{#2}}}%
        \expandafter\pld@next
    \fi}
%    \end{macrocode}
% The similar for |\pld@S| instead of |\pld@V| for sorting symbols.
%    \begin{macrocode}
\def\pld@SortVars@S{%
    \pld@false \let\pld@temp\pld@monom \let\pld@monom\@empty
    \pld@temp\pld@S\relax\relax
    \pld@if \expandafter\pld@SortVars@S \fi}
%    \end{macrocode}
%    \begin{macrocode}
\def\pld@SVSymbol#1#2\pld@S#3#4{%
    \ifx\relax#3\relax
        \pld@AddTo\pld@monom{\pld@S{#1}{#2}}%
    \else
        \pld@IfVarL{#1}{#3}{\pld@AddTo\pld@monom{\pld@S{#1}{#2}}%
                            \def\pld@next{\pld@S{#3}{#4}}}%
                           {\pld@true
                            \pld@AddTo\pld@monom{\pld@S{#3}{#4}}%
                            \def\pld@next{\pld@S{#1}{#2}}}%
        \expandafter\pld@next
    \fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@SortSummands}
% Now comes the same for whole monomials except that we can't redefine any
% kind of |\pld@V| and that we will use insertion sort. So, while not reaching
% the end \ldots
%    \begin{macrocode}
\def\pld@SortSummands#1+{%
    \ifx\relax#1\relax\else
%    \end{macrocode}
% we find the right place for |\pld@monom| in |\pld@tempoly|.
%    \begin{macrocode}
        \ifx\@empty\pld@tempoly
            \def\pld@tempoly{#1}%
        \else
            \def\pld@monom{#1}%
            \let\pld@temp\pld@tempoly \let\pld@tempoly\@empty
            \expandafter\pld@SortSummands@i\pld@temp+\relax+%
        \fi
        \expandafter\pld@SortSummands
    \fi}
%    \end{macrocode}
% For this, we iterate down the intermediate result and \ldots
%    \begin{macrocode}
\def\pld@SortSummands@i#1+{%
    \ifx\relax#1\relax
        \pld@ExtendPoly\pld@tempoly\pld@monom
        \expandafter\@gobble
    \else
        \expandafter\pld@SortSummands@j
    \fi
    {#1}}
%    \end{macrocode}
% we test whether we've found the right place and insert the monomial if
% necessary.
%    \begin{macrocode}
\def\pld@SortSummands@j#1{%
    \expandafter\pld@IfMonomL\expandafter{\pld@monom}{#1}%
        {\pld@AddToPoly\pld@tempoly{#1}%
         \pld@SortSummands@i}%
        {\pld@SortSummands@k\pld@monom+#1+}}
\def\pld@SortSummands@k#1+\relax+{\pld@ExtendPoly\pld@tempoly{#1}}
%    \end{macrocode}
% \end{macro}
%
%
% \subsection{Phase II: Lexicographical order}
%
% \begin{macro}{\pld@IfVarL}
% \marg{varibale 1}\marg{variable 2}\marg{then}\marg{else}
% \begin{describe}
% This macro executes \meta{then} if and only if \meta{variable 1} is less
% than \meta{variable 2} (with respect to the lexicographical order defined
% by this macro).
% \end{describe}
% First we check whether the variables are equal.
%    \begin{macrocode}
\def\pld@IfVarL#1#2{%
    \begingroup
      \def\pld@va{#1}\def\pld@vb{#2}%
      \ifx\pld@va\pld@vb
          \aftergroup\@secondoftwo
      \else
%    \end{macrocode}
% If the variables are not equal, we use their `|\meaning| expansion' for a
% string comparison.
%    \begin{macrocode}
          \edef\pld@next{\expandafter\strip@prefix\meaning\pld@va
                                           \relax\noexpand\@empty
                         \expandafter\strip@prefix\meaning\pld@vb
                                           \relax\noexpand\@empty}%
          \expandafter\pld@IfVarL@\pld@next
      \fi
    \endgroup}
%    \end{macrocode}
% If we've reached the end of a variable, we call the appropriate macro
% |\aftergroup|.
%    \begin{macrocode}
\def\pld@IfVarL@#1#2\@empty#3#4\@empty{%
    \let\pld@next\@empty
          \ifx #3\relax \aftergroup\@secondoftwo
    \else \ifx #1\relax \aftergroup\@firstoftwo
    \else
%    \end{macrocode}
% Otherwise we either need to look at the next characters or compare the two
% ones.
%    \begin{macrocode}
        \ifx#1#3%
            \def\pld@next{\pld@IfVarL#2\@empty#4\@empty}%
        \else
            \ifnum`#1<`#3\relax \aftergroup\@firstoftwo
                          \else \aftergroup\@secondoftwo \fi
        \fi
    \fi \fi
    \pld@next}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@IfMonomL}
% \marg{monomial 1}\marg{monomial 2}\marg{then}\marg{else}
% \begin{describe}
% This macro executes \meta{then} if and only if \meta{monomial 1} is less
% than \meta{monomial 2}. It is required that both monomials' variables are
% sorted.
% \end{describe}
% The implementation is straight forward if you know the last definitions.
%    \begin{macrocode}
\def\pld@IfMonomL#1#2{%
    \begingroup
      \pld@IfMonomL@#1\pld@V\relax\relax\@empty
                    #2\pld@V\relax\relax\@empty
    \endgroup}
%    \end{macrocode}
% If we've reached the end of the variables, we call the appropriate macro.
%    \begin{macrocode}
\def\pld@IfMonomL@#1\pld@V#2#3#4\@empty#5\pld@V#6#7#8\@empty{%
    \let\pld@next\@empty
          \ifx #6\relax \aftergroup\@secondoftwo
    \else \ifx #2\relax \aftergroup\@firstoftwo
    \else
%    \end{macrocode}
% If we have two variables, there are two main cases in which the first
% monomial is smaller: the variable of the first one is smaller or the
% variables are equal but the first exponent is smaller. If both variable and
% exponent match, we have test the next variables.
%    \begin{macrocode}
        \def\pld@va{#2}\def\pld@vb{#6}%
        \ifx\pld@va\pld@vb
            \ifnum#3=#7\relax
                \def\pld@next{\pld@IfMonomL@#4\@empty#8\@empty}%
            \else
                \ifnum#3<#7\relax \aftergroup\@firstoftwo
                            \else \aftergroup\@secondoftwo \fi
            \fi
        \else
            \pld@IfVarL#2\relax\@empty#6\relax\@empty
                {\aftergroup\@firstoftwo}%
                {\aftergroup\@secondoftwo}%
        \fi
    \fi \fi
    \pld@next}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@IfMonomE}
% \marg{monomial 1}\marg{monomial 2}\marg{then}\marg{else}
% \begin{describe}
% This macro executes \meta{then} if and only if \meta{monomial 1} has the
% same variables with identical exponents as \meta{monomial 2}. It is required
% that both monomials' variables are sorted.
% \end{describe}
% We just extract the `variable parts' and compare them with |\ifx|.
%    \begin{macrocode}
\def\pld@IfMonomE#1#2{\pld@IfMonomE@#1\pld@V\@empty#2\pld@V\@empty}
%    \end{macrocode}
%    \begin{macrocode}
\def\pld@IfMonomE@#1\pld@V#2\@empty#3\pld@V#4\@empty{%
    \begingroup
      \def\pld@va{#2}\def\pld@vb{#4}%
      \ifx\pld@va\pld@vb \aftergroup\@firstoftwo
                   \else \aftergroup\@secondoftwo \fi
    \endgroup}
%    \end{macrocode}
% \end{macro}
%
%
% \subsection{Putting together the ingredients}
%
% \begin{macro}{\pld@Simplify}
% \meta{polynomial macro}
% \begin{describe}
% just calls the definitions of the last sections in the correct order.
% \end{describe}
%    \begin{macrocode}
\def\pld@Simplify#1{%
    \pld@CondenseFactors#1%
    \pld@SortMonomials#1%
    \pld@CondenseMonomials\pld@true#1}
%    \end{macrocode}
% \end{macro}
%
%
% \section{Multiplication}
%
% \begin{macro}{\pld@MultiplyPoly}
% \begin{macro}{\pld@NMultiplyPoly}
% \meta{macro a}\meta{macro b}\meta{macro c}
% \begin{describe}
% \meta{macro a} gets \meta{macro b}${}\cdot{}$\meta{macro c} respectively
% the negative polynomial in the second case \texttt{N}.
% \end{describe}
% We use a switch to distinguish the positive and negative form.
%    \begin{macrocode}
\def\pld@MultiplyPoly{\begingroup\pld@true \pld@MultiplyPoly@}
\def\pld@NMultiplyPoly{\begingroup\pld@false \pld@MultiplyPoly@}
%    \end{macrocode}
% Multiply the polynomials and condense the result. Note that the latter is
% the main working procedure. To avoid problems with |\polyhornerscheme| (it
% uses empty macros for the representation of the number 0), we check for
% empty macros here---thanks go to Ludger Humbert.
%    \begin{macrocode}
\def\pld@MultiplyPoly@#1#2#3{%
      \let\pld@temp\@empty
      \ifx\@empty#2\@empty\else \ifx\@empty#3\@empty\else
          \expandafter\pld@MultiplyPoly@a\expandafter#2#3+\relax+%
      \fi \fi
      \global\let\@gtempa\pld@temp
    \endgroup
    \let#1\@gtempa \pld@CondenseFactors#1}
%    \end{macrocode}
% Here we combine each (negated) summand |#2| of the second polynomial with
% \ldots
%    \begin{macrocode}
\def\pld@MultiplyPoly@a#1#2+{%
    \ifx\relax#2\else
        \pld@if \def\pld@va{#2}\else \def\pld@va{#2\pld@R{-1}1}\fi
        \expandafter\pld@MultiplyPoly@b#1+\relax+%
        \expandafter\pld@MultiplyPoly@a\expandafter#1%
    \fi}
%    \end{macrocode}
% each summand |#1| of the first one.
%    \begin{macrocode}
\def\pld@MultiplyPoly@b#1+{%
    \ifx\relax#1\else
        \pld@ExtendPoly\pld@temp{\pld@va#1}%
        \expandafter\pld@MultiplyPoly@b
    \fi}
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
%
% \section{Division}
%
%
% \subsection{The algorithm}
%
% \begin{macro}{\pld@DividePoly}
% \begin{macro}{\pld@LongDividePoly}
% A polynomial long division is indicated by |\pld@true|. In this case we also
% need to initialize some macros.
%    \begin{macrocode}
\def\pld@DividePoly{\pld@false \pld@DivPoly}
%    \end{macrocode}
%    \begin{macrocode}
\def\pld@LongDividePoly#1#2{%
    \let\pld@pattern\@empty \let\pld@lastline\@empty
    \let\pld@subline\@empty \let\pld@currentline\@empty
    \let\pld@allines\@empty \let\pld@maxcol\z@
    \pld@true \pld@DivPoly#1#2%
    \pld@ArrangeResult#1}
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% The division algorithm has three main components: the division of two
% monomials, the subtraction of two polynomials, and a loop putting together
% both things.
%
% \begin{macro}{\pld@DivPoly}
% The loop: We initialize remainder, divisor, and quotient.
%    \begin{macrocode}
\def\pld@DivPoly#1#2{%
    \pld@currstage\pld@stage\relax
    \let\pld@remainder#1\let\pld@divisor#2\let\pld@quotient\@empty
    \pld@DivPoly@l}
%    \end{macrocode}
% While the remainder isn't zero and needs to be divided, we extend the
% quotient and subtract the appropriate polynomial from the remainder.
%    \begin{macrocode}
\def\pld@DivPoly@l{%
    \ifx\pld@remainder\@empty\else
        \pld@IfNeedsDivision\pld@remainder\pld@divisor
        {\pld@ExtendPoly\pld@quotient\pld@factor
         \pld@NMultiplyPoly\pld@sub\pld@divisor\pld@factor
         \pld@SubtractPoly\pld@remainder\pld@sub
         \expandafter\pld@DivPoly@l}%
        {}%
    \fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@IfNeedsDivision}
% \meta{polynomial 1}\meta{polynomial 2}\marg{then}\marg{else}
% \begin{describe}
% executes \meta{then} if and only if \meta{polynomial 1} must be divided by
% \meta{polynomial 2} (with possibly nonzero remainder!). |\pld@factor| can be
% used in \meta{then} and holds the quotient of the first monomials. Note that
% this macro requires the polynomials to be sorted.
% \end{describe}
% We expand the two polynomials and add terminators |+\@empty|.
%    \begin{macrocode}
\def\pld@IfNeedsDivision#1#2{%
    \pld@ExpandTwo\pld@IfND{#1+\@empty}{#2+\@empty}}
%    \end{macrocode}
% Now we can divide the first summands of the two polynomials and \ldots
%    \begin{macrocode}
\def\pld@IfND#1+#2\@empty#3+#4\@empty{%
    \pld@DefInverse\pld@factor{#3}%
    \pld@AddTo\pld@factor{#1}%
    \pld@CondenseFactors\pld@factor
%    \end{macrocode}
% check whether all variables have a non-negative exponent.
% Depending on that, we choose the correct argument.
%    \begin{macrocode}
    \begingroup
      \pld@true
      \expandafter\pld@IfND@\pld@factor\pld@V\relax\z@
      \pld@if \aftergroup\@firstoftwo
        \else \aftergroup\@secondoftwo \fi
    \endgroup}
%    \end{macrocode}
% And here we check for (non-)negative exponents.
%    \begin{macrocode}
\def\pld@IfND@#1\pld@V#2#3{%
    \ifx\relax#2\@empty \expandafter\@gobble
                  \else \ifnum#3<\z@ \pld@false \fi
    \fi \pld@IfND@}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@SubtractPoly}
% Here we perform the subtraction. We could define one very short macro for
% `short' and another for polynomial long division, but this macro covers both
% cases. We do nothing if |#2| is empty. This test shouldn't be necessary, but
% who knows how I'll change |\pld@DivPoly| in future.
%    \begin{macrocode}
\def\pld@SubtractPoly#1#2{%
    \ifx#2\@empty\else
%    \end{macrocode}
% For long division, we initialize the horizontal rule's first and last column.
%    \begin{macrocode}
        \pld@if
            \let\pld@firstcol\maxdimen \let\pld@lastcol\z@
        \fi
%    \end{macrocode}
% The submacro does the subtraction and defines appropriate data 
% |\pld@lastline|, |\pld@subline|, \ldots\space.
%    \begin{macrocode}
        \let\pld@tempoly\@empty
        \pld@ExpandTwo\pld@SubtractPoly@
                 {#1+\relax+\@empty}{#2+\relax+\@empty}%
        \let#1\pld@tempoly
%    \end{macrocode}
% For long divisions, we now add the calculated lines and a horizontal rule
% to |\pld@allines| (if the current stage allows it). Eventually we reset data.
%    \begin{macrocode}
        \pld@if
            \ifnum\pld@currstage>\z@
                \pld@Extend\pld@allines{\pld@lastline\cr}%
            \else
                \pld@InsertFake\pld@lastline
            \fi
            \advance\pld@currstage-\tw@
            \ifnum\pld@currstage>\z@
                \pld@Extend\pld@allines{\pld@subline\cr}%
                \edef\pld@subline{%
                    \noexpand\cline{\pld@firstcol-\pld@lastcol}
                    \noalign{\vskip\jot}}%
                \pld@Extend\pld@allines\pld@subline
            \else
                \pld@InsertFake\pld@subline
            \fi
            \advance\pld@currstage\m@ne
            \let\pld@lastline\pld@currentline
            \let\pld@subline\@empty
            \let\pld@currentline\@empty
        \fi
    \fi}
%    \end{macrocode}
% The following submacro reads both first monomials. The difference must be
% zero, so we just gobble the monomials except for long division. This is
% coded explicitly to always reduce the degree---no matter what the
% calculations in behind say is true. For long division, we take the
% original monomial, negate it, and use these two for the visualization.
%    \begin{macrocode}
\def\pld@SubtractPoly@#1+#2\@empty#3+{%
    \pld@if
        \pld@DefNegative\pld@monom{#1}%
        \expandafter\pld@InsertItems\expandafter\@empty
            \expandafter{\pld@monom}{#1}%
    \fi
    \pld@SubtractPoly@l#2\@empty}
%    \end{macrocode}
% All other monomials are read here. We have to distinguish several cases.
% If we've reached the end of both polynomials, the next operation is empty.
%    \begin{macrocode}
\def\pld@SubtractPoly@l#1+#2\@empty#3+#4\@empty{%
    \ifx\relax#1\relax
        \ifx\relax#3\relax \let\pld@next\@empty \else
%    \end{macrocode}
% If we've reached the end of the first polynomial, we add the monomial of the
% second polynomial, subtract it from the result, use it for visualization, and
% call this macro again to read the rest of the polynomial.
%    \begin{macrocode}
          \pld@AddToPoly\pld@tempoly{#3}%
          \pld@if \pld@InsertItems{#3}{#3}{}\fi
          \def\pld@next{\pld@SubtractPoly@l\relax+\@empty#4\@empty}%
        \fi
    \else
    \ifx\relax#3\relax
%    \end{macrocode}
% If we've reached the end of the second polynomial, we just add the rest of
% the first polynomial to the result |\pld@tempoly|.
%    \begin{macrocode}
        \pld@SubtractPoly@r#1+#2\@empty
        \let\pld@next\@empty
    \else
%    \end{macrocode}
% There are three cases if we have two monomials. If they are equal---which
% means that the variables and their exponents match---, we add the monomials
% and use the result to extend the temporary polynomial as well as for the
% visualization.
%    \begin{macrocode}
        \pld@IfMonomE{#1}{#3}%
        {\def\pld@temp{#1+#3}%
         \pld@CondenseMonomials\pld@true\pld@temp
         \ifx\pld@temp\@empty\else
             \pld@ExtendPoly\pld@tempoly\pld@temp
         \fi
         \pld@if \expandafter\pld@InsertItems\expandafter
                 {\pld@temp}{#3}{#1}\fi
         \def\pld@next{\pld@SubtractPoly@l#2\@empty#4\@empty}}%
%    \end{macrocode}
% If the second monomial is stricly smaller, we extend the temporary polynomial
% and the visualization by this monomial and re-insert the first monomial to be
% read again.
%    \begin{macrocode}
        {\pld@IfMonomL{#1}{#3}%
         {\pld@AddToPoly\pld@tempoly{#3}%
          \pld@if \pld@InsertItems{#3}{#3}{}\fi
          \def\pld@next{\pld@SubtractPoly@l#1+#2\@empty#4\@empty}}%
%    \end{macrocode}
% If the first monomial is stricly smaller, we extend the temporary polynomial
% and the visualization by this monomial and re-insert the other to be read
% again (since we haven't reached the correct place in the table yet).
% Note that these two last cases are some kind of insertion sort.
%    \begin{macrocode}
         {\pld@AddToPoly\pld@tempoly{#1}%
          \pld@if \pld@InsertItems{#1}{}{#1}\fi
          \def\pld@next{\pld@SubtractPoly@l#2\@empty#3+#4\@empty}}%
        }%
    \fi \fi
    \pld@next}
%    \end{macrocode}
% Finally the macro used to add the rest of the first polynomial.
%    \begin{macrocode}
\def\pld@SubtractPoly@r#1+\relax+\@empty{\pld@AddToPoly\pld@tempoly{#1}}
%    \end{macrocode}
% \end{macro}
%
%
% \subsection{Tweaking the alignment}
%
% Here comes important code for partial output of long divisions.
%
% \begin{macro}{\pld@InsertFake}
% This macro is somewhat like |\pld@InsertItems| but gets a whole line. Thus
% we iterate down each entry and compare its width with the next dimension
% from |\pld@fakeline| (which is the current width of the column). In detail:
% We iterate down each entry and \ldots
%    \begin{macrocode}
\def\pld@InsertFake#1{%
    \let\pld@temp\@empty
    \expandafter\pld@InsertFake@l#1&\relax&}
%    \end{macrocode}
% \ldots\space either append the rest of |\pld@fakeline| or get the next
% dimension from the macro.
%    \begin{macrocode}
\def\pld@InsertFake@l#1&{%
    \ifx\relax#1\@empty
        \pld@Extend\pld@temp{\expandafter&\pld@fakeline}%
        \let\pld@fakeline\pld@temp
    \else
        \expandafter\pld@InsertFake@do\pld@fakeline\relax{#1}%
        \expandafter\pld@InsertFake@l
    \fi}
\def\pld@InsertFake@do#1&#2\relax#3{%
%    \end{macrocode}
% We assign the remaining column dimensions or, if there is no dimension left,
% we insert 0pt.
%    \begin{macrocode}
    \ifx\@empty#2\@empty \def\pld@fakeline{0pt&}%
                   \else \def\pld@fakeline{#2}\fi
    \@tempdima#1\relax
    \setbox\z@=\hbox{\ensuremath{#3}}%
%    \end{macrocode}
% Then we add the maximum of the current dimension and the width of |#3| to
% |\pld@temp| (which will be assigned to |\pld@fakeline| as seen above).
%    \begin{macrocode}
    \ifdim\@tempdima<\wd\z@ \@tempdima=\wd\z@ \fi
    \ifx\pld@temp\@empty
        \edef\pld@temp{\the\@tempdima}%
    \else
        \pld@Extend\pld@temp{\expandafter&\the\@tempdima}%
    \fi}
%    \end{macrocode}
%    \begin{macrocode}
\def\pld@fakeline{0pt&}% init
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@ConvertFake}
% The contents of |\pld@fakeline| are converted into an appropriate sequence
% of |\vrule|\texttt{ height 0pt depth 0pt width }\meta{column dimension}.
% This put inside the |\halign| below will ensure stable column widths.
%    \begin{macrocode}
\def\pld@ConvertFake#1&{%
    \ifx\relax#1\@empty\else
        \ifx\@empty#1\@empty
            &%
        \else
            \noexpand\vrule\noexpand\@height\z@\noexpand\@depth\z@
                           \noexpand\@width#1\relax&%
        \fi
        \expandafter\pld@ConvertFake
    \fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@SplitQuotient}
% splits |\pld@quotient| into the visible |\pld@real| and invisible
% |\pld@shadow|---according to the given |\pld@stage|. We just iterate down
% the summands:
%    \begin{macrocode}
\def\pld@SplitQuotient{%
    \let\pld@real\@empty \let\pld@shadow\empty
    \pld@currstage\pld@stage\relax
    \expandafter\pld@SplitQuotient@\pld@quotient+\relax+}
\def\pld@SplitQuotient@#1+{%
    \ifx\relax#1\@empty
%    \end{macrocode}
% reaching the end, we check whether the remainder needs to be printed;
%    \begin{macrocode}
            \advance\pld@currstage-\tw@
            \ifnum\pld@currstage<\z@
                \let\pld@PrintRemain\pld@XPLD
            \else
                \let\pld@PrintRemain\pld@PLD
            \fi
    \else
%    \end{macrocode}
% otherwise we either add the current summand to |\pld@real| or |\pld@shadow|.
%    \begin{macrocode}
        \ifx\@empty#1\@empty\else
            \advance\pld@currstage-\tw@
            \ifnum\pld@currstage<\z@
                \pld@AddToPoly\pld@shadow{#1}%
            \else
                \pld@AddToPoly\pld@real{#1}%
            \fi
            \advance\pld@currstage\m@ne
        \fi
        \expandafter\pld@SplitQuotient@
    \fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@PrintPolyShadow}
% prints |\pld@real| and leaves space for |\pld@shadow|.
%    \begin{macrocode}
\def\pld@PrintPolyShadow{%
    \pld@firsttrue
    \ifx\pld@real\@empty\else
        \expandafter\pld@PrintMonoms\pld@real+\relax+%
    \fi
    \ifx\pld@shadow\@empty\else
        \setbox\z@\hbox{$\expandafter\pld@PrintMonoms\pld@shadow
                                                     +\relax+$}%
        \phantom{\copy\z@}%
    \fi}
%    \end{macrocode}
% \end{macro}
%
% \subsection{Aligning long division}\label{iAligningLongDivision}
%
% \begin{macro}{\pld@PrintLongDiv}
% does the horizontal alignment. It puts |\pld@allines| into |\halign|.
%    \begin{macrocode}
\def\pld@PrintLongDiv{%
    \ensuremath{\hbox{\vtop{\begingroup
          \offinterlineskip \tabskip=\z@
  \edef\pld@fakeline{\expandafter\pld@ConvertFake\pld@fakeline&\relax&}%
          \halign{\strut\pld@firsttrue\hfil$##$%
                       &\pld@firsttrue\hfil$##$%
                       &&\hfil$##$\cr
                  \pld@fakeline\cr \noalign{\vskip-\normalbaselineskip}%
                  \pld@allines}%
          \endgroup}}}}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@InsertItems}
% Here now we place the monomials. |\pld@pattern| gives the columns in which
% monomials have been put and thus has to be put now. So we first define the
% monomial and look for it in |\pld@pattern|.
%    \begin{macrocode}
\def\pld@InsertItems#1#2#3{%
    \ifx\@empty#1\@empty
    \ifx\@empty#2\@empty \def\pld@monom{#3}%
                   \else \def\pld@monom{#2}\fi
                   \else \def\pld@monom{#1}\fi
    \@tempcnta\@ne \let\pld@recentmonom\@empty
    \expandafter\pld@InsertItems@find\pld@pattern\relax&%
%    \end{macrocode}
% This column |\@tempcnta| must not exceed the current column range, which is
% used to draw the horizontal line: we change the range if necessary.
%    \begin{macrocode}
    \ifnum\pld@firstcol>\@tempcnta \edef\pld@firstcol{\the\@tempcnta}\fi
    \ifnum\pld@lastcol<\@tempcnta \edef\pld@lastcol{\the\@tempcnta}\fi
    \ifnum\pld@maxcol<\@tempcnta \edef\pld@maxcol{\the\@tempcnta}\fi
%    \end{macrocode}
% Finally we insert the arguments.
%    \begin{macrocode}
    \pld@InsertItems@do\pld@lastline{\pld@PLD{#3}}%
    \pld@InsertItems@do\pld@subline{\pld@PLD{#2}}%
    \pld@InsertItems@do\pld@currentline{\pld@PLD{#1}}}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@InsertItems@do}
% For this, we iterate down the specified line |#1|---five items at the same
% time---\ldots
%    \begin{macrocode}
\def\pld@InsertItems@do#1#2{%
    \let\pld@temp\@empty \@tempcntb\@tempcnta
    \expandafter\pld@InsertItems@do@a#1&&&&&\relax{#2}%
    \let#1\pld@temp}
%    \end{macrocode}
% until we've found the item number |\@tempcnta|$=$|\@tempcntb|$-k\cdot 5$.
%    \begin{macrocode}
\def\pld@InsertItems@do@a#1&#2&#3&#4&#5&#6\relax{%
    \ifcase\@tempcntb \or
    \or \pld@AddTo\pld@temp{#1&}%
    \or \pld@AddTo\pld@temp{#1&#2&}%
    \or \pld@AddTo\pld@temp{#1&#2&#3&}%
    \or \pld@AddTo\pld@temp{#1&#2&#3&#4&}%
    \else
%    \end{macrocode}
% If this is not the case, we call this macro again.
%    \begin{macrocode}
        \pld@AddTo\pld@temp{#1&#2&#3&#4&#5&}%
        \advance\@tempcntb-5\relax
        \def\pld@next{\pld@InsertItems@do@a#6&&&&&\relax}%
        \expandafter\@firstoftwo\expandafter\pld@next
    \fi
%    \end{macrocode}
% Otherwise we add the monomial to |\pld@temp|, which is assigned to the
% correct macro above.
%    \begin{macrocode}
    \pld@InsertItems@do@b}
\def\pld@InsertItems@do@b#1{\pld@AddTo\pld@temp{#1}}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@InsertItems@find}
% To find the monomial in |\pld@pattern|, we just test each monomial against
% the defined |\pld@monom|. If we've reached the end of the pattern, we `append'
% (see below) the monomial to the pattern and we're done for.
%    \begin{macrocode}
\def\pld@InsertItems@find#1&{%
    \ifx\relax#1\relax
	    \expandafter\pld@InsertItems@find@fill\pld@recentmonom\pld@V{}0\@empty
    \else
%    \end{macrocode}
% Otherwise we either drop the rest of the pattern since we've found the
% monomial, or we advance the temporary counter and continue.
%    \begin{macrocode}
        \def\pld@recentmonom{#1}%
        \expandafter\pld@IfMonomE\expandafter{\pld@monom}{#1}%
            {\expandafter\pld@InsertItems@find@\expandafter&}%
            {\advance\@tempcnta\@ne \expandafter\pld@InsertItems@find}%
    \fi}
\def\pld@InsertItems@find@#1&\relax&{}
%    \end{macrocode}
% And now for `appending' a monomial to the pattern. Thanks to Karl Heinz
% Marbaise wrong implementation has been replaced by filling in also the
% monomials between the most recent and current monomial---if that wouldn't be
% done, a higher degree monomial could be preceded by a lower degree one and
% thus would never get printed as $x^7$ in |\polylongdiv{x^{15}+1}{x^5+x^3+x+1}|.
%    \begin{macrocode}
\def\pld@InsertItems@find@fill#1\pld@V#2#3#4\@empty{%
    \expandafter\pld@InsertItems@find@fill@\pld@monom\pld@V{}0\@empty{#3}}
\def\pld@InsertItems@find@fill@#1\pld@V#2#3#4\@empty#5{%
    \ifx\pld@pattern\@empty
        \def\pld@pattern{\pld@V&\pld@V{#2}{#3}&}%
        \@tempcnta\tw@
    \else
        \@tempcntb#5\relax
        \loop \ifnum #3<\@tempcntb
            \advance\@tempcnta\@ne
            \advance\@tempcntb\m@ne
            \ifnum\@tempcntb=\z@
                \def\pld@temp{#1}%
            \else
                \edef\pld@temp{\noexpand\pld@V{#2}{\the\@tempcntb}}%
            \fi
            \pld@Extend\pld@pattern{\pld@temp&}%
        \repeat
        \advance\@tempcnta\m@ne
    \fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@ArrangeResult}
% Here the dividend, divisor, and quotient are added to the `|\halign|' data
% macro. First we add a $0$ below the last horizontal rule if the remainder is
% zero.
%    \begin{macrocode}
\def\pld@ArrangeResult#1{%
    \ifx\pld@remainder\@empty
        \@tempcnta\pld@maxcol\relax
        \pld@InsertItems@do\pld@lastline
            {\pld@firsttrue\pld@PLD{\pld@R{0}{1}}}%
    \fi
    \ifnum\pld@currstage>\z@
        \pld@Extend\pld@allines{\pld@lastline\cr}%
    \else
        \pld@InsertFake\pld@lastline
    \fi
%    \end{macrocode}
% We begin to build the first line. For the quotient printed atop, the divisor
% is the first element. Otherwise we either use a left parentheses or just let
% the first element empty. Note that the size of the parentheses is hard-wired.
%    \begin{macrocode}
    \pld@iftopresult
        \def\pld@lastline{\pld@PrintPoly\pld@divisor\bigr)&}%
    \else
        \let\pld@lastline\@empty
        \ifx B\pld@style\else
            \def\pld@lastline{\pld@leftdelim\strut\pld@rightxdelim&}%
        \fi
    \fi
%    \end{macrocode}
% Now we put the monomials of the dividend in the correct columns and split the
% quotient into its visible and invisible part.
%    \begin{macrocode}
    \expandafter\pld@AR@col\expandafter\pld@PLD
                           \expandafter\pld@lastline#1+\relax+%
    \pld@SplitQuotient
%    \end{macrocode}
% For a result at top, we put the quotient into |\pld@currentline| and add a
% horizontal line below it.
%    \begin{macrocode}
    \pld@iftopresult
        \let\pld@currentline\@empty
        \expandafter\pld@AR@col\expandafter\pld@PLD
                               \expandafter\pld@currentline
                                           \pld@quotient+\relax+%
        \expandafter\pld@AR@col\expandafter\pld@XPLD
                               \expandafter\pld@currentline
                                           \pld@shadow+\relax+%
        \edef\pld@subline{%
            \noexpand\cline{\tw@-\pld@maxcol}%
            \noalign{\vskip\jot}}%
        \pld@Extend\pld@currentline{\expandafter\cr\pld@subline}%
    \else
%    \end{macrocode}
% For a result next to the dividend, we first calculate the number of columns
% it spans. It's the maximal column minus the last column of the dividend
% (which is |\@tempcnta|) plus one extra column not to squeeze it all into
% the last column of the `normal' table.
%    \begin{macrocode}
        \@tempcnta-\@tempcnta
        \advance\@tempcnta\pld@maxcol\relax \advance\@tempcnta\@ne
        \edef\pld@span{\the\@tempcnta}%
%    \end{macrocode}
% Then we can add divisor, quotient, and remainder. First we go for style B.
%    \begin{macrocode}
        \ifx B\pld@style
          \pld@AddTo\pld@lastline{%
            &\multispan\pld@span${}=%
            \pld@PrintPolyWithDelims\pld@divisor
            \expandafter\pld@IfSum\expandafter{\pld@divisor}{}{\cdot}%
            \expandafter\pld@IfSum\expandafter{\pld@quotient}\pld@true
                                                             \pld@false
            \pld@if \pld@leftdelim
                    \pld@PrintPolyShadow
                    \pld@rightdelim
              \else \pld@PrintPolyShadow \fi
            \pld@firstfalse
            \expandafter\pld@PrintRemain\expandafter{\pld@remainder}$}%
        \else
%    \end{macrocode}
% And now for style C. Note that we `smash' the depth of the fraction.
%    \begin{macrocode}
          \pld@AddTo\pld@lastline{%
            &\multispan\pld@span$\pld@leftxdelim\strut\pld@rightdelim
            \pld@div
            \pld@PrintPolyWithDelims\pld@divisor=
            \pld@PrintPolyShadow
            \ifx\pld@remainder\@empty\else
                +{}%
                \setbox\z@=\hbox{$\displaystyle
                  \frac{\let\strut\@empty\pld@firsttrue \expandafter
                        \pld@PrintRemain\expandafter{\pld@remainder}}%
                       {\let\strut\@empty\pld@PrintPoly\pld@divisor}$}%
                \dp\z@=\z@\box\z@
            \fi
            $}%
        \fi
    \fi
%    \end{macrocode}
% Eventually we replace the first line in |\pld@allines| by |\pld@lastline|
% or add |\pld@currentline| before doing so.
%    \begin{macrocode}
    \expandafter\pld@AR@\pld@allines\relax}
\def\pld@AR@#1\cr#2\relax{%
    \pld@iftopresult
        \let\pld@allines\pld@currentline
        \pld@AddTo\pld@allines{\pld@lastline\cr #2}%
    \else
        \let\pld@allines\pld@lastline
        \pld@AddTo\pld@allines{\cr #2}%
    \fi}
%    \end{macrocode}
% The dividend and quotient above are built by looking up the position of each
% monomial in |\pld@pattern| and inserting these monomials. |#1|, which is
% |\pld@PLD| or |\pld@XPLD|, is used to print the monomial.
%    \begin{macrocode}
\def\pld@AR@col#1#2#3+{%
    \ifx\relax#3\@empty\else
        \ifx\@empty#3\@empty\else
            \def\pld@monom{#3}\@tempcnta\@ne
            \expandafter\pld@InsertItems@find\pld@pattern\relax&%
            \pld@InsertItems@do#2{#1{#3}}%
        \fi
        \expandafter\pld@AR@col\expandafter#1\expandafter#2%
    \fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@PLD}
% \begin{macro}{\pld@XPLD}
% have been used above several times. They print single monomials in the
% horizontal alignment of a long division or put a |\phantom| around it.
%    \begin{macrocode}
\def\pld@PLD#1{\ifx\@empty#1\@empty\else\pld@PrintMonoms#1+\relax+\fi}
\def\pld@XPLD#1{\phantom{\pld@PLD{#1}}}
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
%
% \section{Euclidean algorithm}
%
% \begin{macro}{\pld@LongEuclideanPoly}
% Assign the `smaller' polynom to |\pld@remainder| and the other to
% |\pld@divisor| by doing one or two divisions. Additionally |\pld@vb| is
% initialized for the case that no further division is needed (v0.15).
%    \begin{macrocode}
\def\pld@LongEuclideanPoly#1#2{%
    \pld@false \let\pld@allines\@empty
    \pld@DivPoly#1#2%
    \ifx\pld@quotient\@empty
        \pld@DivPoly#2#1%
        \pld@InsertEuclidean#2#1%
        \let\pld@vb#1%
    \else
        \pld@InsertEuclidean#1#2%
        \let\pld@vb#2%
    \fi
%    \end{macrocode}
% Now we start the well known Euclidean algorithm. |\pld@va| and |\pld@vb|
% are used as temporary scratch `registers'.
%    \begin{macrocode}
    \pld@LongEuclideanPoly@l}
\def\pld@LongEuclideanPoly@l{%
    \ifx\pld@remainder\@empty \else
        \let\pld@va\pld@divisor
        \let\pld@vb\pld@remainder
%    \end{macrocode}
%    \begin{macrocode}
        \pld@DivPoly\pld@va\pld@vb
        \pld@Simplify\pld@quotient \pld@Simplify\pld@remainder
        \pld@InsertEuclidean\pld@va\pld@vb
%    \end{macrocode}
%    \begin{macrocode}
        \expandafter\pld@LongEuclideanPoly@l
    \fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@InsertEuclidean}
% Each step inserts one line with dividend, divisor, quotient, and remainder.
%    \begin{macrocode}
\def\pld@InsertEuclidean#1#2{%
    \ifx \pld@allines\@empty \else
        \pld@AddTo\pld@allines{\noalign{\vskip\jot}}%
    \fi
    \pld@Extend\pld@allines{\expandafter\pld@PrintPolyArg
                            \expandafter{#1}&}%
    \pld@Extend\pld@allines{\expandafter\pld@PrintPolyWithDelimsArg
                            \expandafter{#2}\hfil\cdot\hfil}%
    \pld@Extend\pld@allines{\expandafter\pld@PrintPolyWithDelimsArg
                            \expandafter{\pld@quotient}&}%
    \pld@Extend\pld@allines{\expandafter\pld@PrintPolyWithDelimsArg
                            \expandafter{\pld@remainder}\cr}}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@PrintLongEuclidean}
% just like |\pld@PrintLongDiv|.
%    \begin{macrocode}
\def\pld@PrintLongEuclidean{
    \ensuremath{\hbox{\vtop{\begingroup
          \offinterlineskip \tabskip=\z@
          \halign{\strut\pld@firsttrue\hfil$##$%
                  &${}={}$\hfil$##$\hfil
                  &${}+##$\hfil\cr \pld@allines}%
          \endgroup}}}}
%    \end{macrocode}
% \end{macro}
%
%
% \section{Factorization}
%
% The algorithm is based on the following proposition:
% All \emph{rational} zeros of a polynomial $a_nX^n+\ldots+a_1X+a_0$ with
% \emph{integer} coefficients are among the fractions $\pm\frac\beta\alpha$
% where $\beta$ is a divisor of $a_0$ and $\alpha$ a divisor of the leading
% coefficient $a_n$.
% So our first tasks are to iterate through divisors and to test for zeros.
%
% \begin{macro}{\pld@NextDivisorPair}
% \marg{integer $a$}\marg{integer $b$}
% \begin{describe}
% |\@tempcnta| and |\@tempcntb| get the next divisors of \meta{integer $a$}
% and \meta{integer $b$}. |\pld@if| is set false if and only if all divisor
% pairs has been iterated through. At the beginning we must initialize
% |\@tempcnta=\z@| and |\@tempcntb=\@ne|.
% \end{describe}
% First |\@tempcnta| becomes the next divisor of |#1| and then |\@tempcntb|
% the next one of |#2| if and only if |#1| has no more divisors (which resets
% |\@tempcnta| automatically).
%    \begin{macrocode}
\def\pld@NextDivisorPair#1#2{%
    \pld@NextDivisor\@tempcnta{#1}%
    \pld@if\else
        \pld@NextDivisor\@tempcntb{#2}%
    \fi}
%    \end{macrocode}
% Here we advance the counter by one until the counter gets too big (note that
% this `$>$' requires the arguments to |\pld@NextDivisorPair| being positive)
% \ldots
%    \begin{macrocode}
\def\pld@NextDivisor#1#2{%
    \advance#1\@ne
    \ifnum #1>#2\relax
        #1\@ne \pld@false
        \expandafter\@gobbletwo
    \else
%    \end{macrocode}
% or a divisor of |#2|.
%    \begin{macrocode}
        \@multicnt #2\relax
        \divide\@multicnt#1\multiply\@multicnt#1%
        \advance\@multicnt-#2\relax
        \ifnum \@multicnt=\z@
            \pld@true
            \expandafter\expandafter\expandafter\@gobbletwo
        \else
            \expandafter\expandafter\expandafter\pld@NextDivisor
        \fi
    \fi
    #1{#2}}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@FindZeros}
% \marg{integer $a$}\marg{integer $b$}
% \begin{describe}
% is the main loop: while not all divisor pairs has been processed, we check
% whether $\pm$|\@tempcntb|$/$|\@tempcnta| is a zero.
% \end{describe}
%    \begin{macrocode}
\def\pld@FindZeros#1#2{%
    \pld@NextDivisorPair{#1}{#2}%
    \pld@if
        \pld@CheckZeros
        \def\pld@next{\pld@FindZeros{#1}{#2}}%
        \expandafter\pld@next
    \fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@CheckZeros}
% When $\frac\beta\alpha$ isn't a zero any more, we add the zero with
% multiplicity |\@multicnt| \ldots
%    \begin{macrocode}
\def\pld@CheckZeros{%
    \pld@true \@multicnt\z@
    \loop \pld@if
        \pld@CheckZero{\the\@tempcnta}{\the\@tempcntb}%
    \repeat
    \pld@AddRationalZero{\the\@tempcnta}{\the\@tempcntb}%
%    \end{macrocode}
% and do the same for $-\frac\beta\alpha$. Note that the multiplicity might be
% zero.
%    \begin{macrocode}
    \pld@true \@multicnt\z@
    \loop \pld@if
        \pld@CheckZero{-\the\@tempcnta}{\the\@tempcntb}%
    \repeat
    \pld@AddRationalZero{-\the\@tempcnta}{\the\@tempcntb}}
%    \end{macrocode}
% To check for the zero $\frac\beta\alpha$, we divide |\pld@current| by the
% linear factor $X-\frac\beta\alpha$. Note that |\pld@tempoly| contains the
% string |\pld@V{X}1| where |X| is replaced by the actual variable; so we just
% need to append the fraction.
%    \begin{macrocode}
\def\pld@CheckZero#1#2{%
    \begingroup
      \edef\pld@temp{{-#2}{#1}}%
      \pld@Extend\pld@tempoly{\expandafter+\expandafter\pld@R\pld@temp}%
      \let\pld@stage\maxdimen \pld@DividePoly\pld@current\pld@tempoly
      \ifx\pld@remainder\@empty
          \global\let\@gtempa\pld@quotient
          \aftergroup\pld@true
      \else
          \aftergroup\pld@false
      \fi
    \endgroup
%    \end{macrocode}
% If the division was successful, we advance the multiplicity and assign the
% new polynomial.
%    \begin{macrocode}
    \pld@if
        \advance\@multicnt\@ne
        \let\pld@current\@gtempa
    \fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@AddRationalZero}
% Here we add code to |\pld@allines| to \emph{print} the factor with its
% multiplicity.
%    \begin{macrocode}
\def\pld@AddRationalZero#1#2{%
    \ifnum\@multicnt=\z@\else
        \pld@AccuSetX{#2}{-#1}%
        \pld@AccuGet\pld@temp
        \edef\pld@temp{\noexpand\pld@R\pld@temp}%
%    \end{macrocode}
% Yet |\pld@temp| contains the rational. Note that the `accumulator detour' is
% needed to get rid of |\@tempcnta| and |b|. Eventually append the zero with
% the exponent if necessary.
%    \begin{macrocode}
        \expandafter\pld@AddZero\expandafter{\pld@temp}%
        \ifnum\@multicnt=\@ne\else
            \edef\pld@temp{^{\the\@multicnt}}%
            \pld@Extend\pld@allines\pld@temp
        \fi
    \fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@AddZero}
% We add |\pld@leftdelim| |\pld@firsttrue| |\pld@PLD{X+#1}| |\pld@rightdelim|
% to the current factorization |\pld@allines|.
%    \begin{macrocode}
\def\pld@AddZero#1{%
    \pld@Extend\pld@allines{\expandafter\pld@leftdelim
                            \expandafter\pld@firsttrue
                            \expandafter\pld@PLD
                            \expandafter{\pld@tempoly+#1}%
                            \pld@rightdelim}}
%    \end{macrocode}
% \end{macro}
%
% These are the basic definitions. Now remember that the proposition above
% requires integers coefficients, but we want to support rationals. To do
% this, we multiply the polynomial virtually by the least common multiple of
% all denominators. `Virtually' means that we only multiply the leading
% coefficient and the absolute term to get the correct divisors, but not the
% real polynomial.
%
% \begin{macro}{\pld@FactorizeInit}
% And this is done here. The argument is a definition to be executed with
% appropriate data (the multiplied coeffients) as arguments at the end of this
% macro. Again we redefine |\pld@R|,\ldots,|\pld@V| and iterate through the
% monomials. The accumulator holds the least common multiple and |\@multicnt|
% the least exponent of the variable (since we need to divide by $X^k$ to get
% an absolute term).
%    \begin{macrocode}
\def\pld@FactorizeInit#1{%
    \begingroup
      \pld@firsttrue \let\pld@sub\@empty
      \pld@AccuSetX11%
      \let\pld@R\pld@FRational
      \let\pld@F\@gobbletwo
      \let\pld@S\@gobbletwo
      \let\pld@V\pld@FVar
      \expandafter\pld@FactorizeInit@\pld@current+\relax+%
%    \end{macrocode}
% Below you'll see |\@gtemp| $=$ leading coeffients and |\pld@lastline| $=$
% coefficient of absolute term (after division by $X^k$). Here we multiply by
% the accumulator and make the results positive (if we're advised to do this)
% and \ldots
%    \begin{macrocode}
      \pld@if
          \pld@AccuGet\pld@temp
          \expandafter\pld@AccuMul\@gtempa
          \pld@AccuIfNegative{\pld@AccuNegate}{}%
          \pld@AccuGet\pld@va
          \expandafter\pld@AccuSetX\pld@temp
          \expandafter\pld@AccuMul\pld@lastline
          \pld@AccuIfNegative{\pld@AccuNegate}{}%
          \pld@AccuGet\pld@vb
      \else
          \let\pld@va\@gtempa
          \let\pld@vb\pld@lastline
      \fi
%    \end{macrocode}
% set the coefficient of $X^1$ if necessary---or any other variable power 1.
%    \begin{macrocode}
      \ifx\pld@sub\@empty \def\pld@sub{01}\fi
%    \end{macrocode}
% Then we prepare the arguments for the macro to be executed at the end. In
% particular, |\pld@tempoly| is defined to define |\def\pld@tempoly{\pld@V{X}}|
% below, and this definition is cared out before we execute the macro |#2|.
%    \begin{macrocode}
      \edef\pld@temp{\noexpand#1\pld@va\pld@vb{\the\@multicnt}\pld@sub}%
      \pld@Extend\pld@tempoly{\pld@temp}%
      \global\let\@gtempa\pld@tempoly
    \endgroup
    \@gtempa}
%    \end{macrocode}
% The submacro just iterates down the monomials.
%    \begin{macrocode}
\def\pld@FactorizeInit@#1+{%
    \ifx\relax#1\else
        \def\pld@lastline{11}%
        #1%
        \expandafter\pld@FactorizeInit@
    \fi}
%    \end{macrocode}
% The following two definitions store the leading coefficient in |\@gtempa|,
% the last in |\pld@lastline|, the coefficient of $X^1$ in |\pld@sub|, update
% the least common multiple, \ldots
%    \begin{macrocode}
\def\pld@FRational#1#2{%
    \def\pld@lastline{{#1}{#2}}%
    \pld@iffirst
        \global\let\@gtempa\pld@lastline
        \def\pld@tempoly{\@multicnt\z@}%
    \fi
    \pld@LCM{#2}%
    \@multicnt\z@}
%    \end{macrocode}
% and save the variable and its `leading' exponent in |\@multicnt|. Note that
% these two definitions are cared out later on, and the assignment of
% |\@multicnt| here saves the exponent of the last monomial.
%    \begin{macrocode}
\def\pld@FVar#1#2{%
    \pld@iffirst
        \pld@firstfalse
        \global\let\@gtempa\pld@lastline
        \def\pld@tempoly{\def\pld@tempoly{\pld@V{#1}}%
                         \@multicnt#2\relax}%
    \fi
    \@multicnt#2\relax
%    \end{macrocode}
%    \begin{macrocode}
    \ifnum\@multicnt=\@ne
        \let\pld@sub\pld@lastline
    \fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@Factorize}
% If the given polynomial is zero, the factorization is `$0$'. Otherwise we
% initialize data and start the algorithm. Note that |\pld@Factorize@| is an
% argument to |\pld@FactorizeInit| and called from inside with appropriate
% arguments.
%    \begin{macrocode}
\def\pld@Factorize#1{%
    \ifx\@empty#1\@empty
        \def\pld@allines{\pld@PrintPolyWithDelims\@empty}%
    \else
        \let\pld@allines\@empty
        \let\pld@current#1%
        \pld@true \pld@FactorizeInit
        \pld@Factorize@
    \fi}
%    \end{macrocode}
% Now the arguments are
%   |#1#2|$=$\meta{`leading coefficient'},
%   |#3#4|$=$\meta{`coefficient of least monomial'},
%   |#5|$=$\meta{least exponent},
%   |#6#7|$=$\meta{coefficient of linear summand}.
% Here the first two coefficient have been multiplied by the least common
% multiple of all denominators. The factorization gets `variable power |#5|'
% and the current polynomial is divided this.
%    \begin{macrocode}
\def\pld@Factorize@#1#2#3#4#5#6#7{%
    \ifnum #5=\z@\else
        \pld@Extend\pld@allines{\expandafter\pld@firsttrue
                                \expandafter\pld@PLD
                                \expandafter{\pld@tempoly{#5}}}%
        \let\pld@va\pld@tempoly
        \pld@AddTo\pld@va{{-#5}}%
        \pld@MultiplyPoly\pld@current\pld@current\pld@va
    \fi
%    \end{macrocode}
% Then we initialize the variable's exponent and the two divisors and really
% start the algorithm.
%    \begin{macrocode}
    \pld@AddTo\pld@tempoly{1}%
    \@tempcnta\z@ \@tempcntb\@ne
    \pld@FindZeros{#1}{#3}%
%    \end{macrocode}
% Eventually we scan the remaining polynomial without multiplying the
% coefficient by the least common multiple of the denominators.
%    \begin{macrocode}
    \pld@false \pld@FactorizeInit
    \pld@FactorizeFinal}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@FactorizeFinal}
% Thus we might find nonrational zeros here. Let $a={}$|#1#2|, $b={}$|#6#7|,
% and $c={}$|#3#4|. Then we have to calculate
%   $\frac b{2a}\pm\sqrt{\frac{b^2}{4a^2}-\frac ca}$.
%    \begin{macrocode}
\def\pld@FactorizeFinal#1#2#3#4#5#6#7{%
    \ifnum\@multicnt=\tw@
        \pld@AddTo\pld@tempoly{1}%
        \pld@AccuSetX{#6}{#7}%
        \pld@AccuIfZero{\let\pld@va\@empty}%
                       {\pld@AccuMul12%
                        \pld@AccuMul{#2}{#1}%
                        \pld@AccuGet\pld@sub
                        \edef\pld@va{\noexpand\pld@R\pld@sub+}%
%    \end{macrocode}
% That's $\frac b{2a}$ so far, stored away in |\pld@va|.
%    \begin{macrocode}
                        \expandafter\pld@AccuMul\pld@sub}%
        \begingroup
          \pld@AccuSetX{#3}{#4}%
          \pld@AccuMul{-#2}{#1}%
          \pld@AccuGet\pld@temp
          \global\let\@gtempa\pld@temp
        \endgroup
        \expandafter\pld@AccuAdd\@gtempa
%    \end{macrocode}
% And now the accumulator holds $\frac{b^2}{4a^2}-\frac ca$. Depending on the
% sign---complex zeros are not supported, even though the complex analysis was
% my field of activity for some years---we do nothing more or get a printable
% version of the square root and \ldots
%    \begin{macrocode}
        \pld@AccuIfNegative
        {\@multicnt\tw@}%
        {\pld@AccuGet\pld@temp
         \expandafter\pld@FDefSqrt\pld@temp
%    \end{macrocode}
% append two nonrational zeros.
%    \begin{macrocode}
         \let\pld@vb\pld@va
         \pld@AddTo\pld@vb{\pld@R{-1}1}%
         \pld@Extend\pld@va{\pld@temp}%
         \pld@Extend\pld@vb{\pld@temp}%
         \expandafter\pld@AddZero\expandafter{\pld@va}%
         \expandafter\pld@AddZero\expandafter{\pld@vb}%
         \@multicnt\z@
        }%
    \fi
%    \end{macrocode}
% In this latter case or if the polynomial's degree has been zero from the
% beginning of this macro, we check whether we can omit the leading coeffient.
%    \begin{macrocode}
    \ifnum\@multicnt=\z@
         \pld@AccuSetX{#1}{#2}%
         \pld@AccuIfOne{\let\pld@current\@empty}%
                       {\def\pld@current{\pld@R{#1}{#2}}}%
    \fi
    \ifx\pld@current\@empty\else
        \let\pld@temp\pld@allines
        \def\pld@allines{\pld@PrintPolyWithDelims\pld@current}%
        \pld@Extend\pld@allines{\pld@temp}%
    \fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@FDefSqrt}
% Finally we need a printable version of the square root of |#1|$/$|#2|.
% We use the fact, that the root is not rational, thus only one of nominator
% and denominator can be a square. Depending on the actual numbers, the
% submacro defines |\pld@temp| correctly. Note that this submacro is used to
% make the code more readable.
%    \begin{macrocode}
\def\pld@FDefSqrt#1#2{%
    \pld@IfSquare{#1}%
    {\pld@FDefSqrt@{\pld@R{\pld@temp}1}%
                   {\sqrt{\noexpand\pld@R{#2}1}}}%
    {\pld@IfSquare{#2}%
     {\ifnum\pld@temp=\@ne
          \pld@FDefSqrt@{\sqrt{\noexpand\pld@R{#1}1}}{}%
      \else
          \pld@FDefSqrt@{\sqrt{\noexpand\pld@R{#1}1}}%
                        {\pld@R{\pld@temp}1}%
      \fi}%
     {\def\pld@temp{\pld@F{\sqrt{\pld@R{#1}{#2}}}{}}}%
    }}
%    \end{macrocode}
% It just (e)defines a general fraction without expanding some control
% sequences.
%    \begin{macrocode}
\def\pld@FDefSqrt@#1#2{%
    \edef\pld@temp{\noexpand\pld@F
                   {\noexpand#1}%
                   {\ifx\@empty#2\@empty\else \noexpand#2\fi}}}
%    \end{macrocode}
% \end{macro}
%
%
% \section{Arithmetic}
%
% \begin{macro}{\pld@IfSquare}
% Let's begin with the macro used in the last section. As always, we initialize
% data.
%    \begin{macrocode}
\def\pld@IfSquare#1{%
    \@tempcnta=#1\relax
    \@multicnt\@tempcnta \@tempcntb\@tempcnta
    \divide\@tempcntb\tw@ \advance\@tempcntb\@ne
%    \end{macrocode}
% Then we use the iteration
%   $x_{n+1}=\left\lfloor \frac12\left(a+\lfloor\frac a{x_n}\rfloor\right)
%            \right\rfloor$
% to calculate $\lfloor \sqrt{|#1|}\rfloor$. In version 0.11 there was a bug
% in the loop condition.
%    \begin{macrocode}
    \loop \ifnum\@tempcntb<\@multicnt
        \@multicnt\@tempcntb
        \@tempcntb\@tempcnta
        \divide\@tempcntb\@multicnt
        \advance\@tempcntb\@multicnt
        \divide\@tempcntb\tw@
    \repeat
%    \end{macrocode}
% Now it is easy to decide whether |#1| is a square.
%    \begin{macrocode}
    \edef\pld@temp{\the\@multicnt}%
    \multiply\@multicnt\@multicnt
    \ifnum \@multicnt=\@tempcnta
        \expandafter\@firstoftwo
    \else
        \expandafter\@secondoftwo
    \fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@Euclidean}
% \begin{macro}{\pld@XEuclidean}
% \meta{macro}\marg{integer $a$}\marg{integer $b$}
% \begin{describe}
% The base of our rational arithmetic is the Euclidean algorithm. The contents
% of \meta{macro} becomes |{|$\frac a{\gcd(a,b)}$|}{|$\frac b{\gcd(a,b)}$|}|
% in the first case. The eXtended version adds the greatest common divisor:
% |{|$\frac a{\gcd(a,b)}$|}{|$\frac b{\gcd(a,b)}$|}{|$\gcd(a,b)$|}|.
% \end{describe}
% As described, the second version extends the first definition.
%    \begin{macrocode}
\def\pld@XEuclidean#1#2#3{\pld@Euclidean#1{#2}{#3}%
                          \edef#1{#1{\the\@tempcntb}}}
%    \end{macrocode}
% Here we assign the number smaller in size (in fact not bigger) to
% |\@tempcnta| and the other to |\@tempcntb|, and make both nonnegative.
%    \begin{macrocode}
\def\pld@Euclidean#1#2#3{%
   \@tempcnta#2\relax \divide\@tempcnta#3\relax
   \ifnum\@tempcnta=\z@ \@tempcnta#2\relax \@tempcntb#3\relax
                  \else \@tempcnta#3\relax \@tempcntb#2\relax \fi
   \ifnum\@tempcnta<\z@ \@tempcnta -\@tempcnta \fi
   \ifnum\@tempcntb<\z@ \@tempcntb -\@tempcntb \fi
%    \end{macrocode}
% The loop leaves the greatest common divisor in |\@tempcntb|.
%    \begin{macrocode}
   \pld@Euclidean@l
%    \end{macrocode}
% Now we only have to divide the numbers and define the macro |#1|.
%    \begin{macrocode}
   \@tempcnta#3\relax \divide\@tempcnta\@tempcntb
   \edef#1{{\the\@tempcnta}}%
   \@tempcnta#2\relax \divide\@tempcnta\@tempcntb
   \edef#1{{\the\@tempcnta}#1}}
%    \end{macrocode}
% And here is the usual Euclidean algorithm.\footnote{Note that
% \texttt{\bslash @multicnt} is used as a third scratch counter.}
%    \begin{macrocode}
\def\pld@Euclidean@l{%
   \ifnum\@tempcnta=\z@\else
       \@multicnt\@tempcntb
       \divide\@tempcntb\@tempcnta
       \multiply\@tempcntb\@tempcnta
       \advance\@multicnt -\@tempcntb
       \@tempcntb\@tempcnta
       \@tempcnta\@multicnt
       \expandafter\pld@Euclidean@l
   \fi}
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\pld@AccuGet}
% A rational number is stored as \marg{nominator}\marg{denominator} in
% the accumulator |\pld@accu|. Here we ensure that the denominator is
% positive.
%    \begin{macrocode}
\def\pld@AccuGet{\expandafter\pld@AccuGet@\pld@accu}
\def\pld@AccuGet@#1#2#3{%
    \ifnum #2<\z@ \edef#3{{-#1}{-#2}}\else\edef#3{{#1}{#2}}\fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@AccuSet}
% \begin{macro}{\pld@AccuSetX}
% Setting the accumulator is also simple. We divide the nominator and
% denominator by their greatest common divisor only in the first case.
%    \begin{macrocode}
\def\pld@AccuSet#1#2{%
    \def\pld@accu{{#1}{#2}}%
    \expandafter\pld@Euclidean\expandafter\pld@accu\pld@accu
    \expandafter\pld@AccuGet@\pld@accu\pld@accu}
\def\pld@AccuSetX#1#2{\pld@AccuGet@{#1}{#2}\pld@accu}
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\pld@AccuPrint}
% Here we typeset the rational via |\frac| only if necessary.
%    \begin{macrocode}
\def\pld@AccuPrint{\expandafter\pld@AccuPrint@\pld@accu}
\def\pld@AccuPrint@#1#2{%
    \ifnum #2=\@ne \number#1\else \frac{\number#1}{\number#2}\fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@AccuNegate}
% We just negate the nominator.
%    \begin{macrocode}
\def\pld@AccuNegate{\expandafter\pld@AccuNegate@\pld@accu}
\def\pld@AccuNegate@#1#2{\def\pld@accu{{-#1}{#2}}}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@AccuIfZero}
% \begin{macro}{\pld@AccuIfOne}
% \begin{macro}{\pld@AccuIfAbsOne}
% \begin{macro}{\pld@AccuIfNegative}
% All these definitions work the same way: expand |\pld@accu|, do the test,
% and either execute the first \meta{then} or the second \meta{else} part.
%    \begin{macrocode}
\def\pld@AccuIfZero{\expandafter\pld@AccuIfZero@\pld@accu}
\def\pld@AccuIfZero@#1#2{%
    \ifnum #1=\z@ \expandafter\@firstoftwo
            \else \expandafter\@secondoftwo \fi}
%    \end{macrocode}
%    \begin{macrocode}
\def\pld@AccuIfOne{\expandafter\pld@AccuIfOne@\pld@accu}
\def\pld@AccuIfOne@#1#2{%
    \ifnum #1=#2\relax \expandafter\@firstoftwo
                 \else \expandafter\@secondoftwo \fi}
%    \end{macrocode}
%    \begin{macrocode}
\def\pld@AccuIfAbsOne{\expandafter\pld@AccuIfAbsOne@\pld@accu}
\def\pld@AccuIfAbsOne@#1#2{%
    \ifnum #1=#2\relax \expandafter\@firstoftwo \else
        \ifnum -#1=#2\relax
            \expandafter\expandafter\expandafter\@firstoftwo
        \else
            \expandafter\expandafter\expandafter\@secondoftwo
        \fi
    \fi}
%    \end{macrocode}
%    \begin{macrocode}
\def\pld@AccuIfNegative{\expandafter\pld@AccuIfNegative@\pld@accu}
\def\pld@AccuIfNegative@#1#2{%
    \ifnum #1<\z@ \@tempcnta\m@ne \else \@tempcnta\@ne \fi
    \ifnum #2<\z@ \@tempcnta -\@tempcnta \fi
    \ifnum \@tempcnta<\z@ \expandafter\@firstoftwo
                    \else \expandafter\@secondoftwo \fi}
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \begin{macro}{\pld@LCM}
% \marg{integer}
% \begin{describe}
% puts the least common multiple of \meta{integer} and \meta{nominator} into
% the accumulator.
% \end{describe}
% We use $\mathop{\mathrm{lcm}}(a,b)=\frac{a\cdot b}{\gcd(a,b)}=
% \frac{|\#1|}{\gcd(|\#1|,|\#3|)}\cdot |#3|$.
%    \begin{macrocode}
\def\pld@LCM{\expandafter\pld@LCM@\pld@accu}
\def\pld@LCM@#1#2#3{%
    \pld@Euclidean\pld@accu{#1}{#3}%
    \@tempcnta\expandafter\@firstoftwo\pld@accu\relax
    \multiply\@tempcnta#3\relax
    \edef\pld@accu{{\the\@tempcnta}1}}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@AccuMul}
% We use the Euclidean algorithm before \ldots
%    \begin{macrocode}
\def\pld@AccuMul{\expandafter\pld@AccuMul@\pld@accu}
\def\pld@AccuMul@#1#2#3#4{%
    \begingroup
      \pld@Euclidean\pld@va{#1}{#4}%
      \pld@Euclidean\pld@vb{#3}{#2}%
      \pld@ExpandTwo\pld@AccuMul@m\pld@va\pld@vb
      \xdef\@gtempa{{\the\@tempcnta}{\the\@tempcntb}}%
    \endgroup
    \let\pld@accu\@gtempa}
%    \end{macrocode}
% we multiply nominators and denominators.
%    \begin{macrocode}
\def\pld@AccuMul@m#1#2#3#4{%
    \@tempcnta#1\relax \multiply\@tempcnta#3\relax
    \@tempcntb#2\relax \multiply\@tempcntb#4\relax}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pld@AccuAdd}
% The addition of two rationals is the most interesting part in this section.
% It is based upon the fact that $\frac ab+\frac cd=\frac{ad+bc}{bd}$ has
% \begin{eqnarray*}
% \meta{nominator}&=&\left(\textstyle\frac a{\gcd(a,c)}\cdot\frac d{\gcd(b,d)}+\frac b{\gcd(b,d)}\cdot\frac c{\gcd(a,c)}\right)\cdot\gcd(a,c),\\
% \meta{denominator}&=&\frac{bd}{\gcd(b,d)},
% \end{eqnarray*}
% where the factors and sums are all integers and potentially smaller in size
% than in $\frac{ad+bc}{db}$. As one quickly verifies\footnote{Sorry for that
% phrase, I'm a mathematician $:\!-)$}, the nominator and denominator has the
% greatest common divisor
%    \[\gcd(-\cdot-,b)\cdot\gcd\left(\textstyle-\cdot-,\frac d{\gcd(b,d)}\right),\]
% where $-\cdot-$ stands for the big parenthesized sum of the nominator.
%^^A The greatest common divisor is even \[\gcd(-\cdot-,b)\gcd(-\cdot-,d)\),
%^^A but we don't need either of this explicitly, the Euclidean algorithm will
%^^A take care of this.
%
% The implementation again expands |\pld@accu|, \ldots
%    \begin{macrocode}
\def\pld@AccuAdd{\expandafter\pld@AccuAdd@a\pld@accu}
%    \end{macrocode}
% and provides another submacro with the necessary fractions.
%    \begin{macrocode}
\def\pld@AccuAdd@a#1#2#3#4{%
    \ifnum#3=\z@\else
        \pld@AccuAdd@c{#1}{#2}{#3}{#4}%
    \fi}
\def\pld@AccuAdd@c#1#2#3#4{%
    \begingroup
      \pld@XEuclidean\pld@va{#1}{#3}%
      \pld@XEuclidean\pld@vb{#2}{#4}%
      \edef\pld@va{\pld@va\pld@vb}%
      \expandafter\pld@AccuAdd@b\pld@va{#2}{#4}}
%    \end{macrocode}
% We now have
% \begin{eqnarray*}
% \meta{nominator}&=&\left(|#1|\cdot|#5|+|#4|\cdot|#2|\right)\cdot |#3|,\\
% \meta{denominator}&=&|#7|\cdot|#5|.
% \end{eqnarray*}
%    \begin{macrocode}
\def\pld@AccuAdd@b#1#2#3#4#5#6#7#8{%
    \endgroup
    \@tempcnta#1\relax \multiply\@tempcnta#5\relax
    \@tempcntb#2\relax \multiply\@tempcntb#4\relax
    \advance\@tempcnta\@tempcntb
%    \end{macrocode}
% Finally we divide by $\gcd(-\cdot-,b)$ and multiply with
% $\frac{|\#3|}{|\#5|}$, which implicitly divides the result by
% $\gcd\left(-\cdot-,\frac d{\gcd(b,d)}\right)$.
%    \begin{macrocode}
    \expandafter\pld@Euclidean\expandafter\pld@accu\expandafter
        {\the\@tempcnta}{#7}%
    \pld@AccuMul{#3}{#5}}
%    \end{macrocode}
% \end{macro}
%
%
% \section{Horner's scheme}
%
% The following code lines come without comments. Good luck!
%
%    \begin{macrocode}
\renewcommand\polyset[1]{%
    \ifx\@empty#1\@empty\else
        \let\pld@KVsplit@saved\KV@split
        \let\KV@split\pld@KVsplit
        \setkeys{pld}{#1}%
        \let\KV@split\pld@KVsplit@saved
    \fi}
\def\pld@KVsplit#1=#2=#3\relax{%
  \KV@@sp@def\@tempa{#1}%
  \ifx\@tempa\@empty\else
    \expandafter\let\expandafter\@tempc
      \csname\KV@prefix\@tempa\endcsname
    \ifx\@tempc\relax
      \expandafter\pld@IfVar\expandafter{\@tempa}%
        {\pld@GetPoly{\pld@polya}{}{#2}%
         \ifx\pld@polya\@empty \def\pld@polya{\pld@R 01}\fi
         \expandafter\let\csname pld@value@\@tempa\endcsname\pld@polya}%
        {\KV@errx{\@tempa\space undefined}}%
    \else
      \ifx\@empty#3\@empty
        \KV@default
      \else
        \KV@@sp@def\@tempb{#2}%
        \expandafter\@tempc\expandafter{\@tempb}\relax
      \fi
    \fi
  \fi}
%    \end{macrocode}
%    \begin{macrocode}
\def\pld@KVCases#1#2#3{%
    \@ifundefined{pld@#1@#2}%
    {\PackageError{Polynom}{Unknown value #2}{Try #3.}}%
    {\csname pld@#1@#2\endcsname}}
\def\pld@KVIf#1#2{%
    \@ifundefined{if#2}%
    {\PackageError{Polynom}{Unknown value #2}{Try `true' or `false'.}}%
    {\expandafter\let\expandafter#1\csname if#2\endcsname}}
%    \end{macrocode}
%    \begin{macrocode}
\define@key{pld}{showbase}[middle]{\pld@KVCases{showbase}{#1}{`false', `top', `middle', or `bottom'}}%
\def\pld@showbase@false{\let\pld@basepos=f}
\def\pld@showbase@top{\let\pld@basepos=t}
\def\pld@showbase@middle{\let\pld@basepos=m}
\def\pld@showbase@bottom{\let\pld@basepos=b}
\define@key{pld}{showvar}[true]{\pld@KVIf\pld@ifshowvar{#1}}
\define@key{pld}{showbasesep}[true]{\pld@KVIf\pld@ifshowbasesep{#1}}
\define@key{pld}{showmiddlerow}[true]{\pld@KVIf\pld@ifshowmiddlerow{#1}}

\define@key{pld}{resultstyle}{\def\pld@resultstyle{#1}}
\define@key{pld}{resultleftrule}[true]{\pld@KVIf\pld@ifhornerresultleftrule{#1}}
\define@key{pld}{resultrightrule}[true]{\pld@KVIf\pld@ifhornerresultrightrule{#1}}
\define@key{pld}{resultbottomrule}[true]{\pld@KVIf\pld@ifhornerresultbottomrule{#1}}

\define@key{pld}{tutor}[true]{\pld@KVCases{tutor}{#1}{`true', or `false'}}%
\def\pld@tutor@true{\let\pld@iftutor\iftrue}
\def\pld@tutor@false{\let\pld@iftutor\iffalse}
\define@key{pld}{tutorstyle}{\def\pld@tutorstyle{#1}}
\define@key{pld}{tutorlimit}{\@tempcnta#1\relax \advance\@tempcnta\@ne
    \edef\pld@tutorlimit{\the\@tempcnta}}

\define@key{pld}{equalcolwidths}[true]{\pld@KVIf\pld@ifhornerequalcolwidths{#1}}
\define@key{pld}{arraycolsep}{\def\pld@hornerarraycolsep{#1\relax}}
\define@key{pld}{arrayrowsep}{\def\pld@hornerarrayrowsep{#1\relax}}

\polyset{showbase,
         showvar=false,
         showbasesep=true,
         showmiddlerow=true,
         tutor=false,
         tutorlimit=1,
         tutorstyle=\scriptscriptstyle,
         resultstyle=,
         resultleftrule=false,
         resultrightrule=false,
         resultbottomrule=false,
         equalcolwidths=true,
         arraycolsep=\arraycolsep,
         arrayrowsep=.5\arraycolsep}

\define@key{pld}{mul}{\def\pld@mul{#1}}%
\define@key{pld}{plusface}{\pld@KVCases{hornerplusface}{#1}{`left' or 'right'}}%
\define@key{pld}{plusyoffset}{\@tempdima#1\relax \edef\pld@hornerplusyoffset{\the\@tempdima}}
\define@key{pld}{downarrowxoffset}{\@tempdima#1\relax \edef\pld@hornerdownarrowxoffset{\the\@tempdima}}
\define@key{pld}{diagarrowxoffset}{\@tempdima#1\relax \edef\pld@hornerdiagarrowxoffset{\the\@tempdima}}
\define@key{pld}{downarrow}{\def\pld@hornerdownarrow{#1}}
\define@key{pld}{diagarrow}{\def\pld@hornerdiagarrow{#1}}
\def\pld@hornerplusface@left{\let\pld@hornerplusface\llap}
\def\pld@hornerplusface@right{\let\pld@hornerplusface\rlap}
\polyset{mul=\cdot,
         plusface=right,
         plusyoffset=\z@,
         downarrowxoffset=\z@,
         diagarrowxoffset=\z@,
         downarrow={\vector(0,-1){2.5}},
         diagarrow={\vector(2,1){1.6}}}
%    \end{macrocode}
%    \begin{macrocode}
\newcommand*\polyhornerscheme[1][]{%
    \begingroup
    \let\pld@stage\maxdimen \polyset{#1}%
    \pld@GetPoly{\pld@polya}%
                {\expandafter\pld@Horner\expandafter{\pld@polya}%
    \endgroup \ignorespaces}}

\def\pld@Horner#1{%
    \pld@GetTotalDegree\pld@degree{#1}%
    \pld@Horner@#1++%
    \pld@ArrangeHorner}

\def\pld@Horner@#1+{%
    \pld@SplitMonom\pld@HornerInit{#1}%
    \pld@HornerIterate}

\def\pld@HornerIterate#1+{%
    \advance\@tempcnta\m@ne
    \ifx\@empty#1\@empty
        \ifnum \@tempcnta<\z@
            \let\pld@next\@empty
        \else
            \pld@HornerStep{\pld@R01}{}%
            \def\pld@next{\pld@HornerIterate+}%
        \fi
    \else
        \pld@GetTotalDegree\pld@degree{#1}%
        \ifnum \pld@degree=\@tempcnta
            \pld@SplitMonom\pld@HornerStep{#1}%
            \let\pld@next\pld@HornerIterate
        \else
            \pld@HornerStep{\pld@R01}{}%
            \def\pld@next{\pld@HornerIterate#1+}%
        \fi
    \fi
    \pld@next}

\def\pld@HornerStep#1#2{%
    \pld@AddTo\pld@lastline{&\pld@PrintPolyArg{#1}}%
    \pld@MultiplyPoly\pld@lastsum\pld@lastsum\pld@value
    \pld@Simplify\pld@lastsum
    \ifx\pld@lastsum\@empty \def\pld@lastsum{\pld@R 01}\fi
    \pld@AddTo\pld@subline{&}%
    \pld@HornerExtendLine\pld@subline
    \pld@AddTo\pld@lastsum{+#1}%
    \pld@Simplify\pld@lastsum
    \pld@AddTo\pld@currentline{&}%
    \pld@iftutor
        \pld@HornerExtendCurrentLine
        \advance\@multicnt\@ne
        \pld@HornerIfTutorStage{\pld@HornerExtendTutor\pld@HornerOtherDown}%
        \advance\@multicnt\m@ne
        \ifnum\@tempcnta>\z@
            \pld@HornerIfTutorStage{\pld@HornerExtendTutor\pld@HornerDiag}%
        \fi
    \else
        \pld@HornerExtendCurrentLine
    \fi}

\def\pld@HornerExtendTutor#1{%
    \ifnum\@tempcnta=\z@ \pld@AddTo\pld@hornerresult#1%
                   \else \pld@AddTo\pld@currentline#1\fi}
\def\pld@HornerExtendCurrentLine{%
    \ifnum\@tempcnta=\z@
        \let\pld@hornerresult\@empty
        \pld@Extend\pld@hornerresult{\expandafter{\expandafter\pld@resultstyle\expandafter{%
                                     \expandafter\pld@PrintPolyArg\expandafter{\pld@lastsum}}}}%
        \pld@HornerIfStage{}%
                          {\let\pld@lastsum\@empty
                           \pld@Extend\pld@lastsum{\expandafter\phantom\expandafter{\pld@hornerresult}}%
                           \let\pld@hornerresult\pld@lastsum}%
        \expandafter\@gobbletwo
    \fi
    \pld@HornerExtendLine\pld@currentline}
\def\pld@HornerExtendLine#1{%
    \pld@HornerIfStage{\pld@Extend#1{\expandafter\pld@PrintPolyArg\expandafter{\pld@lastsum}}}%
                      {\pld@Extend#1{\expandafter\phantom\expandafter{%
                                     \expandafter\pld@PrintPolyArg\expandafter{\pld@lastsum}}}}%
}

\def\pld@HornerFirstDown{%
    \rlap{\kern\pld@hornerdownarrowxoffset\relax
          \unitlength\ht\@arstrutbox
          \begin{picture}(0,0)%
          \setbox\z@\hbox{$\pld@tutorstyle{\pld@hornerdownarrow}$}%
          \put(0,.5){\raise\ht\z@\hbox{\raise\dp\z@\copy\z@}}%
          \end{picture}}}
\def\pld@HornerOtherDown{%
    \pld@HornerFirstDown
    \pld@hornerplusface{\kern\pld@hornerdownarrowxoffset\relax
                        \smash{\raise\pld@hornerplusyoffset
                               \hbox{\raise.5\ht\@arstrutbox
                                     \vbox to 2.5\ht\@arstrutbox
                                     {\vss$\pld@tutorstyle{+}$\vss}}}}}
\def\pld@HornerDiag{%
    \rlap{\kern\pld@hornerdiagarrowxoffset\relax
        \unitlength\ht\@arstrutbox
        \begin{picture}(0,0)%
        \setbox\z@\hbox{$\pld@tutorstyle{\pld@hornerdiagarrow}$}%
        \put(0,.5){\box\z@}%
        \put(0,.5){\kern.55\ht\@arstrutbox
                   $\pld@tutorstyle{\pld@mul \pld@hornerleftdelim
                                    \pld@PrintPolyWithDelims\pld@value
                                    \pld@hornerrightdelim}$}%
        \end{picture}}}

\def\pld@HornerIfStage{%
    \advance\@multicnt\m@ne
    \ifnum\@multicnt>\z@ \expandafter\@firstoftwo
                   \else \expandafter\@secondoftwo \fi}
\def\pld@HornerIfTutorStage{%
    \ifnum\@multicnt>\@ne
        \ifnum\@multicnt>\pld@tutorlimit
            \expandafter\expandafter\expandafter\@gobble
        \else
            \expandafter\expandafter\expandafter\@firstofone
        \fi
    \else
        \expandafter\@gobble
    \fi}

\def\pld@HornerInit#1#2{%
    \let\pld@V\@firstoftwo
    \ifx\@empty#2\@empty\else
        \edef\pld@var{#2}%
        \@ifundefined{pld@value@\pld@var}%
        {\PackageError{Polynom}{Missing value for variable \pld@var}{}%
         \@namedef{pld@value@\pld@var}{\pld@R01}}%
        {}%
        \expandafter\let\expandafter\pld@value\csname pld@value@\pld@var\endcsname
    \fi
%
    \setbox\@tempboxa\hbox{$\pld@PrintPoly\pld@value$}%
    \pld@ifminus
        \let\pld@hornerleftdelim(%
        \let\pld@hornerrightdelim)%
    \else
        \let\pld@hornerleftdelim\@empty
        \let\pld@hornerrightdelim\@empty
    \fi
%
    \@multicnt\pld@stage\relax
    \@tempcnta\pld@degree\relax
    \def\pld@lastline{\pld@PrintPolyArg{#1}}%
    \let\pld@subline\@empty
    \let\pld@currentline\@empty
    \def\pld@lastsum{#1}%
    \pld@iftutor
        \pld@HornerExtendCurrentLine
        \advance\@multicnt\@ne
        \pld@HornerIfTutorStage{\pld@AddTo\pld@currentline\pld@HornerFirstDown}%
        \advance\@multicnt\m@ne
        \ifnum\@tempcnta>\z@
            \pld@HornerIfTutorStage{\pld@AddTo\pld@currentline\pld@HornerDiag}%
        \fi
    \else
        \pld@HornerExtendCurrentLine
    \fi
    \def\pld@lastsum{#1}%
    \@tempcnta\pld@degree\relax % init moved up, delete this?
    \advance\@tempcnta\thr@@
    \edef\pld@hornermaxcol{\the\@tempcnta}%
    \@tempcnta\pld@degree\relax}
%    \end{macrocode}
%    \begin{macrocode}
\def\pld@ArrangeHorner{%
    \begingroup
    \@tempdima\z@
    \pld@MeasureCells\pld@lastline
    \pld@MeasureCells\pld@subline
    \pld@MeasureCells\pld@currentline
    \pld@MeasureCells\pld@hornerresult
    \everycr{}\tabskip\z@skip
    \@tempdimb\ht\strutbox \advance\@tempdimb\pld@hornerarrayrowsep
    \@tempdimc\dp\strutbox \advance\@tempdimc\pld@hornerarrayrowsep
    \setbox\@arstrutbox\hbox{\vrule \@height\@tempdimb
                                    \@depth\@tempdimc
                                    \@width\z@}%
    \pld@ifhornerequalcolwidths\else
        \def\@startpbox##1{\hfil\vtop\bgroup \hbox\bgroup \@arrayparboxrestore}%
        \def\@endpbox{\@finalstrut\@arstrutbox \egroup\par\egroup}%
    \fi
    \def\pld@leftdelim{(}\def\pld@rightdelim{)}%
    \leavevmode
    \hbox{$\vcenter{\offinterlineskip \arraycolsep\pld@hornerarraycolsep
        \halign{\@arstrut
                \hskip\arraycolsep \hfill\ensuremath{##}\hskip\arraycolsep
              &##&&%
                \hskip\arraycolsep \@startpbox\@tempdima\hfill\ensuremath{##}\@endpbox \hskip\arraycolsep\cr
                \pld@ShowBase t&\pld@ifshowbasesep\vrule\fi&\pld@lastline\cr
                \pld@ifshowmiddlerow \pld@ShowBase m&\pld@ifshowbasesep\vrule\fi&\pld@subline\cr \fi \cline{2-\pld@hornermaxcol}%
                \pld@ShowBase b&&\pld@currentline\omit
                \pld@ifhornerresultleftrule \vrule \fi
                \hskip\arraycolsep \@startpbox\@tempdima\relax\hfill\ensuremath{\pld@hornerresult}\@endpbox \hskip\arraycolsep
                \pld@ifhornerresultrightrule \vrule \fi \cr
                \pld@ifhornerresultbottomrule \cline{\pld@hornermaxcol-\pld@hornermaxcol} \fi
               }%
    }$}%
    \endgroup}
%    \end{macrocode}
%    \begin{macrocode}
\def\pld@ShowBase#1{%
    \ifx#1\pld@basepos
        \pld@ifshowvar x=\fi\pld@PrintPoly\pld@value
    \fi}
%    \end{macrocode}
%    \begin{macrocode}
\def\pld@MeasureCells#1{\expandafter\pld@MeasureCells@#1&\@nil&}
\def\pld@MeasureCells@#1&{%
    \ifx\@nil#1\relax\else
        \setbox\@tempboxa\hbox{\ensuremath{#1}}%
        \ifdim\wd\@tempboxa>\@tempdima
            \@tempdima\wd\@tempboxa
        \fi
        \expandafter\pld@MeasureCells@
    \fi}
%    \end{macrocode}
%    \begin{macrocode}
\def\pld@GetTotalDegree#1#2{%
    \begingroup
    \let\pld@R\@gobbletwo \let\pld@F\@gobbletwo \let\pld@S\@gobbletwo
    \def\pld@V##1##2{\advance\@tempcnta##2\relax}%
    \def#1##1+##2\@nil{##1}%
    \edef#1{\@tempcnta\z@#1#2+\@nil}%
    #1\xdef\@gtempa{\the\@tempcnta}%
    \endgroup
    \let#1\@gtempa}
%    \end{macrocode}
%
%    \begin{macrocode}
%</package>
%    \end{macrocode}
%
%
% \begingroup\small
% \section{History}
% \renewcommand\labelitemi{--}
% \begin{itemize}
% \item[0.1] from 2000/04/18 (private test version)
%   \item long division algorithm et al, basic scanner, basic simplification
% \item[0.11] from 2001/03/23
%   \item total reimplementation except division algorithm et al
%   \item improved: scanner, simplification, handling of symbols
%   \item new: gcd, factorization, rational arithmetic, key $=$ value interface
% \item[0.12] from 2001/04/11
%   \item bugs in |\pld@IfSquare| and |\pld@ScanOpen| removed
%   \item slightly improved scanner (|^| on expressions) and new key \texttt{delims}
% \item[0.13] from 2001/09/27
%   \item new \texttt{stage} key allows stepwise printing of polynomial long divisions
% \item[0.14] from 2002/01/10
%   \item added \texttt{style=C}; this led to the new \texttt{div} key and the optional argument of \texttt{delims}
% \item[0.15] from 2002/10/29
%   \item bugs fixed in |\polygcd| and |\pld@LongEuclideanPoly|
% \item[0.16] from 2004/08/12
%   \item added (bugfixed version of) Horner's scheme and fixed bug in |\pld@InsertItems@find|
% \end{itemize}
% The phrase `et al' stands for the definitions directly related to the
% division algorithm: polynomial multiplication, |\pld@IfNeedsDivision|,
% subtraction, and alignment.
% \medskip
%
% \noindent TODO:
% \begin{itemize}
%   \item PBZ
%   \item use \texttt{stage} also on \cs{polylonggcd}
%   \item possibility to highlight the most recent \texttt{stage}
%   \item remove problems inside array and tabular
%   \item carry out dependencies in the implementation part (or remove them)
%   \item internal data format: introduce linear, square factors?
%   \item generalize exponents for printing $y^{(4)}-y^{(2)}+\ldots$ ?
%   \item define derivatives?
% \end{itemize}
% \endgroup
%
%
% \Finale
%
%%
%%
\endinput