blib/lib/Math/Polynomial/Solve.pm

filter: Statementstmt 93.8% 503 / 536 Branchbran 79.5% 175 / 220 Conditioncond 66.6% 18 / 27 MC/DCmcdc 55.5% 10 / 18 Subroutinesub 94.8% 37 / 39 Podpod 92.8% 26 / 28 totaltotal 88.5% 769 / 868 CC 147 SCAR 24.8
CC
147
Cov
89%
hqr_eigen_hessenberg
30.0
poly_roots
21.0
balance_matrix
15.0
CRAP 12.0
↑ Summary
1 package Math::Polynomial::Solve;
2  
3 17 require 5.010001;
4 17 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
5 17 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
6 17 ▶use utf8;
Subroutine BEGIN: called CC=1 SCAR=0.0
7 17 ▶use Carp;
Subroutine BEGIN: called CC=1 SCAR=0.0
8  
9 17 ▶use Math::Complex;
Subroutine BEGIN: called CC=1 SCAR=0.0
10 17 ▶use Math::Utils qw(:polynomial :utility);
Subroutine BEGIN: called CC=1 SCAR=0.0
11 17 ▶use Exporter;
Subroutine BEGIN: called CC=1 SCAR=0.0
12  
13 17 our $VERSION = '2.85';
14 17 our @ISA = qw(Exporter);
15  
16 #
17 # Three # for "I am here" messages.
18 # Four # for variable dumps.
19 # Five # for a dump of the companion matrix.
20 # Six # for sturm structs (sign chain, etc).
21 #
22 #use Smart::Comments q(######);
23  
24 #
25 # Export only on request.
26 #
27 17 our %EXPORT_TAGS = (
28 'classical' => [ qw(
29 linear_roots
30 quadratic_roots
31 cubic_roots
32 quartic_roots
33 coefficients
34 is_ascending
35 ) ],
36 'numeric' => [ qw(poly_roots
37 poly_option
38 build_companion
39 balance_matrix
40 hqr_eigen_hessenberg
41 coefficients
42 is_ascending
43 ) ],
44 'sturm' => [ qw(
45 poly_real_root_count
46 poly_sturm_chain
47 sturm_real_root_range_count
48 sturm_bisection
49 sturm_bisection_roots
50 sturm_sign_count
51 sturm_sign_chain
52 sturm_sign_minus_inf
53 sturm_sign_plus_inf
54 coefficients
55 is_ascending
56 ) ],
57 'utility' => [ qw(
58 epsilon
59 laguerre
60 newtonraphson
61 poly_iteration
62 poly_nonzero_term_count
63 poly_tolerance
64 coefficients
65 is_ascending
66 ) ],
67 );
68  
69 our @EXPORT_OK = (
70 17 @{ $EXPORT_TAGS{'classical'} },
71 17 @{ $EXPORT_TAGS{'numeric'} },
72 17 @{ $EXPORT_TAGS{'sturm'} },
73 17 @{ $EXPORT_TAGS{'utility'} } );
74  
75 17 our @EXPORT = qw( coefficients is_ascending ascending_order );
76  
77 #
78 # Add an :all tag automatically.
79 #
80 17 $EXPORT_TAGS{all} = [@EXPORT_OK, @EXPORT];
81  
82 #
83 # Options to set or unset to force poly_roots() to use different
84 # methods of solving.
85 #
86 # hessenberg (default 1): set to 1 to force poly_roots() to use the QR
87 # Hessenberg method regardless of the degree of the polynomial. Set to zero
88 # to force poly_roots() uses one of the specialized routines (linerar_roots(),
89 # quadratic_roots(), etc) if the degree of the polynomial is less than five.
90 #
91 # root_function (default 0): set to 1 to force poly_roots() to use
92 # Math::Complex's root(-c/a, n) function if the polynomial is of the form
93 # ax**n + c.
94 #
95 # varsubst (default 0): try to reduce the degree of the polynomial through
96 # variable substitution before solving.
97 #
98 17 my %option = (
99 hessenberg => 1,
100 root_function => 0,
101 varsubst => 0,
102 );
103  
104 #
105 # Iteration limits. The Hessenberg matrix method and the Laguerre method run
106 # continuously until they converge upon an answer. The iteration limits are
107 # there to prevent the loops from running forever if they fail to converge.
108 #
109 17 my %iteration = (
110 hessenberg => 60,
111 newtonraphson => 60,
112 laguerre => 60,
113 sturm_bisection => 100,
114 );
115  
116 #
117 # Some values here are placeholders only, and will get
118 # replaced in the BEGIN block.
119 #
120 17 my %tolerance = (
121 newtonraphson => 1e-14,
122 laguerre => 1e-14,
123 );
124  
125 #
126 # Set up the epsilon variable, the value that is, in the floating-point
127 # math of the computer, the smallest value a variable can have before
128 # it is indistinguishable from zero when adding it to one.
129 #
130 17 my $epsilon;
131  
132 BEGIN
133 17 ▶{
Subroutine BEGIN: called CC=2 SCAR=6.9
134 17 $epsilon = 0.125;
135 17 my $epsilon2 = $epsilon/2.0;
136  
137 17 ▶ while (1.0 + $epsilon2 > 1.0)
Branch: 1 branch
BranchTrueFalseTotal
if (1 + $epsilon2 > 1) 833 17 850
138 {
139 833 $epsilon = $epsilon2;
140 833 $epsilon2 /= 2.0;
141 }
142  
143 17 $tolerance{laguerre} = 2 * $epsilon;
144 17 $tolerance{newtonraphson} = 2 * $epsilon;
145 }
146  
147 #
148 # Flag to determine whether calling order is
149 # ($an_1, $an_2, $an_3, ...) or if it is
150 # ($a0, $a1, $a2, $a3, ...)
151 #
152 17 my $ascending_flag = 0; # default 0, in a later version it will be 1.
153  
154 #
155 # See the END block.
156 #
157 17 my $coeff_order_set = 0;
158  
159 =pod
160  
161 =encoding UTF-8
162  
163 =head1 NAME
164  
165 Math::Polynomial::Solve - Find the roots of polynomial equations.
166  
167 =head1 SYNOPSIS
168  
169 use Math::Complex; # The roots may be complex numbers.
170 use Math::Polynomial::Solve qw(poly_roots coefficients);
171 coefficients order => 'descending';
172  
173 my @x = poly_roots(1, 1, 4, 4);
174  
175 or
176  
177 use Math::Complex; # The roots may be complex numbers.
178 use Math::Polynomial::Solve qw(:numeric coefficients); # See the EXPORT section
179 coefficients order => 'descending';
180  
181 #
182 # Find roots using the matrix method.
183 #
184 my @x = poly_roots(5, 12, 17, 12, 5);
185  
186 #
187 # Alternatively, use the classical methods instead of the matrix
188 # method if the polynomial degree is less than five.
189 #
190 poly_option(hessenberg => 0);
191 @x = poly_roots(5, 12, 17, 12, 5);
192  
193 or
194  
195 use Math::Complex; # The roots may be complex numbers.
196 use Math::Polynomial::Solve qw(:classical coefficients); # See the EXPORT section
197 coefficients order => 'descending';
198  
199 #
200 # Find the polynomial roots using the classical methods.
201 #
202  
203 # Find the roots of ax + b
204 my @x1 = linear_roots($a, $b);
205  
206 # Find the roots of ax**2 + bx +c
207 my @x2 = quadratic_roots($a, $b, $c);
208  
209 # Find the roots of ax**3 + bx**2 +cx + d
210 my @x3 = cubic_roots($a, $b, $c, $d);
211  
212 # Find the roots of ax**4 + bx**3 +cx**2 + dx + e
213 my @x4 = quartic_roots($a, $b, $c, $d, $e);
214  
215 or
216  
217 use Math::Complex; # The roots may be complex numbers.
218 use Math::Polynomial;
219 use Math::Polynomial::Solve qw(:classical coefficients);
220  
221 #
222 # Change default coefficient order for M::P::S.
223 #
224 coefficients order => 'ascending';
225  
226 #
227 # Form 8*x**3 - 6*x - 1
228 #
229 my $p1 = Math::Polynomial->new(-1, -6, 0, 8);
230  
231 #
232 # Use Math::Polynomial's coefficient order.
233 # If the coefficient order had not been changed,
234 # the statement would be:
235 #
236 # my @roots = poly_roots(reverse $p1->coefficients);
237 #
238 my @roots = poly_roots($p1->coefficients);
239  
240 or
241  
242 use Math::Polynomial::Solve qw(:sturm coefficients);
243 coefficients order => 'descending';
244  
245 #
246 # Find the number of unique real roots of the polynomial.
247 #
248 my $no_of_unique_roots = poly_real_root_count(2, 7, 8, -8, -23, -11);
249  
250 =head1 DESCRIPTION
251  
252 This package supplies a set of functions that find the roots of
253 polynomials, along with some utility functions.
254  
255 Roots will be either real or of type L<Math::Complex>.
256  
257 Functions making use of the Sturm sequence are also available, letting you
258 find the number of real roots present in a range of X values.
259  
260 In addition to the root-finding functions, the internal functions have
261 also been exported for your use.
262  
263 =cut
264  
265 #
266 # $asending = ascending_order();
267 # $oldorder = ascending_order($neworder);
268 #
269 # Obsolete way of doing it, but preserve it in case
270 # someone was an early adopter.
271 #
272 sub ascending_order
273 0 ▶{
Subroutine ascending_order: not called CC=3 SCAR=24.8
Pod undocumented
274 0 my $ascend = $ascending_flag;
275  
276 0 ▶ if (scalar @_ > 0)
Branch: 1 branch
BranchTrueFalseTotal
if (scalar @_ > 0) 0 0 0
277 {
278 0 ▶ $ascending_flag = ($_[0] == 0)? 0: 1;
Branch: 1 branch
BranchTrueFalseTotal
$_[0] == 0 ? : 0 0 0
279 0 $coeff_order_set = 1;
280 }
281  
282 0 return $ascend;
283 }
284  
285 sub is_ascending
286 1 ▶{
Subroutine is_ascending: called CC=1 SCAR=0.0
Pod documented
287 1 return $ascending_flag;
288 }
289  
290 sub coefficients
291 17 ▶{
Subroutine coefficients: called CC=4 SCAR=15.8
Pod documented
292 17 my %def = @_;
293 17 ▶ if (not exists $def{order})
Branch: 3 branches
BranchTrueFalseTotal
if (not exists $def{'order'}) { } 0 17 17
elsif ($def{'order'} =~ /^ascend/i) { } 15 2 17
elsif ($def{'order'} =~ /^descend/i) { } 2 0 2
294 {
295 0 carp "'coefficients' needs to know the order.";
296 0 $coeff_order_set = 0;
297 }
298 elsif ($def{order} =~ m/^ascend/i)
299 {
300 15 $ascending_flag = 1;
301 15 $coeff_order_set = 1;
302 }
303 elsif ($def{order} =~ m/^descend/i)
304 {
305 2 $ascending_flag = 0;
306 2 $coeff_order_set = 1;
307 }
308 else
309 {
310 0 carp "'coefficients' needs to know if the order is ascending or descending.";
311 0 $coeff_order_set = 0;
312 }
313 }
314  
315 #
316 # ($new_coefficients_ref, $varsubst) = poly_analysis(@coefficients);
317 #
318 # If the polynomial has evenly spaced gaps of zero coefficients, reduce
319 # the polynomial through variable substitution.
320 #
321 # For example, a degree-6 polynomial like 9x**6 + 128x**3 + 7
322 # can be reduced to a polynomial 9y**2 + 128y + 7, where y = x**3.
323 #
324 # After solving a quadratic instead of a sextic, the actual roots of
325 # the original equation are found by taking the cube roots of each
326 # root of the quadratic.
327 #
328 # Not exported. Coefficients are always in ascending order.
329 #
330 sub poly_analysis
331 44 ▶{
Subroutine poly_analysis: called CC=6 SCAR=17.9
Pod undocumented
332 44 my(@coefficients) = @_;
333 44 my @czp;
334 44 my $m = 1;
335  
336 #
337 # Is the count of coefficients a multiple of any of the primes?
338 #
339 # Realistically I don't expect any gaps that can't be handled by
340 # the first three prime numbers, but it's not much of a waste of
341 # space to check the first dozen.
342 #
343 44 @czp = grep(($#coefficients % $_) == 0,
344 (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)
345 );
346  
347 #
348 # Any coefficients zero at the non-N degrees? (1==T,0==F).
349 #
350 #### @czp
351 #
352 44 ▶ if (@czp)
Branch: 1 branch
BranchTrueFalseTotal
if (@czp) 30 14 44
353 {
354 30 for my $j (1..$#coefficients - 1)
355 {
356 106 ▶ if (abs($coefficients[$j]) > $epsilon)
Branch: 1 branch
BranchTrueFalseTotal
if (abs $coefficients[$j] > $epsilon) 20 86 106
357 {
358 20 @czp = grep(($j % $_) == 0, @czp);
359 }
360 }
361  
362 #
363 # The remaining list of primes represent the gap size
364 # between non-zero coefficients.
365 #
366 30 map(($m *= $_), @czp);
367  
368 #### Substitution degree: $m
369 }
370  
371 #
372 # If there's a sequence of zero-filled gaps in the coefficients,
373 # reduce the polynomial by degree $m and check again for the
374 # next round of factors (e.g., X**8 + X**4 + 1 needs two rounds
375 # to get to a factor of 4).
376 #
377 44 ▶ if ($m > 1)
Branch: 1 branch
BranchTrueFalseTotal
if ($m > 1) 22 22 44
378 {
379 22 my @alt_coefs;
380 22 push @alt_coefs, $coefficients[$_*$m] for (0..$#coefficients/$m);
381 22 my($cf, $m1) = poly_analysis(@alt_coefs);
382 22 @coefficients = @$cf;
383 22 $m *= $m1;
384 }
385  
386 44 return \@coefficients, $m;
387 }
388  
389 =head1 EXPORT
390  
391 There is an B<all> tag that exports everything.
392  
393 Currently there is one default export, L<coefficients|coefficients()>.
394  
395 If you want to have more fine-grained control you may
396 individually name the functions in an export list, or
397 use one four export tags:
398  
399 L<classical|Classical Functions>,
400 L<numeric|Numeric Functions>,
401 L<sturm|Sturm Functions>,
402 L<utility|Utility Functions>,
403  
404 =head2 EXPORTED BY DEFAULT
405  
406 =head3 coefficients
407  
408 Changes the default order of the coefficents to the functions.
409  
410 When Math::Polynomial::Solve was originally written, it followed the
411 calling convention of L<Math::Polynomial>, using the highest degree
412 coefficient, followed by the next highest degree coefficient, and so
413 on in descending order.
414  
415 Later Math::Polynomial was re-written, and the order of the coefficients were
416 put in ascending order, e.g.:
417  
418 use Math::Polynomial;
419  
420 #
421 # Create the polynomial 8*x**3 - 6*x - 1.
422 #
423 $fpx = Math::Polynomial->new(-1, -6, 0, 8);
424  
425 If you use Math::Polynomial with this module, it will probably be
426 more convenient to change the default parameter list of
427 Math::Polynomial::Solve's functions, using the coefficients() function:
428  
429 use Math::Polynomial;
430 use Math::Polynomial::Solve qw(:all);
431  
432 coefficients order => 'ascending';
433  
434 my $fp4 = Math::Polynomial->interpolate([1 .. 4], [14, 19, 25, 32]);
435  
436 my @fp4_roots = poly_roots($fp4->coefficients);
437  
438 If C<coefficients order =E<gt> 'ascending'> had not been called, the
439 previous line of code would have been written instead as
440  
441 my @fp4_roots = poly_roots(reverse $fp4->coefficients);
442  
443 The function is a way to help with the change in the API when version 3.00 of
444 this module is released. At that point coefficients will be in ascending
445 order by default, and you will need to use
446 C<coefficients order =E<gt> 'descending'> to use the old (current) style.
447  
448 =head3 is_ascending()
449  
450 Returns C<1> if the coefficent order is ascending, C<0> if the order is descending.
451  
452 if (is_ascending())
453 {
454 print "Please enter your coefficients from lowest power to highest: ";
455 }
456 else
457 {
458 print "Please enter your coefficients from highest power to lowest: ";
459 }
460  
461 =head2 Numeric Functions
462  
463 These are the functions that calculate the polynomial's roots through numeric
464 algorithms. They are all exported under the tag "numeric".
465  
466 =head3 poly_roots()
467  
468 Returns the roots of a polynomial equation, regardless of degree.
469 Unlike the other root-finding functions, it will check for coefficients
470 of zero for the highest power, and 'step down' the degree of the
471 polynomial to the appropriate case. Additionally, it will check for
472 coefficients of zero for the lowest power terms, and add zeros to its
473 root list before calling one of the root-finding functions.
474  
475 By default, C<poly_roots()> will use the Hessenberg matrix method for solving
476 polynomials. This can be changed by calling L</poly_options()>.
477  
478 The method of poly_roots() is almost equivalent to
479  
480 @x = hqr_eigen_hessenberg(
481 balance_matrix(build_companion(@coefficients))
482 );
483  
484 except this wouldn't check for leading and trailing zero coefficients, and it
485 ignores the settings of C<poly_options()>.
486  
487 =cut
488  
489 sub poly_roots
490 135 ▶{
Subroutine poly_roots: called CC=19 SCAR=30.4
Pod documented
491 135 ▶ my(@coefficients) = ($ascending_flag == 0)? reverse @_: @_;
Branch: 1 branch
BranchTrueFalseTotal
$ascending_flag == 0 ? : 0 135 135
492 135 my(@x, @zero_x);
493 135 my $subst_degree = 1;
494  
495 #
496 #### @coefficients
497 #
498 # Check for zero coefficients in the higher-powered terms.
499 #
500 135 ▶ pop @coefficients while (scalar @coefficients and
Branch: 1 branch
BranchTrueFalseTotal
scalar @coefficients and abs $coefficients[$#coefficients] < $epsilon and do { pop @coefficients } 0 135 135
Condition33%1/3
scalar @coefficients and abs $coefficients[$#coefficients] < $epsilon
!ll&&!rl&&r
01350
MC/DC0%0/2
scalar @coefficients and abs $coefficients[$#coefficients] < $epsilon
scalar @coefficients abs $coefficients[$#coefficients] < $epsilon
Truth table33%1/3
A and B
A= scalar @coefficientsB= abs $coefficients[$#coefficients] < $epsilon
ABresult
0X0
100
111
501 abs($coefficients[$#coefficients]) < $epsilon);
502  
503 135 ▶ if (@coefficients == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (@coefficients == 0) 0 135 135
504 {
505 0 carp "All coefficients are zero\n";
506 0 return (0);
507 }
508  
509 #
510 # How about zero coefficients in the low terms?
511 #
512 135 ▶ while (scalar @coefficients and
Branch: 1 branch
BranchTrueFalseTotal
if (scalar @coefficients and abs $coefficients[0] < $epsilon) 12 135 147
Condition66%2/3
scalar @coefficients and abs $coefficients[0] < $epsilon
!ll&&!rl&&r
013512
MC/DC50%1/2
scalar @coefficients and abs $coefficients[0] < $epsilon
scalar @coefficients abs $coefficients[0] < $epsilon
Truth table66%2/3
A and B
A= scalar @coefficientsB= abs $coefficients[0] < $epsilon
ABresult
0X0
100
111
513 abs($coefficients[0]) < $epsilon)
514 {
515 12 push @zero_x, 0;
516 shift @coefficients
517 12 }
518  
519 #
520 # If the polynomial is of the form c + ax**n, and if the
521 # root_function option is set, use the Math::Complex::root()
522 # function to return the roots.
523 #
524 ### %option
525 #
526 135 ▶ if ($option{root_function} and
Branch: 1 branch
BranchTrueFalseTotal
if ($option{"root_function"} and poly_nonzero_term_count(@coefficients) == 2) 15 120 135
Condition100%3/3
$option{"root_function"} and poly_nonzero_term_count(@coefficients) == 2
!ll&&!rl&&r
118215
MC/DC100%2/2
$option{"root_function"} and poly_nonzero_term_count(@coefficients) == 2
$option{"root_function"} poly_nonzero_term_count(@coefficients) == 2
Truth table100%3/3
A and B
A= $option{"root_function"}B= poly_nonzero_term_count(@coefficients) == 2
ABresult
0X0
100
111
527 poly_nonzero_term_count(@coefficients) == 2)
528 {
529 15 return @zero_x,
530 root(-$coefficients[0]/$coefficients[$#coefficients],
531 $#coefficients);
532 }
533  
534 #
535 # Next do some analysis of the coefficients.
536 # See if we can reduce the size of the polynomial by
537 # doing some variable substitution.
538 #
539 120 ▶ if ($option{varsubst} and $#coefficients > 1)
Branch: 1 branch
BranchTrueFalseTotal
if ($option{"varsubst"} and $#coefficients > 1) 22 98 120
Condition66%2/3
$option{"varsubst"} and $#coefficients > 1
!ll&&!rl&&r
98022
MC/DC50%1/2
$option{"varsubst"} and $#coefficients > 1
$option{"varsubst"} $#coefficients > 1
Truth table66%2/3
A and B
A= $option{"varsubst"}B= $#coefficients > 1
ABresult
0X0
100
111
540 {
541 22 my $cf;
542 22 ($cf, $subst_degree) = poly_analysis(@coefficients);
543 22 ▶ @coefficients = @$cf if ($subst_degree > 1);
Branch: 1 branch
BranchTrueFalseTotal
if $subst_degree > 1 22 0 22
544 }
545  
546 #
547 # If the remaining polynomial is a quintic or higher, or
548 # if $option{hessenberg} is set, continue with the matrix
549 # calculation.
550 #
551 #### @coefficients
552 #### $subst_degree
553 #
554 #
555 # With the coefficents in ascending order,
556 # pretend it was always that way for the next
557 # function calls.
558 #
559 120 my $temp_ascending_flag = $ascending_flag;
560 120 $ascending_flag = 1;
561  
562 120 ▶ if ($option{hessenberg} or $#coefficients > 4)
Branch: 5 branches
BranchTrueFalseTotal
if ($option{'hessenberg'} or $#coefficients > 4) { } 87 33 120
elsif ($#coefficients == 4) { } 15 18 33
elsif ($#coefficients == 3) { } 4 14 18
elsif ($#coefficients == 2) { } 5 9 14
elsif ($#coefficients == 1) { } 9 0 9
Condition66%2/3
$option{"hessenberg"} or $#coefficients > 4
l!l&&r!l&&!r
87033
MC/DC50%1/2
$option{"hessenberg"} or $#coefficients > 4
$option{"hessenberg"} $#coefficients > 4
Truth table66%2/3
A or B
A= $option{"hessenberg"}B= $#coefficients > 4
ABresult
1X1
011
000
563 {
564 #
565 # QR iterations from the matrix.
566 #
567 87 @x = hqr_eigen_hessenberg(
568 balance_matrix(build_companion(@coefficients))
569 );
570 }
571 elsif ($#coefficients == 4)
572 {
573 15 @x = quartic_roots(@coefficients);
574 }
575 elsif ($#coefficients == 3)
576 {
577 4 @x = cubic_roots(@coefficients);
578 }
579 elsif ($#coefficients == 2)
580 {
581 5 @x = quadratic_roots(@coefficients);
582 }
583 elsif ($#coefficients == 1)
584 {
585 9 @x = linear_roots(@coefficients);
586 }
587  
588 120 $ascending_flag = $temp_ascending_flag;
589  
590 120 ▶ @x = map(root($_, $subst_degree), @x) if ($subst_degree > 1);
Branch: 1 branch
BranchTrueFalseTotal
if $subst_degree > 1 22 98 120
591  
592 120 return @zero_x, @x;
593 }
594  
595  
596 =head3 poly_option()
597  
598 Set options that affect the behavior of the C<poly_roots()> function. All
599 options are set to either 1 ("on") or 0 ("off"). See also L</poly_iteration()>
600 and L</poly_tolerance()>.
601  
602 Options may be set and saved:
603  
604 #
605 # Set a few options...
606 #
607 poly_option(hessenberg => 0, root_function => 1);
608  
609 #
610 # Get all of the current options and their values.
611 #
612 my %all_options = poly_option();
613  
614 #
615 # Set some options but save the former option values
616 # for later.
617 #
618 my %changed_options = poly_option(hessenberg => 1, varsubst => 1);
619  
620 The current options available are:
621  
622 =over 4
623  
624 =item 'hessenberg'
625  
626 Use the QR Hessenberg matrix method to solve the polynomial. By default, this
627 is set to 1. If set to 0, C<poly_roots()> uses one of the L<classical|Classical Functions>
628 root-finding functions listed below, I<if> the degree of the polynomial is four
629 or less.
630  
631 =item 'root_function'
632  
633 Use the L<root()|Math::Complex/OPERATIONS> function from Math::Complex if the
634 polynomial is of the form C<ax**n + c>. This will take precedence over the other
635 solving methods.
636  
637 =item 'varsubst'
638  
639 Reduce polynomials to a lower degree through variable substitution, if possible.
640  
641 For example, with C<varsubst> set to one and the polynomial to solve being
642 C<9x**6 + 128x**3 + 21>, C<poly_roots()> will reduce the polynomial to
643 C<9y**2 + 128y + 21> (where C<y = x**3>),
644 and solve the quadratic (either classically or numerically, depending
645 on the hessenberg option). Taking the cube root of each quadratic root
646 completes the operation.
647  
648 This has the benefit of having a simpler matrix to solve, or if the
649 C<hessenberg> option is set to zero, has the effect of being able to use one of
650 the classical methods on a polynomial of high degree. In the above example, the
651 order-six polynomial gets solved with the quadratic_roots() function if the
652 hessenberg option is zero.
653  
654 Currently the variable substitution is fairly simple and will only look
655 for gaps of zeros in the coefficients that are multiples of the prime numbers
656 less than or equal to 37 (2, 3, 5, et cetera).
657  
658 =back
659  
660 =cut
661  
662 sub poly_option
663 22 ▶{
Subroutine poly_option: called CC=5 SCAR=16.2
Pod documented
664 22 my %opts = @_;
665 22 my %old_opts;
666  
667 22 ▶ return %option if (scalar @_ == 0);
Branch: 1 branch
BranchTrueFalseTotal
if scalar @_ == 0 7 15 22
668  
669 15 for my $okey (keys %opts)
670 {
671 #
672 # If this is a real option, save its old value, then set it.
673 #
674 15 ▶ if (exists $option{$okey})
Branch: 1 branch
BranchTrueFalseTotal
if (exists $option{$okey}) { } 15 0 15
675 {
676 15 $old_opts{$okey} = $option{$okey};
677 15 ▶ $option{$okey} = ($opts{$okey})? 1: 0;
Branch: 1 branch
BranchTrueFalseTotal
$opts{$okey} ? : 7 8 15
678 }
679 else
680 {
681 0 carp "poly_option(): unknown key $okey.";
682 }
683 }
684  
685 15 return %old_opts;
686 }
687  
688 =head3 build_companion
689  
690 Creates the initial companion matrix of the polynomial. Returns an array
691 of arrays (the internal representation of a matrix). This may be used as
692 an argument to the L<Math::Matrix> contructor:
693  
694 my @cm = build_companion(@coef);
695  
696 my $m = Math::Matrix->new(@cm);
697 $m->print();
698  
699 The Wikipedia article at L<http://en.wikipedia.org/wiki/Companion_matrix/> has
700 more information on the subject.
701  
702 =cut
703  
704 #
705 # Perl code to find roots of a polynomial translated by Nick Ing-Simmons
706 # from FORTRAN code by Hiroshi Murakami.
707 #
708 # From the netlib archive: http://netlib.bell-labs.com/netlib/search.html
709 # In particular http://netlib.bell-labs.com/netlib/opt/companion.tgz
710 #
711 sub build_companion
712 87 ▶{
Subroutine build_companion: called CC=3 SCAR=11.0
Pod documented
713 87 ▶ my @coefficients = ($ascending_flag == 0)? reverse @_: @_;
Branch: 1 branch
BranchTrueFalseTotal
$ascending_flag == 0 ? : 0 87 87
714 87 my $n = $#coefficients - 1;
715 87 my @h;
716  
717 #
718 ### build_companion called with: @coefficients
719 #
720 # First step: Divide by the leading coefficient and negate.
721 #
722 87 my $cn = - (pop @coefficients);
723 87 map($_ /= $cn, @coefficients);
724  
725 #
726 # Next: set up the diagonal matrix.
727 #
728 87 for my $i (0 .. $n)
729 {
730 351 $h[$i][$n] = shift @coefficients;
731 351 map($h[$i][$_] = 0.0, 0 .. $n - 1);
732 }
733  
734 87 map($h[$_][$_ - 1] = 1.0, 1 .. $n);
735  
736 87 return @h;
737 }
738  
739 =head3 balance_matrix
740  
741 Balances the matrix (makes the rows and columns have similar norms) created
742 by build_companion() by applying a matrix transformation with a diagonal
743 matrix of powers of two.
744  
745 This is used to help prevent any rounding errors that occur if the elements
746 of the matrix differ greatly in magnitude.
747  
748 =cut
749  
750 # BASE is the base of the floating point representation on the machine.
751 # It is 16 for base 16 float : for example, IBM system 360/370.
752 # It is 2 for base 2 float : for example, IEEE float.
753 sub BASE () { 2 }
754 sub BASESQR () { BASE * BASE }
755  
756 #
757 # @matrix = balance_matrix(@cm);
758 #
759 # Balance the companion matrix created by build_companion().
760 #
761 # Return an array of arrays representing the N by N matrix.
762 #
763 # In the :numeric export set.
764 #
765 sub balance_matrix
766 87 ▶{
Subroutine balance_matrix: called CC=15 SCAR=27.1
Pod documented
767 87 my @h = @_;
768 87 my $n = $#h;
769  
770 #
771 ### Balancing the unsymmetric matrix A.
772 #
773 ##### @h
774 #
775 # Perl code translated by Nick Ing-Simmons from FORTRAN code
776 # by Hiroshi Murakami.
777 #
778 # The Fortran code is based on the Algol code "balance" from paper:
779 # "Balancing a Matrix for Calculation of Eigenvalues and Eigenvectors"
780 # by B. N. Parlett and C. Reinsch, Numer. Math. 13, 293-304(1969).
781 #
782 # Note: The only non-zero elements of the companion matrix are touched.
783 #
784 87 my $noconv = 1;
785 87 ▶ while ($noconv)
Branch: 1 branch
BranchTrueFalseTotal
if ($noconv) 156 87 243
786 {
787 156 $noconv = 0;
788 156 for my $i (0 .. $n)
789 {
790 #
791 # Touch only non-zero elements of companion.
792 #
793 681 my $c;
794 681 ▶ if ($i != $n)
Branch: 1 branch
BranchTrueFalseTotal
if ($i != $n) { } 525 156 681
795 {
796 525 $c = abs($h[$i + 1][$i]);
797 }
798 else
799 {
800 156 $c = 0.0;
801 156 for my $j (0 .. $n - 1)
802 {
803 525 $c += abs($h[$j][$n]);
804 }
805 }
806  
807 681 my $r;
808 681 ▶ if ($i == 0)
Branch: 2 branches
BranchTrueFalseTotal
if ($i == 0) { } 156 525 681
elsif ($i != $n) { } 378 147 525
809 {
810 156 $r = abs($h[0][$n]);
811 }
812 elsif ($i != $n)
813 {
814 378 $r = abs($h[$i][$i - 1]) + abs($h[$i][$n]);
815 }
816 else
817 {
818 147 $r = abs($h[$i][$i - 1]);
819 }
820  
821 681 ▶ next if ($c == 0.0 || $r == 0.0);
Branch: 1 branch
BranchTrueFalseTotal
if $c == 0 or $r == 0 9 672 681
Condition66%2/3
$c == 0 or $r == 0
l!l&&r!l&&!r
90672
MC/DC50%1/2
$c == 0 or $r == 0
$c == 0 $r == 0
Truth table66%2/3
A or B
A= $c == 0B= $r == 0
ABresult
1X1
011
000
822  
823 672 my $g = $r / BASE;
824 672 my $f = 1.0;
825 672 my $s = $c + $r;
826 672 ▶ while ( $c < $g )
Branch: 1 branch
BranchTrueFalseTotal
if ($c < $g) 205 672 877
827 {
828 205 $f = $f * BASE;
829 205 $c = $c * BASESQR;
830 }
831  
832 672 $g = $r * BASE;
833 672 ▶ while ($c >= $g)
Branch: 1 branch
BranchTrueFalseTotal
if ($c >= $g) 113 672 785
834 {
835 113 $f = $f / BASE;
836 113 $c = $c / BASESQR;
837 }
838  
839 672 ▶ if (($c + $r) < 0.95 * $s * $f)
Branch: 1 branch
BranchTrueFalseTotal
if ($c + $r < "0.95" * $s * $f) 173 499 672
840 {
841 173 $g = 1.0 / $f;
842 173 $noconv = 1;
843  
844 #C Generic code.
845 #C do $j=1,$n
846 #C $h($i,$j)=$h($i,$j)*$g
847 #C enddo
848 #C do $j=1,$n
849 #C $h($j,$i)=$h($j,$i)*$f
850 #C enddo
851 #C begin specific code. Touch only non-zero elements of companion.
852 173 ▶ if ($i == 0)
Branch: 1 branch
BranchTrueFalseTotal
if ($i == 0) { } 41 132 173
853 {
854 41 $h[0][$n] *= $g;
855 }
856 else
857 {
858 132 $h[$i][$i - 1] *= $g;
859 132 $h[$i][$n] *= $g;
860 }
861 173 ▶ if ($i != $n)
Branch: 1 branch
BranchTrueFalseTotal
if ($i != $n) { } 145 28 173
862 {
863 145 $h[$i + 1][$i] *= $f;
864 }
865 else
866 {
867 28 for my $j (0 .. $n)
868 {
869 142 $h[$j][$i] *= $f;
870 }
871 }
872 }
873 } # for $i
874 } # while $noconv
875  
876 #
877 ### Returning balanced matrix.
878 ##### @h
879 #
880 87 return @h;
881 }
882  
883  
884 =head3 hqr_eigen_hessenberg
885  
886 Returns the roots of the polynomial equation by solving the matrix created by
887 C<build_companion()> and C<balance_matrix()>. See L</poly_roots()>.
888  
889 =cut
890  
891 sub hqr_eigen_hessenberg
892 87 ▶{
Subroutine hqr_eigen_hessenberg: called CC=30 SCAR=34.0
Pod documented
893 87 my @h = @_;
894 87 my $n = $#h;
895  
896 #
897 ### hqr_eigen_hessenberg()
898 #
899 # Eigenvalue Computation by the Householder QR method for the
900 # Real Hessenberg matrix.
901 #
902 # Perl code translated by Nick Ing-Simmons from FORTRAN code
903 # by Hiroshi Murakami.
904 #
905 # The Fortran code is based on the Algol code "hqr" from the paper:
906 # "The QR Algorithm for Real Hessenberg Matrices"
907 # by R. S. Martin, G. Peters and J. H. Wilkinson,
908 # Numer. Math. 14, 219-231(1970).
909 #
910 87 my($p, $q, $r);
911 87 my $t = 0.0;
912  
913 87 my @roots;
914  
915 ROOT:
916 87 ▶ while ($n >= 0)
Branch: 1 branch
BranchTrueFalseTotal
if ($n >= 0) 207 87 294
917 {
918 207 my $its = 0;
919 207 my $na = $n - 1;
920  
921 207 ▶ while ($its < $iteration{hessenberg})
Branch: 1 branch
BranchTrueFalseTotal
if ($its < $iteration{"hessenberg"}) 1300 0 1300
922 {
923 1300 my($w, $x, $y);
924  
925 #
926 # Look for single small sub-diagonal element;
927 #
928 1300 my $l = 0;
929 1300 for my $d (reverse 1 .. $n)
930 {
931 4219 ▶ if (abs( $h[$d][ $d - 1 ] ) <= $epsilon *
Branch: 1 branch
BranchTrueFalseTotal
if (abs $h[$d][$d - 1] <= $epsilon * (abs($h[$d - 1][$d - 1]) + abs($h[$d][$d]))) 157 4062 4219
932 (abs( $h[ $d - 1 ][ $d - 1 ] ) +
933 abs( $h[$d][$d] ) ) )
934 {
935 157 $l = $d;
936 157 last;
937 }
938 }
939  
940 1300 $x = $h[$n][$n];
941  
942 1300 ▶ if ($l == $n)
Branch: 1 branch
BranchTrueFalseTotal
if ($l == $n) 63 1237 1300
943 {
944 #
945 # One (real) root found.
946 #
947 63 $n--;
948 63 push @roots, $x + $t;
949 63 next ROOT;
950 }
951  
952 1237 $y = $h[$na][$na];
953 1237 $w = $h[$n][$na] * $h[$na][$n];
954  
955 1237 ▶ if ($l == $na)
Branch: 1 branch
BranchTrueFalseTotal
if ($l == $na) 144 1093 1237
956 {
957 144 $p = ( $y - $x ) / 2;
958 144 $q = $p * $p + $w;
959 144 $y = sqrt( abs($q) );
960 144 $x += $t;
961  
962 144 ▶ if ($q > 0.0)
Branch: 1 branch
BranchTrueFalseTotal
if ($q > 0.0) { } 17 127 144
963 {
964 #
965 # Real pair.
966 #
967 17 ▶ $y = -$y if ( $p < 0.0 );
Branch: 1 branch
BranchTrueFalseTotal
if $p < 0 9 8 17
968 17 $y += $p;
969 17 push @roots, $x - $w / $y;
970 17 push @roots, $x + $y;
971 }
972 else
973 {
974 #
975 # Complex or twin pair.
976 #
977 127 push @roots, $x + $p - $y * i;
978 127 push @roots, $x + $p + $y * i;
979 }
980  
981 144 $n -= 2;
982 144 next ROOT;
983 }
984  
985 1093 ▶ croak "Too many iterations ($its) at n=$n\n" if ($its >= $iteration{hessenberg});
Branch: 1 branch
BranchTrueFalseTotal
if $its >= $iteration{"hessenberg"} 0 1093 1093
986  
987 1093 ▶ if ($its && $its % 10 == 0)
Branch: 1 branch
BranchTrueFalseTotal
if ($its and $its % 10 == 0) 53 1040 1093
Condition100%3/3
$its and $its % 10 == 0
!ll&&!rl&&r
11592553
MC/DC100%2/2
$its and $its % 10 == 0
$its $its % 10 == 0
Truth table100%3/3
A and B
A= $itsB= $its % 10 == 0
ABresult
0X0
100
111
988 {
989 #
990 # Form exceptional shift.
991 #
992 ### Exceptional shift at: $its
993 #
994  
995 53 $t += $x;
996 53 for my $i (0 .. $n)
997 {
998 249 $h[$i][$i] -= $x;
999 }
1000  
1001 53 my $s = abs($h[$n][$na]) + abs($h[$na][$n - 2]);
1002 53 $y = 0.75 * $s;
1003 53 $x = $y;
1004 53 $w = -0.4375 * $s * $s;
1005 }
1006  
1007 1093 $its++;
1008  
1009 #
1010 ### Look for two consecutive small
1011 ### sub-diagonal elements.
1012 #
1013 1093 my $m = $l; # Set in case we fall through the loop.
1014 1093 for my $d (reverse $l .. $n - 2)
1015 {
1016 2811 my $z = $h[$d][$d];
1017 2811 my $s = $y - $z;
1018 2811 $r = $x - $z;
1019 2811 $p = ($r * $s - $w) / $h[$d + 1][$d] + $h[$d][$d + 1];
1020 2811 $q = $h[$d + 1][$d + 1] - $z - $r - $s;
1021 2811 $r = $h[$d + 2][$d + 1];
1022  
1023 2811 $s = abs($p) + abs($q) + abs($r);
1024 2811 $p /= $s;
1025 2811 $q /= $s;
1026 2811 $r /= $s;
1027  
1028 #
1029 # The sub-diagonal check doesn't get made for
1030 # the last iteration of the loop, and the only
1031 # reason we have the loop continue up to this
1032 # point is to set $p, $q, and $r.
1033 #
1034 2811 ▶ last if ($d == $l);
Branch: 1 branch
BranchTrueFalseTotal
if $d == $l 1085 1726 2811
1035  
1036 1726 ▶ if (abs($h[$d][$d - 1]) * (abs($q) + abs($r)) <=
Branch: 1 branch
BranchTrueFalseTotal
if (abs($h[$d][$d - 1]) * (abs($q) + abs($r)) <= $epsilon * abs($p) * (abs($h[$d - 1][$d - 1]) + abs($z) + abs($h[$d + 1][$d + 1]))) 8 1718 1726
1037 $epsilon * abs($p) * (
1038 abs($h[$d - 1][$d - 1]) +
1039 abs($z) +
1040 abs($h[$d + 1][$d + 1])
1041 ))
1042 {
1043 8 $m = $d;
1044 8 last;
1045 }
1046 }
1047  
1048 #
1049 #### $n
1050 #### $l
1051 #### $m
1052 #
1053 1093 for my $i (($m + 2) .. $n)
1054 {
1055 2811 $h[$i][$i - 2] = 0.0;
1056 }
1057 1093 for my $i (($m + 3) .. $n)
1058 {
1059 1718 $h[$i][$i - 3] = 0.0;
1060 }
1061  
1062 #
1063 # Double QR step involving rows $l to $n and
1064 # columns $m to $n.
1065 #
1066 1093 for my $k ($m .. $na)
1067 {
1068 3904 my $z;
1069 3904 my $notlast = ($k != $na);
1070 3904 ▶ if ($k != $m)
Branch: 1 branch
BranchTrueFalseTotal
if ($k != $m) 2811 1093 3904
1071 {
1072 2811 $p = $h[$k][$k - 1];
1073 2811 $q = $h[$k + 1][$k - 1];
1074 2811 ▶ $r = ($notlast)? $h[$k + 2][$k - 1]: 0.0;
Branch: 1 branch
BranchTrueFalseTotal
$notlast ? : 1718 1093 2811
1075  
1076 2811 $x = abs($p) + abs($q) + abs($r);
1077 2811 ▶ next if ( $x == 0.0 );
Branch: 1 branch
BranchTrueFalseTotal
if $x == 0 0 2811 2811
1078  
1079 2811 $p /= $x;
1080 2811 $q /= $x;
1081 2811 $r /= $x;
1082 }
1083  
1084 3904 my $s = sqrt($p * $p + $q * $q + $r * $r);
1085 3904 ▶ $s = -$s if ($p < 0.0);
Branch: 1 branch
BranchTrueFalseTotal
if $p < 0 1897 2007 3904
1086  
1087 3904 ▶ if ($k != $m)
Branch: 2 branches
BranchTrueFalseTotal
if ($k != $m) { } 2811 1093 3904
elsif ($l != $m) { } 8 1085 1093
1088 {
1089 2811 $h[$k][$k - 1] = -$s * $x;
1090 }
1091 elsif ($l != $m)
1092 {
1093 8 $h[$k][$k - 1] *= -1;
1094 }
1095  
1096 3904 $p += $s;
1097 3904 $x = $p / $s;
1098 3904 $y = $q / $s;
1099 3904 $z = $r / $s;
1100 3904 $q /= $p;
1101 3904 $r /= $p;
1102  
1103 #
1104 # Row modification.
1105 #
1106 3904 for my $j ($k .. $n)
1107 {
1108 14084 $p = $h[$k][$j] + $q * $h[$k + 1][$j];
1109  
1110 14084 ▶ if ($notlast)
Branch: 1 branch
BranchTrueFalseTotal
if ($notlast) 11898 2186 14084
1111 {
1112 11898 $p += $r * $h[ $k + 2 ][$j];
1113 11898 $h[ $k + 2 ][$j] -= $p * $z;
1114 }
1115  
1116 14084 $h[ $k + 1 ][$j] -= $p * $y;
1117 14084 $h[$k][$j] -= $p * $x;
1118 }
1119  
1120 3904 my $j = $k + 3;
1121 3904 ▶ $j = $n if ($j > $n);
Branch: 1 branch
BranchTrueFalseTotal
if $j > $n 2186 1718 3904
1122  
1123 #
1124 # Column modification.
1125 #
1126 3904 for my $i ($l .. $j)
1127 {
1128 18641 $p = $x * $h[$i][$k] +
1129 $y * $h[$i][$k + 1];
1130  
1131 18641 ▶ if ($notlast)
Branch: 1 branch
BranchTrueFalseTotal
if ($notlast) 13630 5011 18641
1132 {
1133 13630 $p += $z * $h[$i][$k + 2];
1134 13630 $h[$i][$k + 2] -= $p * $r;
1135 }
1136  
1137 18641 $h[$i][$k + 1] -= $p * $q;
1138 18641 $h[$i][$k] -= $p;
1139 }
1140 } # for $k
1141 } # while $its
1142 } # while $n
1143 87 return @roots;
1144 }
1145  
1146  
1147 =head2 Classical Functions
1148  
1149 These are the functions that solve polynomials via the classical methods.
1150 Quartic, cubic, quadratic, and even linear equations may be solved with
1151 these functions. They are all exported under the tag "classical".
1152  
1153 L</poly_roots()> will use these functions I<if> the hessenberg option
1154 is set to 0, I<and if> the degree of the polynomial is four or less.
1155  
1156 The leading coefficient C<$a> must always be non-zero for the classical
1157 functions.
1158  
1159 =head3 linear_roots()
1160  
1161 Here for completeness's sake more than anything else. Returns the
1162 solution for
1163  
1164 ax + b = 0
1165  
1166 by returning C<-b/a>. This may be in either a scalar or an array context.
1167  
1168 =cut
1169  
1170 sub linear_roots
1171 9 ▶{
Subroutine linear_roots: called CC=4 SCAR=17.1
Pod documented
1172 9 ▶ my($b, $a) = ($ascending_flag == 0)? reverse @_: @_;
Branch: 1 branch
BranchTrueFalseTotal
$ascending_flag == 0 ? : 0 9 9
1173  
1174 9 ▶ if (abs($a) < $epsilon)
Branch: 1 branch
BranchTrueFalseTotal
if (abs $a < $epsilon) 0 9 9
1175 {
1176 0 carp "The coefficient of the highest power must not be zero!\n";
1177 0 return ();
1178 }
1179  
1180 9 ▶ return wantarray? (-$b/$a): -$b/$a;
Branch: 1 branch
BranchTrueFalseTotal
wantarray ? : 9 0 9
1181 }
1182  
1183  
1184 =head3 quadratic_roots()
1185  
1186 Gives the roots of the quadratic equation
1187  
1188 ax**2 + bx + c = 0
1189  
1190 using the well-known quadratic formula. Returns a two-element list.
1191  
1192 =cut
1193  
1194 sub quadratic_roots
1195 40 ▶{
Subroutine quadratic_roots: called CC=5 SCAR=16.7
Pod documented
1196 40 ▶ my($c, $b, $a) = ($ascending_flag == 0)? reverse @_: @_;
Branch: 1 branch
BranchTrueFalseTotal
$ascending_flag == 0 ? : 0 40 40
1197  
1198 40 ▶ if (abs($a) < $epsilon)
Branch: 1 branch
BranchTrueFalseTotal
if (abs $a < $epsilon) 0 40 40
1199 {
1200 0 carp "The coefficient of the highest power must not be zero!\n";
1201 0 return ();
1202 }
1203  
1204 40 ▶ return (0, -$b/$a) if (abs($c) < $epsilon);
Branch: 1 branch
BranchTrueFalseTotal
if abs $c < $epsilon 2 38 40
1205  
1206 38 my $dis_sqrt = sqrt($b*$b - $a * 4 * $c);
1207  
1208 38 ▶ $dis_sqrt = -$dis_sqrt if ($b < $epsilon); # Avoid catastrophic cancellation.
Branch: 1 branch
BranchTrueFalseTotal
if $b < $epsilon 26 12 38
1209  
1210 38 my $xt = ($b + $dis_sqrt)/-2;
1211  
1212 38 return ($xt/$a, $c/$xt);
1213 }
1214  
1215  
1216 =head3 cubic_roots()
1217  
1218 Gives the roots of the cubic equation
1219  
1220 ax**3 + bx**2 + cx + d = 0
1221  
1222 by the method described by R. W. D. Nickalls (see the L</ACKNOWLEDGMENTS>
1223 section below). Returns a three-element list. The first element will
1224 always be real. The next two values will either be both real or both
1225 complex numbers.
1226  
1227 =cut
1228  
1229 sub cubic_roots
1230 23 ▶{
Subroutine cubic_roots: called CC=8 SCAR=20.8
Pod documented
1231 23 ▶ my($d, $c, $b, $a) = ($ascending_flag == 0)? reverse @_: @_;
Branch: 1 branch
BranchTrueFalseTotal
$ascending_flag == 0 ? : 0 23 23
1232 23 my @x;
1233  
1234 23 ▶ if (abs($a) < $epsilon)
Branch: 1 branch
BranchTrueFalseTotal
if (abs $a < $epsilon) 0 23 23
1235 {
1236 0 carp "The coefficient of the highest power must not be zero!\n";
1237 0 return @x;
1238 }
1239  
1240 #
1241 # We're calling exported functions that also check
1242 # the $ascending_flag. To avoid reversing the reversed,
1243 # temporarily set the flag to zero and reset before returning.
1244 #
1245 23 my $temp_ascending_flag = $ascending_flag;
1246 23 $ascending_flag = 1;
1247  
1248 23 ▶ if (abs($d) < $epsilon)
Branch: 1 branch
BranchTrueFalseTotal
if (abs $d < $epsilon) 2 21 23
1249 {
1250 2 @x = quadratic_roots($c, $b, $a);
1251 2 $ascending_flag = $temp_ascending_flag;
1252 2 return (0, @x);
1253 }
1254  
1255 21 my $xN = -$b/3/$a;
1256 21 my $yN = $d + $xN * ($c + $xN * ($b + $a * $xN));
1257  
1258 21 my $two_a = 2 * $a;
1259 21 my $delta_sq = ($b * $b - 3 * $a * $c)/(9 * $a * $a);
1260 21 my $h_sq = 4/9 * ($b * $b - 3 * $a * $c) * $delta_sq**2;
1261 21 my $dis = $yN * $yN - $h_sq;
1262 21 my $twothirds_pi = (2 * pi)/3;
1263  
1264 #
1265 ### cubic_roots() calculations...
1266 #### $two_a
1267 #### $delta_sq
1268 #### $h_sq
1269 #### $dis
1270 #
1271 21 ▶ if ($dis > $epsilon)
Branch: 2 branches
BranchTrueFalseTotal
if ($dis > $epsilon) { } 10 11 21
elsif ($dis < -$epsilon) { } 7 4 11
1272 {
1273 #
1274 ### Cubic branch 1, $dis is greater than 0...
1275 #
1276 # One real root, two complex roots.
1277 #
1278 10 my $dis_sqrt = sqrt($dis);
1279 10 my $r_p = $yN - $dis_sqrt;
1280 10 my $r_q = $yN + $dis_sqrt;
1281 10 my $p = cbrt( abs($r_p)/$two_a );
1282 10 my $q = cbrt( abs($r_q)/$two_a );
1283  
1284 10 ▶ $p = -$p if ($r_p > 0);
Branch: 1 branch
BranchTrueFalseTotal
if $r_p > 0 1 9 10
1285 10 ▶ $q = -$q if ($r_q > 0);
Branch: 1 branch
BranchTrueFalseTotal
if $r_q > 0 7 3 10
1286  
1287 10 $x[0] = $xN + $p + $q;
1288 10 $x[1] = $xN + $p * exp($twothirds_pi * i)
1289 + $q * exp(-$twothirds_pi * i);
1290 10 $x[2] = ~$x[1];
1291 }
1292 elsif ($dis < -$epsilon)
1293 {
1294 #
1295 ### Cubic branch 2, $dis is less than 0...
1296 #
1297 # Three distinct real roots.
1298 #
1299 7 my $theta = acos(-$yN/sqrt($h_sq))/3;
1300 7 my $delta = sqrt($b * $b - 3 * $a * $c)/(3 * $a);
1301 7 my $two_d = 2 * $delta;
1302  
1303 7 @x = ($xN + $two_d * cos($theta),
1304 $xN + $two_d * cos($twothirds_pi - $theta),
1305 $xN + $two_d * cos($twothirds_pi + $theta));
1306 }
1307 else
1308 {
1309 #
1310 ### Cubic branch 3, $dis equals 0, within epsilon...
1311 #
1312 # abs($dis) <= $epsilon (effectively zero).
1313 #
1314 # Three real roots (two or three equal).
1315 #
1316 4 my $delta = cbrt($yN/$two_a);
1317  
1318 4 @x = ($xN + $delta, $xN + $delta, $xN - 2 * $delta);
1319 }
1320  
1321 21 $ascending_flag = $temp_ascending_flag;
1322 21 return @x;
1323 }
1324  
1325 =head3 quartic_roots()
1326  
1327 Gives the roots of the quartic equation
1328  
1329 ax**4 + bx**3 + cx**2 + dx + e = 0
1330  
1331 using Ferrari's method (see the L</ACKNOWLEDGMENTS> section below). Returns
1332 a four-element list. The first two elements will be either
1333 both real or both complex. The next two elements will also be alike in
1334 type.
1335  
1336 =cut
1337  
1338 sub quartic_roots
1339 22 ▶{
Subroutine quartic_roots: called CC=6 SCAR=18.2
Pod documented
1340 22 ▶ my($e, $d, $c, $b, $a) = ($ascending_flag == 0)? reverse @_: @_;
Branch: 1 branch
BranchTrueFalseTotal
$ascending_flag == 0 ? : 0 22 22
1341 22 my @x = ();
1342  
1343 22 ▶ if (abs($a) < $epsilon)
Branch: 1 branch
BranchTrueFalseTotal
if (abs $a < $epsilon) 0 22 22
1344 {
1345 0 carp "Coefficient of highest power must not be zero!\n";
1346 0 return @x;
1347 }
1348  
1349 #
1350 # We're calling exported functions that also check
1351 # the $ascending_flag. To avoid reversing the reversed,
1352 # temporarily set the flag to one and reset before returning.
1353 #
1354 22 my $temp_ascending_flag = $ascending_flag;
1355 22 $ascending_flag = 1;
1356  
1357 22 ▶ if (abs($e) < $epsilon)
Branch: 1 branch
BranchTrueFalseTotal
if (abs $e < $epsilon) 0 22 22
1358 {
1359 0 @x = cubic_roots($d, $c, $b, $a);
1360 0 $ascending_flag = $temp_ascending_flag;
1361 0 return (0, @x);
1362 }
1363  
1364 #
1365 # First step: Divide by the leading coefficient.
1366 #
1367 22 $b /= $a;
1368 22 $c /= $a;
1369 22 $d /= $a;
1370 22 $e /= $a;
1371  
1372 #
1373 # Second step: simplify the equation to the
1374 # "resolvent cubic" y**4 + fy**2 + gy + h.
1375 #
1376 # (This is done by setting x = y - b/4).
1377 #
1378 22 my $b4 = $b/4;
1379  
1380 #
1381 # The f, g, and h values are:
1382 #
1383 22 my $f = $c -
1384 6 * $b4 * $b4;
1385 22 my $g = $d +
1386 2 * $b4 * (-$c + 4 * $b4 * $b4);
1387 22 my $h = $e +
1388 $b4 * (-$d + $b4 * ($c - 3 * $b4 * $b4));
1389  
1390 #
1391 ### quartic_roots calculations
1392 #### $b4
1393 #### $f
1394 #### $g
1395 #### $h
1396 #
1397 22 ▶ if (abs($h) < $epsilon)
Branch: 2 branches
BranchTrueFalseTotal
if (abs $h < $epsilon) { } 2 20 22
elsif (abs $g * $g < $epsilon) { } 16 4 20
1398 {
1399 #
1400 ### Quartic branch 1, $h equals 0, within epsilon...
1401 #
1402 # Special case: h == 0. We have a cubic times y.
1403 #
1404 2 @x = (0, cubic_roots($g, $f, 0, 1));
1405 }
1406 elsif (abs($g * $g) < $epsilon)
1407 {
1408 #
1409 ### Quartic branch 2, $g equals 0, within epsilon...
1410 #
1411 # Another special case: g == 0. We have a quadratic
1412 # with y-squared.
1413 #
1414 # (We check $g**2 because that's what the constant
1415 # value actually is in Ferrari's method, and it is
1416 # possible for $g to be outside of epsilon while
1417 # $g**2 is inside, i.e., "zero").
1418 #
1419 16 my($p, $q) = quadratic_roots($h, $f, 1);
1420 16 $p = sqrt($p);
1421 16 $q = sqrt($q);
1422 16 @x = ($p, -$p, $q, -$q);
1423 }
1424 else
1425 {
1426 #
1427 ### Quartic branch 3, Ferrari's method...
1428 #
1429 # Special cases don't apply, so continue on with Ferrari's
1430 # method. This involves setting up the resolvent cubic
1431 # as the product of two quadratics.
1432 #
1433 # After setting up conditions that guarantee that the
1434 # coefficients come out right (including the zero value
1435 # for the third-power term), we wind up with a 6th
1436 # degree polynomial with, fortunately, only even-powered
1437 # terms. In other words, a cubic with z = y**2.
1438 #
1439 # Take a root of that equation, and get the
1440 # quadratics from it.
1441 #
1442 4 my $z;
1443 4 ($z, undef, undef) = cubic_roots(-$g*$g, $f*$f - 4*$h, 2*$f, 1);
1444  
1445 #### $z
1446  
1447 4 my $alpha = sqrt($z);
1448 4 my $rho = $g/$alpha;
1449 4 my $beta = ($f + $z - $rho)/2;
1450 4 my $gamma = ($f + $z + $rho)/2;
1451  
1452 4 @x = quadratic_roots($beta, $alpha, 1);
1453 4 push @x, quadratic_roots($gamma, -$alpha, 1);
1454 }
1455  
1456 22 $ascending_flag = $temp_ascending_flag;
1457 22 return ($x[0] - $b4, $x[1] - $b4, $x[2] - $b4, $x[3] - $b4);
1458 }
1459  
1460 =head2 Sturm Functions
1461  
1462 These are the functions that create and make use of the Sturm sequence.
1463 They are all exported under the tag "sturm".
1464  
1465 =head3 poly_real_root_count()
1466  
1467 Return the number of I<unique>, I<real> roots of the polynomial.
1468  
1469 $unique_roots = poly_real_root_count(@coefficients);
1470  
1471 For example, the equation C<(x + 3)**3> forms the polynomial
1472 C<x**3 + 9x**2 + 27x + 27>, but since all three of its roots are identical,
1473 C<poly_real_root_count(1, 9, 27, 27)> will return 1.
1474  
1475 Likewise, C<poly_real_root_count(1, -8, 25)> will return 0 because the two roots
1476 of C<x**2 -8x + 25> are both complex.
1477  
1478 This function is the all-in-one function to use instead of
1479  
1480 my @chain = poly_sturm_chain(@coefficients);
1481  
1482 return sturm_sign_count(sturm_sign_minus_inf(\@chain)) -
1483 sturm_sign_count(sturm_sign_plus_inf(\@chain));
1484  
1485 if you don't intend to use the Sturm chain for anything else.
1486  
1487 =cut
1488  
1489 sub poly_real_root_count
1490 17 ▶{
Subroutine poly_real_root_count: called CC=1 SCAR=0.0
Pod documented
1491 17 my @coefficients = @_;
1492  
1493 17 my @chain = poly_sturm_chain(@coefficients);
1494  
1495 17 return sturm_sign_count(sturm_sign_minus_inf(\@chain)) -
1496 sturm_sign_count(sturm_sign_plus_inf(\@chain));
1497 }
1498  
1499 =head3 sturm_real_root_range_count()
1500  
1501 Return the number of I<unique>, I<real> roots of the polynomial between two X values.
1502  
1503 my($x0, $x1) = (0, 1000);
1504  
1505 my @chain = poly_sturm_chain(@coefficients);
1506 $root_count = sturm_real_root_range_count(\@chain, $x0, $x1);
1507  
1508 This is equivalent to:
1509  
1510 my($x0, $x1) = (0, 1000);
1511  
1512 my @chain = poly_sturm_chain(@coefficients);
1513 my @signs = sturm_sign_chain(\@chain, [$x0, $x1]);
1514 $root_count = sturm_sign_count(@{$signs[0]}) - sturm_sign_count(@{$signs[1]});
1515  
1516 =cut
1517  
1518 sub sturm_real_root_range_count
1519 156 ▶{
Subroutine sturm_real_root_range_count: called CC=1 SCAR=0.0
Pod documented
1520 156 my($chain_ref, $x0, $x1) = @_;
1521  
1522 156 my @signs = sturm_sign_chain($chain_ref, [$x0, $x1]);
1523  
1524 156 my $count0 = sturm_sign_count(@{$signs[0]});
1525 156 my $count1 = sturm_sign_count(@{$signs[1]});
1526  
1527 #
1528 ###### (from, to): join(", ", ($x0, $x1))
1529 ###### sign count from: $count0
1530 ###### sign count to: $count1
1531 #
1532 156 return $count0 - $count1;
1533 }
1534  
1535  
1536 =head3 sturm_bisection()
1537  
1538 Finds the boundaries around the roots of a polynomial function,
1539 using the root count method of Sturm.
1540  
1541 @boundaries = sturm_bisection(\@chain, $from, $to);
1542  
1543 The elements of @boundaries will be a list of two-element arrays, each
1544 one bracketing a root.
1545  
1546 It will not bracket complex roots.
1547  
1548 This allows you to use a different root-finding function than laguerre(),
1549 which is the default function used by sturm_bisection_roots().
1550  
1551 =cut
1552  
1553 sub sturm_bisection
1554 21 ▶{
Subroutine sturm_bisection: called CC=9 SCAR=23.4
Pod documented
1555 21 my($chain_ref, $from, $to) = @_;
1556 21 my(@coefficients) = @{${$chain_ref}[0]};
1557 21 my @boundaries;
1558  
1559 #
1560 #### @coefficients
1561 #
1562 #
1563 # If we have a linear equation, just solve the thing. We're not
1564 # going to find a useful second derivative, after all. (Which
1565 # would raise the question of why we're here without a useful
1566 # Sturm chain, but never mind...)
1567 #
1568 21 ▶ if ($#coefficients == 1)
Branch: 1 branch
BranchTrueFalseTotal
if ($#coefficients == 1) 0 21 21
1569 {
1570 0 my $root = linear_roots(@coefficients);
1571  
1572 #
1573 # But make sure the root is within the
1574 # asked-for range.
1575 #
1576 0 ▶ return () if ($root < $from or $root > $to);
Branch: 1 branch
BranchTrueFalseTotal
if $root < $from or $root > $to 0 0 0
Condition0%0/3
$root < $from or $root > $to
l!l&&r!l&&!r
000
MC/DC0%0/2
$root < $from or $root > $to
$root < $from $root > $to
Truth table0%0/3
A or B
A= $root < $fromB= $root > $to
ABresult
1X1
011
000
1577 0 return ([$root, $root]);
1578 }
1579  
1580 #
1581 # Do Sturm bisection here.
1582 #
1583 21 my $range_count = sturm_real_root_range_count($chain_ref, $from, $to);
1584  
1585 #
1586 # If we're down to one root in this range, use Laguerre's method
1587 # to hunt it down.
1588 #
1589 21 ▶ return () if ($range_count == 0);
Branch: 1 branch
BranchTrueFalseTotal
if $range_count == 0 0 21 21
1590 21 ▶ return ([$from, $to]) if ($range_count == 1);
Branch: 1 branch
BranchTrueFalseTotal
if $range_count == 1 13 8 21
1591  
1592 #
1593 # More than one root in this range, so subdivide
1594 # until each root has its own range.
1595 #
1596 8 my $its = 0;
1597  
1598 ROOT:
1599 8 for (;;)
1600 {
1601 59 my $mid = ($to + $from)/2.0;
1602 59 my $frommid_count = sturm_real_root_range_count($chain_ref, $from, $mid);
1603 59 my $midto_count = sturm_real_root_range_count($chain_ref, $mid, $to);
1604  
1605 #
1606 #### $its
1607 #### $from
1608 #### $mid
1609 #### $to
1610 #### $frommid_count
1611 #### $midto_count
1612 #
1613  
1614 #
1615 # Bisect again if we only narrowed down to a range
1616 # containing all the roots.
1617 #
1618 59 ▶ if ($frommid_count == 0)
Branch: 2 branches
BranchTrueFalseTotal
if ($frommid_count == 0) { } 39 20 59
elsif ($midto_count == 0) { } 12 8 20
1619 {
1620 39 $from = $mid;
1621 }
1622 elsif ($midto_count == 0)
1623 {
1624 12 $to = $mid;
1625 }
1626 else
1627 {
1628 #
1629 # We've divided the roots between two ranges. Do it
1630 # again until each range has a single root in it.
1631 #
1632 8 push @boundaries, sturm_bisection($chain_ref, $from, $mid);
1633 8 push @boundaries, sturm_bisection($chain_ref, $mid, $to);
1634 8 last ROOT;
1635 }
1636 51 ▶ croak "Too many iterations ($its) at mid=$mid\n" if ($its >= $iteration{sturm_bisection});
Branch: 1 branch
BranchTrueFalseTotal
if $its >= $iteration{"sturm_bisection"} 0 51 51
1637 51 $its++;
1638 }
1639 8 return @boundaries;
1640 }
1641  
1642  
1643 =head3 sturm_bisection_roots()
1644  
1645 Return the I<real> roots counted by L</sturm_real_root_range_count()>.
1646 Uses L</sturm_bisection()> to bracket the roots of the polynomial,
1647 then uses L</laguerre()> to close in on each root.
1648  
1649 my($from, $to) = (-1000, 0);
1650 my @chain = poly_sturm_chain(@coefficients);
1651 my @roots = sturm_bisection_roots(\@chain, $from, $to);
1652  
1653 As it is using the Sturm functions, it will find only the real roots.
1654  
1655 =cut
1656  
1657 sub sturm_bisection_roots
1658 5 ▶{
Subroutine sturm_bisection_roots: called CC=2 SCAR=6.9
Pod documented
1659 5 my($chain_ref, $from, $to) = @_;
1660 5 my $cref0 = ${$chain_ref}[0];
1661 5 my @boundaries = sturm_bisection($chain_ref, $from, $to);
1662 5 my @roots;
1663  
1664 5 my $temp_ascending_flag = $ascending_flag;
1665 5 $ascending_flag = 1;
1666  
1667 #
1668 #### sturm_bisection() returns: @boundaries
1669 #
1670 5 for my $bracket (@boundaries)
1671 {
1672 13 my ($left, $right) = @$bracket;
1673 13 push @roots, laguerre($cref0, ($left + $right)/2.0);
1674 }
1675  
1676 5 $ascending_flag = $temp_ascending_flag;
1677  
1678 5 return @roots;
1679 }
1680  
1681  
1682 =head3 poly_sturm_chain()
1683  
1684 Returns the chain of Sturm functions used to evaluate the number of roots of a
1685 polynomial in a range of X values. The chain is a list of coefficient
1686 references, the coefficients being stored in ascending order.
1687  
1688 If you feed in a sequence of X values to the Sturm functions, you can tell where
1689 the (real, not complex) roots of the polynomial are by counting the number of
1690 times the Y values change sign.
1691  
1692 See L</poly_real_root_count()> above for an example of its use.
1693  
1694 =cut
1695  
1696 sub poly_sturm_chain
1697 55 ▶{
Subroutine poly_sturm_chain: called CC=8 SCAR=20.8
Pod documented
1698 55 my @coefficients = @_;
1699 55 my $degree = $#coefficients;
1700 55 my (@chain, @remd);
1701 55 my ($f1, $f2);
1702  
1703 55 ▶ @coefficients = reverse @coefficients unless ($ascending_flag);
Branch: 1 branch
BranchTrueFalseTotal
unless $ascending_flag 16 39 55
1704  
1705 55 $f1 = [@coefficients];
1706 55 $f2 = pl_derivative(\@coefficients);
1707  
1708 #
1709 # The first link of the chain.
1710 #
1711 55 push @chain, $f1;
1712 55 ▶ push @chain, $f2 if ($degree > 0);
Branch: 1 branch
BranchTrueFalseTotal
if $degree > 0 52 3 55
1713  
1714 55 ▶ if ($degree > 1)
Branch: 1 branch
BranchTrueFalseTotal
if ($degree > 1) 49 6 55
1715 {
1716 #
1717 ###### poly_sturm_chain chain before do loop:
1718 ###### @chain
1719 #
1720 do
1721 49 ▶ {
Branch: 1 branch
BranchTrueFalseTotal
$#remd > 0 and do { do { () = pl_div($f1, $f2); @remd = @{$r;}; pop @remd while @remd and abs $remd[$#remd] < $epsilon; $f1 = $f2; $f2 = @remd ? [map({$_ * -1;} @remd)] : [0]; push @chain, $f2 } } 28 49 77
1722 77 my ($q, $r) = pl_div($f1, $f2);
1723  
1724 #
1725 # Remove any leading zeros in the remainder.
1726 #
1727 77 @remd = @{$r};
1728 77 ▶ pop @remd while (@remd and abs($remd[$#remd]) < $epsilon);
Branch: 1 branch
BranchTrueFalseTotal
@remd and abs $remd[$#remd] < $epsilon and do { pop @remd } 43 77 120
Condition100%3/3
@remd and abs $remd[$#remd] < $epsilon
!ll&&!rl&&r
47343
MC/DC100%2/2
@remd and abs $remd[$#remd] < $epsilon
@remd abs $remd[$#remd] < $epsilon
Truth table100%3/3
A and B
A= @remdB= abs $remd[$#remd] < $epsilon
ABresult
0X0
100
111
1729  
1730 77 $f1 = $f2;
1731 77 ▶ $f2 = (@remd)? [map {$_ * -1} @remd]: [0];
Branch: 1 branch
BranchTrueFalseTotal
@remd ? : 73 4 77
1732 77 push @chain, $f2;
1733 }
1734 while ($#remd > 0);
1735 }
1736  
1737 #
1738 ###### poly_sturm_chain:
1739 ###### @chain
1740 #
1741 55 return @chain;
1742 }
1743  
1744 =head3 sturm_sign_count()
1745  
1746 Counts and returns the number of sign changes in a sequence of signs,
1747 such as those returned by the L</Sturm Sign Sequence Functions>
1748  
1749 See L</poly_real_root_count()> and L</sturm_real_root_range_count()> for
1750 examples of its use.
1751  
1752 =cut
1753  
1754 sub sturm_sign_count
1755 346 ▶{
Subroutine sturm_sign_count: called CC=3 SCAR=11.0
Pod documented
1756 346 my @sign_seq = @_;
1757 346 my $scnt = 0;
1758  
1759 346 my $s1 = shift @sign_seq;
1760 346 for my $s2 (@sign_seq)
1761 {
1762 1060 ▶ $scnt++ if ($s1 != $s2);
Branch: 1 branch
BranchTrueFalseTotal
if $s1 != $s2 627 433 1060
1763 1060 $s1 = $s2;
1764 }
1765  
1766 346 return $scnt;
1767 }
1768  
1769  
1770 =head3 Sturm Sign Sequence Functions
1771  
1772 =head4 sturm_sign_chain()
1773  
1774 =head4 sturm_sign_minus_inf()
1775  
1776 =head4 sturm_sign_plus_inf()
1777  
1778 These functions return the array of signs that are used by the functions
1779 L</poly_real_root_count()> and L</sturm_real_root_range_count()> to find
1780 the number of real roots in a polynomial.
1781  
1782 In normal use you will probably never need to use them, unless you want
1783 to examine the internals of the Sturm functions:
1784  
1785 #
1786 # Examine the sign changes that occur at each endpoint of
1787 # the x range.
1788 #
1789 my(@coefficients) = (1, 4, 7, 23);
1790 my(@xvals) = (-12, 12);
1791  
1792 my @chain = poly_sturm_chain( @coefficients);
1793 my @signs = sturm_sign_chain(\@chain, \@xvals); # An array of arrays.
1794  
1795 print "\nPolynomial: [", join(", ", @coefficients), "]\n";
1796  
1797 for my $j (0..$#signs)
1798 {
1799 my @s = @{$signs[$j]};
1800 print $xval[$j], "\n",
1801 "\t", join(", ", @s), "], sign count = ",
1802 sturm_sign_count(@s), "\n\n";
1803 }
1804  
1805 Similar examinations can be made at plus and minus infinity:
1806  
1807 #
1808 # Examine the sign changes that occur between plus and minus
1809 # infinity.
1810 #
1811 my @coefficients = (1, 4, 7, 23);
1812  
1813 my @chain = poly_sturm_chain( @coefficients);
1814 my @smi = sturm_sign_minus_inf(\@chain);
1815 my @spi = sturm_sign_plus_inf(\@chain);
1816  
1817 print "\nPolynomial: [", join(", ", @coefficients), "]\n";
1818  
1819 print "Minus Inf:\n",
1820 "\t", join(", ", @smi), "], sign count = ",
1821 sturm_sign_count(@smi), "\n\n";
1822  
1823 print "Plus Inf:\n",
1824 "\t", join(", ", @spi), "], sign count = ",
1825 sturm_sign_count(@spi), "\n\n";
1826  
1827 =cut
1828  
1829 #
1830 # @signs = sturm_minus_inf(\@chain);
1831 #
1832 # Return an array of signs from the chain at minus infinity.
1833 #
1834 # In the :sturm export set.
1835 #
1836 sub sturm_sign_minus_inf
1837 17 ▶{
Subroutine sturm_sign_minus_inf: called CC=3 SCAR=11.0
Pod documented
1838 17 my($chain_ref) = @_;
1839 17 my @signs;
1840  
1841 17 for my $c (@$chain_ref)
1842 {
1843 56 my @coefficients = @$c;
1844 56 ▶ push @signs, sign($coefficients[$#coefficients]) *
Branch: 1 branch
BranchTrueFalseTotal
($#coefficients & 1) == 1 ? : 24 32 56
1845 ((($#coefficients & 1) == 1)? -1: 1);
1846 }
1847  
1848 17 return @signs;
1849 }
1850  
1851 #
1852 # @signs = sturm_plus_inf(\@chain);
1853 #
1854 # Return an array of signs from the chain at infinity.
1855 #
1856 # In the :sturm export set.
1857 #
1858 sub sturm_sign_plus_inf
1859 17 ▶{
Subroutine sturm_sign_plus_inf: called CC=2 SCAR=6.9
Pod documented
1860 17 my($chain_ref) = @_;
1861 17 my @signs;
1862  
1863 17 for my $c (@$chain_ref)
1864 {
1865 56 my @coefficients = @$c;
1866 56 push @signs, sign($coefficients[$#coefficients]);
1867 }
1868  
1869 17 return @signs;
1870 }
1871  
1872 #
1873 # @sign_chains = sturm_sign_chain(\@chain, \@xvals);
1874 #
1875 # Return an array of signs for each x-value passed in each function in
1876 # the Sturm chain.
1877 #
1878 # In the :sturm export set.
1879 #
1880 sub sturm_sign_chain
1881 156 ▶{
Subroutine sturm_sign_chain: called CC=4 SCAR=13.9
Pod documented
1882 156 my($chain_ref, $xvals_ref) = @_;
1883 156 my $fn_count = $#$chain_ref;
1884 156 my $x_count = $#$xvals_ref;
1885 156 my @sign_chain;
1886  
1887 156 push @sign_chain, [] for (0..$x_count);
1888  
1889 156 for my $p_ref (@$chain_ref)
1890 {
1891 647 my @ysigns = sign(pl_evaluate($p_ref, $xvals_ref));
1892  
1893 #
1894 # We just retrieved the signs of a single function across
1895 # our x-vals. We want it the other way around; signs listed
1896 # by x-val across functions.
1897 #
1898 # (list of lists)
1899 # |
1900 # v
1901 # f0 f1 f2 f3 f4 ...
1902 # x0 - - + - + (list 0)
1903 #
1904 # x1 + - - + + (list 1)
1905 #
1906 # x2 + - + + + (list 2)
1907 #
1908 # ...
1909 #
1910 647 for my $j (0..$x_count)
1911 {
1912 1294 push @{$sign_chain[$j]}, shift @ysigns;
1913 }
1914 }
1915  
1916 #
1917 ###### sturm_sign_chain() returns
1918 ###### @sign_chain: @sign_chain
1919 #
1920 156 return @sign_chain;
1921 }
1922  
1923  
1924 =head2 Utility Functions
1925  
1926 These are internal functions used by the other functions listed above
1927 that may also be useful to the user, or which affect the behavior of
1928 other functions. They are all exported under the tag "utility".
1929  
1930 =head3 epsilon()
1931  
1932 Returns the machine epsilon value that was calculated when this module was
1933 loaded.
1934  
1935 The value may be changed, although this in general is not recommended.
1936  
1937 my $old_epsilon = epsilon($new_epsilon);
1938  
1939 The previous value of epsilon may be saved to be restored later.
1940  
1941 The Wikipedia article at L<http://en.wikipedia.org/wiki/Machine_epsilon/> has
1942 more information on the subject.
1943  
1944 =cut
1945  
1946 sub epsilon
1947 0 ▶{
Subroutine epsilon: not called CC=2 SCAR=17.9
Pod documented
1948 0 my $eps = $epsilon;
1949 0 ▶ $epsilon = $_[0] if (scalar @_ > 0);
Branch: 1 branch
BranchTrueFalseTotal
if scalar @_ > 0 0 0 0
1950 0 return $eps;
1951 }
1952  
1953 =head3 laguerre()
1954  
1955 A numerical method for finding a root of an equation, especially made
1956 for polynomials.
1957  
1958 @roots = laguerre(\@coefficients, \@xvalues);
1959 push @roots, laguerre(\@coefficients, $another_xvalue);
1960  
1961 For each x value the function will attempt to find a root closest to it.
1962 The function will return real roots only.
1963  
1964 This is the function used by L</sturm_bisection_roots()> after using
1965 L</sturm_bisection()> to narrow its search to a range containing a single
1966 root.
1967  
1968 =cut
1969  
1970 sub laguerre
1971 16 ▶{
Subroutine laguerre: called CC=9 SCAR=22.0
Pod documented
1972 17 ▶ no Math::Complex;
Subroutine BEGIN: called CC=1 SCAR=0.0
1973 16 my($p_ref, $xval_ref) = @_;
1974 16 my $n = $#$p_ref;
1975 16 my @xvalues;
1976 my @roots;
1977  
1978 16 ▶ $p_ref = [reverse @$p_ref] unless ($ascending_flag);
Branch: 1 branch
BranchTrueFalseTotal
unless $ascending_flag 0 16 16
1979  
1980 #
1981 # Allow some flexibility in sending the x-values.
1982 #
1983 16 ▶ if (ref $xval_ref eq "ARRAY")
Branch: 1 branch
BranchTrueFalseTotal
if (ref $xval_ref eq 'ARRAY') { } 3 13 16
1984 {
1985 3 @xvalues = @$xval_ref;
1986 }
1987 else
1988 {
1989 #
1990 # It could happen. Someone might type \$x instead of $x.
1991 #
1992 13 ▶ @xvalues = ((ref $xval_ref eq "SCALAR")? $$xval_ref: $xval_ref);
Branch: 1 branch
BranchTrueFalseTotal
ref $xval_ref eq 'SCALAR' ? : 0 13 13
1993 }
1994  
1995 16 for my $x (@xvalues)
1996 {
1997 #
1998 #### laguerre looking near: $x
1999 #### Coefficient: @$p_ref
2000 #### Degree: $n
2001 #
2002 21 my $its = 0;
2003  
2004 ROOT:
2005 21 for (;;)
2006 {
2007 #
2008 # Get the values of the function and its first and
2009 # second derivatives at X.
2010 #
2011 95 my($y, $dy, $d2y) = pl_dxevaluate($p_ref, $x);
2012  
2013 95 ▶ if (abs($y) <= $tolerance{laguerre})
Branch: 1 branch
BranchTrueFalseTotal
if (abs $y <= $tolerance{"laguerre"}) 20 75 95
2014 {
2015 20 push @roots, $x;
2016 20 last ROOT;
2017 }
2018  
2019 #
2020 #### At Iteration: $its
2021 #### x: $x
2022 #### f(x): $y
2023 #### f'(x): $dy
2024 #### f''(x): $d2y
2025 #
2026 75 my $g = $dy/$y;
2027 75 my $h = $g * $g - $d2y/$y;
2028 75 my $f = sqrt(($n - 1) * ($n * $h - $g*$g));
2029 75 ▶ $f = - $f if (abs($g - $f) > abs($g + $f));
Branch: 1 branch
BranchTrueFalseTotal
if abs $g - $f > abs $g + $f 43 32 75
2030  
2031 #
2032 #### g: $g
2033 #### h: $h
2034 #### f: $f
2035 #
2036 # Divide by the largest value of $g plus
2037 # $f, bearing in mind that $f is the result
2038 # of a square root function and may be positive
2039 # or negative.
2040 #
2041 # Use the abs() function to determine size
2042 # since $g or $f may be complex numbers.
2043 #
2044 75 my $dx = $n/($g + $f);
2045  
2046 75 $x -= $dx;
2047 75 ▶ if (abs($dx) <= $tolerance{laguerre})
Branch: 1 branch
BranchTrueFalseTotal
if (abs $dx <= $tolerance{"laguerre"}) 1 74 75
2048 {
2049 1 push @roots, $x;
2050 1 last ROOT;
2051 }
2052  
2053 74 ▶ croak "Too many iterations ($its) at dx=$dx\n" if ($its >= $iteration{laguerre});
Branch: 1 branch
BranchTrueFalseTotal
if $its >= $iteration{"laguerre"} 0 74 74
2054 74 $its++;
2055 }
2056  
2057 ### root found at iteration $its
2058 #### $x
2059 }
2060  
2061 16 return @roots;
2062 }
2063  
2064  
2065 =head3 newtonraphson()
2066  
2067 Like L</laguerre()>, a numerical method for finding a root of an equation.
2068  
2069 @roots = newtonraphson(\@coefficients, \@xvalues);
2070 push @roots, newtonraphson(\@coefficients, $another_xvalue);
2071  
2072 For each x value the function will attempt to find a root closest to it.
2073 The function will return real roots only.
2074  
2075 This function is provided as an alternative to laguerre(). It is not
2076 used internally by any other functions.
2077  
2078 =cut
2079  
2080 sub newtonraphson
2081 2 ▶{
Subroutine newtonraphson: called CC=7 SCAR=19.9
Pod documented
2082 17 ▶ no Math::Complex;
Subroutine BEGIN: called CC=1 SCAR=0.0
2083 2 my($p_ref, $xval_ref) = @_;
2084 2 my $n = $#$p_ref;
2085 2 my @xvalues;
2086 my @roots;
2087  
2088 2 ▶ $p_ref = [reverse @$p_ref] unless ($ascending_flag);
Branch: 1 branch
BranchTrueFalseTotal
unless $ascending_flag 0 2 2
2089  
2090 #
2091 # Allow some flexibility in sending the x-values.
2092 #
2093 2 ▶ if (ref $xval_ref eq "ARRAY")
Branch: 1 branch
BranchTrueFalseTotal
if (ref $xval_ref eq 'ARRAY') { } 2 0 2
2094 {
2095 2 @xvalues = @$xval_ref;
2096 }
2097 else
2098 {
2099 #
2100 # It could happen. Someone might type \$x instead of $x.
2101 #
2102 0 ▶ @xvalues = ((ref $xval_ref eq "SCALAR")? $$xval_ref: $xval_ref);
Branch: 1 branch
BranchTrueFalseTotal
ref $xval_ref eq 'SCALAR' ? : 0 0 0
2103 }
2104  
2105 #
2106 ### newtonraphson()
2107 #### @xvalues
2108 #
2109 2 for my $x (@xvalues)
2110 {
2111 6 my $its = 0;
2112  
2113 ROOT:
2114 6 for (;;)
2115 {
2116 #
2117 # Get the values of the function and its
2118 # first derivative at X.
2119 #
2120 40 my($y, $dy, undef) = pl_dxevaluate($p_ref, $x);
2121 40 my $dx = $y/$dy;
2122 40 $x -= $dx;
2123  
2124 40 ▶ if (abs($dx) <= $tolerance{newtonraphson})
Branch: 1 branch
BranchTrueFalseTotal
if (abs $dx <= $tolerance{"newtonraphson"}) 6 34 40
2125 {
2126 6 push @roots, $x;
2127 6 last ROOT;
2128 }
2129  
2130 #
2131 #### At Iteration: $its
2132 #### x: $x
2133 #### f(x): $y
2134 #### f'(x): $dy
2135 #
2136 34 ▶ croak "Too many iterations ($its) at dx=$dx\n" if ($its >= $iteration{newtonraphson});
Branch: 1 branch
BranchTrueFalseTotal
if $its >= $iteration{"newtonraphson"} 0 34 34
2137 34 $its++;
2138 }
2139  
2140 ### root found at iteration $its
2141 #### $x
2142 }
2143  
2144 2 return @roots;
2145 }
2146  
2147 =head3 poly_iteration()
2148  
2149 Sets the limit to the number of iterations that a solving method may go
2150 through before giving up trying to find a root. Each method of root-finding
2151 used by L</poly_roots()>, L</sturm_bisection_roots()>, and L</laguerre()>
2152 has its own iteration limit, which may be found, like L</poly_option()>,
2153 simply by looking at the return value of poly_iteration().
2154  
2155 #
2156 # Get all of the current iteration limits.
2157 #
2158 my %its_limits = poly_iteration();
2159  
2160 #
2161 # Double the limit for the hessenberg method, but set the limit
2162 # for Laguerre's method to 20.
2163 #
2164 my %old_limits = poly_iteration(hessenberg => $its_limits{hessenberg} * 2,
2165 laguerre => 20);
2166  
2167 #
2168 # Reset the limits with the former values, but save the values we had
2169 # for later.
2170 #
2171 my %hl_limits = poly_iteration(%old_limits);
2172  
2173 There are iteration limit values for:
2174  
2175 =over 4
2176  
2177 =item 'hessenberg'
2178  
2179 The numeric method used by poly_roots(), if the hessenberg option is set.
2180 Its default value is 60.
2181  
2182 =item 'laguerre'
2183  
2184 The numeric method used by L</laguerre()>. Laguerre's method is used within
2185 sturm_bisection_roots() once it has narrowed its search in on an individual
2186 root, and of course laguerre() may be called independently. Its default value
2187 is 60.
2188  
2189 =item 'newtonraphson'
2190  
2191 The numeric method used by newtonraphson(). The Newton-Raphson method is offered
2192 as an alternative to Laguerre's method. Its default value is 60.
2193  
2194 =item 'sturm_bisection'
2195  
2196 The bisection method used to find roots within a range. Its default value
2197 is 100.
2198  
2199 =back
2200  
2201 =cut
2202  
2203 sub poly_iteration
2204 13 ▶{
Subroutine poly_iteration: called CC=5 SCAR=16.4
Pod documented
2205 13 my %limits = @_;
2206 13 my %old_limits;
2207  
2208 13 ▶ return %iteration if (scalar @_ == 0);
Branch: 1 branch
BranchTrueFalseTotal
if scalar @_ == 0 7 6 13
2209  
2210 6 for my $k (keys %limits)
2211 {
2212 #
2213 # If this is a real iteration limit, save its old
2214 # value, then set it.
2215 #
2216 6 ▶ if (exists $iteration{$k})
Branch: 1 branch
BranchTrueFalseTotal
if (exists $iteration{$k}) { } 6 0 6
2217 {
2218 6 my $val = abs(int($limits{$k}));
2219
2220 6 ▶ carp "poly_iteration(): Unreasonably small value for $k => $val\n" if ($val < 10);
Branch: 1 branch
BranchTrueFalseTotal
if $val < 10 0 6 6
2221  
2222 6 $old_limits{$k} = $iteration{$k};
2223 6 $iteration{$k} = $val;
2224 }
2225 else
2226 {
2227 0 croak "poly_iteration(): unknown key $k.";
2228 }
2229 }
2230  
2231 6 return %old_limits;
2232 }
2233  
2234 =head3 poly_tolerance()
2235  
2236 Set the degree of accuracy needed for comparisons to be equal or roots
2237 to be found. Amongst the root finding functions this currently only
2238 affects laguerre() and newtonraphson(), as the Hessenberg matrix method
2239 determines how close it needs to get using a complicated formula based
2240 on L</epsilon()>.
2241  
2242 #
2243 # Print the tolerances.
2244 #
2245 my %tolerances = poly_tolerance();
2246 print "Default tolerances:\n";
2247 for my $k (keys %tolerances)
2248 {
2249 print "$k => ", $tolerances{$k}, "\n";
2250 }
2251  
2252 #
2253 # Quadruple the tolerance for Laguerre's method.
2254 #
2255 poly_tolerance(laguerre => 4 * $tolerances{laguerre});
2256  
2257 Tolerances may be set for:
2258  
2259 =over 4
2260  
2261 =item 'laguerre'
2262  
2263 The numeric method used by laguerre(). Laguerre's method is used within
2264 sturm_bisection_roots() once an individual root has been found within a
2265 range, and of course it may be called independently.
2266  
2267 =item 'newtonraphson'
2268  
2269 The numeric method used by newtonraphson(). Newton-Raphson is, like
2270 Laguerre's method, a method for finding a root near the starting X value.
2271  
2272 =back
2273  
2274 =cut
2275  
2276 sub poly_tolerance
2277 5 ▶{
Subroutine poly_tolerance: called CC=4 SCAR=14.0
Pod documented
2278 5 my %tols = @_;
2279 5 my %old_tols;
2280  
2281 5 ▶ return %tolerance if (scalar @_ == 0);
Branch: 1 branch
BranchTrueFalseTotal
if scalar @_ == 0 3 2 5
2282  
2283 2 for my $k (keys %tols)
2284 {
2285 #
2286 # If this is a real tolerance limit, save its old
2287 # value, then set it.
2288 #
2289 2 ▶ if (exists $tolerance{$k})
Branch: 1 branch
BranchTrueFalseTotal
if (exists $tolerance{$k}) { } 2 0 2
2290 {
2291 2 my $val = abs($tols{$k});
2292  
2293 2 $old_tols{$k} = $tolerance{$k};
2294 2 $tolerance{$k} = $val;
2295 }
2296 else
2297 {
2298 0 croak "poly_tolerance(): unknown key $k.";
2299 }
2300 }
2301  
2302 2 return %old_tols;
2303 }
2304  
2305 =head3 poly_nonzero_term_count()
2306  
2307 Returns a simple count of the number of coefficients that aren't zero
2308 (zero meaning between -epsilon and epsilon).
2309  
2310 =cut
2311  
2312 sub poly_nonzero_term_count
2313 39 ▶{
Subroutine poly_nonzero_term_count: called CC=3 SCAR=11.0
Pod documented
2314 39 my(@coefficients) = @_;
2315 39 my $nzc = 0;
2316  
2317 39 for my $j (0..$#coefficients)
2318 {
2319 227 ▶ $nzc++ if (abs($coefficients[$j]) > $epsilon);
Branch: 1 branch
BranchTrueFalseTotal
if abs $coefficients[$j] > $epsilon 91 136 227
2320 }
2321 39 return $nzc;
2322 }
2323  
2324 17 ▶END {
Subroutine END: called CC=2 SCAR=9.2
2325 17 ▶ unless ($coeff_order_set)
Branch: 1 branch
BranchTrueFalseTotal
unless ($coeff_order_set) 0 17 17
2326 {
2327 0 warn "Your coefficient order is in a default state, which will change by version 3.00.\n\n",
2328 "Please put\n",
2329 " coefficients order => 'descending';\n",
2330 sprintf("at the beginning of file %s to make\n", (caller())[1]),
2331 "sure your function parameters will be in the correct order when the\n",
2332 "default order changes.\n\n",
2333 "See the README file and the Math::Polynomial::Solve documentation for\n",
2334 "more information.\n",
2335 }
2336 }
2337  
2338 17 1;
2339 __END__
↑ Summary