polexpr (12jan18)

git-svn-id: svn://tug.org/texlive/trunk@46291 c570f23f-e606-0410-a88d-b1316a301751

1 files changed, 373 insertions, 0 deletions

diff --git a/Master/texmf-dist/doc/latex/polexpr/README b/Master/texmf-dist/doc/latex/polexpr/README
new file mode 100644
index 00000000000..a258011f9dd
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/polexpr/README
@@ -0,0 +1,373 @@
+-*- fill-column: 72; mode: text; -*-
+
+Package polexpr
+===============
+
+License
+-------
+
+Copyright (C) 2018 Jean-Francois Burnol
+
+See documentation of package xint for contact information.
+
+This Work may be distributed and/or modified under the
+conditions of the LaTeX Project Public License version 1.3c.
+This version of this license is in
+
+  http://www.latex-project.org/lppl/lppl-1-3c.txt
+
+and version 1.3 or later is part of all distributions of
+LaTeX version 2005/12/01 or later.
+
+This Work has the LPPL maintenance status author-maintained.
+
+The Author of this Work is Jean-Francois Burnol.
+
+This Work consists of the package file polexpr.sty and this README.
+
+
+Abstract
+--------
+
+The package provides "\poldef": a parser of polynomial expressions
+based upon the "\xintdeffunc" mechanism of package xintexpr.
+
+The syntax is
+
+    \poldef <name>(x):=<expression in variable x>;
+
+where in place of "x" an arbitrary letter is authorized. The expression
+uses the operations of algebra (including composition of functions) with
+standard operators, fractional numbers (possibly in scientific notation)
+and previously defined polynomial functions or other constructs as
+recognized by the \xintexpr numerical parser.
+
+The so-defined name() \xintexpr-function is also known to the package
+via its polynomial coefficients, thus allowing dedicated macros to
+implement polynomial algorithmics.
+
+Examples
+--------
+
+\poldef f(x):= 1-x+x^2;
+
+This defines polynomial "f". Polynomial names must start with a letter
+and may contain letters, digits, and underscores. The variable must be a
+single letter. The colon character is optional. The semi-colon at end of
+expression is mandatory.
+
+\PolDef{f}{1-x+x^2} does the same as \poldef f(x):= 1-x+x^2;
+To use another letter than x in the expression, one must pass it as
+an extra optional argument to \PolDef. Useful if the semi-colon has
+been assigned some non-standard catcode by some package.
+
+\PolLet{g}{f} saves a copy of "f" under name "g".
+
+\poldef f(z):= f(z)^2; redefines "f" in terms of itself.
+
+\poldef f(T):= f(f(T)); again redefines "f" in terms of its (new) self.
+
+\poldef k(z):= f(z)-g(g(z)^2)^2; should now define the zero
+polynomial... Let's check:
+\[ k(z) = \PolTypeset[z]{k} \]
+
+\PolDiff{f}{df_dx} sets "df_dx" to the derivative of "f".
+
+\PolDiff{df_dx}{f_xx} obtains second derivative
+
+\PolDiff[3]{f}{d3f_dx3} computes directly the third derivative
+
+$f(z)   = \PolTypeset[z]{f}    $\newline
+$f'(z)  = \PolTypeset[z]{df_dx}$\newline
+$f''(z) = \PolTypeset[z]{f_xx}$\newline
+$f'''(z)= \PolTypeset[z]{d3f_dx3}$\par
+
+*Important*: the package does not currently know rational functions.
+and  "/" in a parsed polynomial expression does the Euclidean quotient:
+
+  (1-x^2)/(1-x) does give 1+x but (1/(1-x))*(1-x^2) evaluates to zero.
+
+*Attention*: "1/2 x" skips the space and is treated like "1/(2x)"
+because of the tacit multiplication rules of \xintexpr. But this means
+it gives zero! Thus one must use (1/2)x or 1/2*x or (1/2)*x for
+disambiguation.
+
+\poldef k(x):= (x-1)(x-2)(x-3)(x-4)/(x^2-5x+4);%
+
+\PolTypeset{k} gives the expected x^2-5x+6
+
+\poldef f1(x):= 25(x-1)(x^2-2)(x-3)(x-4)(x-5);%
+\poldef f2(x):= 37(x-1)(x^2-2)(x-6)(x-7)(x-8);%
+
+\PolGCD{f1}{f2}{k} sets "k" to the (unitary) GCD of "f1" and "f2".
+
+\PolToExpr{k} expandably gives 2-2*x^1-1*x^2+1*x^3 for console
+or file output (this is Maple-compatible input syntax).
+
+Non-expandable macros
+---------------------
+
+\poldef name(letter):= polynomial expression using letter;
+    This evaluates the polynomial expression and stores the
+    coefficients in a private structure accessible later via other
+    package macros, under the user-chosen "name". Of course
+    previously defined polynomials are allowed in a new expression.
+    Names must start with a letter and are constituted of letters,
+    digits and underscore characters. See Examples above.
+
+    As a side effect the function name() is recognized as a genuine
+    \xintexpr...\relax function for (exact) numerical evaluation. It
+    computes values not according to the original expression but via
+    the Horner scheme corresponding to the polynomial coefficients.
+
+    The original expression is lost after parsing, and in particular
+    the package provides no way to typeset it. This has to be done
+    manually, if needed.
+
+\PolDef{name}{P(x)}
+    Does the same but the variable is assumed to be "x". To use another
+    letter, pass it as first optional argument.
+
+\PolLet{g}{f}
+    Makes a copy of already defined polynomial f to new one g.
+    Same effect as \PolDef{g}{f(x)} but faster.
+
+\PolAssign{f}\toarray\Array
+    Defines a one-argument expandable macro \Array{#1} which expands
+    to the (raw) #1th polynomial coefficient.
+
+    - Attention, coefficients here are indexed starting at 1.
+
+    - With #1=-1, -2, ..., \Array{#1} returns leading coefficients.
+
+    - With #1=0, returns the number of coefficients, i.e. 1+degree(f)
+      for non-zero polynomials.
+
+    - Out-of-range #1's return 0/1[0].
+
+\PolGet{f}\fromarray\Array
+    Does the reverse operation to \PolAssign{f}\toarray\Array. No error
+    checks on validity of coefficients as numbers. Each \Array{index}
+    is expanded in an \edef before being assigned to a coefficient.
+    Leading zero coefficients are removed from the polynomial.
+    
+    (contrived) Example: \xintAssignArray{1}{-2}{5}{-3}\to\foo
+                         \PolGet{f}\fromarray\foo
+    This will define "f" as would have \poldef f(x):=1-2x+5x^2-3x^3;
+    However the coefficients are still in their original form (i.e.
+    they were not subjected to \xintRaw or similar xintfrac macro.)
+
+\PolFromCSV{f}{comma separated coefficients}
+    Defines a polynomial directly from the comma separated list (or a
+    macro expanding to such a list) of its coefficients, the constant
+    term being the first item. No validity checks. Spaces from the list
+    argument are trimmed. List items are expanded in an \edef, but
+    currently they are left in their original form like e.g. 1.5e3
+    which is not converted to 15/1[2] "raw" xintfrac format (this may
+    change).
+
+    Leading zero coefficients are removed:
+    \PolFromCSV{J}{0, 0, 0, 0, 0, 0, 0, 0, 0, 0} defines the zero
+    polynomial, which has only one (zero) coefficient.
+
+    See also expandable macro \PolToCSV.
+
+\PolTypeset[x]{name}
+    Typesets in descending powers in math mode using the specified
+    variable (default x.) By default zero coefficients are skipped
+    (issue \poltypesetalltrue to get all of them in output).
+
+    Macros \PolTypesetCmd, \PolTypesetPlus, \PolTypesetMonomial
+    can help configure the output. See the package code.
+
+\PolTypeset*[x]{name}
+    Typesets in ascending powers.
+
+\PolDiff{f1}{f2}
+    This sets f2 to the first derivative of f1. It is allowed to issue
+    \PolDiff{f}{f}, effectively replacing f by f'.
+
+    Coefficients of the result f2 are irreducible fractions
+    (see `Technicalities`_ for the whole story.)
+
+\PolDiff[N]{f1}{f2}
+    This sets f2 to the Nth derivative of f1. Identical arguments
+    is allowed. With N=0, same effect as \PolLet{f2}{f1}.
+    With negative N, switched to using \PolAntiDiff.
+
+\PolAntiDiff{f1}{f2}
+    This sets f2 to the primitive of f1 vanishing at zero.
+
+    Coefficients of the result f2 are irreducible fractions
+    (see `Technicalities`_ for the whole story.)
+
+\PolAntiDiff[N]{f1}{f2}
+    This sets f2 to the result of N successive integrations on f1.
+    With negative N, it switches to using \PolDiff.
+
+\PolDivide{f1}{f2}{Q}{R}
+    This sets Q and R to be the quotient and remainder in the Euclidean
+    division of f1 by f2.
+
+\PolGCD{f}{g}{k}
+    This sets k to be the G.C.D. It is a unitary polynomial except if
+    both f and g vanish, then k is the zero polynomial.
+
+\PolMapCoeffs{\macro}{name}
+    It modifies each coefficient of the defined polynomial via
+    the *expandable* macro \macro. The degree is adjusted as necessary
+    if some leading coefficients vanish after the operation.
+    In replacement text of \macro, \index expands to the coefficient
+    index (which is defined to be zero for the constant term).
+
+    Notice that \macro will have to handle inputs of the shape A/B[N]
+    (xintfrac internal notation). This means that it probably will
+    have to be expressed in terms of macros from xintfrac package.
+
+    Example: \def\foo#1{\xintMul{#1}{\the\numexpr\index^2\relax}}
+    to replace nth coefficient f_n by f_n * n^2.
+
+\PolReduceCoeffs{name}
+    About the same as \PolMapCoeffs{\xintIrr}{name} (but adds [0]
+    postfix which speeds up xintfrac operations when evaluating.)
+
+Expandable macros
+-----------------
+
+All these macros expand completely in two steps except \PolToExpr
+which needs a \write, \edef or a \csname...\endcsname context.
+
+\PolEval{name}\At{value}
+    It boils down to \xinttheexpr reduce(name(value))\relax.
+
+\PolNthCoeff{name}{N}
+    It expands to the raw Nth coefficient (0/1[0] if index is out of
+    range). With N=-1, -2, ... expands to the leading coefficients.
+
+\PolDegree{name}
+    It expands to the degree. This is -1 if zero polynomial but this may
+    change in future. Should it then expand to -\infty ?
+
+\PolToExpr{f}
+    Expands to f_0 + f_1*x + f_2*x^2 + ... (ascending powers). [1, 2]
+
+    [1] in a \write, \edef, or \csname...\endcsname, but not under 
+        \romannumeral-`0
+
+    [2] the letter x is (in this release) not customizable.
+
+    By default zero coefficients are skipped (issue \poltoexprtrue to
+    get all of them in output).
+
+    No + sign before negative coefficients, for compliance with Maple
+    input format. This means though that parsing the result back via
+    naive delimited macros is difficult, see \PolToList and \PolToCSV
+    for more low-level formats making it easier to get expandably some
+    output of one's choice, which may possibly be parsed later on by
+    other macros of one's design, or from other packages.
+
+    Of course "\PolToExpr{f}" can be inserted in a \poldef, as the
+    latter expands token by token, hence will force complete expansion
+    of \PolToExpr{f}, but simply "f(x)" will be more efficient for the
+    identical result.
+
+    \PolToExprCmd is the one-argument macro used by \PolToExpr for the
+    coefficients, it defaults to \xintPRaw{\xintRawWithZeros{#1}}. One
+    will have to redefine it to use \xintIrr{#1} in place of
+    \xintRawWithZeros{#1} to get in output reduced coefficients.
+
+\PolToList{f}
+    Expands to {f_0}{f_1}...{f_N} with N = degree of f (except zero
+    polynomial which does give {0/1[0]} and not an empty output.)
+
+\PolToCSV{f}
+    Expands to f_0, f_1, f_2, ....., f_N. Converse of \PolFromCSV.
+
+Technicalities
+--------------
+
+- The catcode of the semi-colon is reset temporarily by \poldef macro in
+  case some other package (for example the French babel module) may have
+  made it active. This will fail though if the whole thing was already
+  part of a macro argument, in such cases one can use \PolDef rather.
+  The colon in := may be active with no consequences.
+
+- Beware the 1/2 x problem: as mentioned above, it will be give zero due
+  to the tacit multiplication rules of \xintexpr and to the fact that
+  the package will do the Euclidean division of 1 by polynomial 2x.
+
+- During execution of polynomial operations by \poldef (but not during
+  the initial purely numerical parsing of the expression), the xintfrac
+  macro \xintAdd is temporarily patched to always express a/b + c/d with
+  L.C.M.(b,d) as denominator. Indeed the current (xint 1.2p) \xintAdd
+  uses (ad+bc)/bd formula except if b divides d or d divides b, which
+  quickly leads in real life to big denominators.
+
+  It is probable that this convention will be backported as default
+  behaviour of xintfrac's \xintAdd in a future xint release. When this
+  change is merged, there will be an impact on coefficients computed by
+  \poldef because the change will apply even to the pure numerical
+  evaluations arising during the initial stage of the parsing. Of course
+  the coefficients are still the same rational numbers, only
+  representation as fractions may change.
+
+- As a consequence of previous rule, user-chosen common denominators
+  survive addition and multiplications:
+
+  \poldef P(x):= 1/2 + 2/2*x + 3/2*x^3 + 4/2*x^4;
+  \poldef Q(x):= 1/3 + (2/3)x + (3/3)x^3 + (4/3)x^4;
+  \poldef PQ(x):= P(x)*Q(x);
+
+  gives the polynomial
+
+  1/6+4/6*x^1+4/6*x^2+6/6*x^3+20/6*x^4+16/6*x^5+9/6*x^6+24/6*x^7+16/6*x^8
+
+  where all coefficients have the same denominator 6 (which in this
+  example is the l.c.m of the denominators of the reduced coefficients.)
+
+- \PolDiff always applies \xintIrr to the resulting coefficients, except
+  that the "decimal" part [N] (for example an input in scientific
+  notation such as 1.23e5 gives 123/1[3] internally in xintfrac) is not
+  taken into account in the reduction of the fraction. This is tentative
+  and may change.
+
+  Same remark for \PolAntiDiff.
+
+- If f was created from comma separated values by macro \PolFromCSV,
+  then the exact same coefficients (except those zero coefficients
+  beyond the leading monomial) will be in the output of \PolToList and
+  \PolToCSV in their original input form: a 1.3e2 will again be a 1.3e2.
+  
+  In contrast when such coefficients are used in a \poldef (or \PolDef)
+  expression, they get transformed during the parsing to the xintfrac
+  "raw" format. This is an unavoidable consequence of usage by \poldef
+  of \xintdeffunc which itself is based on \xintexpr. This "raw" format
+  speeds up expansion of xintfrac macros for numerical evaluations.
+
+- Currently, the package does not as a result of \poldef add to the TeX
+  memory an already pre-computed "array" structure for the polynomial
+  coefficients, as would be constructed by \PolAssign{f}\toarray\Macro.
+  Such structures are used, but for internal calculations in temporarily
+  restricted scopes. Apart from the function f() known to the
+  (numerical) \xintexpr parser (whose meaning can be found in the log
+  file after \xintverbosetrue), the data is (currently) stored in a
+  single other macro encapsulating the degree, and the coefficients as a
+  list. This may evolve in future.
+
+- As is to be expected internal structures of the package are barely
+  documented and unstable. Don't use them.
+
+
+CHANGE LOG
+----------
+
+- v0.1 (2018/01/11): initial release. Features:
+
+  *. differentiation and anti-differentiation,
+  *. Euclidean division and GCDs,
+  *. various utilities such as \PolFromCSV, \PolToCSV, \PolToExpr.
+
+  Only one-variable polynomials so far.
+
+  Due to lack of available time I have not really yet set-up a
+  sufficient enough test suite. Bug reports very welcome!