diff options
Diffstat (limited to 'Master/texmf-dist/tex/latex')
-rw-r--r-- | Master/texmf-dist/tex/latex/polexpr/polexpr.sty | 472 |
1 files changed, 391 insertions, 81 deletions
diff --git a/Master/texmf-dist/tex/latex/polexpr/polexpr.sty b/Master/texmf-dist/tex/latex/polexpr/polexpr.sty index e5e2acd6922..f163fe10f29 100644 --- a/Master/texmf-dist/tex/latex/polexpr/polexpr.sty +++ b/Master/texmf-dist/tex/latex/polexpr/polexpr.sty @@ -1,13 +1,15 @@ % author: Jean-François Burnol % License: LPPL 1.3c (author-maintained) \ProvidesPackage{polexpr}% - [2018/04/22 v0.5.1 Polynomial expressions with rational coefficients (JFB)]% -\RequirePackage{xintexpr}[2018/03/01]% xint 1.3 + [2018/11/20 v0.6 Polynomial expressions with rational coefficients (JFB)]% +\RequirePackage{xintexpr}[2018/06/17]% xint 1.3c for \ifxintglobaldefs boolean \edef\POL@restorecatcodes {\catcode`\noexpand\_ \the\catcode`\_ % \catcode`\noexpand\! \the\catcode`\! % \catcode0 \the\catcode0\relax}% \catcode`\_ 11 \catcode0 12 +\long\def\xint_stop_atfirstoftwo #1#2{ #1}% not yet in xint 1.3c +\long\def\xint_stop_atsecondoftwo #1#2{ #2}% %% PATCH xintexpr TO AUTHORIZE ' IN NAMES (0.5.1) \catcode`\! 11 @@ -30,7 +32,7 @@ \newif\ifPOL@pol \newif\ifxintveryverbose \newif\ifpoltypesetall -\newif\ifPOL@sturm@normalize +\newif\ifPOL@sturm@declareunnormalized \newif\ifPOL@isolz@nextwillneedrefine \newif\ifpoltoexprall %% the main exchange structure (stored in macros \POLuserpol@<name>) @@ -362,7 +364,7 @@ \def\POL@mapcoeffs@macro{#1}% \expandafter\expandafter\expandafter\POL@split \csname POLuserpol@#2\endcsname;\POL@mapcoeffs@deg\POL@mapcoeffs@coeffs -% attention à ne pas faire un \expandafter ici, car brace removal si 1 item +% ATTENTION à ne pas faire un \expandafter ici, car brace removal si 1 item \xintAssignArray\POL@mapcoeffs@coeffs\to\POL@arrayA \def\index{0}% \count@\z@ @@ -686,58 +688,100 @@ %% Sturm Algorithm (polexpr 0.4) %% 0.5 uses primitive polynomials for faster evaluations afterwards -\newcommand\PolToSturm{% - \@ifstar{\POL@sturm@normalizefalse}{\POL@sturm@normalizetrue}% - \POL@ToSturm -}% -\def\POL@aux@toint#1{\xintREZ{\xintNum{#1}}}% +%% 0.6 corrects misuse of \@ifstar! (mumble). \PolToSturm* was broken. +%% 0.6's \PolToSturm* defines both normalized and unnormalized, the +%% unnormalized using two underscores, so both are available +%% Sole difference is that \PolToSturm* also declares them as +%% user polynomials, whereas the non-starred only keeps the macros +%% holding the coefficients in memory +%% 0.6 fixes the case of a constant polynomial P which caused division +%% by zero error from P'. +\newcommand\PolToSturm{\@ifstar + {\POL@sturm@declareunnormalizedtrue\POL@ToSturm}% + {\POL@sturm@declareunnormalizedfalse\POL@ToSturm}% +}% +\def\POL@aux@toint#1{\xintREZ{\xintNum{#1}}}% for polynomials with int. coeffs! \def\POL@ToSturm#1#2{% \edef\POL@sturmname{#2}% - \POL@let{\POL@sturmname _0}{#1}% - \PolMakePrimitive{\POL@sturmname _0}% - \POL@Diff@@one{\POL@sturmname _0}{\POL@sturmname _1}% + % 0.6 uses 2 underscores (one before index, one after) to keep in memory + % the unnormalized chain + \POL@let{\POL@sturmname _0_}{#1}% + \ifnum\PolDegree{#1}=\z@ + \def\POL@sturm@N{0}% + \POL@count\z@ + % if I applied the same as for positive degree, I should make it -1 + % if constant is negative. I also don't worry if polynomial is zero. + \@namedef{POLuserpol@\POL@sturmname _0}{0.\empty{1/1[0]}}% + \else + \POL@ToSturm@DoSturm + \fi + \expandafter + \let\csname PolSturmChainLength_\POL@sturmname\endcsname\POL@sturm@N + % declare the normalized ones as full-fledged polynomials + % \POL@count\z@ + \xintloop + \POL@newpol{\POL@sturmname _\the\POL@count}% + \unless\ifnum\POL@sturm@N=\POL@count + \advance\POL@count\@ne + \repeat + % optionally declare also the unnormalized ones + \POL@count\z@ + \ifPOL@sturm@declareunnormalized + \POL@count\z@ + \xintloop + \POL@newpol{\POL@sturmname _\the\POL@count _}% + \unless\ifnum\POL@sturm@N=\POL@count + \advance\POL@count\@ne + \repeat + \fi +}% +\def\POL@ToSturm@DoSturm{% + \PolMakePrimitive{\POL@sturmname _0_}% + \POL@Diff@@one{\POL@sturmname _0_}{\POL@sturmname _1_}% % re-utiliser \POL@varcoeffs directement? - \PolMakePrimitive{\POL@sturmname _1}% + \PolMakePrimitive{\POL@sturmname _1_}% \POL@count\@ne \xintloop - \POL@divide{\POL@sturmname _\the\numexpr\POL@count-\@ne}% - {\POL@sturmname _\the\POL@count}% + \POL@divide{\POL@sturmname _\the\numexpr\POL@count-\@ne\relax _}% + {\POL@sturmname _\the\POL@count _}% \expandafter\POL@split\POL@R;\POL@degR\POL@polR \unless\ifnum\POL@degR=\m@ne \advance\POL@count\@ne \expandafter\let - \csname POLuserpol@\POL@sturmname _\the\POL@count\endcsname\POL@R + \csname POLuserpol@\POL@sturmname _\the\POL@count _\endcsname\POL@R \edef\POL@makeprim@icontent{-\POL@icontent\POL@polR}% - \POL@mapcoeffs\POL@makeprim@macro{\POL@sturmname _\the\POL@count}% + \POL@mapcoeffs\POL@makeprim@macro{\POL@sturmname _\the\POL@count _}% \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\let - \csname POLuserpol@\POL@sturmname _\the\POL@count\endcsname\POL@Q - % quotient actually belongs to Z[X] - \POL@mapcoeffs{\POL@aux@toint}{\POL@sturmname _\the\POL@count}% - \ifnum\POL@count>\z@ - \repeat - \@namedef{POLuserpol@\POL@sturmname _\POL@sturm@N}{0.\empty{1/1[0]}}% - \fi + % normalize (now always done even by starred variant) + \ifnum\PolDegree{\POL@sturmname _\POL@sturm@N _}>\z@ + % \POL@count\POL@sturm@N\relax + \xintloop + \advance\POL@count\m@ne + \POL@divide{\POL@sturmname _\the\POL@count _}% + {\POL@sturmname _\POL@sturm@N _}% + \expandafter + \let\csname POLuserpol@\POL@sturmname _\the\POL@count\endcsname\POL@Q + % quotient actually belongs to Z[X] and is primitive + \POL@mapcoeffs{\POL@aux@toint}{\POL@sturmname _\the\POL@count}% + \ifnum\POL@count>\z@ + \repeat + \@namedef{POLuserpol@\POL@sturmname _\POL@sturm@N}{0.\empty{1/1[0]}}% + \else % they are already normalized + \advance\POL@count\@ne % attention to include last one also + \xintloop + \advance\POL@count\m@ne + \expandafter\let + \csname POLuserpol@\POL@sturmname _\the\POL@count\expandafter\endcsname + \csname POLuserpol@\POL@sturmname _\the\POL@count _\endcsname + \ifnum\POL@count>\z@ + \repeat \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 + % Back to \POL@ToSturm }% - \newcommand\PolSturmChainLength[1] {\romannumeral`^^@\csname PolSturmChainLength_#1\endcsname}% + \newcommand\PolSetToSturmChainSignChangesAt[4][\global]{% \edef\POL@sturmchain@X{\xintREZ{#4}}% \edef\POL@sturmname{#3}% @@ -747,19 +791,19 @@ }% \def\POL@sturmchain@getSV@at#1{% ATTENTION USES \POL@count \def\POL@sturmchain@SV{0}% - \edef\POL@sturmchain@sign{\xintiiSgn{\PolEval{\POL@sturmname _0}\At{#1}}}% + \edef\POL@sturmchain@sign{\xintiiSgn{\Pol@Eval{\POL@sturmname _0}{#1}}}% \let\POL@isolz@lastsign\POL@sturmchain@sign \POL@count \z@ \ifnum\POL@isolz@lastsign=\z@ \edef\POL@isolz@lastsign - {\xintiiSgn{\PolEval{\POL@sturmname _1}\At{#1}}}% + {\xintiiSgn{\Pol@Eval{\POL@sturmname _1}{#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}}}% + {\xintiiSgn{\Pol@Eval{\POL@sturmname _\the\POL@count}{#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 @@ -783,16 +827,129 @@ }% -\newcommand\PolSturmIsolateZeros[2][\empty]{% +\newcommand\PolSturmIsolateZeros{\@ifstar + {\PolSturmIsolateZerosAndGetMultiplicities}% + {\PolSturmIsolateZeros@}% +}% +\newcommand\PolSturmIsolateZerosAndGetMultiplicities[2][\empty]{% + % #1 optional E such that roots are searched in -10^E < x < 10^E + % both -10^E and +10^E must not be roots! + % #2 name of Sturm chain (already pre-computed) + \edef\POL@sturmname{#2}% + \edef\POL@sturm@N{\@nameuse{PolSturmChainLength_\POL@sturmname}}% + % isolate the roots (detects case of constant polynomial) + \PolSturmIsolateZeros@{\POL@sturmname}% + \ifnum\POL@isolz@NbOfRoots=\z@ + % no roots, define empty array nevertheless + \begingroup\globaldefs\@ne + \expandafter\xintAssignArray\expandafter\to\csname POL_ZeroMult\POL@sturmname\endcsname + \endgroup + \else + % store Sturm chain name for usage in the main loop + \let\POL@originalsturmname\POL@sturmname + \edef\POL@isolzmult@indices{\xintSeq{1}{\POL@isolz@NbOfRoots}}% + % all we currently know is that multiplicities are at least one + \begingroup\globaldefs\@ne + \expandafter\POL@initarray\csname POL_ZeroMult\POL@sturmname\endcsname{1}% + \endgroup + % check if GCD had positive degree (hence some roots, maybe complex, have + % multiplicity) + \ifnum\PolDegree{\POL@sturmname _\POL@sturm@N _}>\z@ + % scratch array of flags to signal known multiplicities + \POL@initarray\POL@IfMultIsKnown\xint_secondoftwo + \let\POL@isolz@NbOfRoots@with_unknown_mult\POL@isolz@NbOfRoots + \expandafter\expandafter\expandafter\POL@isolzmult@loop + \fi + \fi +}% +\def\POL@isolzmult@loop{% + % we are here only if last iteration gave a new PGCD still of degree > 0 + % As 0.6 \PolToSturm keeps memory of unnormalized Sturm chain, we use the + % PGCD from last iteration and generate a new Sturm chain. + % ATTENTION: first argument of \PolToSturm MUST NOT CONTAIN \POL@sturmname + \let\POL@@sturmname\POL@sturmname + % ATTENTION: we could use an underscore prefix to the name, but attention + % to tacit multiplication if used in an expression; however \PolEvalAt + % does not use expression parsing as \PolEvalAtExpr so this would be + % relatively safe. We must also not overwrite privately used names + % by polexpr or xint... Using prefix @_1 appears safe. They will accumulate. + % As the loop may break at any moment, depending on original P, not only + % on current polynomial which is examined to see if it has zeros, it does + % not seem to make sense to think about interface to keep memory of all + % the defined polynomials. + % \POL@sturm@N supposedly the one from last iteration + \PolToSturm{\POL@@sturmname _\POL@sturm@N _}{@_1\POL@@sturmname}% + % now both \POL@sturmname and \POL@sturm@N have changed + % if GCD is now a constant, we will not come back here + \edef\POL@sturmfinaldeg{\PolDegree{\POL@sturmname _\POL@sturm@N _}}% + \xintFor* ##1 in {\POL@isolzmult@indices}\do + {% + \csname POL@IfMultIsKnown##1\endcsname + {}% nothing to do + {\def\POL@isolzmult@index{##1}% + \POL@SturmIfZeroExactlyKnown{\POL@originalsturmname}{##1}% + \POL@isolzmult@loop@zero_isknown + \POL@isolzmult@loop@zero_isnotknown + \POL@isolzmult@loop@sharedbody + }% + }% + \ifnum\POL@sturmfinaldeg>\z@ + \expandafter\POL@isolzmult@loop + \fi +}% +\def\POL@isolzmult@loop@zero_isknown{% + \xintifZero + {\Pol@Eval{\POL@sturmname _0_}% + {\POL@xintexprGetVar{\POL@originalsturmname L_\POL@isolzmult@index}}}% + {\let\POL@isolzmult@haszero\@ne}% + {\let\POL@isolzmult@haszero\z@}% +}% +\def\POL@isolzmult@loop@zero_isnotknown{% + \edef\POL@isolzmult@loop@A + {\POL@xintexprGetVar{\POL@originalsturmname L_\POL@isolzmult@index}} + \edef\POL@isolzmult@loop@B + {\POL@xintexprGetVar{\POL@originalsturmname R_\POL@isolzmult@index}} + \PolSetToNbOfZerosWithin + \POL@isolzmult@haszero % nb of zeros A < x <= B, here 0 or 1 + \POL@sturmname + \POL@isolzmult@loop@A + \POL@isolzmult@loop@B +}% +\def\POL@isolzmult@loop@sharedbody{% + \ifnum\POL@isolzmult@haszero>\z@ + \expandafter + \xdef + \csname POL_ZeroMult\POL@originalsturmname\POL@isolzmult@index\endcsname + {\the\numexpr + \csname POL_ZeroMult\POL@originalsturmname + \POL@isolzmult@index\endcsname+\@ne}% + \else + % multiplicity now known, no need to check this index in future + \@namedef{POL@IfMultIsKnown\POL@isolzmult@index}{\xint_firstoftwo}% + \edef\POL@isolz@NbOfRoots@with_unknown_mult + {\the\numexpr\POL@isolz@NbOfRoots@with_unknown_mult-\@ne}% + \ifnum\POL@isolz@NbOfRoots@with_unknown_mult=\z@ + \def\POL@sturmfinaldeg{0}% flag to force termination + \expandafter\expandafter\expandafter\xintBreakFor + \fi + \fi +}% + + +\newcommand\PolSturmIsolateZeros@[2][\empty]{% % #1 optional E such that roots are searched in -10^E < x < 10^E % both -10^E and +10^E must not be roots! % #2 name of Sturm chain (already pre-computed from a given polynomial) + % For reasons I have forgotten (no time now) this code **must** be used + % with a *normalized* Sturm chain. \edef\POL@sturmname{#2}% \edef\POL@sturmlength{\PolSturmChainLength{#2}}% - \ifx\empty#1\relax + % attention to constant polynomial, we must redefine the arrays then + \ifnum\POL@sturmlength>\z@ + \ifx\empty#1\relax \POL@isolz@getsignchanges@plusinf \POL@isolz@getsignchanges@minusinf - \else + \else \edef\POL@isolz@E{\the\numexpr\xint_zapspaces #1 \xint_gobble_i\relax}% \POL@sturmchain@getSV@at{1[\POL@isolz@E]}% \let\POL@isolz@plusinf@SV \POL@sturmchain@SV @@ -810,26 +967,35 @@ {The polynomial #2 vanishes at set lower bound -10^\POL@isolz@E}% {Compile again with a bigger exponent in source. (X to abort).}% \fi - \fi - \edef\POL@isolz@NbOfRoots + \fi + \edef\POL@isolz@NbOfRoots {\the\numexpr\POL@isolz@minusinf@SV-\POL@isolz@plusinf@SV}% + \else + % constant polynomial + \def\POL@isolz@NbOfRoots{0}% + \fi \ifnum\POL@isolz@NbOfRoots=\z@ \begingroup\globaldefs\@ne \expandafter\xintAssignArray\expandafter\to\csname POL_ZeroInt#2L\endcsname \expandafter\xintAssignArray\expandafter\to\csname POL_ZeroInt#2R\endcsname + \expandafter\xintAssignArray\expandafter\to\csname POL_ZeroIsKnown#2\endcsname \endgroup \else \begingroup\globaldefs\@ne - \expandafter\POL@isolz@initarray\csname POL_ZeroInt#2L\endcsname - \expandafter\POL@isolz@initarray\csname POL_ZeroInt#2R\endcsname + \expandafter\POL@initarray\csname POL_ZeroInt#2L\endcsname{0}% + \expandafter\POL@initarray\csname POL_ZeroInt#2R\endcsname{0}% + \expandafter\POL@initarray\csname POL_ZeroIsKnown#2\endcsname + \xint_stop_atsecondoftwo \endgroup \ifx\empty#1\relax\expandafter\POL@isolz@getaprioribound\fi \expandafter\POL@isolz@main \fi }% -\def\POL@isolz@initarray#1{% - \expandafter\xintAssignArray - \romannumeral\xintreplicate{\POL@isolz@NbOfRoots}{{0}}\to#1% +\def\POL@initarray#1#2{% +% ATTENTION, if only one item, \xintAssignArray UNBRACES IT +% so we use an \empty trick to avoid that. Maybe considered a bug of xinttools? + \expandafter\xintAssignArray\expandafter\empty + \romannumeral\xintreplicate{\POL@isolz@NbOfRoots}{{#2}}\to#1% }% \def\POL@isolz@getsignchanges@plusinf{% % Count number of sign changes at plus infinity in Sturm sequence @@ -920,11 +1086,11 @@ \ifnum\POL@IsoAtZeroSign=\z@ \xdef\POL@isolz@IntervalIndex {\the\numexpr\POL@isolz@minusinf@SV-\POL@IsoRightSV}% - \POL@refine@storeleftandright % store zero root + \POL@refine@storeleftandright % store zero root, \POL@IsoRightSign is zero \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]}}}}% + {\xintiiOpp{\xintiiSgn{\Pol@Eval{\POL@sturmname _1}{0/1[0]}}}}% \fi \def\POL@IsoLeft@Int{-1}% -10^E isn't a root! \let\POL@IsoLeftSV \POL@isolz@minusinf@SV @@ -1054,6 +1220,7 @@ \ifPOL@isolz@nextwillneedrefine \expandafter\expandafter\expandafter\POL@isolz@refine \else + % \POL@IsoRightSign is zero iff root now exactly know \POL@refine@storeleftandright \ifnum\POL@IsoRightSign=\z@ \global\POL@isolz@nextwillneedrefinetrue @@ -1108,7 +1275,7 @@ \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}}}% + {\xintiiSgn{\Pol@Eval{\POL@sturmname _0}{\POL@IsoRight@raw}}}% \ifnum\POL@IsoRightSign=\POL@@IsoRightSign\space \repeat % now second root has been separated from the one at left end point @@ -1127,7 +1294,7 @@ \else \edef\POL@IsoRight@Int{\xintDec{\POL@@IsoRight@Int}}% \edef\POL@IsoRightSign - {\xintiiSgn{\PolEval{\POL@sturmname _0}\At{\POL@IsoRight@raw}}}% + {\xintiiSgn{\Pol@Eval{\POL@sturmname _0}{\POL@IsoRight@raw}}}% \ifnum\POL@IsoRightSign=\POL@@IsoRightSign\space \POL@refine@doonce % we need to locate in interval (1, 9) in local scale \else @@ -1152,17 +1319,17 @@ \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}}}% + {\xintiiSgn{\Pol@Eval{\POL@sturmname _0}{\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}}}% + {\xintiiSgn{\Pol@Eval{\POL@sturmname _0}{\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}}}% + {\xintiiSgn{\Pol@Eval{\POL@sturmname _0}{\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 @@ -1176,7 +1343,7 @@ \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}}}% + {\xintiiSgn{\Pol@Eval{\POL@sturmname _0}{\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 @@ -1191,12 +1358,12 @@ \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}}}% + {\xintiiSgn{\Pol@Eval{\POL@sturmname _0}{\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}}}% + {\xintiiSgn{\Pol@Eval{\POL@sturmname _0}{\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 @@ -1210,7 +1377,7 @@ \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}}}% + {\xintiiSgn{\Pol@Eval{\POL@sturmname _0}{\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 @@ -1228,12 +1395,19 @@ \xdef\csname POL_ZeroInt\POL@sturmname R\POL@isolz@IntervalIndex\endcsname {\PolDecToString{\POL@IsoRight@rawout}}% - \begingroup\globaldefs\@ne + \begingroup\xintglobaldefstrue \xintdefvar\POL@sturmname L_\POL@isolz@IntervalIndex:=qfrac(\POL@IsoLeft@rawout);% \xintdefvar\POL@sturmname R_\POL@isolz@IntervalIndex:=qfrac(\POL@IsoRight@rawout);% \endgroup + % added at 0.6+ + \ifnum\POL@IsoRightSign=\z@ + \global + \expandafter + \let\csname POL_ZeroIsKnown\POL@sturmname\POL@isolz@IntervalIndex\endcsname + \xint_stop_atfirstoftwo + \fi }% @@ -1269,7 +1443,7 @@ \def\POL@refine@sharedbody#1{% \POL@set@IsoLeft@rawin \edef\POL@IsoLeftSign - {\xintiiSgn{\PolEval{\POL@sturmname _0}\At{\POL@IsoLeft@rawin}}}% + {\xintiiSgn{\Pol@Eval{\POL@sturmname _0}{\POL@IsoLeft@rawin}}}% \ifnum\POL@IsoLeftSign=\z@ % do nothing if that interval was already a singleton \else @@ -1282,7 +1456,7 @@ \expandafter\POL@set@IsoLeft@Int\POL@IsoLeft@rawin \edef\POL@IsoRight@Int{\xintInc{\POL@IsoLeft@Int}}% #1% - \POL@refine@storeleftandright + \POL@refine@storeleftandright % \POL@IsoRightSign not zero \fi }% \def\POL@refine@loop#1{% @@ -1304,7 +1478,7 @@ \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}}}% + {\xintiiSgn{\Pol@Eval{\POL@sturmname _0}{\POL@IsoRight@raw}}}% \ifnum\POL@IsoRightSign=\z@ \let\POL@IsoLeft@Int\POL@IsoRight@Int % root at 1 \def\POL@IsoLeftSign{0}% @@ -1317,7 +1491,7 @@ \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}}}% + {\xintiiSgn{\Pol@Eval{\POL@sturmname _0}{\POL@IsoRight@raw}}}% \ifnum\POL@IsoRightSign=\z@ \let\POL@IsoLeft@Int\POL@IsoRight@Int % root at 9 \def\POL@IsoLeftSign{0}% @@ -1382,7 +1556,7 @@ \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}}}% + {\xintiiSgn{\Pol@Eval{\POL@sturmname _0}{\POL@IsoLeft@raw}}}% % at start left and right are not roots, and values of opposite signs % \edef\POL@IsoRightSign{\the\numexpr-\POL@IsoLeftSign}% \xintloop @@ -1390,7 +1564,7 @@ % 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 + % will check if right is at a zero, it needs \POL@IsoRightSign set up \POL@refine@storeleftandright \fi }% @@ -1402,7 +1576,7 @@ \xintloop \edef\POL@IsoRight@Int{\xintInc{\POL@IsoLeft@Int}}% \edef\POL@IsoRightSign - {\xintiiSgn{\PolEval{\POL@sturmname _0}\At{\POL@IsoRight@raw}}}% + {\xintiiSgn{\Pol@Eval{\POL@sturmname _0}{\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 @@ -1470,16 +1644,16 @@ \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\PolSturmIfZeroExactlyKnown[2]{% #1 = sturmname, #2=index + \romannumeral0\csname POL_ZeroIsKnown#1\endcsname{#2}% +}% +\newcommand\POL@SturmIfZeroExactlyKnown[2]{% #1 = sturmname, #2=index + \romannumeral0\csname POL_ZeroIsKnown#1\the\numexpr#2\relax\endcsname +}% +\newcommand\PolSturmIsolatedZeroMultiplicity[2]{% + \romannumeral`^^@\csname POL_ZeroMult#1\endcsname{#2}% }% \newcommand\PolSturmIsolatedZeroLeft[2]{% \romannumeral`^^@\csname POL_ZeroInt#1L\endcsname{#2}}% @@ -1856,6 +2030,8 @@ }% \newcommand\PolEvalAt[2] {\xintpraw{\csname XINT_expr_userfunc_#1\endcsname{#2}}}% +\newcommand\Pol@Eval[2] + {\csname XINT_expr_userfunc_#1\endcsname{#2}}% \newcommand\PolEvalAtExpr[2]{\xinttheexpr #1(#2)\relax}% % \newcommand\PolEvalReduced[3]{\romannumeral`^^@\Pol@Eval@fork @@ -1878,7 +2054,141 @@ \newcommand\PolFloatEvalAt[2] {\xintpfloat{\csname XINT_flexpr_userfunc_#1\endcsname{#2}}}% \newcommand\PolFloatEvalAtExpr[2]{\xintthefloatexpr #1(#2)\relax}% -% + + +\newcommand\PolSturmMultiplicity[3]{\romannumeral`^^@\Pol@Eval@fork + #2\PolSturmMultiplicityAt + \At\PolSturmMultiplicityAtExpr\krof {#1}{#3}% +}% +\newcommand\PolSturmMultiplicityAtExpr[2] + {\PolSturmMultiplicityAt{#1}{\xinttheexpr#2\relax}}% +\newcommand\PolSturmMultiplicityAt[2] + {\expandafter\POL@sturm@mult@at\romannumeral`^^@#2!{#1}}% +\def\POL@sturm@mult@at#1!#2% +{% + \xintifZero{\Pol@Eval{#2_0}{#1}}% + {\POL@sturm@mult@at@iloop 1!{#2}{#1}}% we have a zero + 0% not a zero +}% +\def\POL@sturm@mult@at@iloop #1!#2#3% +{% #1 = index, #2 = sturmname, #3 value + \PolSturmIfZeroExactlyKnown{#2}{#1}% + {\xintifEq{\POL@xintexprGetVar{#2L_#1}}{#3}% + {\PolSturmIsolatedZeroMultiplicity{#2}{#1}}% +% catcode of ! is 11 in polexpr.sty + {\expandafter\POL@sturm@mult@at@iloop\the\numexpr#1+\@ne !{#2}{#3}}% + }% + {\xintifLt{#3}{\POL@xintexprGetVar{#2R_#1}}% + {\PolSturmIsolatedZeroMultiplicity{#2}{#1}}% + {\expandafter\POL@sturm@mult@at@iloop\the\numexpr#1+\@ne !{#2}{#3}}% + }% +}% + + +\def\Pol@LessThanOrEqualTo@fork#1\LessThanOrEqualTo#2#3\krof{#2}% +\newcommand\PolSturmNbOfRootsOf[3]{\romannumeral`^^@\Pol@LessThanOrEqualTo@fork + #2\PolNbOfRootsLessThanOrEqualTo + \LessThanOrEqualTo\PolNbOfRootsLessThanOrEqualToExpr\krof {#1}{#3}% +}% +\newcommand\PolNbOfRootsLessThanOrEqualToExpr[2] + {\PolNbOfRootsLessThanOrEqualTo{#1}{\xinttheexpr#2\relax}}% +\newcommand\PolNbOfRootsLessThanOrEqualTo[1]{% + \ifnum\PolSturmNbOfIsolatedZeros{#1}=\z@ + \expandafter\xint_firstofthree\expandafter0% + \else + \expandafter\PolNbOfRootsLessThanOrEqualTo@% + \fi {#1}% +}% +\def\PolNbOfRootsLessThanOrEqualTo@ #1#2% +{% + \expandafter\POL@nbofrootsleq@prep\romannumeral`^^@#2!{#1}% +}% +\def\POL@nbofrootsleq@prep#1!#2% +{% + \expandafter\POL@nbofrootsleq@iloop\expandafter 1\expandafter !% + \romannumeral0\xintsgn{\Pol@Eval{#2_0}{#1}}!% + #1!{#2}% +}% +\def\POL@nbofrootsleq@iloop#1!#2!#3!#4% +{% #1 = index, #2 = sign of evaluation at value, #3 = value, #4 = sturmname + \xintifCmp{#3}{\POL@xintexprGetVar{#4L_#1}}% + {\POL@nbofrootsleq@return #1-\@ne !}% + {\POL@nbofrootsleq@return + \PolSturmIfZeroExactlyKnown{#4}{#1}{#1}{#1-\@ne}!% + }% + % in third branch we are sure that if root is exactly known + % the test \xintifLt will be negative + {\xintifLt{#3}{\POL@xintexprGetVar{#4R_#1}}% + {\POL@nbofrootsleq@return + #1\ifnum#2=\xintSgn{\Pol@Eval{#4_0}{\POL@xintexprGetVar{#4L_#1}}} + -\@ne\fi !% + }% + {\ifnum#1=\PolSturmNbOfIsolatedZeros{#4} + \expandafter\POL@nbofrootsleq@rightmost + \fi \expandafter\POL@nbofrootsleq@iloop \the\numexpr\@ne+% + }% + }% + #1!#2!#3!{#4}% +}% +\def\POL@nbofrootsleq@return #1!#2!#3!#4!#5{\the\numexpr #1\relax}% +\def\POL@nbofrootsleq@rightmost\expandafter\POL@nbofrootsleq@iloop + \the\numexpr\@ne+#1!#2!#3!#4{#1}% + + +\def\Pol@LessThanOrEqualTo@fork#1\LessThanOrEqualTo#2#3\krof{#2}% +\newcommand\PolSturmNbWithMultOfRootsOf[3] +{\the\numexpr0\Pol@LessThanOrEqualTo@fork + #2\PolNbWithMultOfRootsLessThanOrEqualTo + \LessThanOrEqualTo\PolNbWithMultOfRootsLessThanOrEqualToExpr\krof {#1}{#3}% +}% +\newcommand\PolNbWithMultOfRootsLessThanOrEqualToExpr[2] + {\PolNbWithMultOfRootsLessThanOrEqualTo{#1}{\xinttheexpr#2\relax}}% +\newcommand\PolNbWithMultOfRootsLessThanOrEqualTo[1]{% + \ifnum\PolSturmNbOfIsolatedZeros{#1}=\z@ + \expandafter\POL@nbwmofroots@noroots + \else + \expandafter\PolNbWithMultOfRootsLessThanOrEqualTo@% + \fi {#1}% +}% +\def\POL@nbwmofroots@noroots#1#2{\relax}% +\def\PolNbWithMultOfRootsLessThanOrEqualTo@ #1#2% +{% + \expandafter\POL@nbwmofrootsleq@prep\romannumeral`^^@#2!{#1}% +}% +\def\POL@nbwmofrootsleq@prep#1!#2% +{% + \expandafter\POL@nbwmofrootsleq@iloop\expandafter 1\expandafter !% + \romannumeral0\xintsgn{\Pol@Eval{#2_0}{#1}}!% + #1!{#2}% +}% +\def\POL@nbwmofrootsleq@iloop#1!#2!#3!#4% +{% #1 = index, #2 = sign of evaluation at value, #3 = value, #4 = sturmname + \xintifCmp{#3}{\POL@xintexprGetVar{#4L_#1}}% + {\POL@nbwmofrootsleq@return !}% + {\POL@nbwmofrootsleq@return + \PolSturmIfZeroExactlyKnown{#4}{#1}% + {+\PolSturmIsolatedZeroMultiplicity{#4}{#1}}{}!% + }% + % in third branch we are sure that if root is exactly known + % the test \xintifLt will be negative + {\xintifLt{#3}{\POL@xintexprGetVar{#4R_#1}}% + {\POL@nbwmofrootsleq@return + \unless + \ifnum#2=\xintSgn{\Pol@Eval{#4_0}{\POL@xintexprGetVar{#4L_#1}}} + +\PolSturmIsolatedZeroMultiplicity{#4}{#1}\fi !% + }% + {+\PolSturmIsolatedZeroMultiplicity{#4}{#1}% + \ifnum#1=\PolSturmNbOfIsolatedZeros{#4} + \expandafter\POL@nbwmofrootsleq@return\expandafter !% + \fi + \expandafter\POL@nbwmofrootsleq@iloop \the\numexpr\@ne+% + }% + }% + #1!#2!#3!{#4}% +}% +\def\POL@nbwmofrootsleq@return #1!#2!#3!#4!#5{#1\relax}% + + \newcommand\PolLeadingCoeff[1]{% \romannumeral`^^@\expandafter\expandafter\expandafter\xintlastitem \expandafter\expandafter\expandafter |