From 93ccafaede54490e77718a7d682343e94af262ec Mon Sep 17 00:00:00 2001 From: Karl Berry Date: Fri, 16 Feb 2018 22:30:09 +0000 Subject: polexpr (16feb18) git-svn-id: svn://tug.org/texlive/trunk@46653 c570f23f-e606-0410-a88d-b1316a301751 --- Master/texmf-dist/doc/latex/polexpr/README.md | 99 +- Master/texmf-dist/doc/latex/polexpr/polexpr.html | 1317 ++++++++++++++++++---- Master/texmf-dist/doc/latex/polexpr/polexpr.txt | 1235 ++++++++++++++++++-- Master/texmf-dist/tex/latex/polexpr/polexpr.sty | 1013 +++++++++++++++-- 4 files changed, 3195 insertions(+), 469 deletions(-) (limited to 'Master') diff --git a/Master/texmf-dist/doc/latex/polexpr/README.md b/Master/texmf-dist/doc/latex/polexpr/README.md index e6a1026e61c..78690d48d33 100644 --- a/Master/texmf-dist/doc/latex/polexpr/README.md +++ b/Master/texmf-dist/doc/latex/polexpr/README.md @@ -42,66 +42,41 @@ The polynomials are then not only genuine `\xintexpr` (and package via their coefficients. This allows dedicated macros to implement polynomial algorithmics. -CHANGE LOG ----------- - -- v0.1 (2018/01/11): initial release. Features: - - The `\poldef` parser itself, - - Differentiation and anti-differentiation, - - Euclidean division and GCDs, - - Various utilities such as `\PolFromCSV`, `\PolMapCoeffs`, - `\PolToCSV`, `\PolToExpr`, ... - Only one-variable polynomials so far. -- v0.2 (2018/01/14) - - Fix: `"README thinks \numexpr recognizes ^ operator"`. - - Convert README to reStructuredText markup. - - Move main documentation from README to separate `polexpr.txt` - file. - - Provide `polexpr.html` as obtained via - [DocUtils](http://docutils.sourceforge.net/docs/index.html) - `rst2html.py`. - - Convert README to (CTAN compatible) Markdown markup. - Due to lack of available time the test suite might not be extensive - enough. Bug reports are very welcome! -- v0.3 (2018/01/17) - - bug fixes: - - the `0.1` `\PolEval` accepted expressions for its second - argument, but this was removed by mistake at `0.2`. - Restored. - - incompatible or breaking changes: - - `\PolToExpr` now by default uses *descending* powers (it - also treats differently coefficients equal to 1 or -1.) Use - `\PolToExpr*` for *ascending* powers. - - `\PolEval` reduced the output to smallest terms, but as this is - costly with big fractions and not needed if e.g. wrapped in - an `\xintRound` or `\xintFloat`, this step has been removed; - the former meaning is available as `\PolEvalReduced`. - - new (or newly documented) macros: - - `\PolTypesetCmd` - - `\PolTypesetCmdPrefix`, - - `\PolTypesetMonomialCmd`, - - `\PolEvalReduced`, - - `\PolFloatEval`, - - `\PolToFloatExpr`, - - `\PolToExprOneTerm`, - - `\PolToFloatExprOneTerm`, - - `\PolToExprCmd`, - - `\PolToFloatExprCmd`, - - `\PolToExprTermPrefix`, - - `\PolToExprVar`, - - `\PolToExprTimes`. - - improvements: - - documentation has a table of contents, internal hyperlinks, - standardized signature notations and added explanations. - - one can do `\PolLet{g}={f}` or `\PolLet{g}{f}`. - - `\PolToExpr{f}` is highly customizable. - - `\poldef` and other defining macros prepare the polynomial - functions for usage within `\xintthefloatexpr` (or - `\xintdeffloatvar`). Coefficients are pre-rounded to the - floating point precision. Indispensible for numerical - algorithms, as exact fractions, even reduced, quickly become - very big. See the documentation about how to use the exact - polynomials also in floating point context. -- v0.3.1 (2018/01/18) - Fixes two typos in example code included in the documentation. +Releases +-------- +- 0.1 (2018/01/11) + Initial release (files README, polexpr.sty). +- 0.2 (2018/01/14) + Documentation moved to polexpr.{txt,html}. +- 0.3 (2018/01/17) + Make polynomials known to `\xintfloatexpr` and improve + documentation. +- 0.3.1 (2018/01/18) + Fix two typos in documentation. +- 0.4 (2018/02/16) + - Revert 0.3 automatic generation of floating point variants. + - Move CHANGE LOG from README.md to HTML documentation. + - A few bug fixes and breaking changes. Please refer to + `polexpr.html`. + - Main new feature: root localization via [Sturm + Theorem](https://en.wikipedia.org/wiki/Sturm%27s_theorem). + +Files of 0.4 release: + +- README.md, +- polexpr.sty (package file), +- polexpr.txt (documentation), +- polexpr.html (conversion via + [DocUtils](http://docutils.sourceforge.net/docs/index.html) + rst2html.py) + +Acknowledgments +--------------- + +Thanks to Jürgen Gilg whose question about +[xint](http://www.ctan.org/pkg/xint) usage for differentiating +polynomials was the initial trigger leading to this package, and to +Jürgen Gilg and Thomas Söll for testing it on some concrete problems. + +Renewed thanks on occasion of `0.4` release! diff --git a/Master/texmf-dist/doc/latex/polexpr/polexpr.html b/Master/texmf-dist/doc/latex/polexpr/polexpr.html index 962771bdfa7..4ddb208d10f 100644 --- a/Master/texmf-dist/doc/latex/polexpr/polexpr.html +++ b/Master/texmf-dist/doc/latex/polexpr/polexpr.html @@ -362,76 +362,128 @@ ul.auto-toc {

Package polexpr documentation

-

0.3.1 (2018/01/18)

+

0.4 (2018/02/16)

Contents

-
-

First Examples

+
+

Basic Examples

The syntax is:

 \poldef polname(x):= expression in variable x;
@@ -526,10 +578,200 @@ PSTricks-compatible; the letter used in output can be
 
gives ascending powers: 2-2*x-x^2+x^3.
+
+

Examples of localization of roots

+

First some remarks about auxiliaries.

