diff options
Diffstat (limited to 'Master/texmf-dist/doc/latex/polexpr/polexpr.txt')
-rw-r--r-- | Master/texmf-dist/doc/latex/polexpr/polexpr.txt | 1235 |
1 files changed, 1113 insertions, 122 deletions
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}<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 --------------------- @@ -143,27 +346,20 @@ Non-expandable macros 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:: + .. attention:: - Package macros (such as derivatives or Euclidean division) - operate with the "exact" polynomials; "floating point" - polynomials are always obtained in a second step. + Release ``0.3`` also did the necessary set-up to let the + polynomial be known to the ``\xintfloatexpr`` (or + ``\xintdeffloatvar``) parser. - To modifiy "in-place" the original coefficients of a polynomial - and round them to float precision:: + 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. - \PolMapCoeffs{\xintFloat}{polname} - % or \xintFloat[P] for precision P digits - - See `\\PolMapCoeffs{\\macro}{polname}`_. + 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 @@ -174,10 +370,34 @@ Non-expandable macros ``\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 <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: + +``\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}{<csv>}`` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -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 ``<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*: + +``\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 + <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 <PolEvalAt_>`_. + +.. _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 + <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 <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 <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}{\<csv\>}_>`_. +.. _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 + ``<sturmname>_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 <poldef;_>`_ parser itself, + * Differentiation and anti-differentiation, + * Euclidean division and GCDs, + * Various utilities such as `\\PolFromCSV <PolFromCSV_>`_, + `\\PolMapCoeffs <PolMapCoeffs_>`_, + `\\PolToCSV <PolToCSV_>`_, `\\PolToExpr <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 <PolEvalAt_>`_ 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} <PolEvalAtExpr_>`_ syntax is needed for + using expressions in the second argument. + * incompatible or breaking changes: + + - `\\PolToExpr <PolToExpr_>`_ now by default uses *descending* + powers (it also treats differently coefficients equal to 1 or -1.) + Use `\\PolToExpr* <PolToExpr*_>`_ for *ascending* powers. + - `\\PolEval <PolEvalAt_>`_ 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 + <PolEvalReducedAt_>`_. + * new (or newly documented) macros: + + - `\\PolTypesetCmd <PolTypesetCmd_>`_ + - `\\PolTypesetCmdPrefix <PolTypesetCmdPrefix_>`_ + - `\\PolTypesetMonomialCmd <PolTypesetMonomialCmd_>`_ + - `\\PolEvalReducedAt <PolEvalReducedAt_>`_ + - `\\PolToFloatExpr <PolToFloatExpr_>`_ + - `\\PolToExprOneTerm <PolToExprOneTerm_>`_ + - `\\PolToFloatExprOneTerm <PolToFloatExprOneTerm_>`_ + - `\\PolToExprCmd <PolToExprCmd_>`_ + - `\\PolToFloatExprCmd <PolToFloatExprCmd_>`_ + - `\\PolToExprTermPrefix <PolToExprTermPrefix_>`_ + - `\\PolToExprVar <PolToExprVar_>`_ + - `\\PolToExprTimes <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 <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 <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 <PolMapCoeffs_>`_. + - `\\PolGCD <PolGCD_>`_ was buggy in case of first polynomial being + of lesser degree than the second one. + * breaking changes: + + - formerly `\\PolEval{P}\\At{foo} <PolEvalAt_>`_ 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} <PolEvalAtExpr_>`_ 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 <PolEvalReducedAt_>`_ + and `\\PolFloatEval <PolFloatEvalAt_>`_. + - 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 <PolGenFloatVariant_>`_. + * new non-expandable macros: + + - `\\PolGenFloatVariant <PolGenFloatVariant_>`_ + - `\\PolGlobalLet <PolGlobalLet_>`_ + - `\\PolTypesetOne <PolTypesetOne_>`_ + - `\\PolQuo <PolQuo_>`_ + - `\\PolRem <PolRem_>`_ + - `\\PolToSturm <PolToSturm_>`_ + - `\\PolToSturm\* <PolToSturm*_>`_ + - `\\PolSetToSturmChainSignChangesAt <PolSetToSturmChainSignChangesAt_>`_ + - `\\PolSetToNbOfZerosWithin <PolSetToNbOfZerosWithin_>`_ + - `\\PolSturmIsolateZeros <PolSturmIsolateZeros_>`_ + - `\\PolRefineInterval* <PolRefineInterval*_>`_ + - `\\PolRefineInterval[N] <PolRefineInterval[N]_>`_ + - `\\PolEnsureIntervalLength <PolEnsureIntervalLength_>`_ + - `\\PolEnsureIntervalLengths <PolEnsureIntervalLengths_>`_ + - `\\PolPrintIntervals <PolPrintIntervals_>`_ + - `\\PolPrintIntervalsPrintExactZero <PolPrintIntervalsPrintExactZero_>`_ + - `\\PolPrintIntervalsPrintLeftEndPoint <PolPrintIntervalsPrintLeftEndPoint_>`_ + - `\\PolPrintIntervalsPrintRightEndPoint <PolPrintIntervalsPrintRightEndPoint_>`_ + - `\\PolReduceCoeffs* <PolReduceCoeffs*_>`_ + - `\\PolMakeMonic <PolMakeMonic_>`_ + * new expandable macros: + + - `\\PolToExprOneTermStyleA <PolToExprOneTermStyleA_>`_ + - `\\PolIfCoeffIsPlusOrMinusOne <PolIfCoeffIsPlusOrMinusOne_>`_ + - `\\PolLeadingCoeff <PolLeadingCoeff_>`_ + - `\\PolSturmChainLength <PolSturmChainLength_>`_ + - `\\PolSturmNbOfIsolatedZeros <PolSturmNbOfIsolatedZeros_>`_ + - `\\PolSturmIfZeroExactlyKnown <PolSturmIfZeroExactlyKnown_>`_ + - `\\PolSturmIsolatedZeroLeft <PolSturmIsolatedZeroLeft_>`_ + - `\\PolSturmIsolatedZeroRight <PolSturmIsolatedZeroRight_>`_ + - `\\PolPrintIntervalsTheEndPoint <PolPrintIntervalsTheEndPoint_>`_ + - `\\PolPrintIntervalsTheIndex <PolPrintIntervalsTheIndex_>`_ + - `\\PolIfEndPointIsPositive <PolIfEndPointIsPositive_>`_ + - `\\PolIfEndPointIsNegative <PolIfEndPointIsNegative_>`_ + - `\\PolIfEndPointIsZero <PolIfEndPointIsZero_>`_ + - `\\PolIntervalWidth <PolIntervalWidth_>`_ + - `\\PolDecToString <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 |