% \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\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\relax{%
\ifcase\@tempcntb \or
\or \pld@AddTo\pld@temp{#1&}%
\or \pld@AddTo\pld@temp{#1&}%
\or \pld@AddTo\pld@temp{#1&}%
\or \pld@AddTo\pld@temp{#1&}%
\else
% \end{macrocode}
% If this is not the case, we call this macro again.
% \begin{macrocode}
\pld@AddTo\pld@temp{#1&}%
\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