summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/doc/latex/polexpr/README
blob: a258011f9dd98a3a1cd58b3a06b1791f2e8e1d61 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
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!