diff options
| -rw-r--r-- | Master/texmf-dist/doc/latex/polexpr/README.md | 99 | ||||
| -rw-r--r-- | Master/texmf-dist/doc/latex/polexpr/polexpr.html | 1317 | ||||
| -rw-r--r-- | Master/texmf-dist/doc/latex/polexpr/polexpr.txt | 1235 | ||||
| -rw-r--r-- | Master/texmf-dist/tex/latex/polexpr/polexpr.sty | 1013 |
4 files changed, 3195 insertions, 469 deletions
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 { <body> <div class="document" id="package-polexpr-documentation"> <h1 class="title">Package polexpr documentation</h1> -<h2 class="subtitle" id="id1">0.3.1 (2018/01/18)</h2> +<h2 class="subtitle" id="id1">0.4 (2018/02/16)</h2> <!-- comment: -*- fill-column: 72; mode: rst; -*- --> <div class="contents topic" id="contents"> <p class="topic-title first">Contents</p> <ul class="simple"> -<li><a class="reference internal" href="#first-examples" id="id15">First Examples</a></li> -<li><a class="reference internal" href="#non-expandable-macros" id="id16">Non-expandable macros</a><ul> -<li><a class="reference internal" href="#poldef-polname-letter-expression-in-letter" id="id17"><tt class="docutils literal">\poldef <span class="pre">polname(letter):=</span> expression in letter;</tt></a></li> -<li><a class="reference internal" href="#poldef-letter-polname-expression-in-letter" id="id18"><tt class="docutils literal"><span class="pre">\PolDef[letter]{polname}{expression</span> in letter}</tt></a></li> -<li><a class="reference internal" href="#pollet-polname-2-polname-1" id="id19"><tt class="docutils literal"><span class="pre">\PolLet{polname_2}={polname_1}</span></tt></a></li> -<li><a class="reference internal" href="#polassign-polname-toarray-macro" id="id20"><tt class="docutils literal"><span class="pre">\PolAssign{polname}\toarray\macro</span></tt></a></li> -<li><a class="reference internal" href="#polget-polname-fromarray-macro" id="id21"><tt class="docutils literal"><span class="pre">\PolGet{polname}\fromarray\macro</span></tt></a></li> -<li><a class="reference internal" href="#polfromcsv-polname-csv" id="id22"><tt class="docutils literal"><span class="pre">\PolFromCSV{polname}{<csv>}</span></tt></a></li> -<li><a class="reference internal" href="#poltypeset-polname" id="id23"><tt class="docutils literal">\PolTypeset{polname}</tt></a><ul> -<li><a class="reference internal" href="#poltypesetcmd-raw-coeff" id="id24"><tt class="docutils literal">\PolTypesetCmd{raw_coeff}</tt></a></li> -<li><a class="reference internal" href="#poltypesetcmdprefix-raw-coeff" id="id25"><tt class="docutils literal">\PolTypesetCmdPrefix{raw_coeff}</tt></a></li> -<li><a class="reference internal" href="#poltypesetmonomialcmd" id="id26"><tt class="docutils literal">\PolTypesetMonomialCmd</tt></a></li> +<li><a class="reference internal" href="#basic-examples" id="id33">Basic Examples</a></li> +<li><a class="reference internal" href="#examples-of-localization-of-roots" id="id34">Examples of localization of roots</a><ul> +<li><a class="reference internal" href="#a-typical-example" id="id35">A typical example</a></li> +<li><a class="reference internal" href="#a-degree-four-polynomial-with-nearby-roots" id="id36">A degree four polynomial with nearby roots</a></li> +<li><a class="reference internal" href="#the-degree-nine-polynomial-with-0-99-0-999-0-9999-as-triple-roots" id="id37">The degree nine polynomial with 0.99, 0.999, 0.9999 as triple roots</a></li> +<li><a class="reference internal" href="#a-mignotte-type-polynomial" id="id38">A Mignotte type polynomial</a></li> +<li><a class="reference internal" href="#the-degree-41-polynomial-with-2-1-9-1-8-0-0-1-1-9-2-as-roots" id="id39">The degree 41 polynomial with -2, -1.9, -1.8, ..., 0, 0.1, ..., 1.9, 2 as roots</a></li> +<li><a class="reference internal" href="#roots-of-chebyshev-polynomials" id="id40">Roots of Chebyshev polynomials</a></li> </ul> </li> -<li><a class="reference internal" href="#id5" id="id27"><tt class="docutils literal"><span class="pre">\PolTypeset*{polname}</span></tt></a></li> -<li><a class="reference internal" href="#poldiff-polname-1-polname-2" id="id28"><tt class="docutils literal"><span class="pre">\PolDiff{polname_1}{polname_2}</span></tt></a></li> -<li><a class="reference internal" href="#poldiff-n-polname-1-polname-2" id="id29"><tt class="docutils literal"><span class="pre">\PolDiff[N]{polname_1}{polname_2}</span></tt></a></li> -<li><a class="reference internal" href="#polantidiff-polname-1-polname-2" id="id30"><tt class="docutils literal"><span class="pre">\PolAntiDiff{polname_1}{polname_2}</span></tt></a></li> -<li><a class="reference internal" href="#polantidiff-n-polname-1-polname-2" id="id31"><tt class="docutils literal"><span class="pre">\PolAntiDiff[N]{polname_1}{polname_2}</span></tt></a></li> -<li><a class="reference internal" href="#poldivide-polname-1-polname-2-polname-q-polname-r" id="id32"><tt class="docutils literal"><span class="pre">\PolDivide{polname_1}{polname_2}{polname_Q}{polname_R}</span></tt></a></li> -<li><a class="reference internal" href="#polgcd-polname-1-polname-2-polname-gcd" id="id33"><tt class="docutils literal"><span class="pre">\PolGCD{polname_1}{polname_2}{polname_GCD}</span></tt></a></li> -<li><a class="reference internal" href="#polmapcoeffs-macro-polname" id="id34"><tt class="docutils literal"><span class="pre">\PolMapCoeffs{\macro}{polname}</span></tt></a></li> -<li><a class="reference internal" href="#polreducecoeffs-polname" id="id35"><tt class="docutils literal">\PolReduceCoeffs{polname}</tt></a></li> +<li><a class="reference internal" href="#non-expandable-macros" id="id41">Non-expandable macros</a><ul> +<li><a class="reference internal" href="#poldef-polname-letter-expression-in-letter" id="id42"><tt class="docutils literal">\poldef <span class="pre">polname(letter):=</span> expression in letter;</tt></a></li> +<li><a class="reference internal" href="#poldef-letter-polname-expression-in-letter" id="id43"><tt class="docutils literal"><span class="pre">\PolDef[letter]{polname}{expression</span> in letter}</tt></a></li> +<li><a class="reference internal" href="#polgenfloatvariant-polname" id="id44"><tt class="docutils literal">\PolGenFloatVariant{polname}</tt></a></li> +<li><a class="reference internal" href="#pollet-polname-2-polname-1" id="id45"><tt class="docutils literal"><span class="pre">\PolLet{polname_2}={polname_1}</span></tt></a></li> +<li><a class="reference internal" href="#polgloballet-polname-2-polname-1" id="id46"><tt class="docutils literal"><span class="pre">\PolGlobalLet{polname_2}={polname_1}</span></tt></a></li> +<li><a class="reference internal" href="#polassign-polname-toarray-macro" id="id47"><tt class="docutils literal"><span class="pre">\PolAssign{polname}\toarray\macro</span></tt></a></li> +<li><a class="reference internal" href="#polget-polname-fromarray-macro" id="id48"><tt class="docutils literal"><span class="pre">\PolGet{polname}\fromarray\macro</span></tt></a></li> +<li><a class="reference internal" href="#polfromcsv-polname-csv" id="id49"><tt class="docutils literal"><span class="pre">\PolFromCSV{polname}{<csv>}</span></tt></a></li> +<li><a class="reference internal" href="#poltypeset-polname" id="id50"><tt class="docutils literal">\PolTypeset{polname}</tt></a><ul> +<li><a class="reference internal" href="#poltypesetcmd-raw-coeff" id="id51"><tt class="docutils literal">\PolTypesetCmd{raw_coeff}</tt></a></li> +<li><a class="reference internal" href="#poltypesetone-raw-coeff" id="id52"><tt class="docutils literal">\PolTypesetOne{raw_coeff}</tt></a></li> +<li><a class="reference internal" href="#id6" id="id53"><tt class="docutils literal">\PolTypesetMonomialCmd</tt></a></li> +<li><a class="reference internal" href="#poltypesetcmdprefix-raw-coeff" id="id54"><tt class="docutils literal">\PolTypesetCmdPrefix{raw_coeff}</tt></a></li> </ul> </li> -<li><a class="reference internal" href="#expandable-macros" id="id36">Expandable macros</a><ul> -<li><a class="reference internal" href="#poleval-polname-at-numerical-expression" id="id37"><tt class="docutils literal"><span class="pre">\PolEval{polname}\At{numerical</span> expression}</tt></a></li> -<li><a class="reference internal" href="#polevalreduced-polname-at-numerical-expression" id="id38"><tt class="docutils literal"><span class="pre">\PolEvalReduced{polname}\At{numerical</span> expression}</tt></a></li> -<li><a class="reference internal" href="#polfloateval-polname-at-numerical-expression" id="id39"><tt class="docutils literal"><span class="pre">\PolFloatEval{polname}\At{numerical</span> expression}</tt></a></li> -<li><a class="reference internal" href="#polnthcoeff-polname-number" id="id40"><tt class="docutils literal"><span class="pre">\PolNthCoeff{polname}{number}</span></tt></a></li> -<li><a class="reference internal" href="#poldegree-polname" id="id41"><tt class="docutils literal">\PolDegree{polname}</tt></a></li> -<li><a class="reference internal" href="#poltoexpr-polname" id="id42"><tt class="docutils literal">\PolToExpr{polname}</tt></a><ul> -<li><a class="reference internal" href="#poltoexproneterm-raw-coeff-number" id="id43"><tt class="docutils literal"><span class="pre">\PolToExprOneTerm{raw_coeff}{number}</span></tt></a></li> -<li><a class="reference internal" href="#poltoexpronetermstyleb-raw-coeff-number" id="id44"><tt class="docutils literal"><span class="pre">\PolToExprOneTermStyleB{raw_coeff}{number}</span></tt></a></li> -<li><a class="reference internal" href="#poltoexprcmd-raw-coeff" id="id45"><tt class="docutils literal">\PolToExprCmd{raw_coeff}</tt></a></li> -<li><a class="reference internal" href="#poltoexprtermprefix-raw-coeff" id="id46"><tt class="docutils literal">\PolToExprTermPrefix{raw_coeff}</tt></a></li> -<li><a class="reference internal" href="#poltoexprvar" id="id47"><tt class="docutils literal">\PolToExprVar</tt></a></li> -<li><a class="reference internal" href="#poltoexprtimes" id="id48"><tt class="docutils literal">\PolToExprTimes</tt></a></li> +<li><a class="reference internal" href="#id8" id="id55"><tt class="docutils literal"><span class="pre">\PolTypeset*{polname}</span></tt></a></li> +<li><a class="reference internal" href="#poldiff-polname-1-polname-2" id="id56"><tt class="docutils literal"><span class="pre">\PolDiff{polname_1}{polname_2}</span></tt></a></li> +<li><a class="reference internal" href="#poldiff-n-polname-1-polname-2" id="id57"><tt class="docutils literal"><span class="pre">\PolDiff[N]{polname_1}{polname_2}</span></tt></a></li> +<li><a class="reference internal" href="#polantidiff-polname-1-polname-2" id="id58"><tt class="docutils literal"><span class="pre">\PolAntiDiff{polname_1}{polname_2}</span></tt></a></li> +<li><a class="reference internal" href="#polantidiff-n-polname-1-polname-2" id="id59"><tt class="docutils literal"><span class="pre">\PolAntiDiff[N]{polname_1}{polname_2}</span></tt></a></li> +<li><a class="reference internal" href="#poldivide-polname-1-polname-2-polname-q-polname-r" id="id60"><tt class="docutils literal"><span class="pre">\PolDivide{polname_1}{polname_2}{polname_Q}{polname_R}</span></tt></a></li> +<li><a class="reference internal" href="#polquo-polname-1-polname-2-polname-q" id="id61"><tt class="docutils literal"><span class="pre">\PolQuo{polname_1}{polname_2}{polname_Q}</span></tt></a></li> +<li><a class="reference internal" href="#polrem-polname-1-polname-2-polname-r" id="id62"><tt class="docutils literal"><span class="pre">\PolRem{polname_1}{polname_2}{polname_R}</span></tt></a></li> +<li><a class="reference internal" href="#polgcd-polname-1-polname-2-polname-gcd" id="id63"><tt class="docutils literal"><span class="pre">\PolGCD{polname_1}{polname_2}{polname_GCD}</span></tt></a></li> +<li><a class="reference internal" href="#poltosturm-polname-sturmname" id="id64"><tt class="docutils literal"><span class="pre">\PolToSturm{polname}{sturmname}</span></tt></a></li> +<li><a class="reference internal" href="#id10" id="id65"><tt class="docutils literal"><span class="pre">\PolToSturm*{polname}{sturmname}</span></tt></a></li> +<li><a class="reference internal" href="#polsettosturmchainsignchangesat-macro-sturmname-fraction" id="id66"><tt class="docutils literal"><span class="pre">\PolSetToSturmChainSignChangesAt{\macro}{sturmname}{fraction}</span></tt></a></li> +<li><a class="reference internal" href="#polsettonbofzeroswithin-macro-sturmname-value-a-value-b" id="id67"><tt class="docutils literal"><span class="pre">\PolSetToNbOfZerosWithin{\macro}{sturmname}{value_a}{value_b}</span></tt></a></li> +<li><a class="reference internal" href="#polsturmisolatezeros-sturmname" id="id68"><tt class="docutils literal">\PolSturmIsolateZeros{sturmname}</tt></a></li> +<li><a class="reference internal" href="#polrefineinterval-sturmname-index" id="id69"><tt class="docutils literal"><span class="pre">\PolRefineInterval*{sturmname}{index}</span></tt></a></li> +<li><a class="reference internal" href="#polrefineinterval-n-sturmname-index" id="id70"><tt class="docutils literal"><span class="pre">\PolRefineInterval[N]{sturmname}{index}</span></tt></a></li> +<li><a class="reference internal" href="#polensureintervallength-sturmname-index-e" id="id71"><tt class="docutils literal"><span class="pre">\PolEnsureIntervalLength{sturmname}{index}{E}</span></tt></a></li> +<li><a class="reference internal" href="#polensureintervallengths-sturmname-e" id="id72"><tt class="docutils literal"><span class="pre">\PolEnsureIntervalLengths{sturmname}{E}</span></tt></a></li> +<li><a class="reference internal" href="#polprintintervals-varname-sturmname" id="id73"><tt class="docutils literal"><span class="pre">\PolPrintIntervals[varname]{sturmname}</span></tt></a><ul> +<li><a class="reference internal" href="#id11" id="id74"><tt class="docutils literal">\PolPrintIntervalsPrintExactZero</tt></a></li> +<li><a class="reference internal" href="#id12" id="id75"><tt class="docutils literal">\PolPrintIntervalsPrintLeftEndPoint</tt></a></li> +<li><a class="reference internal" href="#id13" id="id76"><tt class="docutils literal">\PolPrintIntervalsPrintRightEndPoint</tt></a></li> </ul> </li> -<li><a class="reference internal" href="#id12" id="id49"><tt class="docutils literal"><span class="pre">\PolToExpr*{polname}</span></tt></a></li> -<li><a class="reference internal" href="#poltofloatexpr-polname" id="id50"><tt class="docutils literal">\PolToFloatExpr{polname}</tt></a><ul> -<li><a class="reference internal" href="#poltofloatexproneterm-raw-coeff-number" id="id51"><tt class="docutils literal"><span class="pre">\PolToFloatExprOneTerm{raw_coeff}{number}</span></tt></a></li> -<li><a class="reference internal" href="#poltofloatexprcmd-raw-coeff" id="id52"><tt class="docutils literal">\PolToFloatExprCmd{raw_coeff}</tt></a></li> +<li><a class="reference internal" href="#polmapcoeffs-macro-polname" id="id77"><tt class="docutils literal"><span class="pre">\PolMapCoeffs{\macro}{polname}</span></tt></a></li> +<li><a class="reference internal" href="#polreducecoeffs-polname" id="id78"><tt class="docutils literal">\PolReduceCoeffs{polname}</tt></a></li> +<li><a class="reference internal" href="#id15" id="id79"><tt class="docutils literal"><span class="pre">\PolReduceCoeffs*{polname}</span></tt></a></li> +<li><a class="reference internal" href="#polmakemonic-polname" id="id80"><tt class="docutils literal">\PolMakeMonic{polname}</tt></a></li> </ul> </li> -<li><a class="reference internal" href="#id13" id="id53"><tt class="docutils literal"><span class="pre">\PolToFloatExpr*{polname}</span></tt></a></li> -<li><a class="reference internal" href="#poltolist-polname" id="id54"><tt class="docutils literal">\PolToList{polname}</tt></a></li> -<li><a class="reference internal" href="#poltocsv-polname" id="id55"><tt class="docutils literal">\PolToCSV{polname}</tt></a></li> +<li><a class="reference internal" href="#expandable-macros" id="id81">Expandable macros</a><ul> +<li><a class="reference internal" href="#poleval-polname-atexpr-numerical-expression" id="id82"><tt class="docutils literal"><span class="pre">\PolEval{polname}\AtExpr{numerical</span> expression}</tt></a></li> +<li><a class="reference internal" href="#poleval-polname-at-fraction" id="id83"><tt class="docutils literal"><span class="pre">\PolEval{polname}\At{fraction}</span></tt></a></li> +<li><a class="reference internal" href="#polevalreduced-polname-atexpr-numerical-expression" id="id84"><tt class="docutils literal"><span class="pre">\PolEvalReduced{polname}\AtExpr{numerical</span> expression}</tt></a></li> +<li><a class="reference internal" href="#polevalreduced-polname-at-fraction" id="id85"><tt class="docutils literal"><span class="pre">\PolEvalReduced{polname}\At{fraction}</span></tt></a></li> +<li><a class="reference internal" href="#polfloateval-polname-atexpr-numerical-expression" id="id86"><tt class="docutils literal"><span class="pre">\PolFloatEval{polname}\AtExpr{numerical</span> expression}</tt></a></li> +<li><a class="reference internal" href="#polfloateval-polname-at-fraction" id="id87"><tt class="docutils literal"><span class="pre">\PolFloatEval{polname}\At{fraction}</span></tt></a></li> +<li><a class="reference internal" href="#polifcoeffisplusorminusone-a-b" id="id88"><tt class="docutils literal"><span class="pre">\PolIfCoeffIsPlusOrMinusOne{A}{B}</span></tt></a></li> +<li><a class="reference internal" href="#polleadingcoeff-polname" id="id89"><tt class="docutils literal">\PolLeadingCoeff{polname}</tt></a></li> +<li><a class="reference internal" href="#polnthcoeff-polname-number" id="id90"><tt class="docutils literal"><span class="pre">\PolNthCoeff{polname}{number}</span></tt></a></li> +<li><a class="reference internal" href="#poldegree-polname" id="id91"><tt class="docutils literal">\PolDegree{polname}</tt></a></li> +<li><a class="reference internal" href="#poltoexpr-polname" id="id92"><tt class="docutils literal">\PolToExpr{polname}</tt></a><ul> +<li><a class="reference internal" href="#poltoexproneterm-raw-coeff-number" id="id93"><tt class="docutils literal"><span class="pre">\PolToExprOneTerm{raw_coeff}{number}</span></tt></a></li> +<li><a class="reference internal" href="#poltoexpronetermstylea-raw-coeff-number" id="id94"><tt class="docutils literal"><span class="pre">\PolToExprOneTermStyleA{raw_coeff}{number}</span></tt></a></li> +<li><a class="reference internal" href="#poltoexpronetermstyleb-raw-coeff-number" id="id95"><tt class="docutils literal"><span class="pre">\PolToExprOneTermStyleB{raw_coeff}{number}</span></tt></a></li> +<li><a class="reference internal" href="#poltoexprcmd-raw-coeff" id="id96"><tt class="docutils literal">\PolToExprCmd{raw_coeff}</tt></a></li> +<li><a class="reference internal" href="#poltoexprtermprefix-raw-coeff" id="id97"><tt class="docutils literal">\PolToExprTermPrefix{raw_coeff}</tt></a></li> +<li><a class="reference internal" href="#id23" id="id98"><tt class="docutils literal">\PolToExprVar</tt></a></li> +<li><a class="reference internal" href="#id24" id="id99"><tt class="docutils literal">\PolToExprTimes</tt></a></li> </ul> </li> -<li><a class="reference internal" href="#booleans-with-default-setting-as-indicated" id="id56">Booleans (with default setting as indicated)</a><ul> -<li><a class="reference internal" href="#xintverbosefalse" id="id57"><tt class="docutils literal">\xintverbosefalse</tt></a></li> -<li><a class="reference internal" href="#poltypesetallfalse" id="id58"><tt class="docutils literal">\poltypesetallfalse</tt></a></li> -<li><a class="reference internal" href="#poltoexprallfalse" id="id59"><tt class="docutils literal">\poltoexprallfalse</tt></a></li> +<li><a class="reference internal" href="#id26" id="id100"><tt class="docutils literal"><span class="pre">\PolToExpr*{polname}</span></tt></a></li> +<li><a class="reference internal" href="#poltofloatexpr-polname" id="id101"><tt class="docutils literal">\PolToFloatExpr{polname}</tt></a><ul> +<li><a class="reference internal" href="#poltofloatexproneterm-raw-coeff-number" id="id102"><tt class="docutils literal"><span class="pre">\PolToFloatExprOneTerm{raw_coeff}{number}</span></tt></a></li> +<li><a class="reference internal" href="#poltofloatexprcmd-raw-coeff" id="id103"><tt class="docutils literal">\PolToFloatExprCmd{raw_coeff}</tt></a></li> </ul> </li> -<li><a class="reference internal" href="#technicalities" id="id60">Technicalities</a></li> -<li><a class="reference internal" href="#releases" id="id61">RELEASES</a></li> -<li><a class="reference internal" href="#acknowledgments" id="id62">Acknowledgments</a></li> +<li><a class="reference internal" href="#id30" id="id104"><tt class="docutils literal"><span class="pre">\PolToFloatExpr*{polname}</span></tt></a></li> +<li><a class="reference internal" href="#poltolist-polname" id="id105"><tt class="docutils literal">\PolToList{polname}</tt></a></li> +<li><a class="reference internal" href="#poltocsv-polname" id="id106"><tt class="docutils literal">\PolToCSV{polname}</tt></a></li> +<li><a class="reference internal" href="#polsturmchainlength-sturmname" id="id107"><tt class="docutils literal">\PolSturmChainLength{sturmname}</tt></a></li> +<li><a class="reference internal" href="#polsturmifzeroexactlyknown-sturmname-index-a-b" id="id108"><tt class="docutils literal"><span class="pre">\PolSturmIfZeroExactlyKnown{sturmname}{index}{A}{B}</span></tt></a></li> +<li><a class="reference internal" href="#polsturmisolatedzeroleft-sturmname-index" id="id109"><tt class="docutils literal"><span class="pre">\PolSturmIsolatedZeroLeft{sturmname}{index}</span></tt></a></li> +<li><a class="reference internal" href="#polsturmisolatedzeroright-sturmname-index" id="id110"><tt class="docutils literal"><span class="pre">\PolSturmIsolatedZeroRight{sturmname}{index}</span></tt></a></li> +<li><a class="reference internal" href="#polsturmnbofisolatedzeros-sturmname" id="id111"><tt class="docutils literal">\PolSturmNbOfIsolatedZeros{sturmname}</tt></a></li> +<li><a class="reference internal" href="#polintervalwidth-sturmname-index" id="id112"><tt class="docutils literal"><span class="pre">\PolIntervalWidth{sturmname}{index}</span></tt></a></li> +<li><a class="reference internal" href="#macros-for-use-within-execution-of-polprintintervals" id="id113">Macros for use within execution of <tt class="docutils literal">\PolPrintIntervals</tt></a><ul> +<li><a class="reference internal" href="#id31" id="id114"><tt class="docutils literal">\PolPrintIntervalsTheEndPoint</tt></a></li> +<li><a class="reference internal" href="#id32" id="id115"><tt class="docutils literal">\PolPrintIntervalsTheIndex</tt></a></li> +<li><a class="reference internal" href="#polifendpointispositive-a-b" id="id116"><tt class="docutils literal"><span class="pre">\PolIfEndPointIsPositive{A}{B}</span></tt></a></li> +<li><a class="reference internal" href="#polifendpointisnegative-a-b" id="id117"><tt class="docutils literal"><span class="pre">\PolIfEndPointIsNegative{A}{B}</span></tt></a></li> +<li><a class="reference internal" href="#polifendpointiszero-a-b" id="id118"><tt class="docutils literal"><span class="pre">\PolIfEndPointIsZero{A}{B}</span></tt></a></li> +</ul> +</li> +<li><a class="reference internal" href="#poldectostring-decimal-number" id="id119"><tt class="docutils literal">\PolDecToString{decimal number}</tt></a></li> +</ul> +</li> +<li><a class="reference internal" href="#booleans-with-default-setting-as-indicated" id="id120">Booleans (with default setting as indicated)</a><ul> +<li><a class="reference internal" href="#xintverbosefalse" id="id121"><tt class="docutils literal">\xintverbosefalse</tt></a></li> +<li><a class="reference internal" href="#poltypesetallfalse" id="id122"><tt class="docutils literal">\poltypesetallfalse</tt></a></li> +<li><a class="reference internal" href="#poltoexprallfalse" id="id123"><tt class="docutils literal">\poltoexprallfalse</tt></a></li> +</ul> +</li> +<li><a class="reference internal" href="#technicalities" id="id124">Technicalities</a></li> +<li><a class="reference internal" href="#change-log" id="id125">CHANGE LOG</a></li> +<li><a class="reference internal" href="#acknowledgments" id="id126">Acknowledgments</a></li> </ul> </div> -<div class="section" id="first-examples"> -<h1><a class="toc-backref" href="#id15">First Examples</a></h1> +<div class="section" id="basic-examples"> +<h1><a class="toc-backref" href="#id33">Basic Examples</a></h1> <p>The syntax is:</p> <pre class="literal-block"> \poldef polname(x):= expression in variable x; @@ -526,10 +578,200 @@ PSTricks-compatible; the letter used in output can be <dd>gives ascending powers: <tt class="docutils literal"><span class="pre">2-2*x-x^2+x^3</span></tt>.</dd> </dl> </div> +<div class="section" id="examples-of-localization-of-roots"> +<h1><a class="toc-backref" href="#id34">Examples of localization of roots</a></h1> +<p>First some remarks about auxiliaries.</p> +<ul> +<li><p class="first">To make printed decimal numbers more enjoyable than via +<tt class="docutils literal">\xintSignedFrac</tt>:</p> +<pre class="literal-block"> +\renewcommand\PolTypesetOne[1]{\PolDecToString{\xintREZ{#1}}}% +</pre> +<p><tt class="docutils literal">\PolDecToString</tt> will use decimal notation to incorporate the power +of ten part; and the <tt class="docutils literal">\xintREZ</tt> 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:</p> +<pre class="literal-block"> +\renewcommand\PolToExprCmd[1]{\PolDecToString{\xintREZ{#1}}}% +</pre> +<p>to modify output of <a class="reference internal" href="#poltoexpr-polname">\PolToExpr{polname}</a>.</p> +</li> +<li><p class="first">for extra info in log file <tt class="docutils literal">\xintverbosetrue</tt>. In fact one can also +work from command line then (I recommend <tt class="docutils literal">rlwrap</tt> for encapsulating +<tt class="docutils literal">latex</tt>).</p> +</li> +</ul> +<div class="section" id="a-typical-example"> +<h2><a class="toc-backref" href="#id35">A typical example</a></h2> +<pre class="literal-block"> +\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$! +</pre> +</div> +<div class="section" id="a-degree-four-polynomial-with-nearby-roots"> +<h2><a class="toc-backref" href="#id36">A degree four polynomial with nearby roots</a></h2> +<pre class="literal-block"> +\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 +</pre> +</div> +<div class="section" id="the-degree-nine-polynomial-with-0-99-0-999-0-9999-as-triple-roots"> +<h2><a class="toc-backref" href="#id37">The degree nine polynomial with 0.99, 0.999, 0.9999 as triple roots</a></h2> +<pre class="literal-block"> +\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 +</pre> +</div> +<div class="section" id="a-mignotte-type-polynomial"> +<h2><a class="toc-backref" href="#id38">A Mignotte type polynomial</a></h2> +<pre class="literal-block"> +\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}$. +</pre> +<p>The last line produces:</p> +<pre class="literal-block"> +0.09999900004999650028 < Z_2 < 0.09999900004999650029 +</pre> +</div> +<div class="section" id="the-degree-41-polynomial-with-2-1-9-1-8-0-0-1-1-9-2-as-roots"> +<h2><a class="toc-backref" href="#id39">The degree 41 polynomial with -2, -1.9, -1.8, ..., 0, 0.1, ..., 1.9, 2 as roots</a></h2> +<pre class="literal-block"> +\PolDef{P}{mul((x-i*1e-1), i=-20..20)}% i/10 is same but less efficient +</pre> +<p>In the defining expression we could have used <tt class="docutils literal">i/10</tt> but this gives +less efficient internal form for the coefficients (the <tt class="docutils literal">10</tt>'s end up +in denominators). Using <tt class="docutils literal">\PolToExpr{P}</tt> after having done</p> +<pre class="literal-block"> +\renewcommand\PolToExprCmd[1]{\PolDecToString{\xintREZ{#1}}} +</pre> +<p>we get this expanded form:</p> +<pre class="literal-block"> +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 +</pre> +<p>which shows coefficients with up to 36 significant digits...</p> +<p>Stress test: not a hard challenge to <tt class="docutils literal">xint + polexpr</tt>, but be a bit patient!</p> +<pre class="literal-block"> +\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? +</pre> +</div> +<div class="section" id="roots-of-chebyshev-polynomials"> +<h2><a class="toc-backref" href="#id40">Roots of Chebyshev polynomials</a></h2> +<pre class="literal-block"> +\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} +</pre> +</div> +</div> <div class="section" id="non-expandable-macros"> -<h1><a class="toc-backref" href="#id16">Non-expandable macros</a></h1> +<h1><a class="toc-backref" href="#id41">Non-expandable macros</a></h1> <div class="section" id="poldef-polname-letter-expression-in-letter"> -<span id="poldef"></span><h2><a class="toc-backref" href="#id17"><tt class="docutils literal">\poldef <span class="pre">polname(letter):=</span> expression in letter;</tt></a></h2> +<span id="poldef"></span><h2><a class="toc-backref" href="#id42"><tt class="docutils literal">\poldef <span class="pre">polname(letter):=</span> expression in letter;</tt></a></h2> <blockquote> <p>This evaluates the <em>polynomial expression</em> and stores the coefficients in a private structure accessible later via other package macros, @@ -546,25 +788,18 @@ genuine <tt class="docutils literal"><span class="pre">\xintexpr...\relax</span> evaluation (or within an <tt class="docutils literal">\xintdefvar</tt> assignment.) It computes values not according to the original expression but via the Horner scheme corresponding to the polynomial coefficients.</p> -<p>Also, a function with the same name is created for use within -<tt class="docutils literal">\xintfloatexpr</tt> (or <tt class="docutils literal">\xintdeffloatvar</tt>.) 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 <tt class="docutils literal">\xinttheDigits</tt> value.</p> -<div class="admonition important"> -<p class="first admonition-title">Important</p> -<p>Package macros (such as derivatives or Euclidean division) -operate with the "exact" polynomials; "floating point" -polynomials are always obtained in a second step.</p> -<p>To modifiy "in-place" the original coefficients of a polynomial -and round them to float precision:</p> -<pre class="literal-block"> -\PolMapCoeffs{\xintFloat}{polname} -% or \xintFloat[P] for precision P digits -</pre> -<p class="last">See <a class="reference internal" href="#polmapcoeffs-macro-polname">\PolMapCoeffs{\macro}{polname}</a>.</p> +<div class="admonition attention"> +<p class="first admonition-title">Attention!</p> +<p>Release <tt class="docutils literal">0.3</tt> also did the necessary set-up to let the +polynomial be known to the <tt class="docutils literal">\xintfloatexpr</tt> (or +<tt class="docutils literal">\xintdeffloatvar</tt>) parser.</p> +<p>Since <tt class="docutils literal">0.4</tt> 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 <tt class="docutils literal">\poldef</tt> or <tt class="docutils literal">\PolDef</tt> but as +a product of the other package macros.</p> +<p class="last">See <a class="reference internal" href="#polgenfloatvariant-polname">\PolGenFloatVariant{polname}</a>.</p> </div> <p>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.</p> </blockquote> </div> <div class="section" id="poldef-letter-polname-expression-in-letter"> -<span id="id2"></span><h2><a class="toc-backref" href="#id18"><tt class="docutils literal"><span class="pre">\PolDef[letter]{polname}{expression</span> in letter}</tt></a></h2> +<span id="id2"></span><h2><a class="toc-backref" href="#id43"><tt class="docutils literal"><span class="pre">\PolDef[letter]{polname}{expression</span> in letter}</tt></a></h2> <blockquote> -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 <tt class="docutils literal">[letter]</tt> optional argument, -the variable is assumed to be <tt class="docutils literal">x</tt>.</blockquote> +Does the same as <a class="reference external" href="poldef;">\poldef</a> 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 +<tt class="docutils literal">[letter]</tt> optional argument, the variable is assumed to be <tt class="docutils literal">x</tt>.</blockquote> +</div> +<div class="section" id="polgenfloatvariant-polname"> +<span id="polgenfloatvariant"></span><h2><a class="toc-backref" href="#id44"><tt class="docutils literal">\PolGenFloatVariant{polname}</tt></a></h2> +<blockquote> +<p>Makes the polynomial also usable in the <tt class="docutils literal">\xintfloatexpr</tt> parser. +It will therein evaluates via an Horner scheme with coefficients +already pre-rounded to the float precision.</p> +<p>See also <a class="reference internal" href="#poltofloatexpr-polname">\PolToFloatExpr{polname}</a>.</p> +<div class="admonition attention"> +<p class="first admonition-title">Attention!</p> +<p>Release <tt class="docutils literal">0.3</tt> did this automatically on <tt class="docutils literal">\PolDef</tt> and +<tt class="docutils literal">\poldef</tt> but this was removed at <tt class="docutils literal">0.4</tt> for optimization.</p> +<p class="last">Any operation, for example generating the derivative polynomial, +or dividing two polynomials or using the <tt class="docutils literal">\PolLet</tt>, <strong>must</strong> be +followed by explicit usage of <tt class="docutils literal">\PolGenFloatVariant{polname}</tt> if +the new polynomial is to be used in <tt class="docutils literal">\xintfloatexpr</tt> or alike +context.</p> +</div> +</blockquote> </div> <div class="section" id="pollet-polname-2-polname-1"> -<h2><a class="toc-backref" href="#id19"><tt class="docutils literal"><span class="pre">\PolLet{polname_2}={polname_1}</span></tt></a></h2> +<span id="pollet"></span><h2><a class="toc-backref" href="#id45"><tt class="docutils literal"><span class="pre">\PolLet{polname_2}={polname_1}</span></tt></a></h2> <blockquote> Makes a copy of the already defined polynomial <tt class="docutils literal">polname_1</tt> to a new one <tt class="docutils literal">polname_2</tt>. Same effect as <tt class="docutils literal"><span class="pre">\PolDef{polname_2}{polname_1(x)}</span></tt> but with less overhead. The <tt class="docutils literal">=</tt> is optional.</blockquote> </div> +<div class="section" id="polgloballet-polname-2-polname-1"> +<span id="polgloballet"></span><h2><a class="toc-backref" href="#id46"><tt class="docutils literal"><span class="pre">\PolGlobalLet{polname_2}={polname_1}</span></tt></a></h2> +<blockquote> +Acts globally.</blockquote> +</div> <div class="section" id="polassign-polname-toarray-macro"> -<h2><a class="toc-backref" href="#id20"><tt class="docutils literal"><span class="pre">\PolAssign{polname}\toarray\macro</span></tt></a></h2> +<span id="polassign"></span><h2><a class="toc-backref" href="#id47"><tt class="docutils literal"><span class="pre">\PolAssign{polname}\toarray\macro</span></tt></a></h2> <blockquote> <p>Defines a one-argument expandable macro <tt class="docutils literal"><span class="pre">\macro{#1}</span></tt> which expands to the (raw) #1th polynomial coefficient.</p> @@ -611,7 +870,7 @@ indices act the same in both.)</p> </blockquote> </div> <div class="section" id="polget-polname-fromarray-macro"> -<h2><a class="toc-backref" href="#id21"><tt class="docutils literal"><span class="pre">\PolGet{polname}\fromarray\macro</span></tt></a></h2> +<span id="polget"></span><h2><a class="toc-backref" href="#id48"><tt class="docutils literal"><span class="pre">\PolGet{polname}\fromarray\macro</span></tt></a></h2> <blockquote> <p>Does the converse operation to <tt class="docutils literal"><span class="pre">\PolAssign{polname}\toarray\macro</span></tt>. No error checks on validity of coefficients as numbers. Each @@ -625,18 +884,18 @@ polynomial.</p> </pre> <p>This will define <tt class="docutils literal">f</tt> as would have <tt class="docutils literal">\poldef <span class="pre">f(x):=1-2x+5x^2-3x^3;</span></tt>. However the coefficients are still in their original form (i.e. -they were not subjected to <tt class="docutils literal">\xintRaw</tt> or similar xintfrac macro.)</p> +they were not subjected to <tt class="docutils literal">\xintRaw</tt> or similar <a class="reference external" href="http://www.ctan.org/pkg/xint">xintfrac</a> macro.)</p> </blockquote> </div> <div class="section" id="polfromcsv-polname-csv"> -<h2><a class="toc-backref" href="#id22"><tt class="docutils literal"><span class="pre">\PolFromCSV{polname}{<csv>}</span></tt></a></h2> +<span id="polfromcsv"></span><h2><a class="toc-backref" href="#id49"><tt class="docutils literal"><span class="pre">\PolFromCSV{polname}{<csv>}</span></tt></a></h2> <blockquote> <p>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 <tt class="docutils literal">\edef</tt>, but currently left in their original form like e.g. -<tt class="docutils literal">1.5e3</tt> which is not converted to <tt class="docutils literal">15/1[2]</tt> <em>raw</em> xintfrac +<tt class="docutils literal">1.5e3</tt> which is not converted to <tt class="docutils literal">15/1[2]</tt> <em>raw</em> <a class="reference external" href="http://www.ctan.org/pkg/xint">xintfrac</a> format (this may change).</p> <p>Leading zero coefficients are removed:</p> <pre class="literal-block"> @@ -647,7 +906,7 @@ format (this may change).</p> </blockquote> </div> <div class="section" id="poltypeset-polname"> -<h2><a class="toc-backref" href="#id23"><tt class="docutils literal">\PolTypeset{polname}</tt></a></h2> +<span id="poltypeset"></span><h2><a class="toc-backref" href="#id50"><tt class="docutils literal">\PolTypeset{polname}</tt></a></h2> <blockquote> <p>Typesets in descending powers in math mode. It uses letter <tt class="docutils literal">x</tt> but this can be changed via an optional argument:</p> @@ -661,31 +920,52 @@ can be re-defined for customization. Their default definitions are expandable, but this is not a requirement.</p> </blockquote> <div class="section" id="poltypesetcmd-raw-coeff"> -<h3><a class="toc-backref" href="#id24"><tt class="docutils literal">\PolTypesetCmd{raw_coeff}</tt></a></h3> +<span id="poltypesetcmd"></span><h3><a class="toc-backref" href="#id51"><tt class="docutils literal">\PolTypesetCmd{raw_coeff}</tt></a></h3> +<blockquote> +<p>Checks if the coefficient is <tt class="docutils literal">1</tt> or <tt class="docutils literal"><span class="pre">-1</span></tt> and then skips printing +the <tt class="docutils literal">1</tt>, except for the constant term. Also it sets conditional +<a class="reference internal" href="#polifcoeffisplusorminusone-a-b">\PolIfCoeffIsPlusOrMinusOne{A}{B}</a>.</p> +<p>The actual printing of the coefficients, when not equal to plus or +minus one is handled by <a class="reference internal" href="#poltypesetone-raw-coeff">\PolTypesetOne{raw_coeff}</a>.</p> +</blockquote> +</div> +<div class="section" id="poltypesetone-raw-coeff"> +<span id="poltypesetone"></span><h3><a class="toc-backref" href="#id52"><tt class="docutils literal">\PolTypesetOne{raw_coeff}</tt></a></h3> <blockquote> -<p>Basically will use <tt class="docutils literal">\xintSignedFrac</tt> from <a class="reference external" href="http://www.ctan.org/pkg/xint">xintfrac</a>, but checks if -the coefficient is <tt class="docutils literal">1</tt> or <tt class="docutils literal"><span class="pre">-1</span></tt> and then skips printing the -<tt class="docutils literal">1</tt>, except for the constant term...</p> -<p>One can do things such as for example: <a class="footnote-reference" href="#id4" id="id3">[1]</a></p> +<p>The default is <tt class="docutils literal">\xintSignedFrac</tt> but this macro is annoying as it +insists to use a power of ten, and not decimal notation.</p> +<p>One can do things such as for example: <a class="footnote-reference" href="#id5" id="id4">[1]</a></p> <pre class="literal-block"> -\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}}} </pre> <p>where e.g. we used the <tt class="docutils literal">\num</tt> macro of <tt class="docutils literal">siunitx</tt> as it understands floating point notation.</p> -<table class="docutils footnote" frame="void" id="id4" rules="none"> +<table class="docutils footnote" frame="void" id="id5" rules="none"> <colgroup><col class="label" /><col /></colgroup> <tbody valign="top"> -<tr><td class="label"><a class="fn-backref" href="#id3">[1]</a></td><td>the difference in the syntaxes of <tt class="docutils literal">\xintPFloat</tt> and +<tr><td class="label"><a class="fn-backref" href="#id4">[1]</a></td><td>the difference in the syntaxes of <tt class="docutils literal">\xintPFloat</tt> and <tt class="docutils literal">\xintRound</tt> is explained from the fact that <tt class="docutils literal">\xintPFloat</tt> by default uses the prevailing precision hence the extra argument like here <tt class="docutils literal">5</tt> is an optional one.</td></tr> </tbody> </table> +<p>One can also give a try to using <a class="reference internal" href="#poldectostring-decimal-number">\PolDecToString{decimal number}</a> +which uses decimal notation (at least for the numerator part).</p> </blockquote> </div> +<div class="section" id="id6"> +<span id="poltypesetmonomialcmd"></span><h3><a class="toc-backref" href="#id53"><tt class="docutils literal">\PolTypesetMonomialCmd</tt></a></h3> +<blockquote> +This decides how a monomial (in variable <tt class="docutils literal">\PolVar</tt> and with +exponent <tt class="docutils literal">\PolIndex</tt>) is to be printed. The default does nothing +for the constant term, <tt class="docutils literal">\PolVar</tt> for the first degree and +<tt class="docutils literal"><span class="pre">\PolVar^{\PolIndex}</span></tt> for higher degrees monomials. Beware that +<tt class="docutils literal">\PolIndex</tt> expands to digit tokens and needs termination in +<tt class="docutils literal">\ifnum</tt> tests.</blockquote> +</div> <div class="section" id="poltypesetcmdprefix-raw-coeff"> -<h3><a class="toc-backref" href="#id25"><tt class="docutils literal">\PolTypesetCmdPrefix{raw_coeff}</tt></a></h3> +<span id="poltypesetcmdprefix"></span><h3><a class="toc-backref" href="#id54"><tt class="docutils literal">\PolTypesetCmdPrefix{raw_coeff}</tt></a></h3> <blockquote> Expands to a <tt class="docutils literal">+</tt> if the <tt class="docutils literal">raw_coeff</tt> is zero or positive, and to nothing if <tt class="docutils literal">raw_coeff</tt> is negative, as in latter case the @@ -694,25 +974,15 @@ the <tt class="docutils literal">-</tt> 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.</blockquote> </div> -<div class="section" id="poltypesetmonomialcmd"> -<h3><a class="toc-backref" href="#id26"><tt class="docutils literal">\PolTypesetMonomialCmd</tt></a></h3> -<blockquote> -This decides how a monomial (in variable <tt class="docutils literal">\PolVar</tt> and with -exponent <tt class="docutils literal">\PolIndex</tt>) is to be printed. The default does nothing -for the constant term, <tt class="docutils literal">\PolVar</tt> for the first degree and -<tt class="docutils literal"><span class="pre">\PolVar^{\PolIndex}</span></tt> for higher degrees monomials. Beware that -<tt class="docutils literal">\PolIndex</tt> expands to digit tokens and needs termination in -<tt class="docutils literal">\ifnum</tt> tests.</blockquote> -</div> </div> -<div class="section" id="id5"> -<h2><a class="toc-backref" href="#id27"><tt class="docutils literal"><span class="pre">\PolTypeset*{polname}</span></tt></a></h2> +<div class="section" id="id8"> +<span id="id7"></span><h2><a class="toc-backref" href="#id55"><tt class="docutils literal"><span class="pre">\PolTypeset*{polname}</span></tt></a></h2> <blockquote> Typesets in ascending powers. Use e.g. <tt class="docutils literal">[h]</tt> optional argument (after the <tt class="docutils literal">*</tt>) to use letter <tt class="docutils literal">h</tt> rather than <tt class="docutils literal">x</tt>.</blockquote> </div> <div class="section" id="poldiff-polname-1-polname-2"> -<h2><a class="toc-backref" href="#id28"><tt class="docutils literal"><span class="pre">\PolDiff{polname_1}{polname_2}</span></tt></a></h2> +<span id="poldiff"></span><h2><a class="toc-backref" href="#id56"><tt class="docutils literal"><span class="pre">\PolDiff{polname_1}{polname_2}</span></tt></a></h2> <blockquote> <p>This sets <tt class="docutils literal">polname_2</tt> to the first derivative of <tt class="docutils literal">polname_1</tt>. It is allowed to issue <tt class="docutils literal"><span class="pre">\PolDiff{f}{f}</span></tt>, effectively replacing <tt class="docutils literal">f</tt> @@ -722,7 +992,7 @@ by <tt class="docutils literal">f'</tt>.</p> </blockquote> </div> <div class="section" id="poldiff-n-polname-1-polname-2"> -<h2><a class="toc-backref" href="#id29"><tt class="docutils literal"><span class="pre">\PolDiff[N]{polname_1}{polname_2}</span></tt></a></h2> +<span id="poldiff-n"></span><h2><a class="toc-backref" href="#id57"><tt class="docutils literal"><span class="pre">\PolDiff[N]{polname_1}{polname_2}</span></tt></a></h2> <blockquote> This sets <tt class="docutils literal">polname_2</tt> to the <tt class="docutils literal">N</tt>-th derivative of <tt class="docutils literal">polname_1</tt>. Identical arguments is allowed. With <tt class="docutils literal">N=0</tt>, same effect as @@ -730,7 +1000,7 @@ Identical arguments is allowed. With <tt class="docutils literal">N=0</tt>, same using <tt class="docutils literal">\PolAntiDiff</tt>.</blockquote> </div> <div class="section" id="polantidiff-polname-1-polname-2"> -<h2><a class="toc-backref" href="#id30"><tt class="docutils literal"><span class="pre">\PolAntiDiff{polname_1}{polname_2}</span></tt></a></h2> +<span id="polantidiff"></span><h2><a class="toc-backref" href="#id58"><tt class="docutils literal"><span class="pre">\PolAntiDiff{polname_1}{polname_2}</span></tt></a></h2> <blockquote> <p>This sets <tt class="docutils literal">polname_2</tt> to the primitive of <tt class="docutils literal">polname_1</tt> vanishing at zero.</p> @@ -739,27 +1009,287 @@ at zero.</p> </blockquote> </div> <div class="section" id="polantidiff-n-polname-1-polname-2"> -<h2><a class="toc-backref" href="#id31"><tt class="docutils literal"><span class="pre">\PolAntiDiff[N]{polname_1}{polname_2}</span></tt></a></h2> +<span id="polantidiff-n"></span><h2><a class="toc-backref" href="#id59"><tt class="docutils literal"><span class="pre">\PolAntiDiff[N]{polname_1}{polname_2}</span></tt></a></h2> <blockquote> This sets <tt class="docutils literal">polname_2</tt> to the result of <tt class="docutils literal">N</tt> successive integrations on <tt class="docutils literal">polname_1</tt>. With negative <tt class="docutils literal">N</tt>, it switches to using <tt class="docutils literal">\PolDiff</tt>.</blockquote> </div> <div class="section" id="poldivide-polname-1-polname-2-polname-q-polname-r"> -<h2><a class="toc-backref" href="#id32"><tt class="docutils literal"><span class="pre">\PolDivide{polname_1}{polname_2}{polname_Q}{polname_R}</span></tt></a></h2> +<span id="poldivide"></span><h2><a class="toc-backref" href="#id60"><tt class="docutils literal"><span class="pre">\PolDivide{polname_1}{polname_2}{polname_Q}{polname_R}</span></tt></a></h2> <blockquote> This sets <tt class="docutils literal">polname_Q</tt> and <tt class="docutils literal">polname_R</tt> to be the quotient and remainder in the Euclidean division of <tt class="docutils literal">polname_1</tt> by <tt class="docutils literal">polname_2</tt>.</blockquote> </div> +<div class="section" id="polquo-polname-1-polname-2-polname-q"> +<span id="polquo"></span><h2><a class="toc-backref" href="#id61"><tt class="docutils literal"><span class="pre">\PolQuo{polname_1}{polname_2}{polname_Q}</span></tt></a></h2> +<blockquote> +This sets <tt class="docutils literal">polname_Q</tt> to be the quotient in the Euclidean division +of <tt class="docutils literal">polname_1</tt> by <tt class="docutils literal">polname_2</tt>.</blockquote> +</div> +<div class="section" id="polrem-polname-1-polname-2-polname-r"> +<span id="polrem"></span><h2><a class="toc-backref" href="#id62"><tt class="docutils literal"><span class="pre">\PolRem{polname_1}{polname_2}{polname_R}</span></tt></a></h2> +<blockquote> +This sets <tt class="docutils literal">polname_R</tt> to be the remainder in the Euclidean division +of <tt class="docutils literal">polname_1</tt> by <tt class="docutils literal">polname_2</tt>.</blockquote> +</div> <div class="section" id="polgcd-polname-1-polname-2-polname-gcd"> -<h2><a class="toc-backref" href="#id33"><tt class="docutils literal"><span class="pre">\PolGCD{polname_1}{polname_2}{polname_GCD}</span></tt></a></h2> +<span id="polgcd"></span><h2><a class="toc-backref" href="#id63"><tt class="docutils literal"><span class="pre">\PolGCD{polname_1}{polname_2}{polname_GCD}</span></tt></a></h2> +<blockquote> +This sets <tt class="docutils literal">polname_GCD</tt> to be the (monic) GCD of the two first +polynomials. It is a unitary polynomial except if both <tt class="docutils literal">polname_1</tt> +and <tt class="docutils literal">polname_2</tt> vanish, then <tt class="docutils literal">polname_GCD</tt> is the zero +polynomial.</blockquote> +<!-- ``\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. --> +</div> +<div class="section" id="poltosturm-polname-sturmname"> +<span id="poltosturm"></span><h2><a class="toc-backref" href="#id64"><tt class="docutils literal"><span class="pre">\PolToSturm{polname}{sturmname}</span></tt></a></h2> +<blockquote> +<p>With, for example, <tt class="docutils literal">polname</tt> being <tt class="docutils literal">P</tt> and <tt class="docutils literal">sturmname</tt> being +<tt class="docutils literal">S</tt>, the macro starts by computing polynomials <tt class="docutils literal">S_0 = P</tt>, <tt class="docutils literal">S_1 += P'</tt>, ..., with <tt class="docutils literal">S_{n+1}</tt> the opposite of the remainder of +euclidean division of <tt class="docutils literal"><span class="pre">S_{n-1}</span></tt> by <tt class="docutils literal">S_{n}</tt>. The last non-zero +remainder <tt class="docutils literal">S_N</tt> is up to a factor the GCD of <tt class="docutils literal">P</tt> and <tt class="docutils literal">P'</tt> +hence a constant if and only if <tt class="docutils literal">P</tt> is square-free.</p> +<p>In case <tt class="docutils literal">S_N</tt> is not a constant, the macro then goes on with +dividing all <tt class="docutils literal">S_k</tt>'s with <tt class="docutils literal">S_N</tt> (which becomes <tt class="docutils literal">1</tt>).</p> +<p>Thus <tt class="docutils literal">S_0</tt> now has exactly the same real and complex +roots as polynomial <tt class="docutils literal">polname</tt>, but each with multiplicity one.</p> +</blockquote> +</div> +<div class="section" id="id10"> +<span id="id9"></span><h2><a class="toc-backref" href="#id65"><tt class="docutils literal"><span class="pre">\PolToSturm*{polname}{sturmname}</span></tt></a></h2> +<blockquote> +Does not divide the Sturm chain by its last element.</blockquote> +</div> +<div class="section" id="polsettosturmchainsignchangesat-macro-sturmname-fraction"> +<span id="polsettosturmchainsignchangesat"></span><h2><a class="toc-backref" href="#id66"><tt class="docutils literal"><span class="pre">\PolSetToSturmChainSignChangesAt{\macro}{sturmname}{fraction}</span></tt></a></h2> +<blockquote> +<p>Sets macro <tt class="docutils literal">\macro</tt> to the number of sign changes in the Sturm +chain with name prefix <tt class="docutils literal">sturmname</tt>, at location <tt class="docutils literal">fraction</tt> +(which must be in format as acceptable by the <a class="reference external" href="http://www.ctan.org/pkg/xint">xintfrac</a> macros.)</p> +<div class="admonition note"> +<p class="first admonition-title">Note</p> +<p>The author was lazy and did not provide rather an expandable +variant, where one would do <tt class="docutils literal"><span class="pre">\edef\macro{\PolNbOf...}</span></tt>.</p> +<p>This will presumably get added in a future release.</p> +<p class="last">After some hesitation it was decided the macro would by default +act globally. To make the scope of its macro definition local, +use <tt class="docutils literal">[\empty]</tt> as extra optional argument.</p> +</div> +</blockquote> +</div> +<div class="section" id="polsettonbofzeroswithin-macro-sturmname-value-a-value-b"> +<span id="polsettonbofzeroswithin"></span><h2><a class="toc-backref" href="#id67"><tt class="docutils literal"><span class="pre">\PolSetToNbOfZerosWithin{\macro}{sturmname}{value_a}{value_b}</span></tt></a></h2> +<blockquote> +<p>Applies the <a class="reference external" href="https://en.wikipedia.org/wiki/Sturm%27s_theorem">Sturm Theorem</a> to set <tt class="docutils literal">\macro</tt> to the exact number +of distinct roots of <tt class="docutils literal">sturmname_0</tt> in the interval <tt class="docutils literal">(value_a, +value_b]</tt> (the macro first re-orders the value for <tt class="docutils literal">value_a <= +value_b</tt> to hold).</p> +<div class="admonition note"> +<p class="first admonition-title">Note</p> +<p>The author was lazy and did not provide rather an expandable +variant, where one would do <tt class="docutils literal"><span class="pre">\edef\macro{\PolNbOf...}</span></tt>.</p> +<p>This will presumably get added in future.</p> +<p class="last">After some hesitation it was decided the macro would by default +act globally. To make the scope of its macro definition local, +use <tt class="docutils literal">[\empty]</tt> as extra optional argument.</p> +</div> +</blockquote> +</div> +<div class="section" id="polsturmisolatezeros-sturmname"> +<span id="polsturmisolatezeros"></span><h2><a class="toc-backref" href="#id68"><tt class="docutils literal">\PolSturmIsolateZeros{sturmname}</tt></a></h2> +<blockquote> +<p>First, it evaluates using <a class="reference external" href="https://en.wikipedia.org/wiki/Sturm%27s_theorem">Sturm theorem</a> the number of distinct +real roots of <tt class="docutils literal">sturmname_0</tt>.</p> +<div class="admonition important"> +<p class="first admonition-title">Important</p> +<p class="last">The Sturm chain <strong>must</strong> be of the reduced type, i.e. +as constructed via <a class="reference internal" href="#poltosturm-polname-sturmname">\PolToSturm{polname}{sturmname}</a>.</p> +</div> +<p>Then it locates, again using <a class="reference external" href="https://en.wikipedia.org/wiki/Sturm%27s_theorem">Sturm theorem</a>, 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.</p> +<!-- This procedure is covariant +with the independent variable ``x`` becoming ``-x``. +Hmm, pas sûr et trop fatigué --> +<p>The interval boundaries are decimal numbers, originating +in iterated decimal subdivision from initial intervals +<tt class="docutils literal"><span class="pre">(-10^E,</span> 0)</tt> and <tt class="docutils literal">(0, 10^E)</tt>; if zero is a root it is always +identified individually. The non-singleton intervals are of the +type <tt class="docutils literal">(a/10^f, <span class="pre">(a+1)/10^f)</span></tt> with <tt class="docutils literal">a</tt> an integer, which is +neither <tt class="docutils literal">0</tt> nor <tt class="docutils literal"><span class="pre">-1</span></tt>. Hence <tt class="docutils literal">a</tt> and <tt class="docutils literal">a+1</tt> are both positive +or both negative.</p> +<p>The interval boundaries (and exactly found roots) are made available +for future computations in <tt class="docutils literal">\xintexpr</tt>-essions or polynomial +definitions as variables <tt class="docutils literal"><sturmname>L_1</tt>, +<tt class="docutils literal"><sturmname>L_2</tt>, etc..., for the left end-points and +<tt class="docutils literal"><sturmname>R_1</tt>, <tt class="docutils literal"><sturmname>R_2</tt>, ..., for the right +end-points.</p> +<p>Also two macro arrays (in the sense of +<a class="reference external" href="http://www.ctan.org/pkg/xint">xinttools</a>'s <tt class="docutils literal">\xintAssignArray</tt>) are created for holding the +interval end-points written out in standard decimal notation +(see <a class="reference internal" href="#poldectostring-decimal-number">\PolDecToString{decimal number}</a>). +To access these values, macros +<a class="reference internal" href="#polsturmisolatedzeroleft-sturmname-index">\PolSturmIsolatedZeroLeft{sturmname}{index}</a> and +<a class="reference internal" href="#polsturmisolatedzeroright-sturmname-index">\PolSturmIsolatedZeroRight{sturmname}{index}</a> are provided.</p> +<div class="admonition important"> +<p class="first admonition-title">Important</p> +<p class="last">Trailing zeroes in these stored decimal numbers are significant: +they are also present in the decimal expansion of the exact root.</p> +</div> +<div class="admonition note"> +<p class="first admonition-title">Note</p> +<p class="last">The actual array macros are <tt class="docutils literal">\POL_ZeroInt<sturmname>L</tt> and +<tt class="docutils literal">\POL_ZeroInt<sturmname>R</tt> but as these names use the +non-letter character <tt class="docutils literal">_</tt> and possibly also digits from +<tt class="docutils literal">sturmname</tt>, the accessor macros above have been made part of +the package.</p> +</div> +<p>The start of decimal expansion of a positive <tt class="docutils literal">k</tt>-th root is given +by <tt class="docutils literal"><span class="pre">\PolSturmIsolatedZeroLeft{sturmname}{k}</span></tt>, and for a negative +root it is given by <tt class="docutils literal"><span class="pre">\PolSturmIsolatedZeroRight{sturmname}{k}</span></tt>. +These two decimal numbers are either both zero or both of the same +sign.</p> +<p>The number of distinct roots is obtainable as +<tt class="docutils literal">\PolSturmNbOfIsolatedZeros{sturmname}</tt>.</p> +<div class="admonition note"> +<p class="first admonition-title">Note</p> +<p class="last">In the current implementation the <tt class="docutils literal"><span class="pre"><sturmname>...</span></tt> variables +and the <tt class="docutils literal"><span class="pre">\POL_ZeroInt...</span></tt> arrays are globally defined. On the +other hand the Sturm sequence polynomials obey the current scope.</p> +</div> +<div class="admonition note"> +<p class="first admonition-title">Note</p> +<p class="last">When two successive roots are located in adjacent intervals, the +separation between them is not lower bounded. See +<a class="reference internal" href="#polrefineinterval-sturmname-index">\PolRefineInterval*{sturmname}{index}</a>.</p> +</div> +<div class="admonition note"> +<p class="first admonition-title">Note</p> +<p>As all computations are done <em>exactly</em> there can be no errors... +apart those due to bad coding by author. The results are exact +bounds for the mathematically exact real roots.</p> +<p class="last">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.</p> +</div> +</blockquote> +</div> +<div class="section" id="polrefineinterval-sturmname-index"> +<span id="polrefineinterval"></span><h2><a class="toc-backref" href="#id69"><tt class="docutils literal"><span class="pre">\PolRefineInterval*{sturmname}{index}</span></tt></a></h2> +<blockquote> +The <tt class="docutils literal">index</tt>-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 <tt class="docutils literal">k</tt>th root is then +strictly separated from the other roots.</blockquote> +</div> +<div class="section" id="polrefineinterval-n-sturmname-index"> +<span id="polrefineinterval-n"></span><h2><a class="toc-backref" href="#id70"><tt class="docutils literal"><span class="pre">\PolRefineInterval[N]{sturmname}{index}</span></tt></a></h2> +<blockquote> +The <tt class="docutils literal">index</tt>-th interval (starting count at one) is further +subdivided once, reducing its length by a factor of 10. This is done +<tt class="docutils literal">N</tt> times if the optional argument <tt class="docutils literal">[N]</tt> is present.</blockquote> +</div> +<div class="section" id="polensureintervallength-sturmname-index-e"> +<span id="polensureintervallength"></span><h2><a class="toc-backref" href="#id71"><tt class="docutils literal"><span class="pre">\PolEnsureIntervalLength{sturmname}{index}{E}</span></tt></a></h2> <blockquote> -This sets <tt class="docutils literal">polname_GCD</tt> to be the G.C.D. It is a unitary -polynomial except if both <tt class="docutils literal">polname_1</tt> and <tt class="docutils literal">polname_2</tt> vanish, -then <tt class="docutils literal">polname_GCD</tt> is the zero polynomial.</blockquote> +The <tt class="docutils literal">index</tt>-th interval is subdivided until its length becomes at +most <tt class="docutils literal">10^E</tt>. This means (for <tt class="docutils literal">E<0</tt>) that the first <tt class="docutils literal"><span class="pre">-E</span></tt> digits +after decimal mark of the <tt class="docutils literal">k</tt>th root will then be known exactly.</blockquote> +</div> +<div class="section" id="polensureintervallengths-sturmname-e"> +<span id="polensureintervallengths"></span><h2><a class="toc-backref" href="#id72"><tt class="docutils literal"><span class="pre">\PolEnsureIntervalLengths{sturmname}{E}</span></tt></a></h2> +<blockquote> +<p>The intervals as obtained from <tt class="docutils literal">\PolSturmIsolateZeros</tt> are (if +necessary) subdivided further by (base 10) dichotomy in order for +each of them to have length at most <tt class="docutils literal">10^E</tt> (length will be shorter +than <tt class="docutils literal">10^E</tt> in output only if it did not change or became zero.)</p> +<p>This means that decimal expansions of all roots will be known with +<tt class="docutils literal"><span class="pre">-E</span></tt> digits (for <tt class="docutils literal">E<0</tt>) after decimal mark.</p> +</blockquote> +</div> +<div class="section" id="polprintintervals-varname-sturmname"> +<span id="polprintintervals"></span><h2><a class="toc-backref" href="#id73"><tt class="docutils literal"><span class="pre">\PolPrintIntervals[varname]{sturmname}</span></tt></a></h2> +<blockquote> +<p>This is a convenience macro which prints the bounds for the roots +<tt class="docutils literal">Z_1</tt>, <tt class="docutils literal">Z_2</tt>, ... (the optional argument <tt class="docutils literal">varname</tt> allows to +specify a replacement for the default <tt class="docutils literal">Z</tt>). This will be done in a +math mode <tt class="docutils literal">array</tt>, one interval per row, and pattern <tt class="docutils literal">rcccl</tt>, +where the second and fourth column hold the <tt class="docutils literal"><</tt> 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.</p> +<p>In each array cell the corresponding interval end-point (which may +be an exactly known root) is available as macro +<a class="reference internal" href="#polprintintervalstheendpoint">\PolPrintIntervalsTheEndPoint</a> (in decimal notation). And the +corresponding interval index is available as +<a class="reference internal" href="#polprintintervalstheindex">\PolPrintIntervalsTheIndex</a>.</p> +<p>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: <a class="reference internal" href="#polifendpointispositive-a-b">\PolIfEndPointIsPositive{A}{B}</a>, +<a class="reference internal" href="#polifendpointisnegative-a-b">\PolIfEndPointIsNegative{A}{B}</a>, <a class="reference internal" href="#polifendpointiszero-a-b">\PolIfEndPointIsZero{A}{B}</a>.</p> +</blockquote> +<div class="section" id="id11"> +<span id="polprintintervalsprintexactzero"></span><h3><a class="toc-backref" href="#id74"><tt class="docutils literal">\PolPrintIntervalsPrintExactZero</tt></a></h3> +<blockquote> +<p>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:</p> +<pre class="literal-block"> +\newcommand\PolPrintIntervalsPrintExactZero{\PolPrintIntervalsTheEndPoint}% +</pre> +<p>Recall that this is expanded in an array cell.</p> +<p>If for example you want to print in red the third root, known +exactly, the macro could make a test for the value of +<a class="reference internal" href="#polprintintervalstheindex">\PolPrintIntervalsTheIndex</a> and act accordingly.</p> +</blockquote> +</div> +<div class="section" id="id12"> +<span id="polprintintervalsprintleftendpoint"></span><h3><a class="toc-backref" href="#id75"><tt class="docutils literal">\PolPrintIntervalsPrintLeftEndPoint</tt></a></h3> +<blockquote> +<p>Package definition is:</p> +<pre class="literal-block"> +\newcommand\PolPrintIntervalsPrintLeftEndPoint{\PolPrintIntervalsTheEndPoint}% +</pre> +</blockquote> +</div> +<div class="section" id="id13"> +<span id="polprintintervalsprintrightendpoint"></span><h3><a class="toc-backref" href="#id76"><tt class="docutils literal">\PolPrintIntervalsPrintRightEndPoint</tt></a></h3> +<blockquote> +<p>Package definition is:</p> +<pre class="literal-block"> +\newcommand\PolPrintIntervalsPrintRightEndPoint{\PolPrintIntervalsTheEndPoint}% +</pre> +</blockquote> +</div> </div> <div class="section" id="polmapcoeffs-macro-polname"> -<h2><a class="toc-backref" href="#id34"><tt class="docutils literal"><span class="pre">\PolMapCoeffs{\macro}{polname}</span></tt></a></h2> +<span id="polmapcoeffs"></span><h2><a class="toc-backref" href="#id77"><tt class="docutils literal"><span class="pre">\PolMapCoeffs{\macro}{polname}</span></tt></a></h2> <blockquote> <p>It modifies ('in-place': original coefficients get lost) each coefficient of the defined polynomial via the <em>expandable</em> macro @@ -769,7 +1299,7 @@ coefficients vanish after the operation. In replacement text of defined to be zero for the constant term).</p> <p>Notice that <tt class="docutils literal">\macro</tt> will have to handle inputs of the shape <tt class="docutils literal">A/B[N]</tt> (<a class="reference external" href="http://www.ctan.org/pkg/xint">xintfrac</a> internal notation). This means that it probably -will have to be expressed in terms of macros from xintfrac package.</p> +will have to be expressed in terms of macros from <a class="reference external" href="http://www.ctan.org/pkg/xint">xintfrac</a> package.</p> <p>Example:</p> <pre class="literal-block"> \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.</p> </blockquote> </div> <div class="section" id="polreducecoeffs-polname"> -<h2><a class="toc-backref" href="#id35"><tt class="docutils literal">\PolReduceCoeffs{polname}</tt></a></h2> +<span id="polreducecoeffs"></span><h2><a class="toc-backref" href="#id78"><tt class="docutils literal">\PolReduceCoeffs{polname}</tt></a></h2> <blockquote> About the same as <tt class="docutils literal"><span class="pre">\PolMapCoeffs{\xintIrr}{polname}</span></tt> (but maintaining a <tt class="docutils literal">[0]</tt> postfix for speedier <a class="reference external" href="http://www.ctan.org/pkg/xint">xintfrac</a> parsing when polynomial function is used for computations.) This is a one-argument macro, working 'in-place'.</blockquote> </div> +<div class="section" id="id15"> +<span id="id14"></span><h2><a class="toc-backref" href="#id79"><tt class="docutils literal"><span class="pre">\PolReduceCoeffs*{polname}</span></tt></a></h2> +<blockquote> +<p>This starred variant leaves un-touched the decimal exponent in the +internal representation of the fractional coefficients, i.e. if a +coefficient is internally <tt class="docutils literal">A/B[N]</tt>, then <tt class="docutils literal">A/B</tt> is reduced to +smallest terms, but the <tt class="docutils literal">10^N</tt> part is kept as is. Note: if the +polynomial is freshly defined directly via <a class="reference internal" href="#polfromcsv">\PolFromCSV</a> its coefficients might still be internally in some +format like <tt class="docutils literal">1.5e7</tt>; the macro will anyhow always first do the +needed conversion to strict format <tt class="docutils literal">A/B[N]</tt>.</p> +<p>Evaluations with polynomials treated by this can be much faster than +with those handled by the non-starred variant +<a class="reference internal" href="#polreducecoeffs-polname">\PolReduceCoeffs{polname}</a>: 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 <a class="reference external" href="http://www.ctan.org/pkg/xint">xintfrac</a> macros used internally by +<a class="reference internal" href="#polevalat">\PolEval</a>.</p> +</blockquote> +</div> +<div class="section" id="polmakemonic-polname"> +<span id="polmakemonic"></span><h2><a class="toc-backref" href="#id80"><tt class="docutils literal">\PolMakeMonic{polname}</tt></a></h2> +<blockquote> +Divides by the leading coefficient. It is recommended to execute +<a class="reference internal" href="#id15">\PolReduceCoeffs*{polname}</a> 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.</blockquote> +</div> </div> <div class="section" id="expandable-macros"> -<h1><a class="toc-backref" href="#id36">Expandable macros</a></h1> +<h1><a class="toc-backref" href="#id81">Expandable macros</a></h1> <p>All these macros expand completely in two steps except <tt class="docutils literal">\PolToExpr</tt> and <tt class="docutils literal">\PolToFloatExpr</tt> (and their auxiliaries) which need a <tt class="docutils literal">\write</tt>, <tt class="docutils literal">\edef</tt> or a <tt class="docutils literal"><span class="pre">\csname...\endcsname</span></tt> context.</p> -<div class="section" id="poleval-polname-at-numerical-expression"> -<h2><a class="toc-backref" href="#id37"><tt class="docutils literal"><span class="pre">\PolEval{polname}\At{numerical</span> expression}</tt></a></h2> +<div class="section" id="poleval-polname-atexpr-numerical-expression"> +<span id="polevalatexpr"></span><h2><a class="toc-backref" href="#id82"><tt class="docutils literal"><span class="pre">\PolEval{polname}\AtExpr{numerical</span> expression}</tt></a></h2> <blockquote> -<p>It boils down to <tt class="docutils literal">\xinttheexpr polname(numerical <span class="pre">expression)\relax</span></tt>.</p> -<div class="admonition note"> -<p class="first admonition-title">Note</p> -<p>The <tt class="docutils literal">0.2</tt> version stupidly tried to be clever and as a result -of a misguided optimization choked if <tt class="docutils literal">value</tt> was not a number -but a numerical expression (a sum e.g.), but the more powerful -behaviour has been reinstored at <tt class="docutils literal">0.3</tt> release.</p> -<p class="last">The <tt class="docutils literal">0.1</tt> and <tt class="docutils literal">0.2</tt> version did a <tt class="docutils literal">reduce</tt> which however is -costly on big fractions and irrelevant if the output is served as -argument of <tt class="docutils literal">\xintRound</tt> or <tt class="docutils literal">\xintFloat</tt>. Thus <tt class="docutils literal">reduce</tt> was -removed, and former meaning is now available as -<a class="reference internal" href="#polevalreduced-polname-at-numerical-expression">\PolEvalReduced{polname}\At{numerical expression}</a></p> +It boils down to +<tt class="docutils literal">\xinttheexpr polname(numerical <span class="pre">expression)\relax</span></tt>.</blockquote> +</div> +<div class="section" id="poleval-polname-at-fraction"> +<span id="polevalat"></span><h2><a class="toc-backref" href="#id83"><tt class="docutils literal"><span class="pre">\PolEval{polname}\At{fraction}</span></tt></a></h2> +<blockquote> +<p>Evaluates the polynomial at value <tt class="docutils literal">fraction</tt> which must be in (or +expand to) a format acceptable to the <a class="reference external" href="http://www.ctan.org/pkg/xint">xintfrac</a> macros.</p> +<div class="admonition attention"> +<p class="first admonition-title">Attention!</p> +<p>Meaning was changed at <tt class="docutils literal">0.4</tt>. Formerly <tt class="docutils literal"><span class="pre">\PolEval{P}\At{foo}</span></tt> +accepted for <tt class="docutils literal">foo</tt> an expression which was handled by +<tt class="docutils literal">\xintexpr</tt>. See <a class="reference internal" href="#poleval-polname-atexpr-numerical-expression">\PolEval{polname}\AtExpr{numerical +expression}</a>.</p> +<p class="last">In particular, to use an <tt class="docutils literal">\xintexpr</tt> user-declared variable (or +e.g. the variables as defined by <a class="reference external" href="PolSturmIsolateZeros">\PolSturmIsolateZeros</a>) one <strong>must</strong> use the <tt class="docutils literal">\AtExpr</tt> syntax.</p> </div> </blockquote> </div> -<div class="section" id="polevalreduced-polname-at-numerical-expression"> -<h2><a class="toc-backref" href="#id38"><tt class="docutils literal"><span class="pre">\PolEvalReduced{polname}\At{numerical</span> expression}</tt></a></h2> +<div class="section" id="polevalreduced-polname-atexpr-numerical-expression"> +<span id="polevalreducedatexpr"></span><h2><a class="toc-backref" href="#id84"><tt class="docutils literal"><span class="pre">\PolEvalReduced{polname}\AtExpr{numerical</span> expression}</tt></a></h2> <blockquote> Boils down to <tt class="docutils literal">\xinttheexpr reduce(polname(numerical <span class="pre">expression))\relax</span></tt>.</blockquote> </div> -<div class="section" id="polfloateval-polname-at-numerical-expression"> -<h2><a class="toc-backref" href="#id39"><tt class="docutils literal"><span class="pre">\PolFloatEval{polname}\At{numerical</span> expression}</tt></a></h2> +<div class="section" id="polevalreduced-polname-at-fraction"> +<span id="polevalreducedat"></span><h2><a class="toc-backref" href="#id85"><tt class="docutils literal"><span class="pre">\PolEvalReduced{polname}\At{fraction}</span></tt></a></h2> +<blockquote> +<p>Evaluates the polynomial at value <tt class="docutils literal">fraction</tt> which must be in (or +expand to) a format acceptable to the <a class="reference external" href="http://www.ctan.org/pkg/xint">xintfrac</a> macros, and produce +an irreducible fraction.</p> +<div class="admonition attention"> +<p class="first admonition-title">Attention!</p> +<p class="last">Meaning was changed at <tt class="docutils literal">0.4</tt>. Formerly the evaluation point +could be given as an expression.</p> +</div> +</blockquote> +</div> +<div class="section" id="polfloateval-polname-atexpr-numerical-expression"> +<span id="polfloatevalatexpr"></span><h2><a class="toc-backref" href="#id86"><tt class="docutils literal"><span class="pre">\PolFloatEval{polname}\AtExpr{numerical</span> expression}</tt></a></h2> <blockquote> <p>Boils down to <tt class="docutils literal">\xintthefloatexpr polname(numerical <span class="pre">expression)\relax</span></tt>.</p> -<p>This is done via a Horner Scheme (see <a class="reference internal" href="#poldef">\poldef</a>), with -already rounded coefficients. <a class="footnote-reference" href="#id8" id="id6">[2]</a> To use the <em>exact coefficients</em> -(and <em>exact</em> additions and multiplications), just insert it in the -float expression as in this example: <a class="footnote-reference" href="#id9" id="id7">[3]</a></p> +<p>This is done via a Horner Scheme (see <a class="reference internal" href="#poldef">\poldef</a> and +<a class="reference internal" href="#polgenfloatvariant-polname">\PolGenFloatVariant{polname}</a>), with already rounded +coefficients. <a class="footnote-reference" href="#id19" id="id17">[2]</a> To use the <em>exact coefficients</em> with <em>exactly +executed</em> additions and multiplications, just insert it in the float +expression as in this example: <a class="footnote-reference" href="#id20" id="id18">[3]</a></p> <pre class="literal-block"> \xintthefloatexpr 3.27*\xintexpr f(2.53)\relax^2\relax </pre> <p>The <tt class="docutils literal">f(2.53)</tt> is exactly computed then rounded at the time of getting raised to the power <tt class="docutils literal">2</tt>. Moving the <tt class="docutils literal">^2</tt> inside, that operation would also be treated exactly.</p> -<table class="docutils footnote" frame="void" id="id8" rules="none"> +<div class="admonition attention"> +<p class="first admonition-title">Attention!</p> +<p class="last">At <tt class="docutils literal">polexpr 0.3</tt>, polynoms were automatically also prepared for +use in floating point contexts. This got dropped at <tt class="docutils literal">0.4</tt> for +optimization purposes. See <a class="reference internal" href="#polgenfloatvariant-polname">\PolGenFloatVariant{polname}</a>.</p> +</div> +<table class="docutils footnote" frame="void" id="id19" rules="none"> <colgroup><col class="label" /><col /></colgroup> <tbody valign="top"> -<tr><td class="label"><a class="fn-backref" href="#id6">[2]</a></td><td>Anyway each floating point operation starts by rounding its +<tr><td class="label"><a class="fn-backref" href="#id17">[2]</a></td><td>Anyway each floating point operation starts by rounding its operands to the floating point precision.</td></tr> </tbody> </table> -<table class="docutils footnote" frame="void" id="id9" rules="none"> +<table class="docutils footnote" frame="void" id="id20" rules="none"> <colgroup><col class="label" /><col /></colgroup> <tbody valign="top"> -<tr><td class="label"><a class="fn-backref" href="#id7">[3]</a></td><td>The <tt class="docutils literal">\xintexpr</tt> could be <tt class="docutils literal">\xinttheexpr</tt> but that would be -less efficient. Cf. <a class="reference external" href="http://www.ctan.org/pkg/xint">xintexpr</a> documentation about nested -expressions.</td></tr> +<tr><td class="label"><a class="fn-backref" href="#id18">[3]</a></td><td>The <tt class="docutils literal">\xintexpr</tt> here could be <tt class="docutils literal">\xinttheexpr</tt> but that +would be less efficient. Cf. <a class="reference external" href="http://www.ctan.org/pkg/xint">xintexpr</a> documentation about +nested expressions.</td></tr> </tbody> </table> </blockquote> </div> +<div class="section" id="polfloateval-polname-at-fraction"> +<span id="polfloatevalat"></span><h2><a class="toc-backref" href="#id87"><tt class="docutils literal"><span class="pre">\PolFloatEval{polname}\At{fraction}</span></tt></a></h2> +<blockquote> +<p>Evaluates the polynomial at value <tt class="docutils literal">fraction</tt> which must be in (or +expand to) a format acceptable to the <a class="reference external" href="http://www.ctan.org/pkg/xint">xintfrac</a> macros, and produces +a floating point number.</p> +<div class="admonition attention"> +<p class="first admonition-title">Attention!</p> +<p class="last">Meaning was changed at <tt class="docutils literal">0.4</tt>. Formerly the evaluation point +could be given as an expression.</p> +</div> +</blockquote> +</div> +<div class="section" id="polifcoeffisplusorminusone-a-b"> +<span id="polifcoeffisplusorminusone"></span><h2><a class="toc-backref" href="#id88"><tt class="docutils literal"><span class="pre">\PolIfCoeffIsPlusOrMinusOne{A}{B}</span></tt></a></h2> +<blockquote> +<p>This macro is a priori undefined.</p> +<p>It is defined via the default <a class="reference internal" href="#poltypesetcmd-raw-coeff">\PolTypesetCmd{raw_coeff}</a> to be +used if needed in the execution of <a class="reference internal" href="#poltypesetmonomialcmd">\PolTypesetMonomialCmd</a>, +e.g. to insert a <tt class="docutils literal">\cdot</tt> in front of <tt class="docutils literal"><span class="pre">\PolVar^{\PolIndex}</span></tt> if +the coefficient is not plus or minus one.</p> +<p>The macro will execute <tt class="docutils literal">A</tt> if the coefficient has been found to be +plus or minus one, and <tt class="docutils literal">B</tt> if not.</p> +</blockquote> +</div> +<div class="section" id="polleadingcoeff-polname"> +<span id="polleadingcoeff"></span><h2><a class="toc-backref" href="#id89"><tt class="docutils literal">\PolLeadingCoeff{polname}</tt></a></h2> +<blockquote> +Expands to the leading coefficient.</blockquote> +</div> <div class="section" id="polnthcoeff-polname-number"> -<h2><a class="toc-backref" href="#id40"><tt class="docutils literal"><span class="pre">\PolNthCoeff{polname}{number}</span></tt></a></h2> +<span id="polnthcoeff"></span><h2><a class="toc-backref" href="#id90"><tt class="docutils literal"><span class="pre">\PolNthCoeff{polname}{number}</span></tt></a></h2> <blockquote> It expands to the raw <tt class="docutils literal">N</tt>-th coefficient (<tt class="docutils literal">0/1[0]</tt> if the index number is out of range). With <tt class="docutils literal"><span class="pre">N=-1</span></tt>, <tt class="docutils literal"><span class="pre">-2</span></tt>, ... expands to the leading coefficients.</blockquote> </div> <div class="section" id="poldegree-polname"> -<h2><a class="toc-backref" href="#id41"><tt class="docutils literal">\PolDegree{polname}</tt></a></h2> +<span id="poldegree"></span><h2><a class="toc-backref" href="#id91"><tt class="docutils literal">\PolDegree{polname}</tt></a></h2> <blockquote> It expands to the degree. This is <tt class="docutils literal"><span class="pre">-1</span></tt> if zero polynomial but this may change in future. Should it then expand to <tt class="docutils literal"><span class="pre">-\infty</span></tt> ?</blockquote> </div> <div class="section" id="poltoexpr-polname"> -<h2><a class="toc-backref" href="#id42"><tt class="docutils literal">\PolToExpr{polname}</tt></a></h2> +<span id="poltoexpr"></span><h2><a class="toc-backref" href="#id92"><tt class="docutils literal">\PolToExpr{polname}</tt></a></h2> <blockquote> -<p>Expands <a class="footnote-reference" href="#id11" id="id10">[4]</a> to <tt class="docutils literal"><span class="pre">coeff_N*x^N+...</span></tt> (descending powers.)</p> -<table class="docutils footnote" frame="void" id="id11" rules="none"> +<p>Expands <a class="footnote-reference" href="#id22" id="id21">[4]</a> to <tt class="docutils literal"><span class="pre">coeff_N*x^N+...</span></tt> (descending powers.)</p> +<table class="docutils footnote" frame="void" id="id22" rules="none"> <colgroup><col class="label" /><col /></colgroup> <tbody valign="top"> -<tr><td class="label"><a class="fn-backref" href="#id10">[4]</a></td><td>in a <tt class="docutils literal">\write</tt>, <tt class="docutils literal">\edef</tt>, or <tt class="docutils literal"><span class="pre">\csname...\endcsname</span></tt>, but +<tr><td class="label"><a class="fn-backref" href="#id21">[4]</a></td><td>in a <tt class="docutils literal">\write</tt>, <tt class="docutils literal">\edef</tt>, or <tt class="docutils literal"><span class="pre">\csname...\endcsname</span></tt>, but not under <tt class="docutils literal"><span class="pre">\romannumeral-`0</span></tt>.</td></tr> </tbody> </table> @@ -885,7 +1497,7 @@ of <tt class="docutils literal">\PolToExpr{f}</tt>, but a simple <tt class="docu the identical result.</p> </blockquote> <div class="section" id="poltoexproneterm-raw-coeff-number"> -<h3><a class="toc-backref" href="#id43"><tt class="docutils literal"><span class="pre">\PolToExprOneTerm{raw_coeff}{number}</span></tt></a></h3> +<span id="poltoexproneterm"></span><h3><a class="toc-backref" href="#id93"><tt class="docutils literal"><span class="pre">\PolToExprOneTerm{raw_coeff}{number}</span></tt></a></h3> <blockquote> <p>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 <tt class="docutils literal">x^number</tt>, except if the co or a minus one. See <a class="reference internal" href="#poltoexprtimes">\PolToExprTimes</a>.</p> </blockquote> </div> +<div class="section" id="poltoexpronetermstylea-raw-coeff-number"> +<span id="poltoexpronetermstylea"></span><h3><a class="toc-backref" href="#id94"><tt class="docutils literal"><span class="pre">\PolToExprOneTermStyleA{raw_coeff}{number}</span></tt></a></h3> +<blockquote> +Holds the default package meaning of +<a class="reference internal" href="#poltoexproneterm-raw-coeff-number">\PolToExprOneTerm{raw_coeff}{number}</a>.</blockquote> +</div> <div class="section" id="poltoexpronetermstyleb-raw-coeff-number"> -<h3><a class="toc-backref" href="#id44"><tt class="docutils literal"><span class="pre">\PolToExprOneTermStyleB{raw_coeff}{number}</span></tt></a></h3> +<span id="poltoexpronetermstyleb"></span><h3><a class="toc-backref" href="#id95"><tt class="docutils literal"><span class="pre">\PolToExprOneTermStyleB{raw_coeff}{number}</span></tt></a></h3> <blockquote> <p>For output in this style:</p> <pre class="literal-block"> 2*x^11/3+3*x^8/7-x^5−x^4/4−x^3−x^2/2−2*x+1 </pre> -<p>issue <tt class="docutils literal">\let\PolToExprOneTerm\PolToExprOneTermStyleB</tt> before using -<tt class="docutils literal">\PolToExpr</tt>. Note that then <tt class="docutils literal">\PolToExprCmd</tt> isn't used at all.</p> +<p>issue <tt class="docutils literal">\let\PolToExprOneTerm\PolToExprOneTermStyleB</tt> before usage of +<tt class="docutils literal">\PolToExpr</tt>. Note that then <tt class="docutils literal">\PolToExprCmd</tt> isn't used at all. +To revert to package default, issue +<tt class="docutils literal">\let\PolToExprOneTerm\PolToExprOneTermStyleA</tt>.</p> <p>To suppress the <tt class="docutils literal">*</tt>'s, cf. <a class="reference internal" href="#poltoexprtimes">\PolToExprTimes</a>.</p> </blockquote> </div> <div class="section" id="poltoexprcmd-raw-coeff"> -<h3><a class="toc-backref" href="#id45"><tt class="docutils literal">\PolToExprCmd{raw_coeff}</tt></a></h3> +<span id="poltoexprcmd"></span><h3><a class="toc-backref" href="#id96"><tt class="docutils literal">\PolToExprCmd{raw_coeff}</tt></a></h3> <blockquote> It is the one-argument macro used by the package definition of <tt class="docutils literal">\PolToExprOneTerm</tt> for the coefficients themselves (when not @@ -920,21 +1540,21 @@ to <tt class="docutils literal"><span class="pre">\xintIrr{#1}</span></tt> or to output forcefully reduced coefficients.</blockquote> </div> <div class="section" id="poltoexprtermprefix-raw-coeff"> -<h3><a class="toc-backref" href="#id46"><tt class="docutils literal">\PolToExprTermPrefix{raw_coeff}</tt></a></h3> +<span id="poltoexprtermprefix"></span><h3><a class="toc-backref" href="#id97"><tt class="docutils literal">\PolToExprTermPrefix{raw_coeff}</tt></a></h3> <blockquote> Defined identically as <a class="reference internal" href="#poltypesetcmdprefix-raw-coeff">\PolTypesetCmdPrefix{raw_coeff}</a>. It prefixes with a plus sign for non-negative coefficients, because they don't carry one by themselves.</blockquote> </div> -<div class="section" id="poltoexprvar"> -<h3><a class="toc-backref" href="#id47"><tt class="docutils literal">\PolToExprVar</tt></a></h3> +<div class="section" id="id23"> +<span id="poltoexprvar"></span><h3><a class="toc-backref" href="#id98"><tt class="docutils literal">\PolToExprVar</tt></a></h3> <blockquote> 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 <tt class="docutils literal">x</tt>.</blockquote> </div> -<div class="section" id="poltoexprtimes"> -<h3><a class="toc-backref" href="#id48"><tt class="docutils literal">\PolToExprTimes</tt></a></h3> +<div class="section" id="id24"> +<span id="poltoexprtimes"></span><h3><a class="toc-backref" href="#id99"><tt class="docutils literal">\PolToExprTimes</tt></a></h3> <blockquote> This expands to the symbol used for multiplication of an <tt class="docutils literal"><span class="pre">x^{number}</span></tt> by the corresponding coefficient. The default is @@ -943,41 +1563,39 @@ this will give output incompatible with some professional computer algebra software).</blockquote> </div> </div> -<div class="section" id="id12"> -<h2><a class="toc-backref" href="#id49"><tt class="docutils literal"><span class="pre">\PolToExpr*{polname}</span></tt></a></h2> +<div class="section" id="id26"> +<span id="id25"></span><h2><a class="toc-backref" href="#id100"><tt class="docutils literal"><span class="pre">\PolToExpr*{polname}</span></tt></a></h2> <blockquote> Expands to <tt class="docutils literal"><span class="pre">coeff_0+coeff_1*x+coeff_2*x^2+...</span></tt> (ascending powers). Customizable like <a class="reference internal" href="#poltoexpr-polname">\PolToExpr{polname}</a> via the same macros.</blockquote> </div> <div class="section" id="poltofloatexpr-polname"> -<h2><a class="toc-backref" href="#id50"><tt class="docutils literal">\PolToFloatExpr{polname}</tt></a></h2> +<span id="poltofloatexpr"></span><h2><a class="toc-backref" href="#id101"><tt class="docutils literal">\PolToFloatExpr{polname}</tt></a></h2> <blockquote> <p>Similar to <a class="reference internal" href="#poltoexpr-polname">\PolToExpr{polname}</a> but uses <a class="reference external" href="\PolToFloatExprCmd{raw_coeff}">\PolToFloatExprCmd</a> which by default rounds and converts the coefficients to floating point format.</p> <div class="admonition note"> <p class="first admonition-title">Note</p> -<p>The polynomial function for usage in <tt class="docutils literal">\xintfloatexpr</tt> is -already prepared with the rounded coefficients, but the latter -are not easily recoverable (and especially not expandably) from -this. Thus <tt class="docutils literal">\PolToFloatExprCmd</tt> operates from the <em>exact</em> -coefficients anew. This means though that if the prevailing float -precision was changed with <tt class="docutils literal"><span class="pre">\xintDigits:=P;</span></tt> syntax, the output -will obey this precision <tt class="docutils literal">P</tt>, but the polynomial function was -defined earlier and operates on floating point numbers with -coefficients which were rounded at time of definition.</p> -<p class="last">This may change in future, if the pre-rounded coefficients are -stored in a more easily accessible data structure.</p> +<p>It is not necessary to have issued +<a class="reference internal" href="#polgenfloatvariant-polname">\PolGenFloatVariant{polname}</a>. The rounded coefficients are +not easily recoverable from the <tt class="docutils literal">\xintfloatexpr</tt> polynomial +function hence <tt class="docutils literal">\PolToFloatExprCmd</tt> operates from the <em>exact</em> +coefficients anew.</p> +<p class="last">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 <tt class="docutils literal">\xintfloatexpr</tt> and +those output by <tt class="docutils literal">\PolToFloatExpr{polname}</tt>.</p> </div> </blockquote> <div class="section" id="poltofloatexproneterm-raw-coeff-number"> -<h3><a class="toc-backref" href="#id51"><tt class="docutils literal"><span class="pre">\PolToFloatExprOneTerm{raw_coeff}{number}</span></tt></a></h3> +<span id="poltofloatexproneterm"></span><h3><a class="toc-backref" href="#id102"><tt class="docutils literal"><span class="pre">\PolToFloatExprOneTerm{raw_coeff}{number}</span></tt></a></h3> <blockquote> Similar to <a class="reference external" href="\PolToExprOneTerm{raw_coeff}{number}">\PolToExprOneTerm</a>. But does not treat especially coefficients equal to plus or minus one.</blockquote> </div> <div class="section" id="poltofloatexprcmd-raw-coeff"> -<h3><a class="toc-backref" href="#id52"><tt class="docutils literal">\PolToFloatExprCmd{raw_coeff}</tt></a></h3> +<span id="id28"></span><h3><a class="toc-backref" href="#id103"><tt class="docutils literal">\PolToFloatExprCmd{raw_coeff}</tt></a></h3> <blockquote> <p>It is the one-argument macro used by <tt class="docutils literal">\PolToFloatExprOneTerm</tt>. Its package definition is <tt class="docutils literal"><span class="pre">\xintFloat{#1}</span></tt>.</p> @@ -999,29 +1617,151 @@ in <tt class="docutils literal">xintfrac</tt> raw format.</p> </blockquote> </div> </div> -<div class="section" id="id13"> -<h2><a class="toc-backref" href="#id53"><tt class="docutils literal"><span class="pre">\PolToFloatExpr*{polname}</span></tt></a></h2> +<div class="section" id="id30"> +<span id="id29"></span><h2><a class="toc-backref" href="#id104"><tt class="docutils literal"><span class="pre">\PolToFloatExpr*{polname}</span></tt></a></h2> <blockquote> Typesets in ascending powers.</blockquote> </div> <div class="section" id="poltolist-polname"> -<h2><a class="toc-backref" href="#id54"><tt class="docutils literal">\PolToList{polname}</tt></a></h2> +<span id="poltolist"></span><h2><a class="toc-backref" href="#id105"><tt class="docutils literal">\PolToList{polname}</tt></a></h2> <blockquote> Expands to <tt class="docutils literal"><span class="pre">{coeff_0}{coeff_1}...{coeff_N}</span></tt> with <tt class="docutils literal">N</tt> = degree (except zero polynomial which does give <tt class="docutils literal">{0/1[0]}</tt> and not an empty output.)</blockquote> </div> <div class="section" id="poltocsv-polname"> -<h2><a class="toc-backref" href="#id55"><tt class="docutils literal">\PolToCSV{polname}</tt></a></h2> +<span id="poltocsv"></span><h2><a class="toc-backref" href="#id106"><tt class="docutils literal">\PolToCSV{polname}</tt></a></h2> <blockquote> Expands to <tt class="docutils literal">coeff_0, coeff_1, coeff_2, <span class="pre">.....,</span> coeff_N</tt>. Converse to <a class="reference internal" href="#polfromcsv-polname-csv">\PolFromCSV</a>.</blockquote> </div> +<div class="section" id="polsturmchainlength-sturmname"> +<span id="polsturmchainlength"></span><h2><a class="toc-backref" href="#id107"><tt class="docutils literal">\PolSturmChainLength{sturmname}</tt></a></h2> +<blockquote> +<p>Returns the integer <tt class="docutils literal">N</tt> such that <tt class="docutils literal">sturmname_N</tt> is the last one +in the Sturm chain <tt class="docutils literal">sturmname_0</tt>, <tt class="docutils literal">sturmname_1</tt>, ...</p> +<p>See <a class="reference internal" href="#poltosturm-polname-sturmname">\PolToSturm{polname}{sturmname}</a>.</p> +</blockquote> +</div> +<div class="section" id="polsturmifzeroexactlyknown-sturmname-index-a-b"> +<span id="polsturmifzeroexactlyknown"></span><h2><a class="toc-backref" href="#id108"><tt class="docutils literal"><span class="pre">\PolSturmIfZeroExactlyKnown{sturmname}{index}{A}{B}</span></tt></a></h2> +<blockquote> +<p>Executes <tt class="docutils literal">A</tt> if the <tt class="docutils literal">index</tt>th interval reduces to a singleton, +i.e. the root is known exactly, else <tt class="docutils literal">B</tt>.</p> +<div class="admonition note"> +<p class="first admonition-title">Note</p> +<p><tt class="docutils literal">index</tt> may be a TeX count, or a <tt class="docutils literal">\value{latexcounter}</tt>, or a +numerical expression as parsable by <tt class="docutils literal">\numexpr</tt>: it does not +have to be given via explicit digits.</p> +<p class="last">This remark applies also to the other package macros with +<tt class="docutils literal">index</tt> 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).</p> +</div> +</blockquote> +</div> +<div class="section" id="polsturmisolatedzeroleft-sturmname-index"> +<span id="polsturmisolatedzeroleft"></span><h2><a class="toc-backref" href="#id109"><tt class="docutils literal"><span class="pre">\PolSturmIsolatedZeroLeft{sturmname}{index}</span></tt></a></h2> +<blockquote> +Expands to the left end-point for the <tt class="docutils literal">index</tt>th interval +obtained via <a class="reference internal" href="#polsturmisolatezeros-sturmname">\PolSturmIsolateZeros{sturmname}</a> and possibly +refined afterwards.</blockquote> +</div> +<div class="section" id="polsturmisolatedzeroright-sturmname-index"> +<span id="polsturmisolatedzeroright"></span><h2><a class="toc-backref" href="#id110"><tt class="docutils literal"><span class="pre">\PolSturmIsolatedZeroRight{sturmname}{index}</span></tt></a></h2> +<blockquote> +Expands to the right end-point for the <tt class="docutils literal">index</tt>th interval +obtained via <a class="reference internal" href="#polsturmisolatezeros-sturmname">\PolSturmIsolateZeros{sturmname}</a> and possibly +refined afterwards.</blockquote> +</div> +<div class="section" id="polsturmnbofisolatedzeros-sturmname"> +<span id="polsturmnbofisolatedzeros"></span><h2><a class="toc-backref" href="#id111"><tt class="docutils literal">\PolSturmNbOfIsolatedZeros{sturmname}</tt></a></h2> +<blockquote> +Expands to the number of real roots of the polynomial +<tt class="docutils literal"><sturmname>_0</tt> (which is the number of distinct real roots of the +polynomial used to create the Sturm chain via +<a class="reference internal" href="#poltosturm-polname-sturmname">\PolToSturm{polname}{sturmname}</a>.</blockquote> +</div> +<div class="section" id="polintervalwidth-sturmname-index"> +<span id="polintervalwidth"></span><h2><a class="toc-backref" href="#id112"><tt class="docutils literal"><span class="pre">\PolIntervalWidth{sturmname}{index}</span></tt></a></h2> +<blockquote> +The <tt class="docutils literal">10^E</tt> width of the current <tt class="docutils literal">index</tt>th root localization +interval. Output is in <a class="reference external" href="http://www.ctan.org/pkg/xint">xintfrac</a> raw <tt class="docutils literal">1/1[E]</tt> format (if not zero).</blockquote> +</div> +<div class="section" id="macros-for-use-within-execution-of-polprintintervals"> +<h2><a class="toc-backref" href="#id113">Macros for use within execution of <tt class="docutils literal">\PolPrintIntervals</tt></a></h2> +<p>More precisely, they can be used within the replacement texts of the +<a class="reference internal" href="#polprintintervalsprintleftendpoint">\PolPrintIntervalsPrintLeftEndPoint</a>, etc, macros.</p> +<div class="section" id="id31"> +<span id="polprintintervalstheendpoint"></span><h3><a class="toc-backref" href="#id114"><tt class="docutils literal">\PolPrintIntervalsTheEndPoint</tt></a></h3> +<blockquote> +Within a custom <a class="reference internal" href="#polprintintervalsprintleftendpoint">\PolPrintIntervalsPrintLeftEndPoint</a>, custom +<a class="reference internal" href="#polprintintervalsprintrightendpoint">\PolPrintIntervalsPrintRightEndPoint</a>, or custom +<a class="reference internal" href="#polprintintervalsprintexactzero">\PolPrintIntervalsPrintExactZero</a> this macro expands to the left +or right end point of the considered interval. Serves as default +replacement for <a class="reference internal" href="#polprintintervalsprintleftendpoint">\PolPrintIntervalsPrintLeftEndPoint</a> , etc...</blockquote> +</div> +<div class="section" id="id32"> +<span id="polprintintervalstheindex"></span><h3><a class="toc-backref" href="#id115"><tt class="docutils literal">\PolPrintIntervalsTheIndex</tt></a></h3> +<blockquote> +Within a custom <a class="reference internal" href="#polprintintervalsprintleftendpoint">\PolPrintIntervalsPrintLeftEndPoint</a>, custom +<a class="reference internal" href="#polprintintervalsprintrightendpoint">\PolPrintIntervalsPrintRightEndPoint</a>, or custom +<a class="reference internal" href="#polprintintervalsprintexactzero">\PolPrintIntervalsPrintExactZero</a> 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 <a class="reference internal" href="#polprintintervalsprintleftendpoint">\PolPrintIntervalsPrintLeftEndPoint</a> and +the other two similar macros.</blockquote> +</div> +<div class="section" id="polifendpointispositive-a-b"> +<span id="polifendpointispositive"></span><h3><a class="toc-backref" href="#id116"><tt class="docutils literal"><span class="pre">\PolIfEndPointIsPositive{A}{B}</span></tt></a></h3> +<blockquote> +Within a custom <a class="reference internal" href="#polprintintervalsprintleftendpoint">\PolPrintIntervalsPrintLeftEndPoint</a>, custom +<a class="reference internal" href="#polprintintervalsprintrightendpoint">\PolPrintIntervalsPrintRightEndPoint</a>, or custom +<a class="reference internal" href="#polprintintervalsprintexactzero">\PolPrintIntervalsPrintExactZero</a> this macro executes <tt class="docutils literal">A</tt> if +the considered interval end-point is positive, else <tt class="docutils literal">B</tt>.</blockquote> +</div> +<div class="section" id="polifendpointisnegative-a-b"> +<span id="polifendpointisnegative"></span><h3><a class="toc-backref" href="#id117"><tt class="docutils literal"><span class="pre">\PolIfEndPointIsNegative{A}{B}</span></tt></a></h3> +<blockquote> +Within a custom <a class="reference internal" href="#polprintintervalsprintleftendpoint">\PolPrintIntervalsPrintLeftEndPoint</a>, custom +<a class="reference internal" href="#polprintintervalsprintrightendpoint">\PolPrintIntervalsPrintRightEndPoint</a>, or custom +<a class="reference internal" href="#polprintintervalsprintexactzero">\PolPrintIntervalsPrintExactZero</a> this macro executes <tt class="docutils literal">A</tt> if +the considered interval end-point is negative, else <tt class="docutils literal">B</tt>.</blockquote> +</div> +<div class="section" id="polifendpointiszero-a-b"> +<span id="polifendpointiszero"></span><h3><a class="toc-backref" href="#id118"><tt class="docutils literal"><span class="pre">\PolIfEndPointIsZero{A}{B}</span></tt></a></h3> +<blockquote> +Within a custom <a class="reference internal" href="#polprintintervalsprintleftendpoint">\PolPrintIntervalsPrintLeftEndPoint</a>, custom +<a class="reference internal" href="#polprintintervalsprintrightendpoint">\PolPrintIntervalsPrintRightEndPoint</a>, or custom +<a class="reference internal" href="#polprintintervalsprintexactzero">\PolPrintIntervalsPrintExactZero</a> this macro executes <tt class="docutils literal">A</tt> if +the considered interval end-point is zero, else <tt class="docutils literal">B</tt>.</blockquote> +</div> +</div> +<div class="section" id="poldectostring-decimal-number"> +<span id="poldectostring"></span><h2><a class="toc-backref" href="#id119"><tt class="docutils literal">\PolDecToString{decimal number}</tt></a></h2> +<blockquote> +<p>This is a utility macro to print decimal numbers. Indeed for legacy +reasons, <a class="reference external" href="http://www.ctan.org/pkg/xint">xintfrac</a> does not yet have user-level ready-to-use macros +handling specifically the printing of decimal numbers from their +internal representations such as <tt class="docutils literal">A/1[N]</tt>.</p> +<p>For example +<tt class="docutils literal"><span class="pre">\PolDecToString{123.456e-8}</span></tt> will expand to <tt class="docutils literal">0.00000123456</tt> +and <tt class="docutils literal"><span class="pre">\PolDecToString{123.450e-8}</span></tt> to <tt class="docutils literal">0.00000123450</tt>. This +illustrates that trailing zeros are not trimmed (to achieve that one +can use <tt class="docutils literal"><span class="pre">\PolDecToString{\xintREZ{#1}}</span></tt>.)</p> +<p>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.</p> +<p>This utility macro will presumably be incorporated (possibly in a +more powerful form) to <a class="reference external" href="http://www.ctan.org/pkg/xint">xintfrac</a> (or rather to a decimal module) in +a future <a class="reference external" href="http://www.ctan.org/pkg/xint">xint</a> release.</p> +</blockquote> +</div> </div> <div class="section" id="booleans-with-default-setting-as-indicated"> -<h1><a class="toc-backref" href="#id56">Booleans (with default setting as indicated)</a></h1> +<h1><a class="toc-backref" href="#id120">Booleans (with default setting as indicated)</a></h1> <div class="section" id="xintverbosefalse"> -<h2><a class="toc-backref" href="#id57"><tt class="docutils literal">\xintverbosefalse</tt></a></h2> +<h2><a class="toc-backref" href="#id121"><tt class="docutils literal">\xintverbosefalse</tt></a></h2> <blockquote> <p>This is actually an <a class="reference external" href="http://www.ctan.org/pkg/xint">xintexpr</a> configuration. Setting it to <tt class="docutils literal">true</tt> triggers the writing of information to the log when new @@ -1034,20 +1774,20 @@ unstable and undocumented internal structures.</p> </blockquote> </div> <div class="section" id="poltypesetallfalse"> -<h2><a class="toc-backref" href="#id58"><tt class="docutils literal">\poltypesetallfalse</tt></a></h2> +<h2><a class="toc-backref" href="#id122"><tt class="docutils literal">\poltypesetallfalse</tt></a></h2> <blockquote> If <tt class="docutils literal">true</tt>, <a class="reference internal" href="#poltypeset-polname">\PolTypeset{polname}</a> will also typeset the vanishing coefficients.</blockquote> </div> <div class="section" id="poltoexprallfalse"> -<h2><a class="toc-backref" href="#id59"><tt class="docutils literal">\poltoexprallfalse</tt></a></h2> +<h2><a class="toc-backref" href="#id123"><tt class="docutils literal">\poltoexprallfalse</tt></a></h2> <blockquote> If <tt class="docutils literal">true</tt>, <a class="reference internal" href="#poltoexpr-polname">\PolToExpr{polname}</a> and <a class="reference internal" href="#poltofloatexpr-polname">\PolToFloatExpr{polname}</a> will also include the vanishing coefficients in their outputs.</blockquote> </div> </div> <div class="section" id="technicalities"> -<h1><a class="toc-backref" href="#id60">Technicalities</a></h1> +<h1><a class="toc-backref" href="#id124">Technicalities</a></h1> <ul> <li><p class="first">The catcode of the semi-colon is reset temporarily by <a class="reference internal" href="#poldef">\poldef</a> 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 <tt class="docutils literal">:=</tt> may be active with no <li><p class="first">During execution of polynomial operations by <tt class="docutils literal">\poldef</tt> (but not during the initial purely numerical parsing of the expression), the <a class="reference external" href="http://www.ctan.org/pkg/xint">xintfrac</a> macro <tt class="docutils literal">\xintAdd</tt> is temporarily patched to always express -<tt class="docutils literal">a/b + c/d</tt> with <tt class="docutils literal"><span class="pre">l.c.m.(b,d)</span></tt> as denominator. Indeed the current +<tt class="docutils literal">a/b + c/d</tt> with <tt class="docutils literal">lcm(b,d)</tt> as denominator. Indeed the current (xint 1.2p) <tt class="docutils literal">\xintAdd</tt> uses <tt class="docutils literal"><span class="pre">(ad+bc)/bd</span></tt> formula except if <tt class="docutils literal">b</tt> divides <tt class="docutils literal">d</tt> or <tt class="docutils literal">d</tt> divides <tt class="docutils literal">b</tt>, which quickly leads in real life to big denominators.</p> @@ -1082,7 +1822,8 @@ survive addition and multiplications:</p> 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 </pre> <p>where all coefficients have the same denominator 6 (which in this -example is the <tt class="docutils literal">l.c.m</tt> of the denominators of the reduced coefficients.)</p> +example is the least common multiple of the denominators of the +reduced coefficients.)</p> </li> <li><p class="first"><a class="reference internal" href="#poldiff-polname-1-polname-2">\PolDiff{polname_1}{polname_2}</a> always applies <tt class="docutils literal">\xintIrr</tt> to the resulting coefficients, except that the <em>power of ten</em> part <tt class="docutils literal">[N]</tt> @@ -1111,53 +1852,193 @@ high degree and few coefficients (as an example with <tt class="docutils literal additions involvings only zeroes... which does take time). This may change in the future.</p> </li> -<li><p class="first">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 <tt class="docutils literal">\xintdeffloatvar</tt> or -<tt class="docutils literal">\xintthefloatexpr</tt> contexts for any kind of numerical mathematics. -Of course, exact computations are invaluable for number theory or -combinatorics...</p> -</li> <li><p class="first">As is to be expected internal structures of the package are barely documented and unstable. Don't use them.</p> </li> </ul> </div> -<div class="section" id="releases"> -<h1><a class="toc-backref" href="#id61">RELEASES</a></h1> +<div class="section" id="change-log"> +<h1><a class="toc-backref" href="#id125">CHANGE LOG</a></h1> +<ul> +<li><p class="first">v0.1 (2018/01/11): initial release. Features:</p> +<ul class="simple"> +<li>The <a class="reference internal" href="#poldef">\poldef</a> parser itself,</li> +<li>Differentiation and anti-differentiation,</li> +<li>Euclidean division and GCDs,</li> +<li>Various utilities such as <a class="reference internal" href="#polfromcsv">\PolFromCSV</a>, +<a class="reference internal" href="#polmapcoeffs">\PolMapCoeffs</a>, +<a class="reference internal" href="#poltocsv">\PolToCSV</a>, <a class="reference internal" href="#poltoexpr">\PolToExpr</a>, ...</li> +</ul> +<p>Only one-variable polynomials so far.</p> +</li> +<li><p class="first">v0.2 (2018/01/14)</p> +<ul class="simple"> +<li>Fix: <tt class="docutils literal">"README thinks \numexpr recognizes ^ operator"</tt>.</li> +<li>Convert README to reStructuredText markup.</li> +<li>Move main documentation from README to separate <tt class="docutils literal">polexpr.txt</tt> file.</li> +<li>Provide <tt class="docutils literal">polexpr.html</tt> as obtained via <a class="reference external" href="http://docutils.sourceforge.net/docs/index.html">DocUtils</a> <tt class="docutils literal">rst2html.py</tt>.</li> +<li>Convert README to (CTAN compatible) Markdown markup.</li> +</ul> +<p>Due to lack of available time the test suite might not be extensive +enough. Bug reports are very welcome!</p> +</li> +<li><p class="first">v0.3 (2018/01/17)</p> +<ul> +<li><p class="first">bug fixes:</p> <ul> -<li><p class="first">0.1 (2018/01/11)</p> -<p>Initial release (files README, polexpr.sty).</p> +<li><p class="first">the <tt class="docutils literal">0.1</tt> <a class="reference internal" href="#polevalat">\PolEval</a> accepted expressions for its second +argument, but this was removed by mistake at <tt class="docutils literal">0.2</tt>. Restored.</p> +<p><strong>Attention</strong>: at <tt class="docutils literal">0.4</tt> this has been reverted again, and +<a class="reference internal" href="#polevalatexpr">\PolEval{P}\AtExpr{foo}</a> syntax is needed for +using expressions in the second argument.</p> </li> -<li><p class="first">0.2 (2018/01/14)</p> -<p>Documentation moved to polexpr.{txt,html}.</p> +</ul> +</li> +<li><p class="first">incompatible or breaking changes:</p> +<ul class="simple"> +<li><a class="reference internal" href="#poltoexpr">\PolToExpr</a> now by default uses <em>descending</em> +powers (it also treats differently coefficients equal to 1 or -1.) +Use <a class="reference internal" href="#id25">\PolToExpr*</a> for <em>ascending</em> powers.</li> +<li><a class="reference internal" href="#polevalat">\PolEval</a> reduced the output to smallest terms, +but as this is costly with big fractions and not needed if e.g. +wrapped in an <tt class="docutils literal">\xintRound</tt> or <tt class="docutils literal">\xintFloat</tt>, this step has been +removed; the former meaning is available as <a class="reference internal" href="#polevalreducedat">\PolEvalReduced</a>.</li> +</ul> +</li> +<li><p class="first">new (or newly documented) macros:</p> +<ul class="simple"> +<li><a class="reference internal" href="#poltypesetcmd">\PolTypesetCmd</a></li> +<li><a class="reference internal" href="#poltypesetcmdprefix">\PolTypesetCmdPrefix</a></li> +<li><a class="reference internal" href="#poltypesetmonomialcmd">\PolTypesetMonomialCmd</a></li> +<li><a class="reference internal" href="#polevalreducedat">\PolEvalReducedAt</a></li> +<li><a class="reference internal" href="#poltofloatexpr">\PolToFloatExpr</a></li> +<li><a class="reference internal" href="#poltoexproneterm">\PolToExprOneTerm</a></li> +<li><a class="reference internal" href="#poltofloatexproneterm">\PolToFloatExprOneTerm</a></li> +<li><a class="reference internal" href="#poltoexprcmd">\PolToExprCmd</a></li> +<li><a class="reference internal" href="#id28">\PolToFloatExprCmd</a></li> +<li><a class="reference internal" href="#poltoexprtermprefix">\PolToExprTermPrefix</a></li> +<li><a class="reference internal" href="#poltoexprvar">\PolToExprVar</a></li> +<li><a class="reference internal" href="#poltoexprtimes">\PolToExprTimes</a></li> +</ul> +</li> +<li><p class="first">improvements:</p> +<ul> +<li><p class="first">documentation has a table of contents, internal hyperlinks, +standardized signature notations and added explanations.</p> +</li> +<li><p class="first">one can do <tt class="docutils literal"><span class="pre">\PolLet{g}={f}</span></tt> or <tt class="docutils literal"><span class="pre">\PolLet{g}{f}</span></tt>.</p> </li> -<li><p class="first">0.3 (2018/01/17)</p> -<p>Make polynomials known to <tt class="docutils literal">\xintfloatexpr</tt> and improve -documentation.</p> +<li><p class="first"><tt class="docutils literal">\PolToExpr{f}</tt> is highly customizable.</p> </li> -<li><p class="first">0.3.1 (2018/01/18)</p> -<p>Fix two typos in documentation.</p> +<li><p class="first"><a class="reference internal" href="#poldef">\poldef</a> and other defining macros prepare the polynomial +functions for usage within <tt class="docutils literal">\xintthefloatexpr</tt> (or +<tt class="docutils literal">\xintdeffloatvar</tt>). 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.</p> +<p><strong>Attention</strong>: this has been reverted at <tt class="docutils literal">0.4</tt>. The macro +<a class="reference internal" href="#polgenfloatvariant">\PolGenFloatVariant</a> must be used for +generation floating point polynomial functions.</p> +</li> +</ul> </li> </ul> -<p>Files of 0.3.1 release:</p> +</li> +<li><p class="first">v0.3.1 (2018/01/18)</p> +<p>Fixes two typos in example code included in the documentation.</p> +</li> +<li><p class="first">v0.4 (2018/02/16)</p> +<ul> +<li><p class="first">bug fixes:</p> <ul class="simple"> -<li>README.md,</li> -<li>polexpr.sty (package file),</li> -<li>polexpr.txt (documentation),</li> -<li>polexpr.html (conversion via <a class="reference external" href="http://docutils.sourceforge.net/docs/index.html">DocUtils</a> rst2html.py)</li> +<li>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 <a class="reference internal" href="#polmapcoeffs">\PolMapCoeffs</a>.</li> +<li><a class="reference internal" href="#polgcd">\PolGCD</a> was buggy in case of first polynomial being +of lesser degree than the second one.</li> +</ul> +</li> +<li><p class="first">breaking changes:</p> +<ul> +<li><p class="first">formerly <a class="reference internal" href="#polevalat">\PolEval{P}\At{foo}</a> allowed <tt class="docutils literal">foo</tt> to +be an expression, which was transparently handled via +<tt class="docutils literal">\xinttheexpr</tt>. Now, <tt class="docutils literal">foo</tt> must be a fraction (or a macro +expanding to such) in the format acceptable by <tt class="docutils literal">xintfrac.sty</tt> +macros. Use <a class="reference internal" href="#polevalatexpr">\PolEval{P}\AtExpr{foo}</a> for more +general arguments using expression syntax. E.g., if <tt class="docutils literal">foo</tt> is the +name of a variable known to <tt class="docutils literal">\xintexpr</tt>.</p> +<p>The same holds for <a class="reference internal" href="#polevalreducedat">\PolEvalReduced</a> +and <a class="reference internal" href="#polfloatevalat">\PolFloatEval</a>.</p> +</li> +<li><p class="first">the <tt class="docutils literal">3.0</tt> automatic generation of floating point variants has +been reverted. Not only do <em>not</em> the package macros automatically +generate floating point variants of newly created polynomials, +they actually make pre-existing such variant undefined.</p> +<p>See <a class="reference internal" href="#polgenfloatvariant">\PolGenFloatVariant</a>.</p> +</li> +</ul> +</li> +<li><p class="first">new non-expandable macros:</p> +<ul class="simple"> +<li><a class="reference internal" href="#polgenfloatvariant">\PolGenFloatVariant</a></li> +<li><a class="reference internal" href="#polgloballet">\PolGlobalLet</a></li> +<li><a class="reference internal" href="#poltypesetone">\PolTypesetOne</a></li> +<li><a class="reference internal" href="#polquo">\PolQuo</a></li> +<li><a class="reference internal" href="#polrem">\PolRem</a></li> +<li><a class="reference internal" href="#poltosturm">\PolToSturm</a></li> +<li><a class="reference internal" href="#id9">\PolToSturm*</a></li> +<li><a class="reference internal" href="#polsettosturmchainsignchangesat">\PolSetToSturmChainSignChangesAt</a></li> +<li><a class="reference internal" href="#polsettonbofzeroswithin">\PolSetToNbOfZerosWithin</a></li> +<li><a class="reference internal" href="#polsturmisolatezeros">\PolSturmIsolateZeros</a></li> +<li><a class="reference internal" href="#polrefineinterval">\PolRefineInterval*</a></li> +<li><a class="reference internal" href="#polrefineinterval-n">\PolRefineInterval[N]</a></li> +<li><a class="reference internal" href="#polensureintervallength">\PolEnsureIntervalLength</a></li> +<li><a class="reference internal" href="#polensureintervallengths">\PolEnsureIntervalLengths</a></li> +<li><a class="reference internal" href="#polprintintervals">\PolPrintIntervals</a></li> +<li><a class="reference internal" href="#polprintintervalsprintexactzero">\PolPrintIntervalsPrintExactZero</a></li> +<li><a class="reference internal" href="#polprintintervalsprintleftendpoint">\PolPrintIntervalsPrintLeftEndPoint</a></li> +<li><a class="reference internal" href="#polprintintervalsprintrightendpoint">\PolPrintIntervalsPrintRightEndPoint</a></li> +<li><a class="reference internal" href="#id14">\PolReduceCoeffs*</a></li> +<li><a class="reference internal" href="#polmakemonic">\PolMakeMonic</a></li> +</ul> +</li> +<li><p class="first">new expandable macros:</p> +<ul class="simple"> +<li><a class="reference internal" href="#poltoexpronetermstylea">\PolToExprOneTermStyleA</a></li> +<li><a class="reference internal" href="#polifcoeffisplusorminusone">\PolIfCoeffIsPlusOrMinusOne</a></li> +<li><a class="reference internal" href="#polleadingcoeff">\PolLeadingCoeff</a></li> +<li><a class="reference internal" href="#polsturmchainlength">\PolSturmChainLength</a></li> +<li><a class="reference internal" href="#polsturmnbofisolatedzeros">\PolSturmNbOfIsolatedZeros</a></li> +<li><a class="reference internal" href="#polsturmifzeroexactlyknown">\PolSturmIfZeroExactlyKnown</a></li> +<li><a class="reference internal" href="#polsturmisolatedzeroleft">\PolSturmIsolatedZeroLeft</a></li> +<li><a class="reference internal" href="#polsturmisolatedzeroright">\PolSturmIsolatedZeroRight</a></li> +<li><a class="reference internal" href="#polprintintervalstheendpoint">\PolPrintIntervalsTheEndPoint</a></li> +<li><a class="reference internal" href="#polprintintervalstheindex">\PolPrintIntervalsTheIndex</a></li> +<li><a class="reference internal" href="#polifendpointispositive">\PolIfEndPointIsPositive</a></li> +<li><a class="reference internal" href="#polifendpointisnegative">\PolIfEndPointIsNegative</a></li> +<li><a class="reference internal" href="#polifendpointiszero">\PolIfEndPointIsZero</a></li> +<li><a class="reference internal" href="#polintervalwidth">\PolIntervalWidth</a></li> +<li><a class="reference internal" href="#poldectostring">\PolDecToString</a></li> +</ul> +</li> +<li><p class="first">improvements:</p> +<p>The main new feature is implementation of the <a class="reference external" href="https://en.wikipedia.org/wiki/Sturm%27s_theorem">Sturm algorithm</a> +for localization of the real roots of polynomials.</p> +</li> +</ul> +</li> </ul> -<p>See README.md for the License and the change log (there were -some breaking changes from 0.2 to 0.3).</p> </div> <div class="section" id="acknowledgments"> -<h1><a class="toc-backref" href="#id62">Acknowledgments</a></h1> +<h1><a class="toc-backref" href="#id126">Acknowledgments</a></h1> <p>Thanks to Jürgen Gilg whose question about <a class="reference external" href="http://www.ctan.org/pkg/xint">xint</a> 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.</p> +<p>Renewed thanks on occasion of <tt class="docutils literal">0.4</tt> release!</p> +<p>See README.md for the License.</p> </div> </div> </body> 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 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@<name>) %% 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}% |