summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/polynom
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
committerNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
commite0c6872cf40896c7be36b11dcc744620f10adf1d (patch)
tree60335e10d2f4354b0674ec22d7b53f0f8abee672 /macros/latex/contrib/polynom
Initial commit
Diffstat (limited to 'macros/latex/contrib/polynom')
-rw-r--r--macros/latex/contrib/polynom/README11
-rw-r--r--macros/latex/contrib/polynom/polydemo.pdfbin0 -> 146225 bytes
-rw-r--r--macros/latex/contrib/polynom/polydemo.tex107
-rw-r--r--macros/latex/contrib/polynom/polynom.dtx3792
-rw-r--r--macros/latex/contrib/polynom/polynom.ins44
-rw-r--r--macros/latex/contrib/polynom/polynom.pdfbin0 -> 338333 bytes
6 files changed, 3954 insertions, 0 deletions
diff --git a/macros/latex/contrib/polynom/README b/macros/latex/contrib/polynom/README
new file mode 100644
index 0000000000..e36a0a14c6
--- /dev/null
+++ b/macros/latex/contrib/polynom/README
@@ -0,0 +1,11 @@
+Polynom package
+Copyright 2000-2017 Carsten Heinz, Hendri Adriaens
+Released under the LaTeX Project Public License 1.3 or later
+
+The polynom package implements macros for manipulating
+polynomials. For example, it can typeset polynomial long
+divisions and synthetic divisions (Horner's scheme). The
+main test case and application is the polynomial ring in
+one variable with rational coefficients.
+Please note that this is work in progress. Multivariate
+polynomials are currently not supported.
diff --git a/macros/latex/contrib/polynom/polydemo.pdf b/macros/latex/contrib/polynom/polydemo.pdf
new file mode 100644
index 0000000000..7e75c1b391
--- /dev/null
+++ b/macros/latex/contrib/polynom/polydemo.pdf
Binary files differ
diff --git a/macros/latex/contrib/polynom/polydemo.tex b/macros/latex/contrib/polynom/polydemo.tex
new file mode 100644
index 0000000000..972fc768c7
--- /dev/null
+++ b/macros/latex/contrib/polynom/polydemo.tex
@@ -0,0 +1,107 @@
+%
+% This file is copyright 2004 Carsten Heinz.
+%
+% This file 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.
+%
+\documentclass[12pt]{article}
+\pagestyle{empty}
+
+\usepackage{geometry,hyperref,color,polynom}
+\geometry{screen}
+\hypersetup{pdfpagemode=FullScreen}
+
+%%%%%%%%%%%%%
+%
+% \tokentotext<csname>{<tokens>}
+% converts token sequence into a \texttt-printable form.
+%
+%%%%%%%%%%%%%
+\makeatletter % We'll use three internal LaTeX definitions
+\newcommand\tokentotext[2]{%
+ \def#1{#2}%
+ \edef#1{\expandafter\strip@prefix\meaning#1}%
+ \edef#1{\expandafter\zap@space#1 \@empty}}
+\makeatother
+
+
+\newcounter{currentstage}
+%%%%%%%%%%%%%
+%
+% \dopolylongdiv{<page title>}{<loop min>}{<loop max>}{<key=value list for \polyset>}
+%
+%%%%%%%%%%%%%
+\newcommand\dopolylongdiv[4]{%
+ \begingroup
+ \tokentotext\keyvaluetext{#4}%
+ \polyset{#4}%
+ \setcounter{currentstage}{#2}\addtocounter{currentstage}{-1}%
+ %
+ \loop \ifnum \value{currentstage}<#3\relax
+ \addtocounter{currentstage}{1}%
+ \newpage
+ \section*{\strut#1}\section*{\strut\texttt{\keyvaluetext}}%
+ \[\polylongdiv[stage=\value{currentstage}]{x^3+x^2-1}{x+2}\]
+ \repeat
+ \endgroup}
+%%%%%%%%%%%%%
+%
+% \dopolyhornerscheme{<page title>}{<loop min>}{<loop max>}{<key=value list for \polyset>}
+%
+%%%%%%%%%%%%%
+\newcommand\dopolyhornerscheme[4]{% similar to \dopolylongdiv
+ \begingroup
+ \tokentotext\keyvaluetext{#4}%
+ \polyset{#4}%
+ \setcounter{currentstage}{#2}\addtocounter{currentstage}{-1}%
+ %
+ \loop \ifnum \value{currentstage}<#3\relax
+ \addtocounter{currentstage}{1}%
+ \newpage
+ \section*{\strut#1}\section*{\strut\texttt{\keyvaluetext}}%
+ \[\polyhornerscheme[x=-2,stage=\value{currentstage}]{x^3+x^2-1}\]
+ \repeat
+ \endgroup}
+
+%%%%%%%%%%%%%
+%
+% T H E D O C U M E N T
+%
+%%%%%%%%%%%%%
+\begin{document}
+
+\LARGE
+
+\dopolylongdiv{Polynomial long division -- Stages 1 to 10}{1}{10}
+ {}
+
+\dopolylongdiv{Polynomial long division -- Stages 1 to 11}{1}{11}
+ {style=B}
+
+\dopolylongdiv{Polynomial long division -- Stages 1 to 11}{1}{11}
+ {style=C}
+
+\dopolylongdiv{Polynomial long division -- Stages 1 to 11}{1}{11}
+ {style=D}
+
+\dopolyhornerscheme{Horner's scheme -- Stages 1 to 8}{1}{8}
+ {}
+
+\dopolyhornerscheme{Horner's scheme -- Stages 1 to 8}{1}{8}
+ {tutor=true,resultstyle=\color{blue}}
+
+\dopolyhornerscheme{Horner's scheme -- Rule the result}{8}{8}
+ {resultbottomrule,resultleftrule,resultrightrule}
+
+\dopolyhornerscheme{Horner's scheme -- Stages 1 to 8}{1}{8}
+ {tutor=true,tutorlimit=3}
+
+\dopolyhornerscheme{Horner's scheme: Some more options}{8}{8}
+ {showbase=top,showbasesep=false}
+
+\end{document}
diff --git a/macros/latex/contrib/polynom/polynom.dtx b/macros/latex/contrib/polynom/polynom.dtx
new file mode 100644
index 0000000000..c85ba214fa
--- /dev/null
+++ b/macros/latex/contrib/polynom/polynom.dtx
@@ -0,0 +1,3792 @@
+% \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-2017 Carsten Heinz, Hendri Adriaens.
+%
+% 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 Hendri Adriaens.
+%
+%<*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--2017\\ Carsten Heinz \texttt{<\,cheinz@gmx.de\,>}, Hendri Adriaens}
+% \date{2017/07/17\enspace Version 0.19\\ \box\abstractbox}
+% \maketitle
+% \section{Preface}
+%
+%Because Carsten Heinz could not be reached anymore for a long time,
+%this package has been taken over according to the LPPL for
+%maintenance by Hendri Adriaens. This package was using and
+%redefining internals of the \packagename{keyval} package and hence
+%it was incompatible with \packagename{xkeyval}. This problem has
+%been solved and the processing of the \texttt{vars} key has been
+%simplified. All following text is the original by Carsten Heinz.
+%\hfill\emph{Hendri Adriaens, 2006/04/20}\\
+%We thank Walter Daems for providing the \texttt D style.\hfill\emph{2016/12/09}\\
+%And Hendrik Vogt for providing a bug fix on \texttt{\textbackslash polylongdiv}.\hfill\emph{2017/07/17}
+%
+% \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$\vert$D}
+% & 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{4500}
+%
+%
+% \section{Preliminaries}
+%
+% Let's start with identification.
+% \begin{macrocode}
+%<*package>
+\NeedsTeXFormat{LaTeX2e}
+\ProvidesPackage{polynom}[2017/07/17 0.19 (CH,HA)]
+% \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]
+\def\polyset{\setkeys{pld}}
+% \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}
+% \end{macro}
+% The key iterates down the tokens and expands the list, making a new
+% key for every variable.
+% \begin{macrocode}
+\define@key{pld}{vars}{%
+ \let\pld@variables\@empty
+ \@tfor\pld@temp:=#1\do{%
+ \pld@Extend\pld@variables{\expandafter,\pld@temp}%
+ \edef\pld@temp{%
+ \noexpand\define@key{pld}{\pld@temp}%
+ {\noexpand\pld@GetValue{\pld@temp}{####1}}%
+ }%
+ \pld@temp
+ }%
+}
+% \end{macrocode}
+% \begin{macro}{\pld@GetValue}
+% Helper macro to retrieve the value of a variable.
+% \begin{macrocode}
+\def\pld@GetValue#1#2{%
+ \pld@GetPoly{\pld@polya}{}{#2}%
+ \ifx\pld@polya\@empty\def\pld@polya{\pld@R 01}\fi
+ \expandafter\let\csname pld@value@#1\endcsname\pld@polya
+}
+% \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' or `D'.}}%
+ {\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
+\let\pld@styleD\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. We use an if to use the fix by Hendrik Vogt only inside this macro.
+% \begin{macrocode}
+\newif\ifpld@InsidePolylongdiv
+\newcommand*\polylongdiv[1][]{%
+ \begingroup\pld@InsidePolylongdivtrue
+ \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@
+ \let\pld@maxcolplustwo\z@ \let\pld@linepos\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}%
+ {\ifpld@InsidePolylongdiv\expandafter\pld@insert@remainder
+ \pld@last@remainder+\relax\relax\fi}%
+ \fi}
+% \end{macrocode}
+% The fix by Hendrik Vogt.
+% \begin{macrocode}
+\def\pld@insert@remainder#1+#2\relax{%
+ \ifx\relax#1\relax\else\pld@InsertItems\@empty\@empty{#1}\fi
+ \ifx\relax#2\relax\else\pld@insert@remainder#2\relax\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
+ \let\pld@last@remainder\@empty
+ \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}%
+ \def\pld@last@remainder{#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}
+ \@tempcntb\pld@maxcol\relax\advance\@tempcntb\tw@
+ \edef\pld@maxcolplustwo{\the\@tempcntb}
+ \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 C\pld@style
+ \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}%
+ \@tempcntb\pld@maxcol\relax\advance\@tempcntb\pld@span%
+ \advance\@tempcntb\@ne%
+ \edef\pld@linepos{\the\@tempcntb}%
+% \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}
+ \if C\pld@style
+ \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
+ $}%
+ \else
+% \end{macrocode}
+% Finally, style D.
+% \begin{macrocode}
+ \pld@AddTo\pld@lastline{%
+ \cr%
+ \noalign{\vskip-\normalbaselineskip}%
+ \multispan\pld@maxcol~&~&\multispan\pld@span${}\vrule~%
+ \pld@PrintPoly\pld@divisor\hfil\hfil$\cr%
+ \cline{\pld@maxcolplustwo-\pld@linepos}%
+ \multispan\pld@maxcol~&~&\multispan\pld@span${}\vrule height
+ 2.25ex~\pld@PrintPolyShadow$\hfil\cr\noalign{\vskip-2\normalbaselineskip}}%
+ \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}
+\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
diff --git a/macros/latex/contrib/polynom/polynom.ins b/macros/latex/contrib/polynom/polynom.ins
new file mode 100644
index 0000000000..0ff74c5b3b
--- /dev/null
+++ b/macros/latex/contrib/polynom/polynom.ins
@@ -0,0 +1,44 @@
+%%
+%% This file generates all files required to use the polynom package.
+%% At your command prompt write
+%%
+%% tex polynom.ins
+%%
+\input docstrip
+\preamble
+
+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-2017 Carsten Heinz, Hendri Adriaens.
+
+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 Hendri Adriaens.
+
+\endpreamble
+
+
+\usedir{tex/latex/polynom}
+\keepsilent
+\generate{\file{polynom.sty}{\from{polynom.dtx}{package}}}
+
+
+\Msg{**}
+\Msg{** Now read the short software license at the beginning}
+\Msg{** of `polynom.{dtx,ins,sty}'. Run `polynom.dtx' through}
+\Msg{** LaTeX2e to get the user's guide.}
+\Msg{**}
+\Msg{** You probably need to move the file `polynom.sty' into}
+\Msg{** a directory searched by TeX.}
+\Msg{**}
+
+\endbatchfile
diff --git a/macros/latex/contrib/polynom/polynom.pdf b/macros/latex/contrib/polynom/polynom.pdf
new file mode 100644
index 0000000000..a045eba366
--- /dev/null
+++ b/macros/latex/contrib/polynom/polynom.pdf
Binary files differ