summaryrefslogtreecommitdiff
path: root/macros/generic/polexpr/polexpr-examples.tex
blob: 564c1912da5660c584b785777583081c18ff110e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
% -*- sentence-end-double-space: t -*-
\documentclass[a4paper,svgnames,dvipsnames,dvipdfmx]{article}
\usepackage{geometry}
\usepackage{shortvrb}
\usepackage{xcolor}
\usepackage{graphicx}
\usepackage{polexpr}
\usepackage{hyperref}
\usepackage{bookmark}
% \usepackage{amsmath}
\usepackage{framed}
\usepackage{newtxtext,newtxmath}
\title{\pkg{polexpr} root localization examples}
\author{Jean-François Burnol}
\date{To access the reference documentation:\\
% faut-il vraiment le ./ ?
      \texttt{texdoc} \href{run:./polexpr.html}{polexpr.html}}
%\usepackage{parskip}
\MakeShortVerb{\|}

% Note 25 juin 2021 et 8 janvier 2022 pour polexpr-examples.tex
%
% Ceci est extrait quasi verbatim de xint.dtx
%
% Le code est pour LaTeX, pas pour Plain TeX.
% Prévu pour latex+dvipdfmx, et j'ai supprimé ajouts spécifiques pour
% pdflatex/xetex/lualatex en ce qui concerne les couleurs et polices.
%
% Regarding latex+dvipdfmx, a document with many more usage
% of everbatim* could run into color stack overflow problems
% Refer to xint.dtx for how this problem is avoided there
% via direct usage of \special rather than \color in the
% \everbatimxprehook