+
    +

  • To make printed decimal numbers more enjoyable than via +\xintSignedFrac:

    +
    +\renewcommand\PolTypesetOne[1]{\PolDecToString{\xintREZ{#1}}}%
+
    +

    \PolDecToString will use decimal notation to incorporate the power +of ten part; and the \xintREZ will have the effect to suppress +trailing zeros if present in raw numerator (if those digits end up +after decimal mark.) Notice that the above are expandable macros and +that one can also do:

    +
    +\renewcommand\PolToExprCmd[1]{\PolDecToString{\xintREZ{#1}}}%
+
    +

    to modify output of \PolToExpr{polname}.

    +
    • +

  • for extra info in log file \xintverbosetrue. In fact one can also +work from command line then (I recommend rlwrap for encapsulating +latex).

    +
    • +
+
+

A typical example

+
+\poldef f(x) := x^7 - x^6 - 2x + 1;
+
+\PolToSturm{f}{f}
+\PolSturmIsolateZeros{f}
+The \PolTypeset{f} polynomial has \PolSturmNbOfIsolatedZeros{f} distinct real
+roots which are located in the following intervals:
+\PolPrintIntervals{f}
+Here is the second root with ten more decimal digits:
+\PolRefineInterval[10]{f}{2}
+\[\PolSturmIsolatedZeroLeft{f}{2}<Z_2<\PolSturmIsolatedZeroRight{f}{2}\]
+And here is the first root with twenty digits after decimal mark:
+\PolEnsureIntervalLength{f}{1}{-20}
+\[\PolSturmIsolatedZeroLeft{f}{1}<Z_1<\PolSturmIsolatedZeroRight{f}{1}\]
+The derivative polynomial is \PolTypeset{f_1}.
+\PolToSturm{f_1}{f_1}\PolSturmIsolateZeros{f_1}%
+It has \PolSturmNbOfIsolatedZeros{f_1} distinct real
+roots:
+\PolPrintIntervals[W]{f_1}
+\PolEnsureIntervalLengths{f_1}{-10}%
+Here they are with ten digits after decimal mark:
+\PolPrintIntervals[W]{f_1}
+\PolDiff{f_1}{f_xx}
+\PolToSturm{f_xx}{f_xx}
+\PolSturmIsolateZeros{f_xx}
+The second derivative is \PolTypeset{f_xx}.
+It has \PolSturmNbOfIsolatedZeros{f_xx} distinct real
+roots:
+\PolPrintIntervals[X]{f_xx}
+Here is the positive one with 20 digits after decimal mark:
+\PolEnsureIntervalLength{f_xx}{2}{-20}%
+\[X_2 = \PolSturmIsolatedZeroLeft{f_xx}{2}\dots\]
+The more mathematically advanced among our dear readers will be able
+to give the exact value for $X_2$!
+
+
+
+

A degree four polynomial with nearby roots

+
+\PolDef{Q}{(x-1.050001)(x-1.105001)(x-1.110501)(x-1.111051)}
+\PolTypeset{Q}
+\PolToSturm{Q}{Q} % it is allowed to use same prefix for Sturm chain
+\PolSturmIsolateZeros{Q}
+\PolPrintIntervals{Q}
+% reports 1.0 < Z_1 < 1.1, 1.10 < Z_2 < 1.11, 1.110 < Z_3 < 1.111, and 1.111 < Z_4 < 1.112
+% but the above bounds do not allow minimizing separation between roots
+% so we refine:
+\PolRefineInterval*{Q}{1}
+\PolRefineInterval*{Q}{2}
+\PolRefineInterval*{Q}{3}
+\PolRefineInterval*{Q}{4}
+\PolPrintIntervals{Q}
+% reports 1.05 < Z_1 < 1.06, 1.105 < Z_2 < 1.106, 1.1105 < Z_3 < 1.1106,
+% and 1.11105 < Z_4 < 1.11106.
+\PolEnsureIntervalLengths{Q}{-6}
+\PolPrintIntervals{Q}
+% of course finds here all roots exactly
+
+
+
+

The degree nine polynomial with 0.99, 0.999, 0.9999 as triple roots

+
+\PolDef{P}{(x-0.99)^3(x-0.999)^3(x-0.9999)^3}
+\PolTypeset{P}\par
+\PolToSturm{P}{P}%
+\PolLet{Psqfree}{P_0}\PolMakeMonic{Psqfree}\PolReduceCoeffs*{Psqfree}
+\par
+The monic square-free radical is \PolTypeset{Psqfree}.
+\PolSturmIsolateZeros{P}
+\par
+It has \PolSturmNbOfIsolatedZeros{P} real roots.
+\PolPrintIntervals{P}% all three roots found exactly
+
+
+
+

A Mignotte type polynomial

+
+\PolDef{P}{x^10 - (10x-1)^2}%
+\PolTypeset{P}              % prints it in expanded form
+\PolToSturm{P}{P}           % we can use same prefix for Sturm chain
+\PolSturmIsolateZeros{P}    % finds 4 real roots
+\PolPrintIntervals{P}%
+% reports  -2 < Z_1 < -1, 0 < Z_2 < 0.1, 0.1 < Z_3 < 0.2, 1 < Z_4 < 2
+\PolRefineInterval*{P}{2}% will refine to 0.0999990 < Z_2 < 0.0999991
+\PolRefineInterval*{P}{3}% will refine to 0.100001 < Z_3 < 0.100002
+\PolPrintIntervals{P}%
+\PolEnsureIntervalLengths{P}{-10}%
+\PolPrintIntervals{P}% now all roots are known 10 decimal digits after mark
+\PolEnsureIntervalLength{P}{2}{-20}% makes Z_2 known with 20 digits after mark
+There are $\PolSturmNbOfIsolatedZeros{P}$ distinct real roots and there holds
+$\PolSturmIsolatedZeroLeft{P}{2}<Z_2<\PolSturmIsolatedZeroRight{P}{2}$.
+
+

The last line produces:

+
+0.09999900004999650028 < Z_2 < 0.09999900004999650029
+
+
+
+

The degree 41 polynomial with -2, -1.9, -1.8, ..., 0, 0.1, ..., 1.9, 2 as roots

+
+\PolDef{P}{mul((x-i*1e-1), i=-20..20)}% i/10 is same but less efficient
+
+

In the defining expression we could have used i/10 but this gives +less efficient internal form for the coefficients (the 10's end up +in denominators). Using \PolToExpr{P} after having done

+
+\renewcommand\PolToExprCmd[1]{\PolDecToString{\xintREZ{#1}}}
+
+

we get this expanded form:

+
+x^41
+-28.7*x^39
++375.7117*x^37
+-2975.11006*x^35
++15935.28150578*x^33
+-61167.527674162*x^31
++173944.259366417394*x^29
+-373686.963560544648*x^27
++613012.0665016658846445*x^25
+-771182.31133138163125495*x^23
++743263.86672885754888959569*x^21
+-545609.076599482896371978698*x^19
++301748.325708943677229642930528*x^17
+-123655.8987669450434698869844544*x^15
++36666.1782054884005855608205864192*x^13
+-7607.85821367459445649518380016128*x^11
++1053.15135918687298508885950223794176*x^9
+-90.6380005918141132650786081964032*x^7
++4.33701563847327366842552218288128*x^5
+-0.0944770968420804735498178265088*x^3
++0.00059190121813899276854174416896*x
+
+

which shows coefficients with up to 36 significant digits...

+

Stress test: not a hard challenge to xint + polexpr, but be a bit patient!

+
+\PolDef{P}{mul((x-i*1e-1), i=-20..20)}%
+\PolToSturm{P}{S}        % dutifully computes S_0, ..., S_{41}
+\PolSturmIsolateZeros{S} % finds *exactly* (but a bit slowly) all 41 roots!
+\PolPrintIntervals{S}    % nice, isn't it?
+
+
+
+

Roots of Chebyshev polynomials

+
+\newcount\mycount
+\poldef T_0(x) := 1;
+\poldef T_1(x) := x;
+\mycount 2
+\xintloop
+  \poldef T_\the\mycount(x) :=
+          2x*T_\the\numexpr\mycount-1(x)
+           - T_\the\numexpr\mycount-2(x);
+\ifnum\mycount<15
+\advance\mycount 1
+\repeat
+
+\[T_{15} = \PolTypeset[X]{T_15}\]
+\PolToSturm{T_15}{T_15}
+\PolSturmIsolateZeros{T_15}
+\PolEnsureIntervalLengths{T_15}{-10}
+\PolPrintIntervals{T_15}
+
+
+
-

Non-expandable macros

+

Non-expandable macros

-

\poldef polname(letter):= expression in letter;

+

\poldef polname(letter):= expression in letter;

This evaluates the polynomial expression and stores the coefficients in a private structure accessible later via other package macros, @@ -546,25 +788,18 @@ genuine \xintexpr...\relax evaluation (or within an \xintdefvar assignment.) It computes values not according to the original expression but via the Horner scheme corresponding to the polynomial coefficients.

-

Also, a function with the same name is created for use within -\xintfloatexpr (or \xintdeffloatvar.) This is indispensible -for numerical algorithms as exact computations very quickly lead to -very big fractions. Addition and multiplication steps of the Horner -scheme will be executed as floating-point operations. The -coefficients have already been rounded at time of definition, -according to the then prevailing \xinttheDigits value.

-
-

Important

-

Package macros (such as derivatives or Euclidean division) -operate with the "exact" polynomials; "floating point" -polynomials are always obtained in a second step.

-

To modifiy "in-place" the original coefficients of a polynomial -and round them to float precision:

-
-\PolMapCoeffs{\xintFloat}{polname}
-% or \xintFloat[P] for precision P digits
-
-

See \PolMapCoeffs{\macro}{polname}.

+
+

Attention!

+

Release 0.3 also did the necessary set-up to let the +polynomial be known to the \xintfloatexpr (or +\xintdeffloatvar) parser.

+

Since 0.4 this isn't done automatically. Even more, a +previously existing floating point variant of the same name will +be let undefined again, to avoid hard to debug mismatches between +exact and floating point polynomials. This also applies when the +polynomial is produced not via \poldef or \PolDef but as +a product of the other package macros.

+

See \PolGenFloatVariant{polname}.

The original expression is lost after parsing, and in particular the package provides no way to typeset it. This has to be done @@ -572,23 +807,47 @@ manually, if needed.

-

\PolDef[letter]{polname}{expression in letter}

+

\PolDef[letter]{polname}{expression in letter}

-Does the same in an undelimited macro format (thus avoiding -potential problems with the catcode of the semi-colon in presence of -some packages.) In absence of the [letter] optional argument, -the variable is assumed to be x.
+Does the same as \poldef in an undelimited macro +format (thus avoiding potential problems with the catcode of the +semi-colon in presence of some packages.) In absence of the +[letter] optional argument, the variable is assumed to be x. +
+
+

\PolGenFloatVariant{polname}

+
+

Makes the polynomial also usable in the \xintfloatexpr parser. +It will therein evaluates via an Horner scheme with coefficients +already pre-rounded to the float precision.

+

See also \PolToFloatExpr{polname}.

+
+

Attention!

+

Release 0.3 did this automatically on \PolDef and +\poldef but this was removed at 0.4 for optimization.

+

Any operation, for example generating the derivative polynomial, +or dividing two polynomials or using the \PolLet, must be +followed by explicit usage of \PolGenFloatVariant{polname} if +the new polynomial is to be used in \xintfloatexpr or alike +context.

+
+
-

\PolLet{polname_2}={polname_1}

+

\PolLet{polname_2}={polname_1}

Makes a copy of the already defined polynomial polname_1 to a new one polname_2. Same effect as \PolDef{polname_2}{polname_1(x)} but with less overhead. The = is optional.
+
-

\PolAssign{polname}\toarray\macro

+

\PolAssign{polname}\toarray\macro

Defines a one-argument expandable macro \macro{#1} which expands to the (raw) #1th polynomial coefficient.

@@ -611,7 +870,7 @@ indices act the same in both.)

-

\PolGet{polname}\fromarray\macro

+

\PolGet{polname}\fromarray\macro

Does the converse operation to \PolAssign{polname}\toarray\macro. No error checks on validity of coefficients as numbers. Each @@ -625,18 +884,18 @@ polynomial.

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.)

+they were not subjected to \xintRaw or similar xintfrac macro.)

-

\PolFromCSV{polname}{<csv>}

+

\PolFromCSV{polname}{<csv>}

Defines a polynomial directly from the comma separated list of values (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 each expanded in an \edef, but currently left in their original form like e.g. -1.5e3 which is not converted to 15/1[2] raw xintfrac +1.5e3 which is not converted to 15/1[2] raw xintfrac format (this may change).

Leading zero coefficients are removed:

@@ -647,7 +906,7 @@ format (this may change).
-

\PolTypeset{polname}

+

\PolTypeset{polname}

Typesets in descending powers in math mode. It uses letter x but this can be changed via an optional argument:

@@ -661,31 +920,52 @@ can be re-defined for customization. Their default definitions are expandable, but this is not a requirement.

-

\PolTypesetCmd{raw_coeff}

+

\PolTypesetCmd{raw_coeff}

+
+

Checks if the coefficient is 1 or -1 and then skips printing +the 1, except for the constant term. Also it sets conditional +\PolIfCoeffIsPlusOrMinusOne{A}{B}.

+

The actual printing of the coefficients, when not equal to plus or +minus one is handled by \PolTypesetOne{raw_coeff}.

+
+
+
+

\PolTypesetOne{raw_coeff}

-

Basically will use \xintSignedFrac from xintfrac, but checks if -the coefficient is 1 or -1 and then skips printing the -1, except for the constant term...

-

One can do things such as for example: [1]

+

The default is \xintSignedFrac but this macro is annoying as it +insists to use a power of ten, and not decimal notation.

+

One can do things such as for example: [1]

-\renewcommand\PolTypesetCmd[1]{\num{\xintPFloat[5]{#1}}}
-\renewcommand\PolTypesetCmd[1]{\num{\xintRound{4}{#1}}}
+\renewcommand\PolTypesetOne[1]{\num{\xintPFloat[5]{#1}}}
+\renewcommand\PolTypesetOne[1]{\num{\xintRound{4}{#1}}}

where e.g. we used the \num macro of siunitx as it understands floating point notation.

- +
-
[1]the difference in the syntaxes of \xintPFloat and +
[1]the difference in the syntaxes of \xintPFloat and \xintRound is explained from the fact that \xintPFloat by default uses the prevailing precision hence the extra argument like here 5 is an optional one.
+

One can also give a try to using \PolDecToString{decimal number} +which uses decimal notation (at least for the numerator part).

+
+

\PolTypesetMonomialCmd

+
+This decides how a monomial (in variable \PolVar and with +exponent \PolIndex) is to be printed. The default does nothing +for the constant term, \PolVar for the first degree and +\PolVar^{\PolIndex} for higher degrees monomials. Beware that +\PolIndex expands to digit tokens and needs termination in +\ifnum tests.
+
-

\PolTypesetCmdPrefix{raw_coeff}

+

\PolTypesetCmdPrefix{raw_coeff}

Expands to a + if the raw_coeff is zero or positive, and to nothing if raw_coeff is negative, as in latter case the @@ -694,25 +974,15 @@ the - sign in front of the fraction (if it is this will thus serve as separator in the typeset formula. Not used for the first term.
-
-

\PolTypesetMonomialCmd

-
-This decides how a monomial (in variable \PolVar and with -exponent \PolIndex) is to be printed. The default does nothing -for the constant term, \PolVar for the first degree and -\PolVar^{\PolIndex} for higher degrees monomials. Beware that -\PolIndex expands to digit tokens and needs termination in -\ifnum tests.
-
-
-

\PolTypeset*{polname}

+
+

\PolTypeset*{polname}

Typesets in ascending powers. Use e.g. [h] optional argument (after the *) to use letter h rather than x.
-

\PolDiff{polname_1}{polname_2}

+

\PolDiff{polname_1}{polname_2}

This sets polname_2 to the first derivative of polname_1. It is allowed to issue \PolDiff{f}{f}, effectively replacing f @@ -722,7 +992,7 @@ by f'.

-

\PolDiff[N]{polname_1}{polname_2}

+

\PolDiff[N]{polname_1}{polname_2}

This sets polname_2 to the N-th derivative of polname_1. Identical arguments is allowed. With N=0, same effect as @@ -730,7 +1000,7 @@ Identical arguments is allowed. With N=0, same using \PolAntiDiff.
-

\PolAntiDiff{polname_1}{polname_2}

+

\PolAntiDiff{polname_1}{polname_2}

This sets polname_2 to the primitive of polname_1 vanishing at zero.

@@ -739,27 +1009,287 @@ at zero.

-

\PolAntiDiff[N]{polname_1}{polname_2}

+

\PolAntiDiff[N]{polname_1}{polname_2}

This sets polname_2 to the result of N successive integrations on polname_1. With negative N, it switches to using \PolDiff.
-

\PolDivide{polname_1}{polname_2}{polname_Q}{polname_R}

+

\PolDivide{polname_1}{polname_2}{polname_Q}{polname_R}

This sets polname_Q and polname_R to be the quotient and remainder in the Euclidean division of polname_1 by polname_2.
+
+

\PolQuo{polname_1}{polname_2}{polname_Q}

+
+This sets polname_Q to be the quotient in the Euclidean division +of polname_1 by polname_2.
+
+
+

\PolRem{polname_1}{polname_2}{polname_R}

+
+This sets polname_R to be the remainder in the Euclidean division +of polname_1 by polname_2.
+
-

\PolGCD{polname_1}{polname_2}{polname_GCD}

+

\PolGCD{polname_1}{polname_2}{polname_GCD}

+
+This sets polname_GCD to be the (monic) GCD of the two first +polynomials. It is a unitary polynomial except if both polname_1 +and polname_2 vanish, then polname_GCD is the zero +polynomial.
+ +
+
+

\PolToSturm{polname}{sturmname}

+
+

With, for example, polname being P and sturmname being +S, the macro starts by computing polynomials S_0 = P, S_1 += P', ..., with S_{n+1} the opposite of the remainder of +euclidean division of S_{n-1} by S_{n}. The last non-zero +remainder S_N is up to a factor the GCD of P and P' +hence a constant if and only if P is square-free.

+

In case S_N is not a constant, the macro then goes on with +dividing all S_k's with S_N (which becomes 1).

+

Thus S_0 now has exactly the same real and complex +roots as polynomial polname, but each with multiplicity one.

+
+
+
+

\PolToSturm*{polname}{sturmname}

+
+Does not divide the Sturm chain by its last element.
+
+
+

\PolSetToSturmChainSignChangesAt{\macro}{sturmname}{fraction}

+
+

Sets macro \macro to the number of sign changes in the Sturm +chain with name prefix sturmname, at location fraction +(which must be in format as acceptable by the xintfrac macros.)

+
+

Note

+

The author was lazy and did not provide rather an expandable +variant, where one would do \edef\macro{\PolNbOf...}.

+

This will presumably get added in a future release.

+

After some hesitation it was decided the macro would by default +act globally. To make the scope of its macro definition local, +use [\empty] as extra optional argument.

+
+
+
+
+

\PolSetToNbOfZerosWithin{\macro}{sturmname}{value_a}{value_b}

+
+

Applies the Sturm Theorem to set \macro to the exact number +of distinct roots of sturmname_0 in the interval (value_a, +value_b] (the macro first re-orders the value for value_a <= +value_b to hold).

+
+

Note

+

The author was lazy and did not provide rather an expandable +variant, where one would do \edef\macro{\PolNbOf...}.

+

This will presumably get added in future.

+

After some hesitation it was decided the macro would by default +act globally. To make the scope of its macro definition local, +use [\empty] as extra optional argument.

+
+
+
+
+

\PolSturmIsolateZeros{sturmname}

+
+

First, it evaluates using Sturm theorem the number of distinct +real roots of sturmname_0.

+
+

Important

+

The Sturm chain must be of the reduced type, i.e. +as constructed via \PolToSturm{polname}{sturmname}.

+
+

Then it locates, again using Sturm theorem, as many disjoint +intervals as there are roots. Some intervals reduce to singleton +which are roots. Non-singleton intervals get refined to make sure +none of their two limit points is a root: they contain each a single +root, in their respective interiors.

+ +

The interval boundaries are decimal numbers, originating +in iterated decimal subdivision from initial intervals +(-10^E, 0) and (0, 10^E); if zero is a root it is always +identified individually. The non-singleton intervals are of the +type (a/10^f, (a+1)/10^f) with a an integer, which is +neither 0 nor -1. Hence a and a+1 are both positive +or both negative.

+

The interval boundaries (and exactly found roots) are made available +for future computations in \xintexpr-essions or polynomial +definitions as variables <sturmname>L_1, +<sturmname>L_2, etc..., for the left end-points and +<sturmname>R_1, <sturmname>R_2, ..., for the right +end-points.

+

Also two macro arrays (in the sense of +xinttools's \xintAssignArray) are created for holding the +interval end-points written out in standard decimal notation +(see \PolDecToString{decimal number}). +To access these values, macros +\PolSturmIsolatedZeroLeft{sturmname}{index} and +\PolSturmIsolatedZeroRight{sturmname}{index} are provided.

+
+

Important

+

Trailing zeroes in these stored decimal numbers are significant: +they are also present in the decimal expansion of the exact root.

+
+
+

Note

+

The actual array macros are \POL_ZeroInt<sturmname>L and +\POL_ZeroInt<sturmname>R but as these names use the +non-letter character _ and possibly also digits from +sturmname, the accessor macros above have been made part of +the package.

+
+

The start of decimal expansion of a positive k-th root is given +by \PolSturmIsolatedZeroLeft{sturmname}{k}, and for a negative +root it is given by \PolSturmIsolatedZeroRight{sturmname}{k}. +These two decimal numbers are either both zero or both of the same +sign.

+

The number of distinct roots is obtainable as +\PolSturmNbOfIsolatedZeros{sturmname}.

+
+

Note

+

In the current implementation the <sturmname>... variables +and the \POL_ZeroInt... arrays are globally defined. On the +other hand the Sturm sequence polynomials obey the current scope.

+
+
+

Note

+

When two successive roots are located in adjacent intervals, the +separation between them is not lower bounded. See +\PolRefineInterval*{sturmname}{index}.

+
+
+

Note

+

As all computations are done exactly there can be no errors... +apart those due to bad coding by author. The results are exact +bounds for the mathematically exact real roots.

+

Future releases will perhaps also provide macros based on Newton +or Regula Falsi methods. Exact computations with such methods +lead however quickly to very big fractions, and this forces usage +of some rounding scheme for the abscissas if computation times +are to remain reasonable. This raises issues of its own, which +are studied in numerical mathematics.

+
+
+
+
+

\PolRefineInterval*{sturmname}{index}

+
+The index-th interval (starting indexing at one) is further +subdivided as many times as is necessary in order for the newer +interval to have both its end-points distinct from the end-points of +the original interval. This means that the kth root is then +strictly separated from the other roots.
+
+
+

\PolRefineInterval[N]{sturmname}{index}

+
+The index-th interval (starting count at one) is further +subdivided once, reducing its length by a factor of 10. This is done +N times if the optional argument [N] is present.
+
+
+

\PolEnsureIntervalLength{sturmname}{index}{E}

-This sets polname_GCD to be the G.C.D. It is a unitary -polynomial except if both polname_1 and polname_2 vanish, -then polname_GCD is the zero polynomial.
+The index-th interval is subdivided until its length becomes at +most 10^E. This means (for E<0) that the first -E digits +after decimal mark of the kth root will then be known exactly. +
+
+

\PolEnsureIntervalLengths{sturmname}{E}

+
+

The intervals as obtained from \PolSturmIsolateZeros are (if +necessary) subdivided further by (base 10) dichotomy in order for +each of them to have length at most 10^E (length will be shorter +than 10^E in output only if it did not change or became zero.)

+

This means that decimal expansions of all roots will be known with +-E digits (for E<0) after decimal mark.

+
+
+
+

\PolPrintIntervals[varname]{sturmname}

+
+

This is a convenience macro which prints the bounds for the roots +Z_1, Z_2, ... (the optional argument varname allows to +specify a replacement for the default Z). This will be done in a +math mode array, one interval per row, and pattern rcccl, +where the second and fourth column hold the < sign, except when +the interval reduces to a singleton, which means the root is known +exactly. The user is invited to renewcommand the macro if some other +type of tabular environment for example is wanted.

+

In each array cell the corresponding interval end-point (which may +be an exactly known root) is available as macro +\PolPrintIntervalsTheEndPoint (in decimal notation). And the +corresponding interval index is available as +\PolPrintIntervalsTheIndex.

+

These values may be tested to decide some on-the-fly customization +(color for example), via the following auxiliaries which can be +modified by user. Furthermore these auxiliaries can also use the +following conditionals: \PolIfEndPointIsPositive{A}{B}, +\PolIfEndPointIsNegative{A}{B}, \PolIfEndPointIsZero{A}{B}.

+
+
+

\PolPrintIntervalsPrintExactZero

+
+

This is provided to help customize how an exactly known root is +printed in the right most column of the array. The package +definition is:

+
+\newcommand\PolPrintIntervalsPrintExactZero{\PolPrintIntervalsTheEndPoint}%
+
+

Recall that this is expanded in an array cell.

+

If for example you want to print in red the third root, known +exactly, the macro could make a test for the value of +\PolPrintIntervalsTheIndex and act accordingly.

+
+
+
+

\PolPrintIntervalsPrintLeftEndPoint

+
+

Package definition is:

+
+\newcommand\PolPrintIntervalsPrintLeftEndPoint{\PolPrintIntervalsTheEndPoint}%
+
+
+
+
+

\PolPrintIntervalsPrintRightEndPoint

+
+

Package definition is:

+
+\newcommand\PolPrintIntervalsPrintRightEndPoint{\PolPrintIntervalsTheEndPoint}%
+
+
+
-

\PolMapCoeffs{\macro}{polname}

+

\PolMapCoeffs{\macro}{polname}

It modifies ('in-place': original coefficients get lost) each coefficient of the defined polynomial via the expandable macro @@ -769,7 +1299,7 @@ coefficients vanish after the operation. In replacement text of 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.

+will have to be expressed in terms of macros from xintfrac package.

Example:

 \def\foo#1{\xintMul{#1}{\the\numexpr\index*\index\relax}}
@@ -779,94 +1309,176 @@ will have to be expressed in terms of macros from xintfrac package.
-

\PolReduceCoeffs{polname}

+

\PolReduceCoeffs{polname}

About the same as \PolMapCoeffs{\xintIrr}{polname} (but maintaining a [0] postfix for speedier xintfrac parsing when polynomial function is used for computations.) This is a one-argument macro, working 'in-place'.
+
+

\PolReduceCoeffs*{polname}

+
+

This starred variant leaves un-touched the decimal exponent in the +internal representation of the fractional coefficients, i.e. if a +coefficient is internally A/B[N], then A/B is reduced to +smallest terms, but the 10^N part is kept as is. Note: if the +polynomial is freshly defined directly via \PolFromCSV its coefficients might still be internally in some +format like 1.5e7; the macro will anyhow always first do the +needed conversion to strict format A/B[N].

+

Evaluations with polynomials treated by this can be much faster than +with those handled by the non-starred variant +\PolReduceCoeffs{polname}: as the numerators and denominators +remain smaller, this proves very beneficial in favorable cases +(especially when the coefficients are decimal numbers) to the +expansion speed of the xintfrac macros used internally by +\PolEval.

+
+
+
+

\PolMakeMonic{polname}

+
+Divides by the leading coefficient. It is recommended to execute +\PolReduceCoeffs*{polname} immediately afterwards. This is not +done automatically, due to the case the original polynomial had integer +coefficients and we want to keep the leading one as common +denominator.
+
-

Expandable macros

+

Expandable macros

All these macros expand completely in two steps except \PolToExpr and \PolToFloatExpr (and their auxiliaries) which need a \write, \edef or a \csname...\endcsname context.

-
-

\PolEval{polname}\At{numerical expression}

+
+

\PolEval{polname}\AtExpr{numerical expression}

-

It boils down to \xinttheexpr polname(numerical expression)\relax.

-
-

Note

-

The 0.2 version stupidly tried to be clever and as a result -of a misguided optimization choked if value was not a number -but a numerical expression (a sum e.g.), but the more powerful -behaviour has been reinstored at 0.3 release.

-

The 0.1 and 0.2 version did a reduce which however is -costly on big fractions and irrelevant if the output is served as -argument of \xintRound or \xintFloat. Thus reduce was -removed, and former meaning is now available as -\PolEvalReduced{polname}\At{numerical expression}

+It boils down to +\xinttheexpr polname(numerical expression)\relax.
+
+
+

\PolEval{polname}\At{fraction}

+
+

Evaluates the polynomial at value fraction which must be in (or +expand to) a format acceptable to the xintfrac macros.

+
+

Attention!

+

Meaning was changed at 0.4. Formerly \PolEval{P}\At{foo} +accepted for foo an expression which was handled by +\xintexpr. See \PolEval{polname}\AtExpr{numerical +expression}.

+

In particular, to use an \xintexpr user-declared variable (or +e.g. the variables as defined by \PolSturmIsolateZeros) one must use the \AtExpr syntax.

-
-

\PolEvalReduced{polname}\At{numerical expression}

+
+

\PolEvalReduced{polname}\AtExpr{numerical expression}

Boils down to \xinttheexpr reduce(polname(numerical expression))\relax.
-
-

\PolFloatEval{polname}\At{numerical expression}

+
+

\PolEvalReduced{polname}\At{fraction}

+
+

Evaluates the polynomial at value fraction which must be in (or +expand to) a format acceptable to the xintfrac macros, and produce +an irreducible fraction.

+
+

Attention!

+

Meaning was changed at 0.4. Formerly the evaluation point +could be given as an expression.

+
+
+
+
+

\PolFloatEval{polname}\AtExpr{numerical expression}

Boils down to \xintthefloatexpr polname(numerical expression)\relax.

-

This is done via a Horner Scheme (see \poldef), with -already rounded coefficients. [2] To use the exact coefficients -(and exact additions and multiplications), just insert it in the -float expression as in this example: [3]

+

This is done via a Horner Scheme (see \poldef and +\PolGenFloatVariant{polname}), with already rounded +coefficients. [2] To use the exact coefficients with exactly +executed additions and multiplications, just insert it in the float +expression as in this example: [3]

 \xintthefloatexpr 3.27*\xintexpr f(2.53)\relax^2\relax

The f(2.53) is exactly computed then rounded at the time of getting raised to the power 2. Moving the ^2 inside, that operation would also be treated exactly.

- +
+

Attention!

+

At polexpr 0.3, polynoms were automatically also prepared for +use in floating point contexts. This got dropped at 0.4 for +optimization purposes. See \PolGenFloatVariant{polname}.

+
+
-
[2]Anyway each floating point operation starts by rounding its +
[2]Anyway each floating point operation starts by rounding its operands to the floating point precision.
- +
- +
[3]The \xintexpr could be \xinttheexpr but that would be -less efficient. Cf. xintexpr documentation about nested -expressions.
[3]The \xintexpr here could be \xinttheexpr but that +would be less efficient. Cf. xintexpr documentation about +nested expressions.
+
+

\PolFloatEval{polname}\At{fraction}

+
+

Evaluates the polynomial at value fraction which must be in (or +expand to) a format acceptable to the xintfrac macros, and produces +a floating point number.

+
+

Attention!

+

Meaning was changed at 0.4. Formerly the evaluation point +could be given as an expression.

+
+
+
+
+

\PolIfCoeffIsPlusOrMinusOne{A}{B}

+
+

This macro is a priori undefined.

+

It is defined via the default \PolTypesetCmd{raw_coeff} to be +used if needed in the execution of \PolTypesetMonomialCmd, +e.g. to insert a \cdot in front of \PolVar^{\PolIndex} if +the coefficient is not plus or minus one.

+

The macro will execute A if the coefficient has been found to be +plus or minus one, and B if not.

+
+
+
+

\PolLeadingCoeff{polname}

+
+Expands to the leading coefficient.
+
-

\PolNthCoeff{polname}{number}

+

\PolNthCoeff{polname}{number}

It expands to the raw N-th coefficient (0/1[0] if the index number is out of range). With N=-1, -2, ... expands to the leading coefficients.
-

\PolDegree{polname}

+

\PolDegree{polname}

It expands to the degree. This is -1 if zero polynomial but this may change in future. Should it then expand to -\infty ?
-

\PolToExpr{polname}

+

\PolToExpr{polname}

-

Expands [4] to coeff_N*x^N+... (descending powers.)

- +

Expands [4] to coeff_N*x^N+... (descending powers.)

+
-
[4]in a \write, \edef, or \csname...\endcsname, but +
[4]in a \write, \edef, or \csname...\endcsname, but not under \romannumeral-`0.
@@ -885,7 +1497,7 @@ of \PolToExpr{f}, but a simple -

\PolToExprOneTerm{raw_coeff}{number}

+

\PolToExprOneTerm{raw_coeff}{number}

This two argument expandable command takes care of the monomial and its coefficient. The default definition is done in order for @@ -897,20 +1509,28 @@ always precedes the x^number, except if the co or a minus one. See \PolToExprTimes.

+
-

\PolToExprOneTermStyleB{raw_coeff}{number}

+

\PolToExprOneTermStyleB{raw_coeff}{number}

For output in this style:

 2*x^11/3+3*x^8/7-x^5−x^4/4−x^3−x^2/2−2*x+1
-

issue \let\PolToExprOneTerm\PolToExprOneTermStyleB before using -\PolToExpr. Note that then \PolToExprCmd isn't used at all.

+

issue \let\PolToExprOneTerm\PolToExprOneTermStyleB before usage of +\PolToExpr. Note that then \PolToExprCmd isn't used at all. +To revert to package default, issue +\let\PolToExprOneTerm\PolToExprOneTermStyleA.

To suppress the *'s, cf. \PolToExprTimes.

-

\PolToExprCmd{raw_coeff}

+

\PolToExprCmd{raw_coeff}

It is the one-argument macro used by the package definition of \PolToExprOneTerm for the coefficients themselves (when not @@ -920,21 +1540,21 @@ to \xintIrr{#1} or to output forcefully reduced coefficients.
-

\PolToExprTermPrefix{raw_coeff}

+

\PolToExprTermPrefix{raw_coeff}

Defined identically as \PolTypesetCmdPrefix{raw_coeff}. It prefixes with a plus sign for non-negative coefficients, because they don't carry one by themselves.
-
-

\PolToExprVar

+
+

\PolToExprVar

This expands to the variable to use in output (it does not have to be a single letter, may be an expandable macro.) Initial definition is x.
-
-

\PolToExprTimes

+
+

\PolToExprTimes

This expands to the symbol used for multiplication of an x^{number} by the corresponding coefficient. The default is @@ -943,41 +1563,39 @@ this will give output incompatible with some professional computer algebra software).
-
-

\PolToExpr*{polname}

+
+

\PolToExpr*{polname}

Expands to coeff_0+coeff_1*x+coeff_2*x^2+... (ascending powers). Customizable like \PolToExpr{polname} via the same macros.
-

\PolToFloatExpr{polname}

+

\PolToFloatExpr{polname}

Similar to \PolToExpr{polname} but uses \PolToFloatExprCmd which by default rounds and converts the coefficients to floating point format.

Note

-

The polynomial function for usage in \xintfloatexpr is -already prepared with the rounded coefficients, but the latter -are not easily recoverable (and especially not expandably) from -this. Thus \PolToFloatExprCmd operates from the exact -coefficients anew. This means though that if the prevailing float -precision was changed with \xintDigits:=P; syntax, the output -will obey this precision P, but the polynomial function was -defined earlier and operates on floating point numbers with -coefficients which were rounded at time of definition.

-

This may change in future, if the pre-rounded coefficients are -stored in a more easily accessible data structure.

+

It is not necessary to have issued +\PolGenFloatVariant{polname}. The rounded coefficients are +not easily recoverable from the \xintfloatexpr polynomial +function hence \PolToFloatExprCmd operates from the exact +coefficients anew.

+

Attention that both macros obey the prevailing float precision. +If it is changed between those macro calls, then a mismatch +exists between the coefficients as used in \xintfloatexpr and +those output by \PolToFloatExpr{polname}.

-

\PolToFloatExprOneTerm{raw_coeff}{number}

+

\PolToFloatExprOneTerm{raw_coeff}{number}

Similar to \PolToExprOneTerm. But does not treat especially coefficients equal to plus or minus one.
-

\PolToFloatExprCmd{raw_coeff}

+

\PolToFloatExprCmd{raw_coeff}

It is the one-argument macro used by \PolToFloatExprOneTerm. Its package definition is \xintFloat{#1}.

@@ -999,29 +1617,151 @@ in xintfrac raw format.

-
-

\PolToFloatExpr*{polname}

+
+

\PolToFloatExpr*{polname}

Typesets in ascending powers.
-

\PolToList{polname}

+

\PolToList{polname}

Expands to {coeff_0}{coeff_1}...{coeff_N} with N = degree (except zero polynomial which does give {0/1[0]} and not an empty output.)
-

\PolToCSV{polname}

+

\PolToCSV{polname}

Expands to coeff_0, coeff_1, coeff_2, ....., coeff_N. Converse to \PolFromCSV.
+
+

\PolSturmChainLength{sturmname}

+
+

Returns the integer N such that sturmname_N is the last one +in the Sturm chain sturmname_0, sturmname_1, ...

+

See \PolToSturm{polname}{sturmname}.

+
+
+
+

\PolSturmIfZeroExactlyKnown{sturmname}{index}{A}{B}

+
+

Executes A if the indexth interval reduces to a singleton, +i.e. the root is known exactly, else B.

+
+

Note

+

index may be a TeX count, or a \value{latexcounter}, or a +numerical expression as parsable by \numexpr: it does not +have to be given via explicit digits.

+

This remark applies also to the other package macros with +index being the name of the argument in this documentation. +There is also an out-of-range check done for some reasonable +error message (right before everything goes haywire).

+
+
+
+
+

\PolSturmIsolatedZeroLeft{sturmname}{index}

+
+Expands to the left end-point for the indexth interval +obtained via \PolSturmIsolateZeros{sturmname} and possibly +refined afterwards.
+
+
+

\PolSturmIsolatedZeroRight{sturmname}{index}

+
+Expands to the right end-point for the indexth interval +obtained via \PolSturmIsolateZeros{sturmname} and possibly +refined afterwards.
+
+
+

\PolSturmNbOfIsolatedZeros{sturmname}

+
+Expands to the number of real roots of the polynomial +<sturmname>_0 (which is the number of distinct real roots of the +polynomial used to create the Sturm chain via +\PolToSturm{polname}{sturmname}.
+
+
+

\PolIntervalWidth{sturmname}{index}

+
+The 10^E width of the current indexth root localization +interval. Output is in xintfrac raw 1/1[E] format (if not zero).
+
+
+

Macros for use within execution of \PolPrintIntervals

+

More precisely, they can be used within the replacement texts of the +\PolPrintIntervalsPrintLeftEndPoint, etc, macros.

+
+

\PolPrintIntervalsTheEndPoint

+
+Within a custom \PolPrintIntervalsPrintLeftEndPoint, custom +\PolPrintIntervalsPrintRightEndPoint, or custom +\PolPrintIntervalsPrintExactZero this macro expands to the left +or right end point of the considered interval. Serves as default +replacement for \PolPrintIntervalsPrintLeftEndPoint , etc...
+
+
+

\PolPrintIntervalsTheIndex

+
+Within a custom \PolPrintIntervalsPrintLeftEndPoint, custom +\PolPrintIntervalsPrintRightEndPoint, or custom +\PolPrintIntervalsPrintExactZero this macro expands to the index +of the considered interval. For example if user wants to print the +corresponding end points in red, the index value can thus be tested +in the replacement text of \PolPrintIntervalsPrintLeftEndPoint and +the other two similar macros.
+
+
+

\PolIfEndPointIsPositive{A}{B}

+
+Within a custom \PolPrintIntervalsPrintLeftEndPoint, custom +\PolPrintIntervalsPrintRightEndPoint, or custom +\PolPrintIntervalsPrintExactZero this macro executes A if +the considered interval end-point is positive, else B.
+
+
+

\PolIfEndPointIsNegative{A}{B}

+
+Within a custom \PolPrintIntervalsPrintLeftEndPoint, custom +\PolPrintIntervalsPrintRightEndPoint, or custom +\PolPrintIntervalsPrintExactZero this macro executes A if +the considered interval end-point is negative, else B.
+
+
+

\PolIfEndPointIsZero{A}{B}

+
+Within a custom \PolPrintIntervalsPrintLeftEndPoint, custom +\PolPrintIntervalsPrintRightEndPoint, or custom +\PolPrintIntervalsPrintExactZero this macro executes A if +the considered interval end-point is zero, else B.
+
+
+
+

\PolDecToString{decimal number}

+
+

This is a utility macro to print decimal numbers. Indeed for legacy +reasons, xintfrac does not yet have user-level ready-to-use macros +handling specifically the printing of decimal numbers from their +internal representations such as A/1[N].

+

For example +\PolDecToString{123.456e-8} will expand to 0.00000123456 +and \PolDecToString{123.450e-8} to 0.00000123450. This +illustrates that trailing zeros are not trimmed (to achieve that one +can use \PolDecToString{\xintREZ{#1}}.)

+

The macro does not try to identify if the fraction has a denominator +consisting only of two's and five's; such a denominator will be left +at right-end of output.

+

This utility macro will presumably be incorporated (possibly in a +more powerful form) to xintfrac (or rather to a decimal module) in +a future xint release.

+
+
-

Booleans (with default setting as indicated)

+

Booleans (with default setting as indicated)

-

\xintverbosefalse

+

\xintverbosefalse

This is actually an xintexpr configuration. Setting it to true triggers the writing of information to the log when new @@ -1034,20 +1774,20 @@ unstable and undocumented internal structures.

-

\poltypesetallfalse

+

\poltypesetallfalse

If true, \PolTypeset{polname} will also typeset the vanishing coefficients.
-

\poltoexprallfalse

+

\poltoexprallfalse

If true, \PolToExpr{polname} and \PolToFloatExpr{polname} will also include the vanishing coefficients in their outputs.
-

Technicalities

+

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 @@ -1058,7 +1798,7 @@ rather. The colon in := may be active with no

  • 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 +a/b + c/d with lcm(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.

    @@ -1082,7 +1822,8 @@ survive addition and multiplications:

    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.)

    +example is the least common multiple of the denominators of the +reduced coefficients.)

  • \PolDiff{polname_1}{polname_2} always applies \xintIrr to the resulting coefficients, except that the power of ten part [N] @@ -1111,53 +1852,193 @@ high degree and few coefficients (as an example with Tests have been made with Newton's iteration (for which computing -exactly the derivative is precisely what this package is made for) or -Regula Falsi method for locating roots: using exact computations leads -quickly to gigantic fractions (but dichotomy method much less so). It -is thus recommended to use \xintdeffloatvar or -\xintthefloatexpr contexts for any kind of numerical mathematics. -Of course, exact computations are invaluable for number theory or -combinatorics...

    -

  • As is to be expected internal structures of the package are barely documented and unstable. Don't use them.

-
-

RELEASES

+
+

CHANGE LOG

+ -

See README.md for the License and the change log (there were -some breaking changes from 0.2 to 0.3).

-

Acknowledgments

+

Acknowledgments

Thanks to Jürgen Gilg whose question about xint usage for differentiating polynomials was the initial trigger leading to this package, and to Jürgen Gilg and Thomas Söll for testing it on some concrete problems.

+

Renewed thanks on occasion of 0.4 release!

+

See README.md for the License.

diff --git a/Master/texmf-dist/doc/latex/polexpr/polexpr.txt b/Master/texmf-dist/doc/latex/polexpr/polexpr.txt index 2825128f004..3e064bc769e 100644 --- a/Master/texmf-dist/doc/latex/polexpr/polexpr.txt +++ b/Master/texmf-dist/doc/latex/polexpr/polexpr.txt @@ -4,12 +4,12 @@ Package polexpr documentation =============================== -0.3.1 (2018/01/18) -================== +0.4 (2018/02/16) +================ .. contents:: -First Examples +Basic Examples -------------- The syntax is:: @@ -68,7 +68,7 @@ from its default ``x``. $f''(z) = \PolTypeset[z]{f_xx}$\newline $f'''(z)= \PolTypeset[z]{d3f_dx3}$\par -.. important:: +.. important:: The package does not currently know rational functions: ``/`` in a parsed polynomial expression does the Euclidean quotient:: @@ -85,7 +85,7 @@ from its default ``x``. .. _warningtacit: -.. attention:: +.. attention:: ``1/2 x^2`` skips the space and is treated like ``1/(2*x^2)`` because of the tacit multiplication rules of \xintexpr. But this means it @@ -117,6 +117,209 @@ the macro call ``\PolGCD{f_1}{f_2}{k}`` sets ``k`` to the (unitary) GCD of ``\PolToExpr*{k}`` gives ascending powers: ``2-2*x-x^2+x^3``. +Examples of localization of roots +--------------------------------- + +First some remarks about auxiliaries. + +- To make printed decimal numbers more enjoyable than via + ``\xintSignedFrac``:: + + \renewcommand\PolTypesetOne[1]{\PolDecToString{\xintREZ{#1}}}% + + ``\PolDecToString`` will use decimal notation to incorporate the power + of ten part; and the ``\xintREZ`` will have the effect to suppress + trailing zeros if present in raw numerator (if those digits end up + after decimal mark.) Notice that the above are expandable macros and + that one can also do:: + + \renewcommand\PolToExprCmd[1]{\PolDecToString{\xintREZ{#1}}}% + + to modify output of `\\PolToExpr{polname}`_. + +- for extra info in log file ``\xintverbosetrue``. In fact one can also + work from command line then (I recommend ``rlwrap`` for encapsulating + ``latex``). + + +A typical example +~~~~~~~~~~~~~~~~~ + +:: + + \poldef f(x) := x^7 - x^6 - 2x + 1; + + \PolToSturm{f}{f} + \PolSturmIsolateZeros{f} + The \PolTypeset{f} polynomial has \PolSturmNbOfIsolatedZeros{f} distinct real + roots which are located in the following intervals: + \PolPrintIntervals{f} + Here is the second root with ten more decimal digits: + \PolRefineInterval[10]{f}{2} + \[\PolSturmIsolatedZeroLeft{f}{2}`_ in an undelimited macro + format (thus avoiding potential problems with the catcode of the + semi-colon in presence of some packages.) In absence of the + ``[letter]`` optional argument, the variable is assumed to be ``x``. + +.. _PolGenFloatVariant: + +``\PolGenFloatVariant{polname}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + Makes the polynomial also usable in the ``\xintfloatexpr`` parser. + It will therein evaluates via an Horner scheme with coefficients + already pre-rounded to the float precision. + + See also `\\PolToFloatExpr{polname}`_. + + .. attention:: + + Release ``0.3`` did this automatically on ``\PolDef`` and + ``\poldef`` but this was removed at ``0.4`` for optimization. + + Any operation, for example generating the derivative polynomial, + or dividing two polynomials or using the ``\PolLet``, **must** be + followed by explicit usage of ``\PolGenFloatVariant{polname}`` if + the new polynomial is to be used in ``\xintfloatexpr`` or alike + context. + +.. _PolLet: ``\PolLet{polname_2}={polname_1}`` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -187,6 +407,15 @@ Non-expandable macros ``\PolDef{polname_2}{polname_1(x)}`` but with less overhead. The ``=`` is optional. +.. _PolGlobalLet: + +``\PolGlobalLet{polname_2}={polname_1}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + Acts globally. + +.. _PolAssign: + ``\PolAssign{polname}\toarray\macro`` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -212,6 +441,8 @@ Non-expandable macros is the shift by one in indexing, mentioned above (negative indices act the same in both.) +.. _PolGet: + ``\PolGet{polname}\fromarray\macro`` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -228,7 +459,9 @@ Non-expandable macros 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.) + they were not subjected to ``\xintRaw`` or similar xintfrac_ macro.) + +.. _PolFromCSV: ``\PolFromCSV{polname}{}`` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -238,7 +471,7 @@ Non-expandable macros the constant term being the first item. No validity checks. Spaces from the list argument are trimmed. List items are each expanded in an ``\edef``, but currently left in their original form like e.g. - ``1.5e3`` which is not converted to ``15/1[2]`` *raw* xintfrac + ``1.5e3`` which is not converted to ``15/1[2]`` *raw* xintfrac_ format (this may change). Leading zero coefficients are removed:: @@ -249,6 +482,8 @@ Non-expandable macros See also expandable macro `\\PolToCSV <\\PolToCSV{polname}_>`_. +.. _PolTypeset: + ``\PolTypeset{polname}`` ~~~~~~~~~~~~~~~~~~~~~~~~ @@ -264,19 +499,32 @@ Non-expandable macros can be re-defined for customization. Their default definitions are expandable, but this is not a requirement. +.. _PolTypesetCmd: + ``\PolTypesetCmd{raw_coeff}`` ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ - Basically will use ``\xintSignedFrac`` from xintfrac_, but checks if - the coefficient is ``1`` or ``-1`` and then skips printing the - ``1``, except for the constant term... + Checks if the coefficient is ``1`` or ``-1`` and then skips printing + the ``1``, except for the constant term. Also it sets conditional + `\\PolIfCoeffIsPlusOrMinusOne{A}{B}`_. + + The actual printing of the coefficients, when not equal to plus or + minus one is handled by `\\PolTypesetOne{raw_coeff}`_. + +.. _PolTypesetOne: + +``\PolTypesetOne{raw_coeff}`` +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + + The default is ``\xintSignedFrac`` but this macro is annoying as it + insists to use a power of ten, and not decimal notation. One can do things such as for example: [#]_ :: - \renewcommand\PolTypesetCmd[1]{\num{\xintPFloat[5]{#1}}} - \renewcommand\PolTypesetCmd[1]{\num{\xintRound{4}{#1}}} + \renewcommand\PolTypesetOne[1]{\num{\xintPFloat[5]{#1}}} + \renewcommand\PolTypesetOne[1]{\num{\xintRound{4}{#1}}} where e.g. we used the ``\num`` macro of ``siunitx`` as it understands floating point notation. @@ -286,15 +534,10 @@ Non-expandable macros ``\xintPFloat`` by default uses the prevailing precision hence the extra argument like here ``5`` is an optional one. -``\PolTypesetCmdPrefix{raw_coeff}`` -^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + One can also give a try to using `\\PolDecToString{decimal number}`_ + which uses decimal notation (at least for the numerator part). - Expands to a ``+`` if the ``raw_coeff`` is zero or positive, and to - nothing if ``raw_coeff`` is negative, as in latter case the - ``\xintSignedFrac`` used by `\\PolTypesetCmd{raw_coeff}`_ will put - the ``-`` sign in front of the fraction (if it is a fraction) and - this will thus serve as separator in the typeset formula. Not used - for the first term. +.. _PolTypesetMonomialCmd: ``\PolTypesetMonomialCmd`` ^^^^^^^^^^^^^^^^^^^^^^^^^^ @@ -306,12 +549,28 @@ Non-expandable macros ``\PolIndex`` expands to digit tokens and needs termination in ``\ifnum`` tests. +.. _PolTypesetCmdPrefix: + +``\PolTypesetCmdPrefix{raw_coeff}`` +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + + Expands to a ``+`` if the ``raw_coeff`` is zero or positive, and to + nothing if ``raw_coeff`` is negative, as in latter case the + ``\xintSignedFrac`` used by `\\PolTypesetCmd{raw_coeff}`_ will put + the ``-`` sign in front of the fraction (if it is a fraction) and + this will thus serve as separator in the typeset formula. Not used + for the first term. + +.. _PolTypeset*: + ``\PolTypeset*{polname}`` ~~~~~~~~~~~~~~~~~~~~~~~~~ Typesets in ascending powers. Use e.g. ``[h]`` optional argument (after the ``*``) to use letter ``h`` rather than ``x``. +.. _PolDiff: + ``\PolDiff{polname_1}{polname_2}`` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -322,6 +581,8 @@ Non-expandable macros Coefficients of the result ``polname_2`` are irreducible fractions (see `Technicalities`_ for the whole story.) +.. _PolDiff[N]: + ``\PolDiff[N]{polname_1}{polname_2}`` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -330,6 +591,8 @@ Non-expandable macros ``\PolLet{polname_2}={polname_1}``. With negative ``N``, switches to using ``\PolAntiDiff``. +.. _PolAntiDiff: + ``\PolAntiDiff{polname_1}{polname_2}`` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -339,12 +602,16 @@ Non-expandable macros Coefficients of the result ``polname_2`` are irreducible fractions (see `Technicalities`_ for the whole story.) +.. _PolAntiDiff[N]: + ``\PolAntiDiff[N]{polname_1}{polname_2}`` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ This sets ``polname_2`` to the result of ``N`` successive integrations on ``polname_1``. With negative ``N``, it switches to using ``\PolDiff``. +.. _PolDivide: + ``\PolDivide{polname_1}{polname_2}{polname_Q}{polname_R}`` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -352,12 +619,314 @@ Non-expandable macros remainder in the Euclidean division of ``polname_1`` by ``polname_2``. +.. _PolQuo: + +``\PolQuo{polname_1}{polname_2}{polname_Q}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + This sets ``polname_Q`` to be the quotient in the Euclidean division + of ``polname_1`` by ``polname_2``. + +.. _PolRem: + +``\PolRem{polname_1}{polname_2}{polname_R}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + This sets ``polname_R`` to be the remainder in the Euclidean division + of ``polname_1`` by ``polname_2``. + +.. _PolGCD: + ``\PolGCD{polname_1}{polname_2}{polname_GCD}`` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ - This sets ``polname_GCD`` to be the G.C.D. It is a unitary - polynomial except if both ``polname_1`` and ``polname_2`` vanish, - then ``polname_GCD`` is the zero polynomial. + This sets ``polname_GCD`` to be the (monic) GCD of the two first + polynomials. It is a unitary polynomial except if both ``polname_1`` + and ``polname_2`` vanish, then ``polname_GCD`` is the zero + polynomial. + +.. ``\PolIGCD{polname_1}{polname_2}{polname_iGCD}`` + ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + **NOT YET** + + This **assumes** that the two polynomials have integer coefficients. + It then computes the greatest common divisor in the integer + polynomial ring, normalized to have a positive leading coefficient + (if the inputs are not both zero). + + ``\PolIContent{polname}`` + ~~~~~~~~~~~~~~~~~~~~~~~~~ + + **NOT YET** + + This computes a positive rational number such that dividing the + polynomial with it returns an integer coefficients polynomial with + no common factor among the coefficients. + +.. _PolToSturm: + +``\PolToSturm{polname}{sturmname}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + With, for example, ``polname`` being ``P`` and ``sturmname`` being + ``S``, the macro starts by computing polynomials ``S_0 = P``, ``S_1 + = P'``, ..., with ``S_{n+1}`` the opposite of the remainder of + euclidean division of ``S_{n-1}`` by ``S_{n}``. The last non-zero + remainder ``S_N`` is up to a factor the GCD of ``P`` and ``P'`` + hence a constant if and only if ``P`` is square-free. + + In case ``S_N`` is not a constant, the macro then goes on with + dividing all ``S_k``'s with ``S_N`` (which becomes ``1``). + + Thus ``S_0`` now has exactly the same real and complex + roots as polynomial ``polname``, but each with multiplicity one. + +.. _PolToSturm*: + +``\PolToSturm*{polname}{sturmname}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + Does not divide the Sturm chain by its last element. + +.. _PolSetToSturmChainSignChangesAt: + +``\PolSetToSturmChainSignChangesAt{\macro}{sturmname}{fraction}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + Sets macro ``\macro`` to the number of sign changes in the Sturm + chain with name prefix ``sturmname``, at location ``fraction`` + (which must be in format as acceptable by the xintfrac_ macros.) + + .. note:: + + The author was lazy and did not provide rather an expandable + variant, where one would do ``\edef\macro{\PolNbOf...}``. + + This will presumably get added in a future release. + + After some hesitation it was decided the macro would by default + act globally. To make the scope of its macro definition local, + use ``[\empty]`` as extra optional argument. + +.. _PolSetToNbOfZerosWithin: + +``\PolSetToNbOfZerosWithin{\macro}{sturmname}{value_a}{value_b}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + Applies the `Sturm Theorem`_ to set ``\macro`` to the exact number + of distinct roots of ``sturmname_0`` in the interval ``(value_a, + value_b]`` (the macro first re-orders the value for ``value_a <= + value_b`` to hold). + + .. note:: + + The author was lazy and did not provide rather an expandable + variant, where one would do ``\edef\macro{\PolNbOf...}``. + + This will presumably get added in future. + + After some hesitation it was decided the macro would by default + act globally. To make the scope of its macro definition local, + use ``[\empty]`` as extra optional argument. + +.. _PolSturmIsolateZeros: + +``\PolSturmIsolateZeros{sturmname}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + First, it evaluates using `Sturm theorem`_ the number of distinct + real roots of ``sturmname_0``. + + .. important:: + + The Sturm chain **must** be of the reduced type, i.e. + as constructed via `\\PolToSturm{polname}{sturmname}`_. + + Then it locates, again using `Sturm theorem`_, as many disjoint + intervals as there are roots. Some intervals reduce to singleton + which are roots. Non-singleton intervals get refined to make sure + none of their two limit points is a root: they contain each a single + root, in their respective interiors. + + .. This procedure is covariant + with the independent variable ``x`` becoming ``-x``. + Hmm, pas sûr et trop fatigué + + The interval boundaries are decimal numbers, originating + in iterated decimal subdivision from initial intervals + ``(-10^E, 0)`` and ``(0, 10^E)``; if zero is a root it is always + identified individually. The non-singleton intervals are of the + type ``(a/10^f, (a+1)/10^f)`` with ``a`` an integer, which is + neither ``0`` nor ``-1``. Hence ``a`` and ``a+1`` are both positive + or both negative. + + The interval boundaries (and exactly found roots) are made available + for future computations in ``\xintexpr``-essions or polynomial + definitions as variables ``L_1``, + ``L_2``, etc..., for the left end-points and + ``R_1``, ``R_2``, ..., for the right + end-points. + + Also two macro arrays (in the sense of + xinttools_'s ``\xintAssignArray``) are created for holding the + interval end-points written out in standard decimal notation + (see `\\PolDecToString{decimal number}`_). + To access these values, macros + `\\PolSturmIsolatedZeroLeft{sturmname}{index}`_ and + `\\PolSturmIsolatedZeroRight{sturmname}{index}`_ are provided. + + .. important:: + + Trailing zeroes in these stored decimal numbers are significant: + they are also present in the decimal expansion of the exact root. + + .. note:: + + The actual array macros are ``\POL_ZeroIntL`` and + ``\POL_ZeroIntR`` but as these names use the + non-letter character ``_`` and possibly also digits from + ``sturmname``, the accessor macros above have been made part of + the package. + + The start of decimal expansion of a positive ``k``-th root is given + by ``\PolSturmIsolatedZeroLeft{sturmname}{k}``, and for a negative + root it is given by ``\PolSturmIsolatedZeroRight{sturmname}{k}``. + These two decimal numbers are either both zero or both of the same + sign. + + The number of distinct roots is obtainable as + ``\PolSturmNbOfIsolatedZeros{sturmname}``. + + .. note:: + + In the current implementation the ``...`` variables + and the ``\POL_ZeroInt...`` arrays are globally defined. On the + other hand the Sturm sequence polynomials obey the current scope. + + .. note:: + + When two successive roots are located in adjacent intervals, the + separation between them is not lower bounded. See + `\\PolRefineInterval*{sturmname}{index}`_. + + .. note:: + + As all computations are done *exactly* there can be no errors... + apart those due to bad coding by author. The results are exact + bounds for the mathematically exact real roots. + + Future releases will perhaps also provide macros based on Newton + or Regula Falsi methods. Exact computations with such methods + lead however quickly to very big fractions, and this forces usage + of some rounding scheme for the abscissas if computation times + are to remain reasonable. This raises issues of its own, which + are studied in numerical mathematics. + +.. _PolRefineInterval*: + +``\PolRefineInterval*{sturmname}{index}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + The ``index``\ -th interval (starting indexing at one) is further + subdivided as many times as is necessary in order for the newer + interval to have both its end-points distinct from the end-points of + the original interval. This means that the ``k``\ th root is then + strictly separated from the other roots. + +.. _PolRefineInterval[N]: + +``\PolRefineInterval[N]{sturmname}{index}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + The ``index``\ -th interval (starting count at one) is further + subdivided once, reducing its length by a factor of 10. This is done + ``N`` times if the optional argument ``[N]`` is present. + +.. _PolEnsureIntervalLength: + +``\PolEnsureIntervalLength{sturmname}{index}{E}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + The ``index``\ -th interval is subdivided until its length becomes at + most ``10^E``. This means (for ``E<0``) that the first ``-E`` digits + after decimal mark of the ``k``\ th root will then be known exactly. + +.. _PolEnsureIntervalLengths: + +``\PolEnsureIntervalLengths{sturmname}{E}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + The intervals as obtained from ``\PolSturmIsolateZeros`` are (if + necessary) subdivided further by (base 10) dichotomy in order for + each of them to have length at most ``10^E`` (length will be shorter + than ``10^E`` in output only if it did not change or became zero.) + + This means that decimal expansions of all roots will be known with + ``-E`` digits (for ``E<0``) after decimal mark. + +.. _PolPrintIntervals: + +``\PolPrintIntervals[varname]{sturmname}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + This is a convenience macro which prints the bounds for the roots + ``Z_1``, ``Z_2``, ... (the optional argument ``varname`` allows to + specify a replacement for the default ``Z``). This will be done in a + math mode ``array``, one interval per row, and pattern ``rcccl``, + where the second and fourth column hold the ``<`` sign, except when + the interval reduces to a singleton, which means the root is known + exactly. The user is invited to renewcommand the macro if some other + type of tabular environment for example is wanted. + + In each array cell the corresponding interval end-point (which may + be an exactly known root) is available as macro + `\\PolPrintIntervalsTheEndPoint`_ (in decimal notation). And the + corresponding interval index is available as + `\\PolPrintIntervalsTheIndex`_. + + These values may be tested to decide some on-the-fly customization + (color for example), via the following auxiliaries which can be + modified by user. Furthermore these auxiliaries can also use the + following conditionals: `\\PolIfEndPointIsPositive{A}{B}`_, + `\\PolIfEndPointIsNegative{A}{B}`_, `\\PolIfEndPointIsZero{A}{B}`_. + +.. _PolPrintIntervalsPrintExactZero: + +``\PolPrintIntervalsPrintExactZero`` +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + This is provided to help customize how an exactly known root is + printed in the right most column of the array. The package + definition is:: + + \newcommand\PolPrintIntervalsPrintExactZero{\PolPrintIntervalsTheEndPoint}% + + Recall that this is expanded in an array cell. + + If for example you want to print in red the third root, known + exactly, the macro could make a test for the value of + `\\PolPrintIntervalsTheIndex`_ and act accordingly. + + +.. _PolPrintIntervalsPrintLeftEndPoint: + +``\PolPrintIntervalsPrintLeftEndPoint`` +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + + Package definition is:: + + \newcommand\PolPrintIntervalsPrintLeftEndPoint{\PolPrintIntervalsTheEndPoint}% + +.. _PolPrintIntervalsPrintRightEndPoint: + +``\PolPrintIntervalsPrintRightEndPoint`` +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + + Package definition is:: + + \newcommand\PolPrintIntervalsPrintRightEndPoint{\PolPrintIntervalsTheEndPoint}% + +.. _PolMapCoeffs: ``\PolMapCoeffs{\macro}{polname}`` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -371,7 +940,7 @@ Non-expandable macros 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. + will have to be expressed in terms of macros from xintfrac_ package. Example:: @@ -380,6 +949,8 @@ Non-expandable macros (or with ``\xintSqr{\index}``) to replace ``n``-th coefficient ``f_n`` by ``f_n*n^2``. +.. _PolReduceCoeffs: + ``\PolReduceCoeffs{polname}`` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -388,6 +959,39 @@ Non-expandable macros polynomial function is used for computations.) This is a one-argument macro, working 'in-place'. +.. _PolReduceCoeffs*: + +``\PolReduceCoeffs*{polname}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + This starred variant leaves un-touched the decimal exponent in the + internal representation of the fractional coefficients, i.e. if a + coefficient is internally ``A/B[N]``, then ``A/B`` is reduced to + smallest terms, but the ``10^N`` part is kept as is. Note: if the + polynomial is freshly defined directly via `\\PolFromCSV + `_ its coefficients might still be internally in some + format like ``1.5e7``; the macro will anyhow always first do the + needed conversion to strict format ``A/B[N]``. + + Evaluations with polynomials treated by this can be much faster than + with those handled by the non-starred variant + `\\PolReduceCoeffs{polname}`_: as the numerators and denominators + remain smaller, this proves very beneficial in favorable cases + (especially when the coefficients are decimal numbers) to the + expansion speed of the xintfrac_ macros used internally by + `\\PolEval `_. + +.. _PolMakeMonic: + +``\PolMakeMonic{polname}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~ + + Divides by the leading coefficient. It is recommended to execute + `\\PolReduceCoeffs*{polname}`_ immediately afterwards. This is not + done automatically, due to the case the original polynomial had integer + coefficients and we want to keep the leading one as common + denominator. + Expandable macros ----------------- @@ -395,38 +999,67 @@ All these macros expand completely in two steps except ``\PolToExpr`` and ``\PolToFloatExpr`` (and their auxiliaries) which need a ``\write``, ``\edef`` or a ``\csname...\endcsname`` context. -``\PolEval{polname}\At{numerical expression}`` -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +.. _PolEvalAtExpr: - It boils down to ``\xinttheexpr polname(numerical expression)\relax``. +``\PolEval{polname}\AtExpr{numerical expression}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ - .. note:: + It boils down to + ``\xinttheexpr polname(numerical expression)\relax``. + + +.. _PolEvalAt: + +``\PolEval{polname}\At{fraction}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ - The ``0.2`` version stupidly tried to be clever and as a result - of a misguided optimization choked if ``value`` was not a number - but a numerical expression (a sum e.g.), but the more powerful - behaviour has been reinstored at ``0.3`` release. + Evaluates the polynomial at value ``fraction`` which must be in (or + expand to) a format acceptable to the xintfrac_ macros. - The ``0.1`` and ``0.2`` version did a ``reduce`` which however is - costly on big fractions and irrelevant if the output is served as - argument of ``\xintRound`` or ``\xintFloat``. Thus ``reduce`` was - removed, and former meaning is now available as - `\\PolEvalReduced{polname}\\At{numerical expression}`_ + .. attention:: -``\PolEvalReduced{polname}\At{numerical expression}`` -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + Meaning was changed at ``0.4``. Formerly ``\PolEval{P}\At{foo}`` + accepted for ``foo`` an expression which was handled by + ``\xintexpr``. See `\\PolEval{polname}\\AtExpr{numerical + expression}`_. + + In particular, to use an ``\xintexpr`` user-declared variable (or + e.g. the variables as defined by `\\PolSturmIsolateZeros + `_) one **must** use the ``\AtExpr`` syntax. + +.. _PolEvalReducedAtExpr: + +``\PolEvalReduced{polname}\AtExpr{numerical expression}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Boils down to ``\xinttheexpr reduce(polname(numerical expression))\relax``. -``\PolFloatEval{polname}\At{numerical expression}`` -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +.. _PolEvalReducedAt: + +``\PolEvalReduced{polname}\At{fraction}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + Evaluates the polynomial at value ``fraction`` which must be in (or + expand to) a format acceptable to the xintfrac_ macros, and produce + an irreducible fraction. + + .. attention:: + + Meaning was changed at ``0.4``. Formerly the evaluation point + could be given as an expression. + +.. _PolFloatEvalAtExpr: + +``\PolFloatEval{polname}\AtExpr{numerical expression}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Boils down to ``\xintthefloatexpr polname(numerical expression)\relax``. - This is done via a Horner Scheme (see `\\poldef `_), with - already rounded coefficients. [#]_ To use the *exact coefficients* - (and *exact* additions and multiplications), just insert it in the - float expression as in this example: [#]_ + This is done via a Horner Scheme (see `\\poldef `_ and + `\\PolGenFloatVariant{polname}`_), with already rounded + coefficients. [#]_ To use the *exact coefficients* with *exactly + executed* additions and multiplications, just insert it in the float + expression as in this example: [#]_ :: @@ -436,12 +1069,56 @@ and ``\PolToFloatExpr`` (and their auxiliaries) which need a getting raised to the power ``2``. Moving the ``^2`` inside, that operation would also be treated exactly. + .. attention:: + + At ``polexpr 0.3``, polynoms were automatically also prepared for + use in floating point contexts. This got dropped at ``0.4`` for + optimization purposes. See `\\PolGenFloatVariant{polname}`_. + .. [#] Anyway each floating point operation starts by rounding its operands to the floating point precision. - .. [#] The ``\xintexpr`` could be ``\xinttheexpr`` but that would be - less efficient. Cf. xintexpr_ documentation about nested - expressions. + .. [#] The ``\xintexpr`` here could be ``\xinttheexpr`` but that + would be less efficient. Cf. xintexpr_ documentation about + nested expressions. + +.. _PolFloatEvalAt: + +``\PolFloatEval{polname}\At{fraction}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + Evaluates the polynomial at value ``fraction`` which must be in (or + expand to) a format acceptable to the xintfrac_ macros, and produces + a floating point number. + + .. attention:: + + Meaning was changed at ``0.4``. Formerly the evaluation point + could be given as an expression. + +.. _PolIfCoeffIsPlusOrMinusOne: + +``\PolIfCoeffIsPlusOrMinusOne{A}{B}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + This macro is a priori undefined. + + It is defined via the default `\\PolTypesetCmd{raw_coeff}`_ to be + used if needed in the execution of `\\PolTypesetMonomialCmd`_, + e.g. to insert a ``\cdot`` in front of ``\PolVar^{\PolIndex}`` if + the coefficient is not plus or minus one. + + The macro will execute ``A`` if the coefficient has been found to be + plus or minus one, and ``B`` if not. + +.. _PolLeadingCoeff: + +``\PolLeadingCoeff{polname}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + Expands to the leading coefficient. + +.. _PolNthCoeff: ``\PolNthCoeff{polname}{number}`` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -450,12 +1127,16 @@ and ``\PolToFloatExpr`` (and their auxiliaries) which need a number is out of range). With ``N=-1``, ``-2``, ... expands to the leading coefficients. +.. _PolDegree: + ``\PolDegree{polname}`` ~~~~~~~~~~~~~~~~~~~~~~~ It expands to the degree. This is ``-1`` if zero polynomial but this may change in future. Should it then expand to ``-\infty`` ? +.. _PolToExpr: + ``\PolToExpr{polname}`` ~~~~~~~~~~~~~~~~~~~~~~~ @@ -480,6 +1161,8 @@ and ``\PolToFloatExpr`` (and their auxiliaries) which need a of ``\PolToExpr{f}``, but a simple ``f(x)`` is more efficient for the identical result. +.. _PolToExprOneTerm: + ``\PolToExprOneTerm{raw_coeff}{number}`` ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ @@ -493,6 +1176,16 @@ and ``\PolToFloatExpr`` (and their auxiliaries) which need a always precedes the ``x^number``, except if the coefficient is a one or a minus one. See `\\PolToExprTimes`_. +.. _PolToExprOneTermStyleA: + +``\PolToExprOneTermStyleA{raw_coeff}{number}`` +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + + Holds the default package meaning of + `\\PolToExprOneTerm{raw_coeff}{number}`_. + +.. _PolToExprOneTermStyleB: + ``\PolToExprOneTermStyleB{raw_coeff}{number}`` ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ @@ -500,11 +1193,15 @@ and ``\PolToFloatExpr`` (and their auxiliaries) which need a 2*x^11/3+3*x^8/7-x^5−x^4/4−x^3−x^2/2−2*x+1 - issue ``\let\PolToExprOneTerm\PolToExprOneTermStyleB`` before using + issue ``\let\PolToExprOneTerm\PolToExprOneTermStyleB`` before usage of ``\PolToExpr``. Note that then ``\PolToExprCmd`` isn't used at all. + To revert to package default, issue + ``\let\PolToExprOneTerm\PolToExprOneTermStyleA``. To suppress the ``*``'s, cf. `\\PolToExprTimes`_. +.. _PolToExprCmd: + ``\PolToExprCmd{raw_coeff}`` ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ @@ -515,6 +1212,8 @@ and ``\PolToFloatExpr`` (and their auxiliaries) which need a to ``\xintIrr{#1}`` or to ``\xintPRaw{\xintIrr{#1}}`` to obtain in the output forcefully reduced coefficients. +.. _PolToExprTermPrefix: + ``\PolToExprTermPrefix{raw_coeff}`` ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ @@ -522,6 +1221,8 @@ and ``\PolToFloatExpr`` (and their auxiliaries) which need a prefixes with a plus sign for non-negative coefficients, because they don't carry one by themselves. +.. _PolToExprVar: + ``\PolToExprVar`` ^^^^^^^^^^^^^^^^^ @@ -529,6 +1230,8 @@ and ``\PolToFloatExpr`` (and their auxiliaries) which need a be a single letter, may be an expandable macro.) Initial definition is ``x``. +.. _PolToExprTimes: + ``\PolToExprTimes`` ^^^^^^^^^^^^^^^^^^^ @@ -538,12 +1241,16 @@ and ``\PolToFloatExpr`` (and their auxiliaries) which need a this will give output incompatible with some professional computer algebra software). +.. _PolToExpr*: + ``\PolToExpr*{polname}`` ~~~~~~~~~~~~~~~~~~~~~~~~ Expands to ``coeff_0+coeff_1*x+coeff_2*x^2+...`` (ascending powers). Customizable like `\\PolToExpr{polname}`_ via the same macros. +.. _PolToFloatExpr: + ``\PolToFloatExpr{polname}`` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -554,18 +1261,18 @@ and ``\PolToFloatExpr`` (and their auxiliaries) which need a .. note:: - The polynomial function for usage in ``\xintfloatexpr`` is - already prepared with the rounded coefficients, but the latter - are not easily recoverable (and especially not expandably) from - this. Thus ``\PolToFloatExprCmd`` operates from the *exact* - coefficients anew. This means though that if the prevailing float - precision was changed with ``\xintDigits:=P;`` syntax, the output - will obey this precision ``P``, but the polynomial function was - defined earlier and operates on floating point numbers with - coefficients which were rounded at time of definition. + It is not necessary to have issued + `\\PolGenFloatVariant{polname}`_. The rounded coefficients are + not easily recoverable from the ``\xintfloatexpr`` polynomial + function hence ``\PolToFloatExprCmd`` operates from the *exact* + coefficients anew. - This may change in future, if the pre-rounded coefficients are - stored in a more easily accessible data structure. + Attention that both macros obey the prevailing float precision. + If it is changed between those macro calls, then a mismatch + exists between the coefficients as used in ``\xintfloatexpr`` and + those output by ``\PolToFloatExpr{polname}``. + +.. _PolToFloatExprOneTerm: ``\PolToFloatExprOneTerm{raw_coeff}{number}`` ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ @@ -574,6 +1281,8 @@ and ``\PolToFloatExpr`` (and their auxiliaries) which need a <\\PolToExprOneTerm{raw_coeff}{number}>`_. But does not treat especially coefficients equal to plus or minus one. +.. _PolToFloatExprCmd: + ``\PolToFloatExprCmd{raw_coeff}`` ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ @@ -596,11 +1305,15 @@ and ``\PolToFloatExpr`` (and their auxiliaries) which need a optimization (I can't help it) because ``#1`` is known to be in ``xintfrac`` raw format. +.. _PolToFloatExpr*: + ``\PolToFloatExpr*{polname}`` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Typesets in ascending powers. +.. _PolToList: + ``\PolToList{polname}`` ~~~~~~~~~~~~~~~~~~~~~~~ @@ -608,12 +1321,165 @@ and ``\PolToFloatExpr`` (and their auxiliaries) which need a (except zero polynomial which does give ``{0/1[0]}`` and not an empty output.) +.. _PolToCSV: + ``\PolToCSV{polname}`` ~~~~~~~~~~~~~~~~~~~~~~ Expands to ``coeff_0, coeff_1, coeff_2, ....., coeff_N``. Converse to `\\PolFromCSV <\\PolFromCSV{polname}{\}_>`_. +.. _PolSturmChainLength: + +``\PolSturmChainLength{sturmname}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + Returns the integer ``N`` such that ``sturmname_N`` is the last one + in the Sturm chain ``sturmname_0``, ``sturmname_1``, ... + + See `\\PolToSturm{polname}{sturmname}`_. + +.. _PolSturmIfZeroExactlyKnown: + +``\PolSturmIfZeroExactlyKnown{sturmname}{index}{A}{B}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + Executes ``A`` if the ``index``\ th interval reduces to a singleton, + i.e. the root is known exactly, else ``B``. + + .. note:: + + ``index`` may be a TeX count, or a ``\value{latexcounter}``, or a + numerical expression as parsable by ``\numexpr``: it does not + have to be given via explicit digits. + + This remark applies also to the other package macros with + ``index`` being the name of the argument in this documentation. + There is also an out-of-range check done for some reasonable + error message (right before everything goes haywire). + + +.. _PolSturmIsolatedZeroLeft: + +``\PolSturmIsolatedZeroLeft{sturmname}{index}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + Expands to the left end-point for the ``index``\ th interval + obtained via `\\PolSturmIsolateZeros{sturmname}`_ and possibly + refined afterwards. + +.. _PolSturmIsolatedZeroRight: + +``\PolSturmIsolatedZeroRight{sturmname}{index}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + Expands to the right end-point for the ``index``\ th interval + obtained via `\\PolSturmIsolateZeros{sturmname}`_ and possibly + refined afterwards. + +.. _PolSturmNbOfIsolatedZeros: + +``\PolSturmNbOfIsolatedZeros{sturmname}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + Expands to the number of real roots of the polynomial + ``_0`` (which is the number of distinct real roots of the + polynomial used to create the Sturm chain via + `\\PolToSturm{polname}{sturmname}`_. + +.. _PolIntervalWidth: + +``\PolIntervalWidth{sturmname}{index}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + The ``10^E`` width of the current ``index``\ th root localization + interval. Output is in xintfrac_ raw ``1/1[E]`` format (if not zero). + +Macros for use within execution of ``\PolPrintIntervals`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +More precisely, they can be used within the replacement texts of the +`\\PolPrintIntervalsPrintLeftEndPoint`_, etc, macros. + + +.. _PolPrintIntervalsTheEndPoint: + +``\PolPrintIntervalsTheEndPoint`` +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + + Within a custom `\\PolPrintIntervalsPrintLeftEndPoint`_, custom + `\\PolPrintIntervalsPrintRightEndPoint`_, or custom + `\\PolPrintIntervalsPrintExactZero`_ this macro expands to the left + or right end point of the considered interval. Serves as default + replacement for `\\PolPrintIntervalsPrintLeftEndPoint`_ , etc... + +.. _PolPrintIntervalsTheIndex: + +``\PolPrintIntervalsTheIndex`` +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + + Within a custom `\\PolPrintIntervalsPrintLeftEndPoint`_, custom + `\\PolPrintIntervalsPrintRightEndPoint`_, or custom + `\\PolPrintIntervalsPrintExactZero`_ this macro expands to the index + of the considered interval. For example if user wants to print the + corresponding end points in red, the index value can thus be tested + in the replacement text of `\\PolPrintIntervalsPrintLeftEndPoint`_ and + the other two similar macros. + +.. _PolIfEndPointIsPositive: + +``\PolIfEndPointIsPositive{A}{B}`` +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + + Within a custom `\\PolPrintIntervalsPrintLeftEndPoint`_, custom + `\\PolPrintIntervalsPrintRightEndPoint`_, or custom + `\\PolPrintIntervalsPrintExactZero`_ this macro executes ``A`` if + the considered interval end-point is positive, else ``B``. + +.. _PolIfEndPointIsNegative: + +``\PolIfEndPointIsNegative{A}{B}`` +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + + Within a custom `\\PolPrintIntervalsPrintLeftEndPoint`_, custom + `\\PolPrintIntervalsPrintRightEndPoint`_, or custom + `\\PolPrintIntervalsPrintExactZero`_ this macro executes ``A`` if + the considered interval end-point is negative, else ``B``. + +.. _PolIfEndPointIsZero: + +``\PolIfEndPointIsZero{A}{B}`` +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + + Within a custom `\\PolPrintIntervalsPrintLeftEndPoint`_, custom + `\\PolPrintIntervalsPrintRightEndPoint`_, or custom + `\\PolPrintIntervalsPrintExactZero`_ this macro executes ``A`` if + the considered interval end-point is zero, else ``B``. + +.. _PolDecToString: + +``\PolDecToString{decimal number}`` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + This is a utility macro to print decimal numbers. Indeed for legacy + reasons, xintfrac_ does not yet have user-level ready-to-use macros + handling specifically the printing of decimal numbers from their + internal representations such as ``A/1[N]``. + + For example + ``\PolDecToString{123.456e-8}`` will expand to ``0.00000123456`` + and ``\PolDecToString{123.450e-8}`` to ``0.00000123450``. This + illustrates that trailing zeros are not trimmed (to achieve that one + can use ``\PolDecToString{\xintREZ{#1}}``.) + + The macro does not try to identify if the fraction has a denominator + consisting only of two's and five's; such a denominator will be left + at right-end of output. + + This utility macro will presumably be incorporated (possibly in a + more powerful form) to xintfrac_ (or rather to a decimal module) in + a future xint_ release. + Booleans (with default setting as indicated) -------------------------------------------- @@ -656,7 +1522,7 @@ Technicalities - 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 + ``a/b + c/d`` with ``lcm(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. @@ -681,7 +1547,8 @@ Technicalities 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.) + example is the least common multiple of the denominators of the + reduced coefficients.) - `\\PolDiff{polname_1}{polname_2}`_ always applies ``\xintIrr`` to the resulting coefficients, except that the *power of ten* part ``[N]`` @@ -712,49 +1579,163 @@ Technicalities additions involvings only zeroes... which does take time). This may change in the future. -- Tests have been made with Newton's iteration (for which computing - exactly the derivative is precisely what this package is made for) or - Regula Falsi method for locating roots: using exact computations leads - quickly to gigantic fractions (but dichotomy method much less so). It - is thus recommended to use ``\xintdeffloatvar`` or - ``\xintthefloatexpr`` contexts for any kind of numerical mathematics. - Of course, exact computations are invaluable for number theory or - combinatorics... - - As is to be expected internal structures of the package are barely documented and unstable. Don't use them. -RELEASES --------- - -- 0.1 (2018/01/11) - - Initial release (files README, polexpr.sty). - -- 0.2 (2018/01/14) - - Documentation moved to polexpr.{txt,html}. -- 0.3 (2018/01/17) - - Make polynomials known to ``\xintfloatexpr`` and improve - documentation. +CHANGE LOG +---------- + +- v0.1 (2018/01/11): initial release. Features: + + * The `\\poldef `_ parser itself, + * Differentiation and anti-differentiation, + * Euclidean division and GCDs, + * Various utilities such as `\\PolFromCSV `_, + `\\PolMapCoeffs `_, + `\\PolToCSV `_, `\\PolToExpr `_, ... + + Only one-variable polynomials so far. + +- v0.2 (2018/01/14) + + * Fix: ``"README thinks \numexpr recognizes ^ operator"``. + * Convert README to reStructuredText markup. + * Move main documentation from README to separate ``polexpr.txt`` file. + * Provide ``polexpr.html`` as obtained via DocUtils_ ``rst2html.py``. + * Convert README to (CTAN compatible) Markdown markup. + + Due to lack of available time the test suite might not be extensive + enough. Bug reports are very welcome! + +- v0.3 (2018/01/17) + + * bug fixes: + + - the ``0.1`` `\\PolEval `_ accepted expressions for its second + argument, but this was removed by mistake at ``0.2``. Restored. + + **Attention**: at ``0.4`` this has been reverted again, and + `\\PolEval{P}\\AtExpr{foo} `_ syntax is needed for + using expressions in the second argument. + * incompatible or breaking changes: + + - `\\PolToExpr `_ now by default uses *descending* + powers (it also treats differently coefficients equal to 1 or -1.) + Use `\\PolToExpr* `_ for *ascending* powers. + - `\\PolEval `_ reduced the output to smallest terms, + but as this is costly with big fractions and not needed if e.g. + wrapped in an ``\xintRound`` or ``\xintFloat``, this step has been + removed; the former meaning is available as `\\PolEvalReduced + `_. + * new (or newly documented) macros: + + - `\\PolTypesetCmd `_ + - `\\PolTypesetCmdPrefix `_ + - `\\PolTypesetMonomialCmd `_ + - `\\PolEvalReducedAt `_ + - `\\PolToFloatExpr `_ + - `\\PolToExprOneTerm `_ + - `\\PolToFloatExprOneTerm `_ + - `\\PolToExprCmd `_ + - `\\PolToFloatExprCmd `_ + - `\\PolToExprTermPrefix `_ + - `\\PolToExprVar `_ + - `\\PolToExprTimes `_ + * improvements: + + - documentation has a table of contents, internal hyperlinks, + standardized signature notations and added explanations. + - one can do ``\PolLet{g}={f}`` or ``\PolLet{g}{f}``. + - ``\PolToExpr{f}`` is highly customizable. + - `\\poldef `_ and other defining macros prepare the polynomial + functions for usage within ``\xintthefloatexpr`` (or + ``\xintdeffloatvar``). Coefficients are pre-rounded to the + floating point precision. Indispensible for numerical algorithms, + as exact fractions, even reduced, quickly become very big. See the + documentation about how to use the exact polynomials also in + floating point context. + + **Attention**: this has been reverted at ``0.4``. The macro + `\\PolGenFloatVariant `_ must be used for + generation floating point polynomial functions. + +- v0.3.1 (2018/01/18) + + Fixes two typos in example code included in the documentation. + +- v0.4 (2018/02/16) + + * bug fixes: + + - when Euclidean division gave a zero remainder, the internal + representation of this zero polynomial could be faulty; this + could cause mysterious bugs in conjunction with other package + macros such as `\\PolMapCoeffs `_. + - `\\PolGCD `_ was buggy in case of first polynomial being + of lesser degree than the second one. + * breaking changes: + + - formerly `\\PolEval{P}\\At{foo} `_ allowed ``foo`` to + be an expression, which was transparently handled via + ``\xinttheexpr``. Now, ``foo`` must be a fraction (or a macro + expanding to such) in the format acceptable by ``xintfrac.sty`` + macros. Use `\\PolEval{P}\\AtExpr{foo} `_ for more + general arguments using expression syntax. E.g., if ``foo`` is the + name of a variable known to ``\xintexpr``. + + The same holds for `\\PolEvalReduced `_ + and `\\PolFloatEval `_. + - the ``3.0`` automatic generation of floating point variants has + been reverted. Not only do *not* the package macros automatically + generate floating point variants of newly created polynomials, + they actually make pre-existing such variant undefined. + + See `\\PolGenFloatVariant `_. + * new non-expandable macros: + + - `\\PolGenFloatVariant `_ + - `\\PolGlobalLet `_ + - `\\PolTypesetOne `_ + - `\\PolQuo `_ + - `\\PolRem `_ + - `\\PolToSturm `_ + - `\\PolToSturm\* `_ + - `\\PolSetToSturmChainSignChangesAt `_ + - `\\PolSetToNbOfZerosWithin `_ + - `\\PolSturmIsolateZeros `_ + - `\\PolRefineInterval* `_ + - `\\PolRefineInterval[N] `_ + - `\\PolEnsureIntervalLength `_ + - `\\PolEnsureIntervalLengths `_ + - `\\PolPrintIntervals `_ + - `\\PolPrintIntervalsPrintExactZero `_ + - `\\PolPrintIntervalsPrintLeftEndPoint `_ + - `\\PolPrintIntervalsPrintRightEndPoint `_ + - `\\PolReduceCoeffs* `_ + - `\\PolMakeMonic `_ + * new expandable macros: + + - `\\PolToExprOneTermStyleA `_ + - `\\PolIfCoeffIsPlusOrMinusOne `_ + - `\\PolLeadingCoeff `_ + - `\\PolSturmChainLength `_ + - `\\PolSturmNbOfIsolatedZeros `_ + - `\\PolSturmIfZeroExactlyKnown `_ + - `\\PolSturmIsolatedZeroLeft `_ + - `\\PolSturmIsolatedZeroRight `_ + - `\\PolPrintIntervalsTheEndPoint `_ + - `\\PolPrintIntervalsTheIndex `_ + - `\\PolIfEndPointIsPositive `_ + - `\\PolIfEndPointIsNegative `_ + - `\\PolIfEndPointIsZero `_ + - `\\PolIntervalWidth `_ + - `\\PolDecToString `_ + * improvements: + + The main new feature is implementation of the `Sturm algorithm`_ + for localization of the real roots of polynomials. -- 0.3.1 (2018/01/18) - - Fix two typos in documentation. - -Files of 0.3.1 release: - -- README.md, -- polexpr.sty (package file), -- polexpr.txt (documentation), -- polexpr.html (conversion via `DocUtils`__ rst2html.py) - - __ http://docutils.sourceforge.net/docs/index.html - -See README.md for the License and the change log (there were -some breaking changes from 0.2 to 0.3). Acknowledgments --------------- @@ -764,6 +1745,16 @@ differentiating polynomials was the initial trigger leading to this package, and to Jürgen Gilg and Thomas Söll for testing it on some concrete problems. +Renewed thanks on occasion of ``0.4`` release! + +See README.md for the License. + +.. _xinttools: .. _xintfrac: .. _xintexpr: .. _xint: http://www.ctan.org/pkg/xint + +.. _Sturm algorithm: +.. _Sturm Theorem: https://en.wikipedia.org/wiki/Sturm%27s_theorem + +.. _DocUtils: http://docutils.sourceforge.net/docs/index.html diff --git a/Master/texmf-dist/tex/latex/polexpr/polexpr.sty b/Master/texmf-dist/tex/latex/polexpr/polexpr.sty index 752efa3fa77..d4d45177744 100644 --- a/Master/texmf-dist/tex/latex/polexpr/polexpr.sty +++ b/Master/texmf-dist/tex/latex/polexpr/polexpr.sty @@ -1,14 +1,20 @@ % author: Jean-François Burnol % License: LPPL 1.3c (author-maintained) \ProvidesPackage{polexpr}% - [2018/01/18 v0.3.1 Polynomial expressions with rational coefficients (JFB)]% + [2018/02/16 v0.4 Polynomial expressions with rational coefficients (JFB)]% \RequirePackage{xintexpr}[2016/03/19]% xint 1.2g (or 1.2c 2015/11/16 at least) \edef\POL@restorecatcodes {\catcode`\noexpand\_ \the\catcode`\_ \catcode0 \the\catcode0\relax}% \catcode`\_ 11 \catcode0 12 %% AUXILIARIES -\newif\ifPOL@pol % (cf core algebra macros) +\newcount\POL@count +\newif\ifPOL@pol +\newif\ifxintveryverbose +\newif\ifpoltypesetall +\newif\ifPOL@sturm@normalize +\newif\ifPOL@isolz@nextwillneedrefine +\newif\ifpoltoexprall %% the main exchange structure (stored in macros \POLuserpol@) %% is: degree.\empty{coeff0}{coeff1}....{coeffN} %% (degree=N except zero polynomial recognized from degree set to -1 @@ -22,19 +28,18 @@ {\def#3{#1}\expandafter\def\expandafter#4\expandafter{#2}}% % \def\POL@resultfromarray #1{% ATTENTION, **MUST** be executed with -% \count@ set to 1 + degree (thus \count@ = 0 for zero polynomial) - \edef\POL@result{% +% \count@ set to 1 + degree (\count@ = 0 for zero polynomial) + \edef\POL@result{\ifnum\count@>\z@ \the\numexpr\count@-\@ne.\noexpand\empty \xintiloop [1+1]% -% always done at least once with index 1, hence ok for zero polynomial \expandafter\POL@braceit\csname POL@array#1\xintiloopindex\endcsname \ifnum\xintiloopindex<\count@ - \repeat}% + \repeat + \else-1.\noexpand\empty{0/1[0]}\fi}% }% \def\POL@braceit#1{{#1}}% needed as \xintiloopindex can not "see" through braces -\newif\ifxintveryverbose \newcommand\PolDef[3][x]{\poldef #2(#1):=#3;}% \def\poldef{\edef\POL@restoresemicolon{\catcode59=\the\catcode59\relax}% \catcode59 12 \POL@defpol}% @@ -76,17 +81,23 @@ %% \def\POL@newpol#1{% \expandafter\POL@ifZero\csname POLuserpol@#1\endcsname - {\@namedef{XINT_expr_userfunc_#1}##1,{0/1[0]}% - \@namedef{XINT_flexpr_userfunc_#1}##1,{0[0]}}% + {\@namedef{XINT_expr_userfunc_#1}##1,{0/1[0]}}% {\POL@newpolhorner{#1}}% \unless\ifcsname XINT_expr_userfuncNE:#1\endcsname\POL@addtoextras{#1}\fi \expandafter\XINT_expr_defuserfunc \csname XINT_expr_func_#1\expandafter\endcsname \csname XINT_expr_userfunc_#1\endcsname + \expandafter\let\csname XINT_flexpr_func_#1\endcsname\@undefined + \ifxintverbose\POL@info{#1}\fi +}% +\def\POL@newfloatpol#1{% + \expandafter\POL@ifZero\csname POLuserpol@#1\endcsname + {\@namedef{XINT_flexpr_userfunc_#1}##1,{0[0]}}% + {\POL@newfloatpolhorner{#1}}% \expandafter\XINT_expr_defuserfunc \csname XINT_flexpr_func_#1\expandafter\endcsname \csname XINT_flexpr_userfunc_#1\endcsname - \ifxintverbose\POL@info{#1}\fi + \ifxintverbose\POL@floatinfo{#1}\fi }% \def\POL@info #1{% \xintMessage {polexpr}{Info}% @@ -94,9 +105,13 @@ associated to \string\XINT_expr_userfunc_#1\space whose meaning uses Horner scheme: \expandafter\meaning - \csname XINT_expr_userfunc_#1\endcsname^^J% - \@spaces And \string\XINT_flexpr_userfunc_#1\space for - the \string\xintfloatexpr\space parser has meaning + \csname XINT_expr_userfunc_#1\endcsname}% +}% +\def\POL@floatinfo #1{% + \xintMessage {polexpr}{Info}% + {Function #1 for the \string\xintfloatexpr\space parser is + associated to \string\XINT_flexpr_userfunc_#1\space + whose meaning uses Horner scheme: \expandafter\meaning \csname XINT_flexpr_userfunc_#1\endcsname}% }% @@ -114,6 +129,14 @@ \endgroup \expandafter\def\csname XINT_expr_userfunc_#1\expandafter\endcsname \expandafter##\expandafter1\expandafter,\expandafter{\POL@tmp{##1}}% +}% +\def\POL@newfloatpolhorner#1{% + %% redefine function to expand by Horner scheme. Is this useful? + %% perhaps bad idea for numerical evaluation of thing such as (1+x)^10? +% note: I added {0/1[0]} item to zero polynomial also to facilitate this + \expandafter\expandafter\expandafter\POL@split + \csname POLuserpol@#1\endcsname;\POL@var@deg\POL@var@coeffs + \edef\POL@var@coeffs{\xintRevWithBraces{\POL@var@coeffs}}% \begingroup \expandafter\POL@newpol@floathorner\POL@var@coeffs\relax \expandafter @@ -177,10 +200,14 @@ %\let\POL@original@redefinemacros\XINT_expr_redefinemacros % do locally \def\POL@redefinemacros{\POL@original_redefinemacros\POL@redefineextras}% \let\POL@redefineextras\@empty -% + + +\newcommand\PolGenFloatVariant[1]{\POL@newfloatpol{#1}}% + + \newcommand\PolLet[2]{\if=\noexpand#2\expandafter\xint_firstoftwo \else\expandafter\xint_secondoftwo\fi - \POL@@let\POL@let {#1}{#2}}% + \POL@@let\POL@let{#1}{#2}}% \def\POL@@let#1#2#3{\POL@let{#1}{#3}}% \def\POL@let#1#2{% \expandafter\let\csname POLuserpol@#1\expandafter\endcsname @@ -188,17 +215,20 @@ \unless\ifcsname XINT_expr_userfuncNE:#1\endcsname\POL@addtoextras{#1}\fi \expandafter\let\csname XINT_expr_userfunc_#1\expandafter\endcsname \csname XINT_expr_userfunc_#2\endcsname - \expandafter\let\csname XINT_flexpr_userfunc_#1\expandafter\endcsname - \csname XINT_flexpr_userfunc_#2\endcsname \expandafter\XINT_expr_defuserfunc \csname XINT_expr_func_#1\expandafter\endcsname \csname XINT_expr_userfunc_#1\endcsname - \expandafter\XINT_expr_defuserfunc - \csname XINT_flexpr_func_#1\expandafter\endcsname - \csname XINT_flexpr_userfunc_#1\endcsname \ifxintverbose\POL@info{#1}\fi }% - +\newcommand\PolGlobalLet[2]{\begingroup + \globaldefs\@ne + \if=\noexpand#2\expandafter\xint_firstoftwo + \else\expandafter\xint_secondoftwo\fi +% There is a potential problem related to \POL@addtoextras, (the local set-up +% will become the global one) but I will reconsider that another day + \POL@@globallet\POL@globallet {#1}{#2}}% +\def\POL@@globallet#1#2#3{\POL@globallet{#1}{#3}}% +\def\POL@globallet#1#2{\POL@let{#1}{#2}\endgroup}% \newcommand\PolAssign[1]{\def\POL@polname{#1}\POL@assign}% zap spaces in #1? \def\POL@assign#1\toarray#2{% @@ -224,13 +254,15 @@ }% -\newcommand\PolGet[1]{\def\POL@polname{#1}% zap spaces in #1? - \begingroup % closed in \POL@getfrom - \POL@getfrom}% -% attention au name clash proche avec \POL@get auxiliaire de \POL@add etc.. -\def\POL@getfrom#1\fromarray#2{% - \count@#2{0} % must be > 0, else could create infinite loop - % \ifnum\count@>\z@\else\InvalidArrayError_PolGet\fi +\newcommand\PolGet{} +\def\PolGet#1#2\fromarray#3{% + \begingroup % closed in \POL@getfromarray + \POL@getfromarray{#1}{#3}% + \POL@newpol{#1}% +}% +\def\POL@getfromarray#1#2{% + \count@=#2{0} %<- intentional space, + % must be > 0, else could create infinite loop \xintloop \edef\POL@tmp{#2{\count@}}% \xintiiifZero{\POL@tmp}% @@ -251,27 +283,30 @@ \expandafter \endgroup \expandafter - \def\csname POLuserpol@\POL@polname\expandafter\endcsname + \def\csname POLuserpol@#1\expandafter\endcsname \expandafter{\POL@result}% - \expandafter\POL@newpol\expandafter{\POL@polname}% }% -\newcommand\PolFromCSV[2]{\def\POL@polname{#1}% - \begingroup % closed in \POL@getfrom +\newcommand\PolFromCSV[2]{% + \begingroup % closed in \POL@getfromarray \xintAssignArray\xintCSVtoList{#2}\to\POL@arrayA - \POL@getfrom\fromarray\POL@arrayA + \POL@getfromarray{#1}\POL@arrayA + \POL@newpol{#1}% % semble un peu indirect et sous-optimal % mais je veux élaguer les coefficients nuls. Peut-être à revoir. }% -\newif\ifpoltypesetall \newcommand\PolTypesetCmdPrefix[1]{\xintiiifSgn{#1}{}{+}{+}}% \newcommand\PolTypesetCmd[1]{\xintifOne{\xintiiAbs{#1}}% {\ifnum\PolIndex=\z@\xintiiSgn{#1}\else - \xintiiifSgn{#1}{-}{}{}\fi}% - {\xintSignedFrac{#1}}}% + \xintiiifSgn{#1}{-}{}{}\fi + \let\PolIfCoeffIsPlusOrMinusOne\@firstoftwo}% + {\PolTypesetOne{#1}% + \let\PolIfCoeffIsPlusOrMinusOne\@secondoftwo}% + }% +\newcommand\PolTypesetOne{\xintSignedFrac}% \newcommand\PolTypesetMonomialCmd{% \ifcase\PolIndex\space % @@ -330,6 +365,10 @@ \newcommand\PolMapCoeffs[2]{% #1 = macro, #2 = name + \POL@mapcoeffs{#1}{#2}% + \POL@newpol{#2}% +}% +\def\POL@mapcoeffs#1#2{% \begingroup \def\POL@map@macro{#1}% \expandafter\expandafter\expandafter\POL@split @@ -352,7 +391,6 @@ \endgroup \expandafter \def\csname POLuserpol@#2\expandafter\endcsname\expandafter{\POL@result}% - \POL@newpol{#2}% }% \def\POL@map@loop.#1{\if\relax#1\expandafter\xint_gob_til_dot\fi \advance\count@\@ne @@ -362,11 +400,34 @@ \edef\index{\the\numexpr\index+\@ne}% \POL@map@loop.}% \def\POL@xintIrr#1{\xintIrr{#1}[0]}% -\newcommand\PolReduceCoeffs[1]{\PolMapCoeffs{\POL@xintIrr}{#1}}% +\def\POL@special@xintIrr#1{% + \expandafter\POL@special@xintIrr@i\romannumeral0\xintraw{#1}}% +\def\POL@special@xintIrr@i#1/#2[#3]{\xintIrr{#1/#2[0]}[#3]}% +\newcommand\PolReduceCoeffs{\@ifstar\POL@sreducecoeffs\POL@reducecoeffs}% +\def\POL@reducecoeffs#1{\PolMapCoeffs{\POL@xintIrr}{#1}}% +\def\POL@sreducecoeffs#1{\PolMapCoeffs{\POL@special@xintIrr}{#1}}% +\def\POL@special@xintIrr@skipraw#1{\POL@special@xintIrr@i#1}% used by ToSturm %% EUCLIDEAN DIVISION \newcommand\PolDivide[4]{% #3=quotient, #4=remainder of #1 by #2 + \POL@divide{#1}{#2}% + \expandafter\let\csname POLuserpol@#3\endcsname\POL@Q + \POL@newpol{#3}% + \expandafter\let\csname POLuserpol@#4\endcsname\POL@R + \POL@newpol{#4}% +}% +\newcommand\PolQuo[3]{% #3=quotient of #1 by #2 + \POL@divide{#1}{#2}% + \expandafter\let\csname POLuserpol@#3\endcsname\POL@Q + \POL@newpol{#3}% +}% +\newcommand\PolRem[3]{% #3=remainder of #1 by #2 + \POL@divide{#1}{#2}% + \expandafter\let\csname POLuserpol@#3\endcsname\POL@R + \POL@newpol{#3}% +}% +\newcommand\POL@divide[2]{% \begingroup \let\xintScalarSub\xintSub \let\XINT_fadd_C\POL_fadd_C @@ -386,17 +447,19 @@ \expandafter \endgroup \expandafter - \def\csname POLuserpol@#3\expandafter\expandafter\expandafter\endcsname + \def\csname POL@Q\expandafter\expandafter\expandafter\endcsname \expandafter\expandafter\expandafter{\expandafter\POL@Q\expandafter}% \expandafter - \def\csname POLuserpol@#4\expandafter\endcsname\expandafter{\POL@R}% - \POL@newpol{#3}% - \POL@newpol{#4}% + \def\csname POL@R\expandafter\endcsname\expandafter{\POL@R}% }% %% GCD \newcommand\PolGCD[3]{% sets #3 to the (unitary) G.C.D. of #1 and #2 + \POL@GCD{#1}{#2}{#3}% + \POL@newpol{#3}% +}% +\def\POL@GCD #1#2#3{% \begingroup \let\xintScalarSub\xintSub \let\XINT_fadd_C\POL_fadd_C @@ -424,7 +487,8 @@ \POL@gcd@exit AB}% {\ifnum\POL@degA<\POL@degB\space \let\POL@tmp\POL@B\let\POL@B\POL@A\let\POL@A\POL@tmp - \let\POL@tmp\POL@degB\let\POL@degB\POL@degA\let\POL@degA\POL@degB + \let\POL@tmp\POL@degB\let\POL@degB\POL@degA\let\POL@degA\POL@tmp + \let\POL@tmp\POL@polB\let\POL@polB\POL@polA\let\POL@polA\POL@tmp \fi \xintAssignArray\POL@polA\to\POL@arrayA \xintAssignArray\POL@polB\to\POL@arrayB @@ -434,7 +498,6 @@ \endgroup \expandafter\def\csname POLuserpol@#3\expandafter\endcsname \expandafter{\POL@result}% - \POL@newpol{#3}% }% \def\POL@normalize#1{% \expandafter\def\expandafter\POL@tmp\expandafter @@ -450,7 +513,7 @@ {\POL@normalize@leading}}[0]}% \advance\count@\m@ne \repeat -}% +}% \def\POL@gcd#1#2{% \POL@normalize{#2}% \edef\POL@degQ{\the\numexpr\csname POL@deg#1\endcsname @@ -498,7 +561,7 @@ \count@\numexpr\csname POL@deg#1\endcsname+\@ne\relax \POL@resultfromarray #1% }% - + %% TODO: BEZOUT @@ -533,7 +596,8 @@ \fi }% \def\POL@Diff@no #1#2{\POL@let{#2}{#1}}% -\def\POL@Diff@one #1#2{% +\def\POL@Diff@one #1#2{\POL@Diff@@one {#1}{#2}\POL@newpol{#2}}% +\def\POL@Diff@@one#1#2{% \expandafter\expandafter\expandafter\POL@split \csname POLuserpol@#1\endcsname;\POL@var@deg\POL@var@coeffs \ifnum\POL@var@deg<\@ne @@ -543,7 +607,6 @@ \expandafter\edef\csname POLuserpol@#2\endcsname {\the\numexpr\POL@var@deg-\@ne.\noexpand\empty\POL@var@coeffs}% \fi - \POL@newpol{#2}% }% % lazy way but allows to share with AntiDiff \def\POL@Iterate#1#2#3{% @@ -593,7 +656,8 @@ \fi }% \let\POL@AntiDiff@no\POL@Diff@no -\def\POL@AntiDiff@one #1#2{% +\def\POL@AntiDiff@one #1#2{\POL@AntiDiff@@one{#1}{#2}\POL@newpol{#2}}% +\def\POL@AntiDiff@@one#1#2{% \expandafter\expandafter\expandafter\POL@split \csname POLuserpol@#1\endcsname;\POL@var@deg\POL@var@coeffs \ifnum\POL@var@deg<\z@ @@ -603,7 +667,798 @@ \expandafter\edef\csname POLuserpol@#2\endcsname {\the\numexpr\POL@var@deg+\@ne.\noexpand\empty{0/1[0]}\POL@var@coeffs}% \fi - \POL@newpol{#2}% +}% + + +%% Sturm Algorithm (polexpr 0.4) +\newcommand\PolToSturm{% + \@ifstar{\POL@sturm@normalizefalse}{\POL@sturm@normalizetrue}% + \POL@ToSturm +}% +\newcommand\POL@ToSturm[2]{% + \edef\POL@sturmname{#2}% + \POL@let{\POL@sturmname _0}{#1}% + \POL@mapcoeffs{\POL@special@xintIrr}{\POL@sturmname _0}% + \POL@Diff@@one{\POL@sturmname _0}{\POL@sturmname _1}% + \POL@count\@ne + \xintloop + \POL@divide{\POL@sturmname _\the\numexpr\POL@count-\@ne}% + {\POL@sturmname _\the\POL@count}% + \expandafter\POL@split\POL@R;\POL@degR\POL@polR + \unless\ifnum\POL@degR=\m@ne + \edef\POL@polR{\xintApply{\POL@dooppandirr}{\POL@polR}}% + \advance\POL@count\@ne + \expandafter\edef\csname POLuserpol@\POL@sturmname _\the\POL@count\endcsname + {\POL@degR.\noexpand\empty\POL@polR}% + \repeat + \edef\POL@sturm@N{\the\POL@count}% + \ifPOL@sturm@normalize + \ifnum\PolDegree{\POL@sturmname _\POL@sturm@N}>\z@ + \xintloop + \advance\POL@count\m@ne + \POL@divide{\POL@sturmname _\the\POL@count}% + {\POL@sturmname _\POL@sturm@N}% + \expandafter\POL@split\POL@Q;\POL@degQ\POL@polQ + \edef\POL@polQ{\xintApply{\POL@special@xintIrr@skipraw}{\POL@polQ}}% + \edef\POL@Q{\POL@degQ.\noexpand\empty\POL@polQ}% + \expandafter\edef\csname POLuserpol@\POL@sturmname _\the\POL@count\endcsname + {\POL@degQ.\noexpand\empty\POL@polQ}% + \ifnum\POL@count>\z@ + \repeat + \@namedef{POLuserpol@\POL@sturmname _\POL@sturm@N}{0.\empty{1/1[0]}}% + \fi + \fi + \POL@count\z@ + \xintloop + \POL@newpol{\POL@sturmname _\the\POL@count}% + \unless\ifnum\POL@sturm@N=\POL@count + \advance\POL@count\@ne + \repeat + \expandafter\let\csname PolSturmChainLength_\POL@sturmname \endcsname\POL@sturm@N +}% +\def\POL@dooppandirr#1{\xintiiOpp{\POL@special@xintIrr@i#1}}% +\newcommand\PolSturmChainLength[1] + {\romannumeral`^^@\csname PolSturmChainLength_#1\endcsname}% +\newcommand\PolSetToSturmChainSignChangesAt[4][\global]{% + \edef\POL@sturmchain@X{\xintREZ{#4}}% + \edef\POL@sturmname{#3}% + \edef\POL@sturmlength{\PolSturmChainLength{\POL@sturmname}}% + \POL@sturmchain@getSV@at\POL@sturmchain@X + #1\let#2\POL@sturmchain@SV +}% +\def\POL@sturmchain@getSV@at#1{% ATTENTION USES \POL@count + \def\POL@sturmchain@SV{0}% + \edef\POL@isolz@lastsign{\xintiiSgn{\PolEval{\POL@sturmname _0}\At{#1}}}% + \let\POL@IsoRightSign\POL@isolz@lastsign % needed only for SturmIsolate etc... + \POL@count \z@ + \ifnum\POL@isolz@lastsign=\z@ + \edef\POL@isolz@lastsign + {\xintiiSgn{\PolEval{\POL@sturmname _1}\At{#1}}}% + \POL@count \@ne + \fi + \xintloop + \unless\ifnum\POL@sturmlength=\POL@count + \advance\POL@count \@ne + \edef\POL@isolz@newsign + {\xintiiSgn{\PolEval{\POL@sturmname _\the\POL@count}\At{#1}}}% + \ifnum\POL@isolz@newsign=\numexpr-\POL@isolz@lastsign\relax + \edef\POL@sturmchain@SV{\the\numexpr\POL@sturmchain@SV+\@ne}% + \let\POL@isolz@lastsign=\POL@isolz@newsign + \fi + \repeat +}% +\newcommand\PolSetToNbOfZerosWithin[5][\global]{% + \edef\POL@tmpA{\xintREZ{#4}}% + \edef\POL@tmpB{\xintREZ{#5}}% + \edef\POL@sturmname{#3}% + \edef\POL@sturmlength{\PolSturmChainLength{\POL@sturmname}}% + \POL@sturmchain@getSV@at\POL@tmpA + \let\POL@SVA\POL@sturmchain@SV + \POL@sturmchain@getSV@at\POL@tmpB + \let\POL@SVB\POL@sturmchain@SV + \ifnum\POL@SVA<\POL@SVB\space + #1\edef#2{\the\numexpr\POL@SVB-\POL@SVA}% + \else + #1\edef#2{\the\numexpr\POL@SVA-\POL@SVB}% + \fi +}% + + +\newcommand\PolSturmIsolateZeros[1]{% + % #1 name of Sturm chain (already pre-computed from a given polynomial) + \edef\POL@sturmname{#1}% + \edef\POL@sturmlength{\PolSturmChainLength{#1}}% + % Count number of sign changes at plus infinity in Sturm sequence + \def\POL@isolz@plusinf@SV{0}% + \edef\POL@isolz@lastsign{\xintiiSgn{\PolLeadingCoeff{#1_0}}}% + \let\POL@isolz@plusinf@sign\POL@isolz@lastsign + \POL@count\@ne + \xintloop + \edef\POL@isolz@newsign{\xintiiSgn{\PolLeadingCoeff{#1_\the\POL@count}}}% + \unless\ifnum\POL@isolz@newsign=\POL@isolz@lastsign + \edef\POL@isolz@plusinf@SV{\the\numexpr\POL@isolz@plusinf@SV+\@ne}% + \fi + \let\POL@isolz@lastsign=\POL@isolz@newsign + \ifnum\POL@sturmlength>\POL@count + \advance\POL@count\@ne + \repeat + % Count number of sign changes at minus infinity in Sturm sequence + \def\POL@isolz@minusinf@SV{0}% + \edef\POL@isolz@lastsign{\xintiiSgn{\PolLeadingCoeff{#1_0}}}% + \ifodd\PolDegree{#1_0} + \edef\POL@isolz@lastsign{\xintiiOpp{\POL@isolz@lastsign}}% + \fi + \let\POL@isolz@minusinf@sign\POL@isolz@lastsign + \POL@count\@ne + \xintloop + \edef\POL@isolz@newsign{\xintiiSgn{\PolLeadingCoeff{#1_\the\POL@count}}}% + \ifodd\PolDegree{#1_\the\POL@count} + \edef\POL@isolz@newsign{\xintiiOpp{\POL@isolz@newsign}}% + \fi + \unless\ifnum\POL@isolz@newsign=\POL@isolz@lastsign + \edef\POL@isolz@minusinf@SV{\the\numexpr\POL@isolz@minusinf@SV+\@ne}% + \fi + \let\POL@isolz@lastsign=\POL@isolz@newsign + \ifnum\POL@sturmlength>\POL@count + \advance\POL@count\@ne + \repeat + \edef\POL@isolz@NbOfRoots + {\the\numexpr\POL@isolz@minusinf@SV-\POL@isolz@plusinf@SV}% + \ifnum\POL@isolz@NbOfRoots=\z@ + \begingroup\globaldefs\@ne + \expandafter\xintAssignArray\expandafter\to\csname POL_ZeroInt#1L\endcsname + \expandafter\xintAssignArray\expandafter\to\csname POL_ZeroInt#1R\endcsname + \endgroup + \else + \begingroup\globaldefs\@ne + \expandafter\POL@isolz@initarray\csname POL_ZeroInt#1L\endcsname + \expandafter\POL@isolz@initarray\csname POL_ZeroInt#1R\endcsname + \endgroup + \expandafter\POL@isolz@getaprioribound + \fi +}% +\def\POL@isolz@initarray#1{% + \expandafter\xintAssignArray + \romannumeral\xintreplicate{\POL@isolz@NbOfRoots}{{0}}\to#1% +}% +% utility macro for a priori bound on root decimal exponent, via Float Rounding +\def\POL@isolz@updateE #1e#2;% +{\unless\ifnum#2<\POL@isolz@E\space\edef\POL@isolz@E{\the\numexpr#2+\@ne}\fi}% +\def\POL@isolz@getaprioribound{% + \PolAssign{\POL@sturmname _0}\toarray\POL@arrayA + \edef\POL@isolz@leading{\POL@arrayA{\POL@arrayA{0}}}% + \POL@count\z@ + \xintloop + \advance\POL@count\@ne + \ifnum\POL@arrayA{0}>\POL@count + \expandafter\edef\csname POL@arrayA\the\POL@count\endcsname + {\xintDiv{\POL@arrayA\POL@count}\POL@isolz@leading}% + \repeat + \def\POL@isolz@E{1}% WE SEEK SMALLEST E SUCH HAT -10^E < roots < +10^E + \advance\POL@count\m@ne + \xintloop + \ifnum\POL@count>\z@ + \expandafter\POL@isolz@updateE + % use floating point to get decimal exponent + \romannumeral0\xintfloat[4]% should I use with [2] rather? (should work) + {\xintAdd{1/1[0]}{\xintAbs{\POL@arrayA\POL@count}}};% + \advance\POL@count\m@ne + \repeat + % \ifxintverbose\xintMessage{polexpr}{Info}% + % {Roots a priori bounded in absolute value by 10 to the \POL@isolz@E.}% + % \fi + \POL@isolz@main +}% +\def\POL@IsoRight@raw{\POL@IsoRight@Int/1[\POL@isolz@E]}% +\def\POL@IsoLeft@raw {\POL@IsoLeft@Int/1[\POL@isolz@E]}% +\def\POL@IsoRight@rawout{% + \ifnum\POL@IsoRightSign=\z@\expandafter\xintREZ\fi\POL@IsoRight@raw}% +\def\POL@IsoLeft@rawout{% + \ifnum\POL@IsoRightSign=\z@ + \expandafter\xint_firstoftwo\else\expandafter\xint_secondoftwo + \fi{\xintREZ\POL@IsoRight@raw}% + {\POL@IsoLeft@Int/1[\POL@isolz@E]}}% +\def\POL@isolz@main {% +% NOTE 2018/02/16. THIS WILL PRESUMABLY BE RE-ORGANIZED IN FUTURE TO DO +% FIRST POSITIVE ROOTS THEN NEGATIVE ROOTS VIA CHANGE OF VARIABLE TO OPPOSITE. + \global\POL@isolz@nextwillneedrefinefalse + \def\POL@IsoRight@Int{0}% + \POL@sturmchain@getSV@at\POL@IsoRight@raw + \let\POL@IsoRightSV\POL@sturmchain@SV + \let\POL@IsoAtZeroSV\POL@IsoRightSV + \let\POL@IsoAtZeroSign\POL@IsoRightSign + \ifnum\POL@IsoAtZeroSign=\z@ + \xdef\POL@isolz@IntervalIndex + {\the\numexpr\POL@isolz@minusinf@SV-\POL@IsoRightSV}% + \POL@refine@storeleftandright % store zero root + \edef\POL@IsoRightSV{\the\numexpr\POL@IsoRightSV+\@ne}% +% subtlety here if original polynomial had multiplicities, but ok. I checked! + \edef\POL@IsoRightSign % evaluated twice, but that's not so bad + {\xintiiOpp{\xintiiSgn{\PolEval{\POL@sturmname _1}\At{0/1[0]}}}}% + \fi + \def\POL@IsoLeft@Int{-1}% -10^E isn't a root! + \let\POL@IsoLeftSV\POL@isolz@minusinf@SV + \let\POL@IsoLeftSign\POL@isolz@minusinf@sign + \edef\POL@isolz@NbOfNegRoots{\the\numexpr\POL@IsoLeftSV-\POL@IsoRightSV}% + \gdef\POL@isolz@IntervalIndex{0}% + \begingroup + \let\POL@IsoAtZeroSV\POL@IsoRightSV % locally shifted if root at zero + \let\POL@IsoAtZeroSign\POL@IsoRightSign + \ifnum\POL@isolz@NbOfNegRoots>\z@ + \def\POL@IsoRight@Int{-1}% + \xintloop + \edef\POL@isolz@E{\the\numexpr\POL@isolz@E-\@ne}% + \POL@sturmchain@getSV@at\POL@IsoRight@raw + \let\POL@IsoRightSV\POL@sturmchain@SV + % would an \ifx test be quicker? (to be checked) + \ifnum\POL@IsoRightSV=\POL@IsoLeftSV\space + % no roots in-between, sign and SV kept + \repeat + \def\POL@IsoLeft@Int{-10}% + \let\POL@@IsoRightSign\POL@IsoRightSign % zero possible + \let\POL@@IsoRightSV\POL@IsoRightSV + \xintloop + \edef\POL@IsoRight@Int{\the\numexpr\POL@IsoLeft@Int+\@ne}% +% we could arguably do a more efficient dichotomy here + \POL@sturmchain@getSV@at\POL@IsoRight@raw + \let\POL@IsoRightSV\POL@sturmchain@SV + \POL@isolz@check + \ifnum\POL@isolz@IntervalIndex=\POL@isolz@NbOfNegRoots\space + \expandafter\xintbreakloop + \fi + \let\POL@IsoLeft@Int\POL@IsoRight@Int + \let\POL@IsoLeftSign\POL@IsoRightSign + \let\POL@IsoLeftSV\POL@IsoRightSV + \ifnum\POL@IsoRight@Int < -\tw@ + \repeat + \ifnum\POL@isolz@IntervalIndex<\POL@isolz@NbOfNegRoots\space + \def\POL@IsoRight@Int{-1}% + \let\POL@IsoRightSign\POL@@IsoRightSign + \let\POL@IsoRightSV\POL@@IsoRightSV + \POL@isolz@check + \ifnum\POL@isolz@IntervalIndex<\POL@isolz@NbOfNegRoots\space + \def\POL@IsoLeft@Int{-1}% + \let\POL@IsoLeftSign\POL@IsoRightSign + \let\POL@IsoLeftSV\POL@IsoRightSV + \def\POL@IsoRight@Int{0}% + \let\POL@IsoRightSV\POL@IsoAtZeroSV % altered if 0 was a root + \let\POL@IsoRightSign\POL@IsoAtZeroSign% id. +% this will recurse to locate roots with smaller decimal exponents + \POL@isolz@check % attention that this should not re-evaluate at 0 + \fi + \fi + \fi + \endgroup + \def\POL@IsoLeft@Int{0}% + \let\POL@IsoLeftSV\POL@IsoAtZeroSV + \let\POL@IsoLeftSign\POL@IsoAtZeroSign + \ifnum\POL@IsoLeftSign=\z@ + \xdef\POL@isolz@IntervalIndex{\the\numexpr\POL@isolz@IntervalIndex+\@ne}% + \global\POL@isolz@nextwillneedrefinetrue + \else + \global\POL@isolz@nextwillneedrefinefalse + \fi + \let\POL@@IsoRightSV=\POL@isolz@plusinf@SV + \let\POL@@IsoRightSign=\POL@isolz@plusinf@sign % 10^E not a root! + \edef\POL@isolz@NbOfPosRoots + {\the\numexpr\POL@IsoLeftSV-\POL@@IsoRightSV}% attention @@ + \ifnum\POL@isolz@NbOfPosRoots>\z@ + \def\POL@IsoRight@Int{1}% + \xintloop + \edef\POL@isolz@E{\the\numexpr\POL@isolz@E-\@ne}% + \POL@sturmchain@getSV@at\POL@IsoRight@raw + \let\POL@IsoRightSV\POL@sturmchain@SV + \ifnum\POL@IsoRightSV=\POL@@IsoRightSV\space + \let\POL@@IsoRightSign\POL@IsoRightSign % root here possible! + \repeat + \unless\ifnum\POL@IsoRightSV=\POL@IsoLeftSV\space + \POL@isolz@check % will recurse inside groups if needed + \fi + \def\POL@IsoLeft@Int{1}% + \let\POL@IsoLeftSV\POL@IsoRightSV + \let\POL@IsoLeftSign\POL@IsoRightSign + \xintloop +% we could arguably do a more efficient dichotomy here + \edef\POL@IsoRight@Int{\the\numexpr\POL@IsoLeft@Int+\@ne}% + \POL@sturmchain@getSV@at\POL@IsoRight@raw + \let\POL@IsoRightSV\POL@sturmchain@SV + \POL@isolz@check + \let\POL@IsoLeft@Int\POL@IsoRight@Int + \let\POL@IsoLeftSign\POL@IsoRightSign + \let\POL@IsoLeftSV\POL@IsoRightSV + \ifnum\POL@isolz@IntervalIndex=\POL@isolz@NbOfRoots\space + \expandafter\xintbreakloop + \fi + \ifnum\POL@IsoLeft@Int < \xint_c_ix + \repeat + \ifnum\POL@isolz@IntervalIndex<\POL@isolz@NbOfRoots\space + % get now the last, right most, root (or roots) + \def\POL@IsoRight@Int{10}% + \let\POL@IsoRightSign\POL@@IsoRightSign + \let\POL@IsoRightSV\POL@@IsoRightSV + \POL@isolz@check + \fi + \fi +}% +\def\POL@isolz@check{% \POL@IsoRightSign must be ready for use here +% \ifxintverbose +% \xintMessage{polexpr}{Info}% +% {\the\numexpr\POL@IsoLeftSV-\POL@IsoRightSV\relax\space roots +% in (\POL@IsoLeft@raw,\POL@IsoRight@raw] (E = \POL@isolz@E)}% +% \fi + \ifcase\numexpr\POL@IsoLeftSV-\POL@IsoRightSV\relax + % no root in ]left, right] + \global\POL@isolz@nextwillneedrefinefalse + \or + % exactly one root in ]left, right] + \xdef\POL@isolz@IntervalIndex{\the\numexpr\POL@isolz@IntervalIndex+\@ne}% + \ifnum\POL@IsoRightSign=\z@ + % if right boundary is a root, ignore previous flag + \global\POL@isolz@nextwillneedrefinefalse + \fi + % if left boundary is known to have been a root we refine interval + \ifPOL@isolz@nextwillneedrefine + \expandafter\expandafter\expandafter\POL@isolz@refine + \else + \POL@refine@storeleftandright + \ifnum\POL@IsoRightSign=\z@ + \global\POL@isolz@nextwillneedrefinetrue + \fi + \fi + \else + % more than one root, we need to recurse + \expandafter\POL@isolz@recursedeeper + \fi +}% +\def\POL@isolz@recursedeeper{% +% NOTE 2018/02/16. I SHOULD DO A REAL BINARY DICHOTOMY HERE WHICH ON AVERAGE +% SHOULD BRING SOME GAIN (LIKE WHAT IS ALREADY DONE FOR THE "refine" MACROS. +% THUS IN FUTURE THIS MIGHT BE REFACTORED. +\begingroup + \edef\POL@isolz@E{\the\numexpr\POL@isolz@E-\@ne}% + \edef\POL@@IsoRight@Int{\xintDSL{\POL@IsoRight@Int}}% + \let\POL@@IsoRightSign \POL@IsoRightSign + \let\POL@@IsoRightSV \POL@IsoRightSV + \edef\POL@IsoLeft@Int {\xintDSL{\POL@IsoLeft@Int}}% + \xintiloop[1+1] + \edef\POL@IsoRight@Int{\xintInc{\POL@IsoLeft@Int}}% + \POL@sturmchain@getSV@at\POL@IsoRight@raw + \let\POL@IsoRightSV\POL@sturmchain@SV + \POL@isolz@check + \let\POL@IsoLeft@Int\POL@IsoRight@Int + \let\POL@IsoLeftSV\POL@IsoRightSV + \let\POL@IsoLeftSign\POL@IsoRightSign% not used, actually + \ifnum\POL@IsoLeftSV=\POL@@IsoRightSV\space + \expandafter\xintbreakiloop + \fi + \ifnum\xintiloopindex < \xint_c_ix + \repeat + \let\POL@IsoRight@Int\POL@@IsoRight@Int + \let\POL@IsoRightSign\POL@@IsoRightSign + \let\POL@IsoRightSV \POL@@IsoRightSV + % if we exited the loop via breakiloop this is superfluous + % but it only costs one \ifnum + \POL@isolz@check +\endgroup +}% +\def\POL@isolz@refine{% + % starting point is first root = left < unique second root < right + % even if we hit exactly via refinement second root, we set flag false as + % processing will continue with original right end-point, which isn't a root + \global\POL@isolz@nextwillneedrefinefalse +\begingroup + \let\POL@@IsoRightSign\POL@IsoRightSign % already evaluated + \xintloop + \edef\POL@isolz@E{\the\numexpr\POL@isolz@E-\@ne}% + \edef\POL@IsoLeft@Int {\xintDSL{\POL@IsoLeft@Int}}% + \edef\POL@IsoRight@Int{\xintInc{\POL@IsoLeft@Int}}% + \edef\POL@IsoRightSign + {\xintiiSgn{\PolEval{\POL@sturmname _0}\At{\POL@IsoRight@raw}}}% + \ifnum\POL@IsoRightSign=\POL@@IsoRightSign\space + \repeat + % now second root has been separated from the one at left end point +% we update the storage of the root at left for it to have the same number +% of digits in mantissa. No, I decided not to do that to avoid complications. + % \begingroup + % \let\POL@IsoRight@Int\POL@IsoLeft@Int + % \def\POL@IsoRightSign{0}% + % \edef\POL@isolz@IntervalIndex{\the\numexpr\POL@isolz@IntervalIndex-\@ne}% + % \POL@refine@storeleftandright + % \endgroup + \edef\POL@@IsoRight@Int{\xintDSL{\xintInc{\xintDSR{\POL@IsoLeft@Int}}}}% + \let\POL@IsoLeft@Int\POL@IsoRight@Int + \let\POL@IsoLeftSign\POL@IsoRightSign + \ifnum\POL@IsoRightSign=\z@ % check if new Left is actually a root + \else + \edef\POL@IsoRight@Int{\xintDec{\POL@@IsoRight@Int}}% + \edef\POL@IsoRightSign + {\xintiiSgn{\PolEval{\POL@sturmname _0}\At{\POL@IsoRight@raw}}}% + \ifnum\POL@IsoRightSign=\POL@@IsoRightSign\space + \POL@refine@doonce % we need to locate in interval (1, 9) in local scale + \else + \let\POL@IsoLeft@Int\POL@IsoRight@Int + \ifnum\POL@IsoRightSign=\z@ + \def\POL@IsoLeftSign{0}% + \else + \let\POL@IsoRight@Int\POL@@IsoRight@Int + % the IsoRightSign is now wrong but here we don't care + \fi\fi + \fi + % on exit, exact root found iff \POL@IsoRightSign is zero + \POL@refine@storeleftandright +\endgroup +}% +\def\POL@refine@doonce{% if exact root is found, always in IsoRight on exit +% NOTE: FUTURE REFACTORING WILL GET RID OF \xintiiAdd WHICH ARE A BIT COSTLY +% BUT BASICALLY NEEDED TO HANDLE BOTH NEGATIVE AND POSITIVE HERE. +% I WILL RE-ORGANIZE THE WHOLE THING IN FUTURE TO GET ROOTS STARTING FROM +% THE ORIGIN AND SIMPLY RE-LABEL THE NEGATIVE ONE AT THE END. 2018/02/16. + \let\POL@@IsoRight@Int\POL@IsoRight@Int % 9 + \let\POL@@IsoRightSign\POL@IsoRightSign + \edef\POL@IsoRight@Int{\xintiiAdd{4}{\POL@IsoLeft@Int}}% 5 + \edef\POL@IsoRightSign + {\xintiiSgn{\PolEval{\POL@sturmname _0}\At{\POL@IsoRight@raw}}}% + \ifnum\POL@IsoRightSign=\POL@IsoLeftSign\space + \let\POL@IsoLeft@Int\POL@IsoRight@Int % 5 + \edef\POL@IsoRight@Int{\xintiiAdd{2}{\POL@IsoLeft@Int}}% + \edef\POL@IsoRightSign + {\xintiiSgn{\PolEval{\POL@sturmname _0}\At{\POL@IsoRight@raw}}}% + \ifnum\POL@IsoRightSign=\POL@IsoLeftSign\space + \let\POL@IsoLeft@Int\POL@IsoRight@Int % 7 + \edef\POL@IsoRight@Int{\xintInc{\POL@IsoLeft@Int}}% + \edef\POL@IsoRightSign + {\xintiiSgn{\PolEval{\POL@sturmname _0}\At{\POL@IsoRight@raw}}}% + \ifnum\POL@IsoRightSign=\POL@IsoLeftSign\space + \let\POL@IsoLeft@Int\POL@IsoRight@Int % 8 + \let\POL@IsoRight@Int\POL@@IsoRight@Int % 9 + \let\POL@IsoRightSign\POL@@IsoRightSign % opposite of one at left + \fi % else 7, 8 with possible root at 8 + \else + \ifnum\POL@IsoRightSign=\z@ + \let\POL@IsoLeft@Int\POL@IsoRight@Int % root at 7 + \def\POL@IsoLeftSign{0}% + \else + \let\POL@@IsoRight@Int\POL@IsoRight@Int % 7 + \edef\POL@IsoRight@Int{\xintInc{\POL@IsoLeft@Int}}% 6 + \edef\POL@IsoRightSign + {\xintiiSgn{\PolEval{\POL@sturmname _0}\At{\POL@IsoRight@raw}}}% + \ifnum\POL@IsoRightSign=\POL@IsoLeftSign\space + \let\POL@IsoLeft@Int\POL@IsoRight@Int % 6 + \let\POL@IsoRight@Int\POL@@IsoRight@Int % 7 + \let\POL@IsoRightSign\POL@@IsoRightSign + \fi % else 5, 6 with possible root at 6 + \fi\fi + \else + \ifnum\POL@IsoRightSign=\z@ + \let\POL@IsoLeft@Int\POL@IsoRight@Int % root at 5 + \def\POL@IsoLeftSign{0}% + \else + \let\POL@@IsoRight@Int\POL@IsoRight@Int % 5 + \edef\POL@IsoRight@Int{\xintiiAdd{2}{\POL@IsoLeft@Int}}% + \edef\POL@IsoRightSign + {\xintiiSgn{\PolEval{\POL@sturmname _0}\At{\POL@IsoRight@raw}}}% + \ifnum\POL@IsoRightSign=\POL@IsoLeftSign\space + \let\POL@IsoLeft@Int\POL@IsoRight@Int % 3 + \edef\POL@IsoRight@Int{\xintInc{\POL@IsoLeft@Int}}% 4 + \edef\POL@IsoRightSign + {\xintiiSgn{\PolEval{\POL@sturmname _0}\At{\POL@IsoRight@raw}}}% + \ifnum\POL@IsoRightSign=\POL@IsoLeftSign\space + \let\POL@IsoLeft@Int\POL@IsoRight@Int % 4 + \let\POL@IsoRight@Int\POL@@IsoRight@Int % 5 + \let\POL@IsoRightSign\POL@@IsoRightSign + \fi % else 3, 4 with possible root at 4 + \else + \ifnum\POL@IsoRightSign=\z@ + \let\POL@IsoLeft@Int\POL@IsoRight@Int % root at 3 + \def\POL@IsoLeftSign{0}% + \else + \let\POL@@IsoRight@Int\POL@IsoRight@Int % 3 + \edef\POL@IsoRight@Int{\xintInc{\POL@IsoLeft@Int}}% 2 + \edef\POL@IsoRightSign + {\xintiiSgn{\PolEval{\POL@sturmname _0}\At{\POL@IsoRight@raw}}}% + \ifnum\POL@IsoRightSign=\POL@IsoLeftSign\space + \let\POL@IsoLeft@Int\POL@IsoRight@Int % 2 + \let\POL@IsoRight@Int\POL@@IsoRight@Int % 3 + \let\POL@IsoRightSign\POL@@IsoRightSign + \fi % else 1, 2 with possible root at 2 + \fi\fi + \fi\fi +}% +\def\POL@refine@storeleftandright{% + \expandafter + \xdef\csname POL_ZeroInt\POL@sturmname + L\POL@isolz@IntervalIndex\endcsname + {\PolDecToString{\POL@IsoLeft@rawout}}% + \expandafter + \xdef\csname POL_ZeroInt\POL@sturmname + R\POL@isolz@IntervalIndex\endcsname + {\PolDecToString{\POL@IsoRight@rawout}}% + \begingroup\globaldefs\@ne + \xintdefvar\POL@sturmname + L_\POL@isolz@IntervalIndex:=qfrac(\POL@IsoLeft@rawout);% + \xintdefvar\POL@sturmname + R_\POL@isolz@IntervalIndex:=qfrac(\POL@IsoRight@rawout);% + \endgroup +}% + + +%% \PolRefineInterval +\def\POL@xintexprGetVar#1{\expandafter\expandafter\expandafter + \XINT_expr_unlock\csname XINT_expr_var_#1\endcsname}% +\def\POL@set@IsoLeft@rawin{% + \edef\POL@IsoLeft@rawin + {\POL@xintexprGetVar{\POL@sturmname L_\POL@isolz@IntervalIndex}}% +}% +\def\POL@set@IsoRight@rawin{% + \edef\POL@IsoRight@rawin + {\POL@xintexprGetVar{\POL@sturmname R_\POL@isolz@IntervalIndex}}% +}% +\def\POL@set@IsoLeft@Int #1/1[#2]{% + \edef\POL@IsoLeft@Int{\xintDSH{\POL@isolz@E-#2}{#1}}% +}% +\newcommand\PolRefineInterval{\@ifstar\POL@srefine@start\POL@refine@start}% +\newcommand\POL@refine@start[3][1]{% + \edef\POL@isolz@IntervalIndex{\the\numexpr#3}% + \edef\POL@sturmname{#2}% + \expandafter\POL@refine@sharedbody\expandafter + {\expandafter\POL@refine@loop\expandafter{\the\numexpr#1}}% +}% +\def\POL@srefine@start#1#2{% + \edef\POL@isolz@IntervalIndex{\the\numexpr#2}% + \edef\POL@sturmname{#1}% + \POL@refine@sharedbody + {\let\POL@refine@left@next\POL@refine@main % we want to recurse if needed + \let\POL@refine@right@next\POL@refine@main % we want to recurse if needed + \POL@refine@main}% +}% +\def\POL@refine@sharedbody#1{% + \POL@set@IsoLeft@rawin + \edef\POL@IsoLeftSign + {\xintiiSgn{\PolEval{\POL@sturmname _0}\At{\POL@IsoLeft@rawin}}}% + \ifnum\POL@IsoLeftSign=\z@ + % do nothing if that interval was already a singleton + \else + % else both end-points are not roots and there is a single one in-between + \POL@set@IsoRight@rawin + \edef\POL@IsoRightSign{\the\numexpr-\POL@IsoLeftSign}% + \edef\POL@isolz@E{\expandafter\POL@refine@getE + % je pense que le xintrez ici est superflu + \romannumeral0\xintrez{\xintSub{\POL@IsoRight@rawin}{\POL@IsoLeft@rawin}}}% + \expandafter\POL@set@IsoLeft@Int\POL@IsoLeft@rawin + \edef\POL@IsoRight@Int{\xintInc{\POL@IsoLeft@Int}}% + #1% + \POL@refine@storeleftandright + \fi +}% +\def\POL@refine@loop#1{% + \let\POL@refine@left@next \@empty % no recursion at end sub-intervals + \let\POL@refine@right@next\@empty + \xintiloop[1+1] + \POL@refine@main + \ifnum\POL@IsoRightSign=\z@ + \expandafter\xintbreakiloop + \fi + \ifnum\xintiloopindex<#1 + \repeat +}% +\def\POL@refine@main{% + \edef\POL@isolz@E{\the\numexpr\POL@isolz@E-\@ne}% + \edef\POL@IsoLeft@Int{\xintDSL{\POL@IsoLeft@Int}}% + \edef\POL@IsoRight@Int{\xintDSL{\POL@IsoRight@Int}}% + \let\POL@@IsoRight@Int\POL@IsoRight@Int + \let\POL@@IsoRightSign\POL@IsoRightSign + \edef\POL@IsoRight@Int{\xintInc{\POL@IsoLeft@Int}}% + \edef\POL@IsoRightSign + {\xintiiSgn{\PolEval{\POL@sturmname _0}\At{\POL@IsoRight@raw}}}% + \ifnum\POL@IsoRightSign=\z@ + \let\POL@IsoLeft@Int\POL@IsoRight@Int % root at 1 + \def\POL@IsoLeftSign{0}% + \let\POL@next\@empty + \else + \ifnum\POL@IsoRightSign=\POL@@IsoRightSign\space + \let\POL@next\POL@refine@left@next % may be \@empty or \POL@refine@main for recursion + \let\POL@refine@right@next\@empty + \else + \let\POL@IsoLeft@Int\POL@IsoRight@Int + \edef\POL@IsoRight@Int{\xintDec{\POL@@IsoRight@Int}}% + \edef\POL@IsoRightSign + {\xintiiSgn{\PolEval{\POL@sturmname _0}\At{\POL@IsoRight@raw}}}% + \ifnum\POL@IsoRightSign=\z@ + \let\POL@IsoLeft@Int\POL@IsoRight@Int % root at 9 + \def\POL@IsoLeftSign{0}% + \let\POL@next\@empty + \else + \ifnum\POL@IsoRightSign=\POL@@IsoRightSign\space + \let\POL@next\POL@refine@doonce + \else + \let\POL@IsoLeft@Int\POL@IsoRight@Int + \let\POL@IsoRight@Int\POL@@IsoRight@Int + \let\POL@IsoRightSign\POL@@IsoRightSign + \let\POL@next\POL@refine@right@next + \let\POL@refine@left@next\@empty + \fi + \fi + \fi\fi + \POL@next +}% +% lacking pre-defined xintfrac macro here (such as an \xintRawExponent) +\def\POL@refine@getE#1[#2]{#2}% \xintREZ already applied, for safety + + +\newcommand\PolIntervalWidth[2]{% +% le \xintRez est à cause des E positifs, car trailing zéros explicites +% si je travaillais à partir des variables xintexpr directement ne devrait +% pas être nécessaire, mais trop fragile par rapport à chgt internes possibles + \romannumeral0\xintrez{\xintSub{\@nameuse{POL_ZeroInt#1R}{#2}}% + {\@nameuse{POL_ZeroInt#1L}{#2}}} +}% + + +\newcommand\PolEnsureIntervalLengths[2]{% #1 = Sturm chain name, + % localize roots in intervals of length at most 10^{#2} + \POL@count\z@ + % \POL@count used by \POL@sturmchain@getSV@at but latter not used + \edef\POL@sturmname{#1}% + \edef\POL@ensure@targetE{\the\numexpr#2}% + \edef\POL@nbofroots{\csname POL_ZeroInt\POL@sturmname L\endcsname 0}% + \xintloop + \advance\POL@count\@ne + \edef\POL@isolz@IntervalIndex{\the\POL@count}% + \POL@ensure@one + \ifnum\POL@nbofroots>\POL@count + \repeat +}% +\newcommand\PolEnsureIntervalLength[3]{% #1 = Sturm chain name, + % #2 = index of interval + % localize roots in intervals of length at most 10^{#3} + \edef\POL@sturmname{#1}% + \edef\POL@ensure@targetE{\the\numexpr#3}% + \edef\POL@isolz@IntervalIndex{\the\numexpr#2}% + \POL@ensure@one +}% +\def\POL@ensure@one{% + \POL@set@IsoLeft@rawin + \POL@set@IsoRight@rawin + \edef\POL@ensure@delta{\xintREZ{\xintSub{\POL@IsoRight@rawin}{\POL@IsoLeft@rawin}}}% + \xintiiifZero{\POL@ensure@delta} + {} + {\edef\POL@isolz@E{\expandafter\POL@refine@getE\POL@ensure@delta}% + \expandafter\POL@set@IsoLeft@Int\POL@IsoLeft@rawin + \edef\POL@IsoRight@Int{\xintInc{\POL@IsoLeft@Int}}% + \ifnum\POL@isolz@E>\POL@ensure@targetE\space + \edef\POL@IsoLeftSign + {\xintiiSgn{\PolEval{\POL@sturmname _0}\At{\POL@IsoLeft@raw}}}% + % at start left and right are not roots, and values of opposite signs + % \edef\POL@IsoRightSign{\the\numexpr-\POL@IsoLeftSign}% + \xintloop + \POL@ensure@Eloopbody % decreases E by one at each iteration + % if separation level is still too coarse we recurse at deeper level + \ifnum\POL@isolz@E>\POL@ensure@targetE\space + \repeat + % will check if right is at a zero, needs \POL@IsoRightSign set up + \POL@refine@storeleftandright + \fi + }% +}% +\def\POL@ensure@Eloopbody {% + \edef\POL@isolz@E{\the\numexpr\POL@isolz@E-\@ne}% + \edef\POL@IsoLeft@Int{\xintDSL{\POL@IsoLeft@Int}}% + % this will loop at most ten times + \xintloop + \edef\POL@IsoRight@Int{\xintInc{\POL@IsoLeft@Int}}% + \edef\POL@IsoRightSign + {\xintiiSgn{\PolEval{\POL@sturmname _0}\At{\POL@IsoRight@raw}}}% + % if we have found a zero at right boundary the \ifnum test will fail + % and we exit the loop + % else we exit the loop if sign at right boundary is opposite of + % sign at left boundary (the latter is +1 or -1, never 0) + % this is a bit wasteful if we go ten times to the right, because + % we know that there the sign will be opposite, evaluation was superfluous + \ifnum\POL@IsoLeftSign=\POL@IsoRightSign\space + \let\POL@IsoLeft@Int\POL@IsoRight@Int + \repeat + % check for case when we exited the inner loop because we actually + % found a zero, then we force exit from the main (E decreasing) loop + \ifnum\POL@IsoRightSign=\z@ + \expandafter\xintbreakloop + \fi +}% + + +\catcode`_ 8 +\newcommand\PolPrintIntervals[2][Z]{% + \POL@count \@nameuse{POL_ZeroInt#2L}{0} + \ifnum\POL@count=\z@ +% No real roots.\par + \else +% There are \the\POL@count\space distinct real roots:\par + \[\count@\POL@count + \global\POL@count\@ne + \begin{array}{rcccl} + \xintloop + \POL@SturmIfZeroExactlyKnown{#2}\POL@count + {% exact root + && + #1_{\the\POL@count}&=& + \POL@printintervals@prepare{#2R}% + \PolPrintIntervalsPrintExactZero + }% + {% interval with root in its strict interior + \POL@printintervals@prepare{#2L}% + \PolPrintIntervalsPrintLeftEndPoint&<& + #1_{\the\POL@count}&<& + \POL@printintervals@prepare{#2R}% + \PolPrintIntervalsPrintRightEndPoint + }% + \global\advance\POL@count\@ne + \unless\ifnum\POL@count>\count@ + \\% + \repeat + \end{array}\] + \fi +}% +\catcode`_ 11 +\newcommand\PolPrintIntervalsPrintExactZero {\PolPrintIntervalsTheEndPoint}% +\newcommand\PolPrintIntervalsPrintLeftEndPoint {\PolPrintIntervalsTheEndPoint}% +\newcommand\PolPrintIntervalsPrintRightEndPoint{\PolPrintIntervalsTheEndPoint}% +\def\POL@printintervals@prepare#1{% + \edef\PolPrintIntervalsTheIndex{\the\POL@count}% + \edef\PolPrintIntervalsTheEndPoint{\@nameuse{POL_ZeroInt#1}\POL@count}% + \xintiiifSgn{\POL@xintexprGetVar{#1_\PolPrintIntervalsTheIndex}} + {\let\PolIfEndPointIsPositive\xint_secondoftwo + \let\PolIfEndPointIsNegative\xint_firstoftwo + \let\PolIfEndPointIsZero\xint_secondoftwo} + {\let\PolIfEndPointIsPositive\xint_secondoftwo + \let\PolIfEndPointIsNegative\xint_secondoftwo + \let\PolIfEndPointIsZero\xint_firstoftwo} + {\let\PolIfEndPointIsPositive\xint_firstoftwo + \let\PolIfEndPointIsNegative\xint_secondoftwo + \let\PolIfEndPointIsZero\xint_secondoftwo}% +}% +\newcommand\POL@SturmIfZeroExactlyKnown[2]{% faster than public one, + % but does not check if #2 is in range + \romannumeral0\xintifeq{\POL@xintexprGetVar{#1L_\the\numexpr#2\relax}}% + {\POL@xintexprGetVar{#1R_\the\numexpr#2\relax}}% +}% + + +\newcommand\PolSturmIfZeroExactlyKnown[2]{% + \romannumeral0\xintifeq{\PolSturmIsolatedZeroLeft{#1}{#2}}% + {\PolSturmIsolatedZeroRight{#1}{#2}}% +}% +\newcommand\PolSturmIsolatedZeroLeft[2]{% + \romannumeral`^^@\csname POL_ZeroInt#1L\endcsname{#2}}% +\newcommand\PolSturmIsolatedZeroRight[2]{% + \romannumeral`^^@\csname POL_ZeroInt#1R\endcsname{#2}}% +\newcommand\PolSturmNbOfIsolatedZeros[1]{% + \romannumeral`^^@\csname POL_ZeroInt#1L0\endcsname +}% + +%% \PolDecToString (should become an xintfrac macro at some point) +\newcommand\PolDecToString[1]{\romannumeral0\expandafter + \POL@dectostring\romannumeral0\xintraw{#1}}% +\def\POL@dectostring #1/#2[#3]{\xintiiifZero {#1}% + \POL@dectostring@z + {\if1\XINT_isOne{#2}\expandafter\POL@dectostring@a + \else\expandafter\POL@dectostring@b + \fi}% + #1/#2[#3]% +}% +\def\POL@dectostring@z#1[#2]{ 0}% +\def\POL@dectostring@a#1/#2[#3]{% + \ifnum#3<\z@\xint_dothis{\xinttrunc{-#3}{#1[#3]}}\fi + \xint_orthat{\xintiie{#1}{#3}}% +}% +\def\POL@dectostring@b#1/#2[#3]{% just to handle this somehow + \ifnum#3<\z@\xint_dothis{\xinttrunc{-#3}{#1[#3]}/#2}\fi + \xint_orthat{\xintiie{#1}{#3}/#2}% +}% + + +\newcommand\PolMakeMonic[1]{% + \edef\POL@leadingcoeff{\PolLeadingCoeff{#1}}% + \edef\POL@leadingcoeff@inverse{\xintDiv{1/1[0]}{\POL@leadingcoeff}}% + \PolMapCoeffs{\xintMul{\POL@leadingcoeff@inverse}}{#1}% }% @@ -635,7 +1490,7 @@ \def\POL@add@b{\POL@get\POL@B\POL@add@c}% \def\POL@add@c{% \global\POL@poltrue - \POL@ifZero\POL@A + \POL@ifZero\POL@A {\let\POL@result\POL@B}% {\POL@ifZero\POL@B {\let\POL@result\POL@A}% @@ -678,7 +1533,7 @@ \def\POL@mul@b{\POL@get\POL@B\POL@mul@c}% \def\POL@mul@c{% \global\POL@poltrue - \POL@ifZero\POL@A + \POL@ifZero\POL@A {\def\POL@result{-1.\empty{0/1[0]}}}% {\POL@ifZero\POL@B {\def\POL@result{-1.\empty{0/1[0]}}}% @@ -731,7 +1586,7 @@ \ifnum\count\tw@<\count@ \repeat \expandafter\let\csname POL@arrayC\the\count@\endcsname\POL@tmp -}% +}% \def\POL@@mul@phaseIIloopbody{% \advance\count@\@ne \def\POL@tmp{0[0]}% @@ -748,7 +1603,7 @@ {\@nameuse{POL@arrayB\the\numexpr\count@+\@ne-\count\tw@}}% }% }% - \repeat + \repeat \expandafter\let\csname POL@arrayC\the\count@\endcsname\POL@tmp }% \def\POL@@mul@phaseIIIloopbody{% @@ -766,7 +1621,7 @@ }% }% \ifnum\@nameuse{POL@arrayA0}>\count\tw@ - \repeat + \repeat \expandafter\let\csname POL@arrayC\the\count@\endcsname\POL@tmp }% @@ -848,7 +1703,7 @@ \ifodd\POL@pow@exp\space \expandafter\POL@@pow@odd \the\numexpr(\POL@pow@exp+\@ne)/\tw@-\@ne\expandafter.% - \else + \else \expandafter\POL@@pow@even \the\numexpr(\POL@pow@exp+\@ne)/\tw@-\@ne\expandafter.% \fi @@ -915,7 +1770,7 @@ \xintScalarDiv{\csname POL@arrayR\the\count@\endcsname}% {\POL@B@leading}}% \expandafter\let\csname POL@arrayQ\the\count\tw@\endcsname - \POL@@div@ratio + \POL@@div@ratio \advance\count@\m@ne \advance\count\tw@\m@ne \count4 \count@ @@ -956,17 +1811,41 @@ %% EXPANDABLE MACROS -\newcommand\PolEval{}% -\def\PolEval#1#2\At#3{\romannumeral`^^@\xinttheexpr #1(#3)\relax}% +\def\Pol@Eval@fork#1\At#2#3\krof{#2}% +\newcommand\PolEval[3]{\romannumeral`^^@\Pol@Eval@fork + #2\PolEvalAt + \At\PolEvalAtExpr\krof {#1}{#3}% +}% +\newcommand\PolEvalAt[2] + {\xintpraw{\csname XINT_expr_userfunc_#1\endcsname{#2},}}% +\newcommand\PolEvalAtExpr[2]{\xinttheexpr #1(#2)\relax}% +% +\newcommand\PolEvalReduced[3]{\romannumeral`^^@\Pol@Eval@fork + #2\PolEvalReducedAt + \At\PolEvalReducedAtExpr\krof {#1}{#3}% +}% +\newcommand\PolEvalReducedAt[2]{% + \xintpraw % in order not to print denominator if the latter equals 1 + {\xintIrr{\csname XINT_expr_userfunc_#1\endcsname{#2},}[0]}% +}% +\newcommand\PolEvalReducedAtExpr[2]{% + \xintpraw + {\xintIrr{\romannumeral`^^@\xintthebareeval#1(#2)\relax}[0]}% +}% % -\newcommand\PolEvalReduced{}% -\def\PolEvalReduced#1#2\At#3{% - \romannumeral0\xintpraw % only serves to not print denominator if = 1 - {\xintIrr{\romannumeral`^^@\xintthebareeval#1(#3)\relax}[0]}% +\newcommand\PolFloatEval[3]{\romannumeral`^^@\Pol@Eval@fork + #2\PolFloatEvalAt + \At\PolFloatEvalAtExpr\krof {#1}{#3}% }% +\newcommand\PolFloatEvalAt[2] + {\xintpfloat{\csname XINT_flexpr_userfunc_#1\endcsname{#2},}}% +\newcommand\PolFloatEvalAtExpr[2]{\xintthefloatexpr #1(#2)\relax}% % -\newcommand\PolFloatEval{}% -\def\PolFloatEval#1#2\At#3{\romannumeral`^^@\xintthefloatexpr #1(#3)\relax}% +\newcommand\PolLeadingCoeff[1]{% + \romannumeral`^^@\expandafter\expandafter\expandafter\xintlastitem + \expandafter\expandafter\expandafter + {\csname POLuserpol@#1\endcsname}% +}% % \newcommand\PolNthCoeff[2]{\romannumeral`^^@% \expandafter\POL@nthcoeff @@ -990,11 +1869,10 @@ \newcommand\PolToCSV[1]{\romannumeral0\xintlistwithsep{, }{\PolToList{#1}}}% -\newif\ifpoltoexprall \newcommand\PolToExprCmd[1]{\xintPRaw{\xintRawWithZeros{#1}}}% \newcommand\PolToFloatExprCmd[1]{\xintFloat{#1}}% \let\PolToExprTermPrefix\PolTypesetCmdPrefix -\newcommand\PolToExprOneTerm[2]{% +\newcommand\PolToExprOneTermStyleA[2]{% \ifnum#2=\z@ \PolToExprCmd{#1}% \else @@ -1007,6 +1885,7 @@ \else\PolToExprVar^\xintiiAbs{#2}% \fi }% +\let\PolToExprOneTerm\PolToExprOneTermStyleA \newcommand\PolToExprOneTermStyleB[2]{% \ifnum#2=\z@ \xintNumerator{#1}% -- cgit v1.2.3