| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 277 | { | ||||||||||||||||||||||||||||||||||||||||||||
| 278 | 0 | ▶ | $ascending_flag = ($_[0] == 0)? 0: 1; | ||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 353 | { | ||||||||||||||||||||||||||||||||||||||||||||
| 354 | 30 | for my $j (1..$#coefficients - 1) | |||||||||||||||||||||||||||||||||||||||||||
| 355 | { | ||||||||||||||||||||||||||||||||||||||||||||
| 356 | 106 | ▶ | if (abs($coefficients[$j]) > $epsilon) | ||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
Condition33%1/3
scalar @coefficients and abs $coefficients[$#coefficients] < $epsilon
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
| |||||||||||||||||||||||||||||||||||||||||||||
| 501 | abs($coefficients[$#coefficients]) < $epsilon); | ||||||||||||||||||||||||||||||||||||||||||||
| 502 | |||||||||||||||||||||||||||||||||||||||||||||
| 503 | 135 | ▶ | if (@coefficients == 0) | ||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
Condition66%2/3
scalar @coefficients and abs $coefficients[0] < $epsilon
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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
Condition100%3/3
$option{"root_function"} and poly_nonzero_term_count(@coefficients) == 2
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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
Condition66%2/3
$option{"varsubst"} and $#coefficients > 1
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
| |||||||||||||||||||||||||||||||||||||||||||||
| 540 | { | ||||||||||||||||||||||||||||||||||||||||||||
| 541 | 22 | my $cf; | |||||||||||||||||||||||||||||||||||||||||||
| 542 | 22 | ($cf, $subst_degree) = poly_analysis(@coefficients); | |||||||||||||||||||||||||||||||||||||||||||
| 543 | 22 | ▶ | @coefficients = @$cf if ($subst_degree > 1); | ||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
Condition66%2/3
$option{"hessenberg"} or $#coefficients > 4
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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 675 | { | ||||||||||||||||||||||||||||||||||||||||||||
| 676 | 15 | $old_opts{$okey} = $option{$okey}; | |||||||||||||||||||||||||||||||||||||||||||
| 677 | 15 | ▶ | $option{$okey} = ($opts{$okey})? 1: 0; | ||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
Condition66%2/3
$c == 0 or $r == 0
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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 917 | { | ||||||||||||||||||||||||||||||||||||||||||||
| 918 | 207 | my $its = 0; | |||||||||||||||||||||||||||||||||||||||||||
| 919 | 207 | my $na = $n - 1; | |||||||||||||||||||||||||||||||||||||||||||
| 920 | |||||||||||||||||||||||||||||||||||||||||||||
| 921 | 207 | ▶ | while ($its < $iteration{hessenberg}) | ||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 963 | { | ||||||||||||||||||||||||||||||||||||||||||||
| 964 | # | ||||||||||||||||||||||||||||||||||||||||||||
| 965 | # Real pair. | ||||||||||||||||||||||||||||||||||||||||||||
| 966 | # | ||||||||||||||||||||||||||||||||||||||||||||
| 967 | 17 | ▶ | $y = -$y if ( $p < 0.0 ); | ||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 986 | |||||||||||||||||||||||||||||||||||||||||||||
| 987 | 1093 | ▶ | if ($its && $its % 10 == 0) | ||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
$its and $its % 10 == 0
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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 1035 | |||||||||||||||||||||||||||||||||||||||||||||
| 1036 | 1726 | ▶ | if (abs($h[$d][$d - 1]) * (abs($q) + abs($r)) <= | ||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 1075 | |||||||||||||||||||||||||||||||||||||||||||||
| 1076 | 2811 | $x = abs($p) + abs($q) + abs($r); | |||||||||||||||||||||||||||||||||||||||||||
| 1077 | 2811 | ▶ | next if ( $x == 0.0 ); | ||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 1086 | |||||||||||||||||||||||||||||||||||||||||||||
| 1087 | 3904 | ▶ | if ($k != $m) | ||||||||||||||||||||||||||||||||||||||||||
|
Branch: 2 branches
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 1173 | |||||||||||||||||||||||||||||||||||||||||||||
| 1174 | 9 | ▶ | if (abs($a) < $epsilon) | ||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 1197 | |||||||||||||||||||||||||||||||||||||||||||||
| 1198 | 40 | ▶ | if (abs($a) < $epsilon) | ||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 1232 | 23 | my @x; | |||||||||||||||||||||||||||||||||||||||||||
| 1233 | |||||||||||||||||||||||||||||||||||||||||||||
| 1234 | 23 | ▶ | if (abs($a) < $epsilon) | ||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 1285 | 10 | ▶ | $q = -$q if ($r_q > 0); | ||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 1341 | 22 | my @x = (); | |||||||||||||||||||||||||||||||||||||||||||
| 1342 | |||||||||||||||||||||||||||||||||||||||||||||
| 1343 | 22 | ▶ | if (abs($a) < $epsilon) | ||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
Condition0%0/3
$root < $from or $root > $to
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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 1590 | 21 | ▶ | return ([$from, $to]) if ($range_count == 1); | ||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 1713 | |||||||||||||||||||||||||||||||||||||||||||||
| 1714 | 55 | ▶ | if ($degree > 1) | ||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||
| 1715 | { | ||||||||||||||||||||||||||||||||||||||||||||
| 1716 | # | ||||||||||||||||||||||||||||||||||||||||||||
| 1717 | ###### poly_sturm_chain chain before do loop: | ||||||||||||||||||||||||||||||||||||||||||||
| 1718 | ###### @chain | ||||||||||||||||||||||||||||||||||||||||||||
| 1719 | # | ||||||||||||||||||||||||||||||||||||||||||||
| 1720 | do | ||||||||||||||||||||||||||||||||||||||||||||
| 1721 | 49 | ▶ | { | ||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
Condition100%3/3
@remd and abs $remd[$#remd] < $epsilon
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
| |||||||||||||||||||||||||||||||||||||||||||||
| 1729 | |||||||||||||||||||||||||||||||||||||||||||||
| 1730 | 77 | $f1 = $f2; | |||||||||||||||||||||||||||||||||||||||||||
| 1731 | 77 | ▶ | $f2 = (@remd)? [map {$_ * -1} @remd]: [0]; | ||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 1979 | |||||||||||||||||||||||||||||||||||||||||||||
| 1980 | # | ||||||||||||||||||||||||||||||||||||||||||||
| 1981 | # Allow some flexibility in sending the x-values. | ||||||||||||||||||||||||||||||||||||||||||||
| 1982 | # | ||||||||||||||||||||||||||||||||||||||||||||
| 1983 | 16 | ▶ | if (ref $xval_ref eq "ARRAY") | ||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 2089 | |||||||||||||||||||||||||||||||||||||||||||||
| 2090 | # | ||||||||||||||||||||||||||||||||||||||||||||
| 2091 | # Allow some flexibility in sending the x-values. | ||||||||||||||||||||||||||||||||||||||||||||
| 2092 | # | ||||||||||||||||||||||||||||||||||||||||||||
| 2093 | 2 | ▶ | if (ref $xval_ref eq "ARRAY") | ||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||
| 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__ | ||||||||||||||||||||||||||||||||||||||||||||