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!
|