% verbatim macros and environments
% ================================
%
% June 2013, then October 2014.
% -----------------------------
%
\makeatletter
\catcode`_ 11
% some of my verbatim environments do not make the space active (\lverb e.g.). Then
% \do@noligs must be modified, \char`#1 must be followed by a space token, else,
% the `#1 expansion will swallow one space.
\def\do@noligs #1{%
  \catcode`#1\active
  \begingroup
     \lccode`~`#1\relax
     \lowercase{%
  \endgroup\def~{\leavevmode\kern\z@\char`#1 }}%
}
% \lowast
% Pas forcément adapté à toutes les polices
\def\lowast{\raisebox{-.25\height}{*}}
\catcode`* 13
\def\makestarlowast {\let*\lowast\catcode`\*\active}%
\catcode`* 12


%--- straight quotes, added (finally...) Nov 2, 2014
%--- obsolete with use of newtxtt 1.05, late 2014
\begingroup\makeatletter
  \catcode`\'\active
  \catcode`\`\active
\@firstofone {\endgroup
  \def\makequotesstraight{% assumes textcomp package
% à propos textcomp est automatique avec pdflatex depuis Février 2020
     \let`\textasciigrave
     \let'\textquotesingle
     \catcode39\active
     \catcode96\active }%
}

% \verb
% =====
% Initially, June 2013, then Sep 9, 2014, and Oct 9-12 2014
%
% pour les short verb |...|

\def\MicroFont{\ttfamily\makestarlowast\makequotesstraight}% default
\def\verb
{%
  \relax \ifmmode\else\leavevmode\null\fi
  \bgroup
  \let\do\@makeother \dospecials
  \@ifstar{\@sverb}% unused
          {\MicroFont
           \catcode 32 10 \endlinechar 32 % allows to fetch across line breaks
           \frenchspacing
           \@@jfverb}%
}%
% Note (Oct 12, 2014): in the improbable situation a newlinechar is
% found in the ##1, \scantokens will convert this to an end of line in
% its "write" phase, which will be then ignored in its "read" phase due
% to \endlinechar-1. This also avoids possible creation of \par which
% would defeat \@@jfverb@@. Thus it is good.
\def\@@jfverb #1{%
   \ifcat\noexpand#1\noexpand~\catcode`#1\active\fi
% No problem with the EOL for the line where the short verb delimiter stands.
   \def\next ##1#1{%
            \@vobeyspaces\everyeof{\relax}\endlinechar\m@ne
            \expandafter\@@jfverb_a\scantokens\expandafter{##1}}%
% hack with \@empty to prevent brace stripping if catcodes have been
% frozen earlier, like in footnotes.
   \next \@empty
}
% We don't want a \discretionary at the very start.
% But then an empty argument is forbidden!
\def\@@jfverb_a #1{#1\@@jfverb_b }

\def\@@jfverb_b #1{\ifx\relax #1%
        \egroup
      \else
% \penalty\z@, or rather (Oct 11, 2014) but I then adjust the textwidth
% precisely:
      \discretionary{\copy\SoftWrapIcon}{}{}%
        #1\expandafter\@@jfverb_b\fi
}
% \SoftWrapIcon box for line-breaking using discretionaries
% =========================================================
\DeclareFontFamily{U}{MdSymbolC}{}
\DeclareFontShape {U}{MdSymbolC}{m}{n}{<-> MdSymbolC-Regular}{}
\newbox\SoftWrapIcon
% Emacs/AUCTeX uses very strange comment-like highlighting for \usefont{U}...
\def\SetSoftWrapIcon{%
    \global\setbox\SoftWrapIcon\hb@xt@\z@
    {\hb@xt@\fontdimen2\font
        {\hss{\color{verbsoftwrapiconcolor}%
              \usefont{U}{MdSymbolC}{m}{n}\char"97}\hss}%
     \hss}%
   }
\AtBeginDocument {{\ttfamily\SetSoftWrapIcon}}%

\catcode`_ 8
\makeatother

% everbatim environment
% =====================

% October 13-14, 2014
% Verbatim with an \everypar hook, mainly to have background color, followed by
% execution of the contents (not limited by a group-scope)

\makeatletter
\catcode`_ 11

\def\everbatim {\s@everbatim\@everbatim }
%! ancienne méthode sans doute motivé par possibilité code ferme un groupe?
%! \@namedef{everbatim*}{\s@everbatim\@everbatimx\expandafter
%!                       {\the\newlinechar}}
\@namedef{everbatim*}{\s@everbatim\@everbatimx }

% Note 25 juin 2021
% On ne peut pas emboîter un everbatim à l'intérieur d'un everbatim
% ou un everbatim* à l'intérieur d'un everbatim*...
\def\s@everbatim {%
%     \ineverbtrue
     \everbatimtop % put there size changes
       \topsep    \z@skip
       \partopsep \z@skip
       \itemsep   \z@skip
       \parsep    \z@skip
       \parskip   \z@skip
       \lineskip  \z@skip
     \let\do\@makeother \dospecials
     \let\do\do@noligs  \verbatim@nolig@list
     \makestarlowast
     \makequotesstraight
     \everbatimhook
     \trivlist
       \@topsepadd \z@skip
       \item\relax
       \leftskip   \@totalleftmargin
       \rightskip  \z@skip
       \parindent  \z@
       \parfillskip\@flushglue
       \parskip    \z@skip
       \@@par
       \def\par{\leavevmode\null\@@par\pagebreak[1]}%
       \everypar\expandafter{\the\everypar \unpenalty
                \everbatimeverypar
                \everypar \expandafter{\the\everypar\everbatimeverypar}%
       }%
       \obeylines \@vobeyspaces
}
\def\everbatimtop {\MacroFont\small}% default
\let\everbatimhook\empty
\def\everbatimeverypar{\strut
                   {\everbatimbgcolorcmd\vrule\@width\linewidth }%
                   \kern-\linewidth
                   \kern\everbatimindent }
\let\everbatimbgcolorcmd\empty
\def\everbatimindent {\z@}

\begingroup
\lccode`X 13
\catcode`X \active
\lccode`Y `* % this is because of \makestarlowast.
% I have to think whether this is useful: obviously if I were to provide
% everbatim and everbatim*  in a package I wouldn't do that.
\catcode`Y  \active
\catcode`| 0 \catcode`[ 1 \catcode`] 2 \catcode`* 12
\catcode`{ 12 \catcode`} 12 |catcode`\\ 12
|lowercase[|endgroup% both freezes catcodes and converts X to active ^^M
|def|@everbatim #1X#2\end{everbatim}%
  [#2|end[everbatim]|everbatimbottom ]
|def|@everbatimx #1X#2\end{everbatimY}]%
  {#2\end{everbatim*}%
% refactored 2022/01/11, rather than passing \newlinechar value
% as was done formerly via everbatim* (see above) and fetching it here as #1  
% it is thus assumed executed contents will not terminate a scope
     \edef\everbatimrestorenewlinechar{\newlinechar\the\newlinechar\relax}%
     \newlinechar 13
% refactored 2022/01/11:
% attention, \parskip set to zero for execution of contents
% reason: avoid extra space if everbatim* is in an \item of a list
% between verbatim and output of execution, if it starts a paragraph
% \vskip-\parskip would be no good in case contents create a display
     \edef\everbatimrestoreparskip{\parskip\the\parskip}%
     \parskip\z@skip
% execution as LaTeX code of contents
     \everbatimxprehook
     \scantokens {#2}%
     \everbatimrestorenewlinechar
     \everbatimrestoreparskip
     \everbatimxposthook
}%
% L'espace venant du endofline final mis par \scantokens sera inhibé si #3 se
% termine par un % ou un \x, etc...

\let\everbatimbottom\empty

\def\endeverbatim  {\if@newlist \leavevmode\fi\endtrivlist }
\@namedef{endeverbatim*}{\endeverbatim}
% \@namedef{endeverbatim*}{\endeverbatim\aftergroup\everbatimundoparskip}
% \def\everbatimundoparskip{\vbox{}\kern-\baselineskip\kern-\parskip}
% \let\everbatimundoparskip\empty

% rationale: we do not want a group
% see xint.dtx for better way avoiding colorstack overflow problem
% with latex+dvipdfmx
\def\everbatimxprehook {\colorlet{everbsavedcolor}{.}%
                        \everbatimxfgcolorcmd}%
\let\everbatimxfgcolorcmd\empty % default
                       
\def\everbatimxposthook {\color{everbsavedcolor}}

\catcode`_ 8
\makeatother

\newcommand\pkg[2][]{\if\relax\detokenize{#1}\relax
                       \href{https://www.ctan.org/pkg/#2}{#2}%
                     \else
                       \href{https://www.ctan.org/pkg/#1}{#2}%
                     \fi
                    }

% Colors for \verb and everbatim
% \MacroFont and \MicroFont
% font size in verbatim blocks

% \verb
%\colorlet{verbcolor}{DarkCyan}
\colorlet{verbcolor}{Maroon}
\colorlet{verbsoftwrapiconcolor}{DarkBlue}
\def\MicroFont{\ttfamily\color{verbcolor}
               \makestarlowast\makequotesstraight}%

% everbatim/everbatim*
\def\everbatimtop{\MacroFont\small}
% the \small is not in \MacroFont in case of a document with macrocode (doc.sty)
% and some customization is desired
%\colorlet{everbatimfgcolor}{Olive}
\colorlet{everbatimfgcolor}{DarkBlue}
\def\MacroFont{\ttfamily\color{everbatimfgcolor}}

%\colorlet{everbatimbgcolor}{WhiteSmoke}
%\colorlet{everbatimbgcolor}{Ivory}
\colorlet{everbatimbgcolor}{Beige}
\def\everbatimbgcolorcmd{\color{everbatimbgcolor}}

%\colorlet{everbatimxfgcolor}{MidnightBlue}
%\colorlet{everbatimxfgcolor}{OliveDrab}
\colorlet{everbatimxfgcolor}{Maroon}
\def\everbatimxfgcolorcmd{\color{everbatimxfgcolor}}

% Notice that \macrocode uses \macro@font which stores the \MacroFont meaning
% in force at \begin{document}. But doc.sty's verbatim uses current \MacroFont
% not the meaning at \begin{document}. Comprenne qui pourra...

\begin{document}
\maketitle


The package provides a parser |\poldef| of algebraic polynomial
expressions.

Once defined, a polynomial is usable by its name either as a numerical
function in |\xintexpr/\xinteval|, or for additional polynomial
definitions, or as argument to the package macros.

%   The localization of
% real roots to arbitrary precision as well as the determination of all
% rational roots is implemented via such macros.

% Since release |0.8|, polexpr extends the \pkg{xintexpr}
% syntax to recognize
% polynomials as a new variable type (and not only as functions).
% Functionality which previously was implemented via macros such as the
% computation of a greatest common divisor is now available directly in
% |\xintexpr|, |\xinteval| or |\poldef| via infix or functional
% syntax.

This document illustrates root localization via usage of macros such as
|\PolToSturm| and |\PolSturmIsolateZeros| which implement the
\href{https://en.wikipedia.org/wiki/Sturm%27s_theorem}{Sturm theorem}:
\begin{itemize}
\item Root localization based on
  \href{https://en.wikipedia.org/wiki/Sturm%27s_theorem}{Sturm theorem} was
  added at release |0.4| (2018/02/16).
\item Ability to find all rational roots was added at release |0.7.2|
  (2018/12/09).
\end{itemize}
As of |0.8| (2021/03/29), \pkg{polexpr} is usable with Plain \TeX\ and not
only with \LaTeX. The examples here use most of the time a syntax which works
with both.

Copying-pasting from |pdf| the example source may lose formatting.
Formerly, they were included verbatim in the |html| documentation.  Here
they are both rendered verbatim and got executed during the \LaTeX\ run
which created this |pdf| file, with the output shown after the source code.

% Perhaps future releases will implement other approaches, which are known
% to be generically computationally more efficient, at least in high
% degrees, than the \href{https://en.wikipedia.org/wiki/Sturm%27s_theorem}{Sturm theorem} based approach.  This is not
% immediate priority though (perhaps support of multivariate polynomials
% would be more important feature; or localization of complex roots).

Regarding how polynomial coefficients are printed on the typeset page by
|\PolTypeset|:
\begin{itemize}\def\everbatimtop {\MacroFont}% sans le \small
\item The default for |\PolTypesetOne| is to use |\xintTeXsignedFrac| with
  \LaTeX, |\xintTeXsignedOver| with Plain.  See the \pkg{xintexpr}
  documentation for a description of what these macros do.  A sensible
  definition is: 
\begin{everbatim}
  \def\PolTypesetOne#1{\PolDecToString{\xintREZ{#1}}}%
\end{everbatim}
% le \smallskip est ennuyeux ici
  It means to use decimal notation, with perhaps a trailing denominator if the
  argument is a fraction, and will suppress trailing zeros after the decimal
  mark.

\item
  As these are expandable macros, they are usable to redefine
  |\PolToExprCmd| as well:
\begin{everbatim}
  \def\PolToExprCmd#1{\PolDecToString{\xintREZ{#1}}}%
\end{everbatim}
% le \smallskip est ennuyeux ici
  This will customize the output of |\PolToExpr| (which a priori is
  destined for writes to external files but may also be used on the typeset
  page).
\end{itemize}

With |\xintverbosetrue| in the \TeX\ source extra information relative
to the internal data manipulated by the macros will be written to the |.log|
file.

\begin{framed}
  Package macros related to root localization create (user-level) new
  polynomials, or numeric variables, via a naming scheme using the given
  |<sturmname>| as prefix. It is thus advisable to keep this
  |<sturmname>| name-space separate from the one used to name polynomial or
  scalar variables.
\end{framed}

\begin{framed}
  Regrettably all examples here use the condemnable |\PolToSturm{f}{f}|
  practice which means that internally defined polynomials will use as prefix
  the original polynomial name.  This merge of namespaces may cause
  overwriting previously defined data and may lead to hard-to-debug problems.
\end{framed}


\section{A first example}

In this example the polynomial is square-free.
\begin{everbatim*}
  \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}
\end{everbatim*}

\begin{everbatim*}
  Here is the second root with ten more decimal digits:
  \PolRefineInterval[10]{f}{2}
  $$\PolSturmIsolatedZeroLeft{f}{2}<Z_2<\PolSturmIsolatedZeroRight{f}{2}$$
\end{everbatim*}

\begin{everbatim*}
  And here is the first root with twenty digits after decimal mark:
  \PolEnsureIntervalLength{f}{1}{-20}
  $$\PolSturmIsolatedZeroLeft{f}{1}<Z_1<\PolSturmIsolatedZeroRight{f}{1}$$
\end{everbatim*}

\begin{everbatim*}
  The first element of the Sturm chain has degree $\PolDegree{f_0}$. As
  this is the original degreee $\PolDegree{f}$ we know that $f$ is square free.
  Its derivative is up to a constant \PolTypeset{f_1} (in this example
  it is identical with it).
  \PolToSturm{f_1}{f_1}\PolSturmIsolateZeros{f_1}%
  The derivative 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}
\end{everbatim*}

\begin{everbatim*}
  \PolDiff{f_1}{f''}
  \PolToSturm{f''}{f''}
  \PolSturmIsolateZeros{f''}
  The second derivative is \PolTypeset{f''}.
  It has \PolSturmNbOfIsolatedZeros{f''} distinct real
  roots:
  \PolPrintIntervals[X]{f''}%
  Here is the positive one with 20 digits after decimal mark:
  \PolEnsureIntervalLength{f''}{2}{-20}%
  $$X_2 = \PolSturmIsolatedZeroLeft{f''}{2}\dots$$
\end{everbatim*}
%The more mathematically advanced among our dear readers will be able
%  to give the exact value for $X_2$!

\section{A degree four polynomial with nearby roots}


Notice that this example is a bit outdated as |0.7| release has
added |\PolSturmIsolateZeros**{<sturmname>}| which would find exactly
the roots. The steps here retain their interest when one is interested
in finding isolating intervals for example to prepare some demonstration
of dichotomy method.


\begin{everbatim*}
  \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}
\end{everbatim*}

\begin{everbatim*}
  \PolRefineInterval*{Q}{1}
  \PolRefineInterval*{Q}{2}
  \PolRefineInterval*{Q}{3}
  \PolRefineInterval*{Q}{4}
  \PolPrintIntervals{Q}
\end{everbatim*}

\begin{everbatim*}
  \PolEnsureIntervalLengths{Q}{-6}
  \PolPrintIntervals{Q}
  % finds here all roots exactly
\end{everbatim*}

\section{The degree nine polynomial with 0.99, 0.999, 0.9999 as triple roots}

Define a user command (\pkg[xint]{xinttools} is loaded automatically by
\pkg{polexpr}):

\begin{everbatim*}
  \def\showmultiplicities#1{% #1 = "sturmname"
  \xintFor* ##1 in {\xintSeq{1}{\PolSturmNbOfIsolatedZeros{#1}}}\do{%
      The multiplicity is \PolSturmIsolatedZeroMultiplicity{#1}{##1}
      \PolSturmIfZeroExactlyKnown{#1}{##1}%
      {at the root $x=\PolSturmIsolatedZeroLeft{#1}{##1}$}
      {for the root such that
      $\PolSturmIsolatedZeroLeft{#1}{##1}<x<\PolSturmIsolatedZeroRight{#1}{##1}$}
      \par
  }}%
\end{everbatim*}

\begin{everbatim*}
  \PolDef{f}{(x-0.99)^3(x-0.999)^3(x-0.9999)^3}
  \def\PolTypesetOne#1{\PolDecToString{\xintREZ{#1}}}
  \PolTypeset{f}\par
\end{everbatim*}

\begin{everbatim*}
  \PolToSturm{f}{f}% it is allowed to use "polname" as "sturmname" too
  \PolSturmIsolateZerosAndGetMultiplicities{f}% use the "sturmname" here
  % or \PolSturmIsolateZeros*{f} which is exactly the same, but shorter..

  \showmultiplicities{f}
\end{everbatim*}
% In this example, the output will look like this (but using math mode)::

%   x^9 - 8.9667x^8 + 35.73400293x^7 - 83.070418400109x^6 + 124.143648875193123x^5
%   - 123.683070924326075877x^4 + 82.149260397553075617891x^3 
%   - 35.07602992699900159127007x^2 + 8.7364078733314648368671733x
%   - 0.967100824643585986488103299

%   The multiplicity is 3 at the root x = 0.99
%   The multiplicity is 3 at the root x = 0.999
%   The multiplicity is 3 at the root x = 0.9999

% On first pass, these rational roots were found (due to their relative
% magnitudes, using |\PolSturmIsolateZeros**| was not needed here). But
% multiplicity computation works also with (decimal) roots not yet
% identified or with non-decimal or irrational roots.

It is fun to modify only a tiny bit the polynomial and see if polexpr
survives:

\begin{everbatim*}
  \PolDef{g}{f(x)+1e-27}
  \PolTypeset{g}\par
  \PolToSturm{g}{g}
  \PolSturmIsolateZeros*{g}

  \showmultiplicities{g}
\end{everbatim*}
% This produces::

%   x^9 - 8.9667x^8 + 35.73400293x^7 - 83.070418400109x^6 + 124.143648875193123x^5
%   - 123.683070924326075877x^4 + 82.149260397553075617891x^3 
%   - 35.07602992699900159127007x^2 + 8.7364078733314648368671733x
%   - 0.967100824643585986488103298

%   The multiplicity is 1 for the root such that 0.98 < x < 0.99
%   The multiplicity is 1 for the root such that 0.9991 < x < 0.9992
%   The multiplicity is 1 for the root such that 0.9997 < x < 0.9998

This means that the multiplicity-3 roots each became a real and a pair of
complex ones. Let's see them better:

\begin{everbatim*}
  \PolEnsureIntervalLengths{g}{-10}

  \showmultiplicities{g}
\end{everbatim*}
% which produces::

%   The multiplicity is 1 for the root such that 0.9899888032 < x < 0.9899888033
%   The multiplicity is 1 for the root such that 0.9991447980 < x < 0.9991447981
%   The multiplicity is 1 for the root such that 0.9997663986 < x < 0.9997663987

\section{A degree five polynomial with three rational roots}

\begin{everbatim*}
  \poldef Q(x) :=  1581755751184441 x^5
                 -14907697165025339 x^4
                 +48415668972339336 x^3
                 -63952057791306264 x^2
                 +46833913221154895 x
                 -49044360626280925;

  \PolToSturm{Q}{Q}
    \def\PolTypesetCmdPrefix#1{\allowbreak\xintiiifSgn{#1}{}{+}{+}}%
    $Q_0(x) = \PolTypeset{Q_0}$
  \PolSturmIsolateZeros**{Q}
  \PolPrintIntervals{Q}

  $Q_{norr}(x) = \PolTypeset{Q_norr}$
\end{everbatim*}

Here, all real roots are rational. Let's get their decimal expansion too:
\begin{everbatim*}
\begingroup
  % print decimal expansion of the found roots
  \def\PolPrintIntervalsPrintExactZero
              {\xintTrunc{20}{\PolPrintIntervalsTheLeftEndPoint}\dots}
  \PolPrintIntervals{Q}
\endgroup % we localized the modified \PolPrintIntervalsPrintExactZero
\end{everbatim*}


  % Z_1 = 3.14159265358107777120...
  % Z_2 = 3.14159265358979340254...
  % Z_3 = 3.14159292035398230088...

\section{A Mignotte type polynomial}


\begin{everbatim*}
  \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
  This polynomial has \PolSturmNbOfIsolatedZeros{P} distinct real roots:
  \PolPrintIntervals{P}%
\end{everbatim*}
Let us refine the second and third intervals to separate the corresponding
roots:
\begin{everbatim*}
  \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}%
\end{everbatim*}
Let us now get to know all roots with 10 digits after decimal mark:
\begin{everbatim*}
  \PolEnsureIntervalLengths{P}{-10}%
  \PolPrintIntervals{P}% now all roots are known 10 decimal digits after mark
\end{everbatim*}
Finally, we display 20 digits of the second root:
\begin{everbatim*}
  \PolEnsureIntervalLength{P}{2}{-20}% makes Z_2 known with 20 digits after mark
  $$\PolSturmIsolatedZeroLeft{P}{2}<Z_2<\PolSturmIsolatedZeroRight{P}{2}$$
\end{everbatim*}
% The last line produces::

%   0.09999900004999650028 < Z_2 < 0.09999900004999650029

\section{The Wilkinson polynomial}


See \url{https://en.wikipedia.org/wiki/Wilkinson%27s_polynomial}.


\begin{everbatim*}
  %\xintverbosetrue % for the curious...

  \poldef f(x) := mul((x - i), i = 1..20);

  \def\PolTypesetCmdPrefix#1{\allowbreak\xintiiifSgn{#1}{}{+}{+}}%
  \def\PolTypesetOne#1{\xintDecToString{#1}}%

  \noindent\PolTypeset{f}

  \PolToSturm{f}{f}
  \PolSturmIsolateZeros{f}
  \PolPrintIntervals{f}
  % \vfill\eject

  % This page is commented out because it takes about 30s on a 2GHz CPU
  % \poldef g(x) := f(x) - 2**{-23} x**19;

  % \PolToSturm{g}{g}
  % \noindent\PolTypeset{g_0}% integer coefficient primitive polynomial

  % \PolSturmIsolateZeros{g}
  % \PolEnsureIntervalLengths{g}{-10}

  % \PolPrintIntervals*{g}
\end{everbatim*}

The first polynomial
%
%   f(x) = x**20
%   - 210 x**19
%   + 20615 x**18
%   - 1256850 x**17
%   + 53327946 x**16
%   - 1672280820 x**15
%   + 40171771630 x**14
%   - 756111184500 x**13
%   + 11310276995381 x**12
%   - 135585182899530 x**11
%   + 1307535010540395 x**10
%   - 10142299865511450 x**9
%   + 63030812099294896 x**8
%   - 311333643161390640 x**7
%   + 1206647803780373360 x**6
%   - 3599979517947607200 x**5
%   + 8037811822645051776 x**4
%   - 12870931245150988800 x**3
%   + 13803759753640704000 x**2
%   - 8752948036761600000 x
%   + 2432902008176640000
%
is handled fast enough, but the modified one |f(x) -
2**-23 x**19| takes about 20x longer.

Its Sturm chain polynomials
have integer coefficients with up to 321 digits, whereas (surprisingly
perhaps) those of the Sturm chain polynomials derived from |f| never
have more than 21 digits ...

Once the Sturm chain is computed and the zeros isolated, obtaining their
decimal digits is relatively faster. Here are the ten real roots of
|f(x) - 2**-23 x**19| which would be computed by the commented-out code above:
\begin{everbatim}
  Z_1 = 0.9999999999...
  Z_2 = 2.0000000000...
  Z_3 = 2.9999999999...
  Z_4 = 4.0000000002...
  Z_5 = 4.9999999275...
  Z_6 = 6.0000069439...
  Z_7 = 6.9996972339...
  Z_8 = 8.0072676034...
  Z_9 = 8.9172502485...
  Z_10 = 20.8469081014...
\end{everbatim}

\section{The second Wilkinson polynomial}


\begin{everbatim*}
  \poldef f(x) := mul(x - 2^-i, i = 1..20);

  %\PolTypeset{f}

  \PolToSturm{f}{f}
  \PolSturmIsolateZeros**{f}
  \PolPrintIntervals{f}
\end{everbatim*}

This takes more time than the polynomial with 1, 2, .., 20 as roots but
less than the latter modified by the |2**-23| tiny change to one of its
coefficient.

% Here is the output (with release 0.7.2)::

%   Z_1  = 0.00000095367431640625
%   Z_2  = 0.0000019073486328125
%   Z_3  = 0.000003814697265625
%   Z_4  = 0.00000762939453125
%   Z_5  = 0.0000152587890625
%   Z_6  = 0.000030517578125
%   Z_7  = 0.00006103515625
%   Z_8  = 0.0001220703125
%   Z_9  = 1/4096
%   Z_10 = 1/2048
%   Z_11 = 1/1024
%   Z_12 = 1/512
%   Z_13 = 1/256
%   Z_14 = 1/128
%   Z_15 = 0.015625
%   Z_16 = 0.03125
%   Z_17 = 0.0625
%   Z_18 = 0.125
%   Z_19 = 0.25
%   Z_20 = 0.5

There is some incoherence in output format which has its source in the
fact that some roots are found in branches which can only find decimal
roots, whereas some are found in branches which could find general
fractions and they use |\xintIrr| before storage of the found root.
This may evolve in future.


\section{The degree 41 polynomial with -2, -1.9, -1.8, ..., 0, 0.1, ..., 1.9, 2 as roots}



\begin{everbatim*}
  \PolDef{P}{mul((x-i*1e-1), i=-20..20)}% i/10 is same but less efficient
\end{everbatim*}
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).

\begin{everbatim*}
\begingroup
  \def\PolToExprCmd#1{\PolDecToString{\xintREZ{#1}}}
  \def\PolToExprTermPrefix#1{\newline\xintiiifSgn{#1}{}{+}{+}}
  \def\PolToExprTimes{${}\cdot{}$}
\ttfamily
\PolToExpr{P}
\endgroup
\end{everbatim*}
  % 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 \pkg{xint} + \pkg{polexpr}, but be a bit
patient!

\begin{everbatim*}
  \PolDef{P}{mul((x-i*1e-1), i=-20..20)}%
  \PolToSturm{P}{S}           % dutifully computes S_0, ..., S_{41}
  % the [1] optional argument limits the search to interval (-10,10)
  \PolSturmIsolateZeros[1]{S} % finds *exactly* (but a bit slowly) all 41 roots!
  \PolPrintIntervals{S}       % nice, isn't it?
% Unfortunately \PolPrintIntervals uses a non-breakable array environment
% But see next section on how to customize \PolPrintIntervals and let it
% allow pagebreaks
\end{everbatim*}

\begin{quote}
  Release |0.5| has \emph{experimental} addition of optional argument |E| to
  |\PolSturmIsolateZeros|. It instructs to search roots only in interval
  |(-10^E, 10^E)|. Important: the extremities are \emph{assumed to not be roots}.
  In this example, the |[1]| in |\PolSturmIsolateZeros[1]{S}| gives some speed
  gain; without it, it turns out in this case that \pkg{polexpr} would have
  started with |(-10^6, 10^6)| interval.

  Please note that this feature may be removed or modified.
\end{quote}

\section{Roots of a Chebyshev polynomial}


\begin{everbatim*}
  \poldef T_0(x) := 1;
  \poldef T_1(x) := x;
  \catcode`@ 11
  \count@ 2
  \xintloop
    \poldef T_\the\count@(x) :=
            2x*T_\the\numexpr\count@-1\relax
             - T_\the\numexpr\count@-2\relax;
  \ifnum\count@<15
  \advance\count@ 1
  \repeat
  \catcode`@ 12

  $$T_{15} = \PolTypeset[X]{T_15}$$
  \PolToSturm{T_15}{T_15}
  \PolSturmIsolateZeros*{T_15}% "*" as we will want to confirm multiplicity one
  % takes time (each next decimal digit is obtained by dichotomy)
  \PolEnsureIntervalLengths{T_15}{-20}% ensure 20 decimal digits for each root
\end{everbatim*}

Here is now an example of customization.  Indeed
|\PolPrintIntervals| default uses |array| and thus does not allow page breaks.
And it uses |Left < Z < Right| as presentation of roots and we would like here
rather |Z = decimal expansion...|.
\begin{everbatim*}
% 0.8.6 adds an internal patch which would allow usage of amsmath environments
% like this:
% \def\PolPrintIntervalsBeginEnv{\begin{align*}}
% \def\PolPrintIntervalsEndEnv{\end{align*}}
% (the problem was that align evaluates twice its contents so global variables
%  need a reset at the end of first pass, which is what 0.8.6 took care of)
%
% Let's simply do this:
\def\PolPrintIntervalsBeginEnv{\begingroup\leftskip3cm\relax}
\def\PolPrintIntervalsEndEnv{\par\endgroup}
%
% The rows are separated by \PolPrintIntervalsRowSeparator which defaults to \\
% with LaTeX and \cr with Plain. (prior to 0.8.6 it was hardcoded)
\def\PolPrintIntervalsRowSeparator{\\[\jot]}
% And we enter math mode manually at each row, copying pasting from package
% defaults with some added mathon/mathoff:
\def\PolPrintIntervalsKnownRoot{%
   $\PolPrintIntervalsPrintMultiplicity\quad
   \PolPrintIntervalsTheVar_{\PolPrintIntervalsTheIndex}=%
   \PolPrintIntervalsPrintExactZero
   $
}%
\def\PolPrintIntervalsUnknownRoot{%
   $\PolPrintIntervalsPrintMultiplicity\quad
   \xintifSgn{\PolPrintIntervalsTheLeftEndPoint}%
     {\xintifSgn{\PolPrintIntervalsTheRightEndPoint}
       {\PolPrintIntervalsTheVar_{\PolPrintIntervalsTheIndex}=%
        \PolPrintIntervalsPrintRightEndPoint\dots}%
      {0>\PolPrintIntervalsTheVar_{\PolPrintIntervalsTheIndex}>%
        \PolPrintIntervalsPrintLeftEndPoint}%
      {\impossibleA}}%
    {\xintifSgn{\PolPrintIntervalsTheRightEndPoint}
      {\impossibleB}%
      {\impossibleC}%
      {0<\PolPrintIntervalsTheVar_{\PolPrintIntervalsTheIndex}<%
        \PolPrintIntervalsPrintRightEndPoint}}%
    {\xintifSgn{\PolPrintIntervalsTheRightEndPoint}
      {\impossibleD}%
      {\impossibleE}%
      {\PolPrintIntervalsTheVar_{\PolPrintIntervalsTheIndex}=%
        \PolPrintIntervalsPrintLeftEndPoint\dots}}%
   $
}%
\PolPrintIntervals{T_15}
\end{everbatim*}
\end{document}