From e0c6872cf40896c7be36b11dcc744620f10adf1d Mon Sep 17 00:00:00 2001 From: Norbert Preining Date: Mon, 2 Sep 2019 13:46:59 +0900 Subject: Initial commit --- macros/latex/contrib/polynom/README | 11 + macros/latex/contrib/polynom/polydemo.pdf | Bin 0 -> 146225 bytes macros/latex/contrib/polynom/polydemo.tex | 107 + macros/latex/contrib/polynom/polynom.dtx | 3792 +++++++++++++++++++++++++++++ macros/latex/contrib/polynom/polynom.ins | 44 + macros/latex/contrib/polynom/polynom.pdf | Bin 0 -> 338333 bytes 6 files changed, 3954 insertions(+) create mode 100644 macros/latex/contrib/polynom/README create mode 100644 macros/latex/contrib/polynom/polydemo.pdf create mode 100644 macros/latex/contrib/polynom/polydemo.tex create mode 100644 macros/latex/contrib/polynom/polynom.dtx create mode 100644 macros/latex/contrib/polynom/polynom.ins create mode 100644 macros/latex/contrib/polynom/polynom.pdf (limited to 'macros/latex/contrib/polynom') diff --git a/macros/latex/contrib/polynom/README b/macros/latex/contrib/polynom/README new file mode 100644 index 0000000000..e36a0a14c6 --- /dev/null +++ b/macros/latex/contrib/polynom/README @@ -0,0 +1,11 @@ +Polynom package +Copyright 2000-2017 Carsten Heinz, Hendri Adriaens +Released under the LaTeX Project Public License 1.3 or later + +The polynom package implements macros for manipulating +polynomials. For example, it can typeset polynomial long +divisions and synthetic divisions (Horner's scheme). The +main test case and application is the polynomial ring in +one variable with rational coefficients. +Please note that this is work in progress. Multivariate +polynomials are currently not supported. diff --git a/macros/latex/contrib/polynom/polydemo.pdf b/macros/latex/contrib/polynom/polydemo.pdf new file mode 100644 index 0000000000..7e75c1b391 Binary files /dev/null and b/macros/latex/contrib/polynom/polydemo.pdf differ diff --git a/macros/latex/contrib/polynom/polydemo.tex b/macros/latex/contrib/polynom/polydemo.tex new file mode 100644 index 0000000000..972fc768c7 --- /dev/null +++ b/macros/latex/contrib/polynom/polydemo.tex @@ -0,0 +1,107 @@ +% +% This file is copyright 2004 Carsten Heinz. +% +% This file may be distributed and/or modified under the conditions +% of the LaTeX Project Public License, either version 1.3 of this +% license or (at your option) any later version. +% The latest version of this license is in +% http://www.latex-project.org/lppl.txt +% and version 1.3 or later is part of all distributions of LaTeX +% version 2003/12/01 or later. +% +\documentclass[12pt]{article} +\pagestyle{empty} + +\usepackage{geometry,hyperref,color,polynom} +\geometry{screen} +\hypersetup{pdfpagemode=FullScreen} + +%%%%%%%%%%%%% +% +% \tokentotext{} +% converts token sequence into a \texttt-printable form. +% +%%%%%%%%%%%%% +\makeatletter % We'll use three internal LaTeX definitions +\newcommand\tokentotext[2]{% + \def#1{#2}% + \edef#1{\expandafter\strip@prefix\meaning#1}% + \edef#1{\expandafter\zap@space#1 \@empty}} +\makeatother + + +\newcounter{currentstage} +%%%%%%%%%%%%% +% +% \dopolylongdiv{}{}{}{} +% +%%%%%%%%%%%%% +\newcommand\dopolylongdiv[4]{% + \begingroup + \tokentotext\keyvaluetext{#4}% + \polyset{#4}% + \setcounter{currentstage}{#2}\addtocounter{currentstage}{-1}% + % + \loop \ifnum \value{currentstage}<#3\relax + \addtocounter{currentstage}{1}% + \newpage + \section*{\strut#1}\section*{\strut\texttt{\keyvaluetext}}% + \[\polylongdiv[stage=\value{currentstage}]{x^3+x^2-1}{x+2}\] + \repeat + \endgroup} +%%%%%%%%%%%%% +% +% \dopolyhornerscheme{}{}{}{} +% +%%%%%%%%%%%%% +\newcommand\dopolyhornerscheme[4]{% similar to \dopolylongdiv + \begingroup + \tokentotext\keyvaluetext{#4}% + \polyset{#4}% + \setcounter{currentstage}{#2}\addtocounter{currentstage}{-1}% + % + \loop \ifnum \value{currentstage}<#3\relax + \addtocounter{currentstage}{1}% + \newpage + \section*{\strut#1}\section*{\strut\texttt{\keyvaluetext}}% + \[\polyhornerscheme[x=-2,stage=\value{currentstage}]{x^3+x^2-1}\] + \repeat + \endgroup} + +%%%%%%%%%%%%% +% +% T H E D O C U M E N T +% +%%%%%%%%%%%%% +\begin{document} + +\LARGE + +\dopolylongdiv{Polynomial long division -- Stages 1 to 10}{1}{10} + {} + +\dopolylongdiv{Polynomial long division -- Stages 1 to 11}{1}{11} + {style=B} + +\dopolylongdiv{Polynomial long division -- Stages 1 to 11}{1}{11} + {style=C} + +\dopolylongdiv{Polynomial long division -- Stages 1 to 11}{1}{11} + {style=D} + +\dopolyhornerscheme{Horner's scheme -- Stages 1 to 8}{1}{8} + {} + +\dopolyhornerscheme{Horner's scheme -- Stages 1 to 8}{1}{8} + {tutor=true,resultstyle=\color{blue}} + +\dopolyhornerscheme{Horner's scheme -- Rule the result}{8}{8} + {resultbottomrule,resultleftrule,resultrightrule} + +\dopolyhornerscheme{Horner's scheme -- Stages 1 to 8}{1}{8} + {tutor=true,tutorlimit=3} + +\dopolyhornerscheme{Horner's scheme: Some more options}{8}{8} + {showbase=top,showbasesep=false} + +\end{document} diff --git a/macros/latex/contrib/polynom/polynom.dtx b/macros/latex/contrib/polynom/polynom.dtx new file mode 100644 index 0000000000..c85ba214fa --- /dev/null +++ b/macros/latex/contrib/polynom/polynom.dtx @@ -0,0 +1,3792 @@ +% \iffalse +% +% The files polynom.dtx and polynom.ins and all files generated +% from these two files are referred to as `this work'. +% +% This work is copyright 2000-2017 Carsten Heinz, Hendri Adriaens. +% +% This work may be distributed and/or modified under the conditions +% of the LaTeX Project Public License, either version 1.3 of this +% license or (at your option) any later version. +% The latest version of this license is in +% http://www.latex-project.org/lppl.txt +% and version 1.3 or later is part of all distributions of LaTeX +% version 2003/12/01 or later. +% +% This work has the LPPL maintenance status "maintained". +% +% The Current Maintainer of this work is Hendri Adriaens. +% +%<*driver> +\documentclass{ltxdoc} +\usepackage{hyperref,polynom} + +\DisableCrossrefs +\OnlyDescription + +\begin{document} + \DocInput{polynom.dtx} +\end{document} +% +% \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= \cdot +% plusface=left|right right +% plusyoffset= 0pt +% +% downarrow= {\vector(0,-1){2.5}} +% diagarrow= {\vector(2,1){1.6}} +% downarrowxoffset= 0pt +% diagarrowxoffset= 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} +% +% \end{macrocode} +% +% +% \begingroup\small +% \section{History} +% \renewcommand\labelitemi{--} +% \begin{itemize} +% \item[0.1] from 2000/04/18 (private test version) +% \item long division algorithm et al, basic scanner, basic simplification +% \item[0.11] from 2001/03/23 +% \item total reimplementation except division algorithm et al +% \item improved: scanner, simplification, handling of symbols +% \item new: gcd, factorization, rational arithmetic, key $=$ value interface +% \item[0.12] from 2001/04/11 +% \item bugs in |\pld@IfSquare| and |\pld@ScanOpen| removed +% \item slightly improved scanner (|^| on expressions) and new key \texttt{delims} +% \item[0.13] from 2001/09/27 +% \item new \texttt{stage} key allows stepwise printing of polynomial long divisions +% \item[0.14] from 2002/01/10 +% \item added \texttt{style=C}; this led to the new \texttt{div} key and the optional argument of \texttt{delims} +% \item[0.15] from 2002/10/29 +% \item bugs fixed in |\polygcd| and |\pld@LongEuclideanPoly| +% \item[0.16] from 2004/08/12 +% \item added (bugfixed version of) Horner's scheme and fixed bug in |\pld@InsertItems@find| +% \end{itemize} +% The phrase `et al' stands for the definitions directly related to the +% division algorithm: polynomial multiplication, |\pld@IfNeedsDivision|, +% subtraction, and alignment. +% \medskip +% +% \noindent TODO: +% \begin{itemize} +% \item PBZ +% \item use \texttt{stage} also on \cs{polylonggcd} +% \item possibility to highlight the most recent \texttt{stage} +% \item remove problems inside array and tabular +% \item carry out dependencies in the implementation part (or remove them) +% \item internal data format: introduce linear, square factors? +% \item generalize exponents for printing $y^{(4)}-y^{(2)}+\ldots$ ? +% \item define derivatives? +% \end{itemize} +% \endgroup +% +% +% \Finale +% +%% +%% +\endinput diff --git a/macros/latex/contrib/polynom/polynom.ins b/macros/latex/contrib/polynom/polynom.ins new file mode 100644 index 0000000000..0ff74c5b3b --- /dev/null +++ b/macros/latex/contrib/polynom/polynom.ins @@ -0,0 +1,44 @@ +%% +%% This file generates all files required to use the polynom package. +%% At your command prompt write +%% +%% tex polynom.ins +%% +\input docstrip +\preamble + +The files polynom.dtx and polynom.ins and all files generated +from these two files are referred to as `this work'. + +This work is copyright 2000-2017 Carsten Heinz, Hendri Adriaens. + +This work may be distributed and/or modified under the conditions +of the LaTeX Project Public License, either version 1.3 of this +license or (at your option) any later version. +The latest version of this license is in + http://www.latex-project.org/lppl.txt +and version 1.3 or later is part of all distributions of LaTeX +version 2003/12/01 or later. + +This work has the LPPL maintenance status "maintained". + +The Current Maintainer of this work is Hendri Adriaens. + +\endpreamble + + +\usedir{tex/latex/polynom} +\keepsilent +\generate{\file{polynom.sty}{\from{polynom.dtx}{package}}} + + +\Msg{**} +\Msg{** Now read the short software license at the beginning} +\Msg{** of `polynom.{dtx,ins,sty}'. Run `polynom.dtx' through} +\Msg{** LaTeX2e to get the user's guide.} +\Msg{**} +\Msg{** You probably need to move the file `polynom.sty' into} +\Msg{** a directory searched by TeX.} +\Msg{**} + +\endbatchfile diff --git a/macros/latex/contrib/polynom/polynom.pdf b/macros/latex/contrib/polynom/polynom.pdf new file mode 100644 index 0000000000..a045eba366 Binary files /dev/null and b/macros/latex/contrib/polynom/polynom.pdf differ -- cgit v1.2.3