summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/latex/polexpr/polexpr.sty
diff options
context:
space:
mode:
authorKarl Berry <karl@freefriends.org>2018-11-21 21:59:41 +0000
committerKarl Berry <karl@freefriends.org>2018-11-21 21:59:41 +0000
commitd547ea6945251bd98a320b6132a7c639809c966c (patch)
tree20fbfac0eef6b88b7539a68ce561dadba4f33795 /Master/texmf-dist/tex/latex/polexpr/polexpr.sty
parent228e5563a08cef3526d4f4a9b744ce328d243797 (diff)
polexpr (21nov18)
git-svn-id: svn://tug.org/texlive/trunk@49213 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Master/texmf-dist/tex/latex/polexpr/polexpr.sty')
-rw-r--r--Master/texmf-dist/tex/latex/polexpr/polexpr.sty472
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