| 1 | package Math::Function::Roots; | ||||||||||||||||||||||||||||||||
| 2 | 7 | ▶ | use base Exporter; | ||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||
| 3 | 7 | ▶ | use vars qw(@EXPORT_OK $E $Max_Iter $VERSION $Last_Iter); | ||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||
| 4 | |||||||||||||||||||||||||||||||||
| 5 | 7 | ▶ | use warnings; | ||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||
| 6 | 7 | ▶ | use strict; | ||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||
| 7 | 7 | ▶ | use Carp; | ||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||
| 8 | |||||||||||||||||||||||||||||||||
| 9 | =head1 NAME | ||||||||||||||||||||||||||||||||
| 10 | |||||||||||||||||||||||||||||||||
| 11 | Math::Function::Roots - Functions for finding roots of arbitrary functions | ||||||||||||||||||||||||||||||||
| 12 | |||||||||||||||||||||||||||||||||
| 13 | =head1 VERSION | ||||||||||||||||||||||||||||||||
| 14 | |||||||||||||||||||||||||||||||||
| 15 | Version 0.065 | ||||||||||||||||||||||||||||||||
| 16 | |||||||||||||||||||||||||||||||||
| 17 | =cut | ||||||||||||||||||||||||||||||||
| 18 | |||||||||||||||||||||||||||||||||
| 19 | 7 | $VERSION = '0.065'; | |||||||||||||||||||||||||||||||
| 20 | |||||||||||||||||||||||||||||||||
| 21 | =head1 SYNOPSIS | ||||||||||||||||||||||||||||||||
| 22 | |||||||||||||||||||||||||||||||||
| 23 | This is a collection of functions (in the perl sense) to find the root | ||||||||||||||||||||||||||||||||
| 24 | of arbitrary functions (in the mathmatical sense). The Functions take a | ||||||||||||||||||||||||||||||||
| 25 | sub reference and a range or guess of the answer and return the | ||||||||||||||||||||||||||||||||
| 26 | root of the function. | ||||||||||||||||||||||||||||||||
| 27 | |||||||||||||||||||||||||||||||||
| 28 | use Math::Function::Roots qw(bisection epsilon max_iter); | ||||||||||||||||||||||||||||||||
| 29 | |||||||||||||||||||||||||||||||||
| 30 | epsilon(0); # Set desired accuracy | ||||||||||||||||||||||||||||||||
| 31 | max_iter(50_000) # Put cap on runtime | ||||||||||||||||||||||||||||||||
| 32 | |||||||||||||||||||||||||||||||||
| 33 | # Find the root of 2x+1 in the range (-5,5) | ||||||||||||||||||||||||||||||||
| 34 | my $result = bisection( sub {2*shift()+1}, -5, 5); | ||||||||||||||||||||||||||||||||
| 35 | # $result == -.5 | ||||||||||||||||||||||||||||||||
| 36 | |||||||||||||||||||||||||||||||||
| 37 | # Alternative method of setting epsilon and max_iter | ||||||||||||||||||||||||||||||||
| 38 | my $result2 = bisection( sub {2*shift()+1}, -5, 5, | ||||||||||||||||||||||||||||||||
| 39 | epsilon=>.00001, | ||||||||||||||||||||||||||||||||
| 40 | max_iter=>20); | ||||||||||||||||||||||||||||||||
| 41 | |||||||||||||||||||||||||||||||||
| 42 | =head1 DESCRIPTION | ||||||||||||||||||||||||||||||||
| 43 | |||||||||||||||||||||||||||||||||
| 44 | Numerical Analysis is the method of using algorithms, often | ||||||||||||||||||||||||||||||||
| 45 | iterative, to approximate the solution to a problem to which finding | ||||||||||||||||||||||||||||||||
| 46 | an exact solution would be difficult. Root Finding Algorithms are used | ||||||||||||||||||||||||||||||||
| 47 | to find the root of functions. They deal with continuous mathematical | ||||||||||||||||||||||||||||||||
| 48 | functions (one unique value of f(x) for every x). A root is anywhere | ||||||||||||||||||||||||||||||||
| 49 | the function evaluates to zero, i.e. where it crosses the | ||||||||||||||||||||||||||||||||
| 50 | x-axis. Different algortihms have different capacity for finding | ||||||||||||||||||||||||||||||||
| 51 | multiple roots, many can only find one root. | ||||||||||||||||||||||||||||||||
| 52 | |||||||||||||||||||||||||||||||||
| 53 | But enough of that, if you are here you probably know what a root | ||||||||||||||||||||||||||||||||
| 54 | finding algorithm is. I have begun implementing the following | ||||||||||||||||||||||||||||||||
| 55 | algorithms, which are described in detail below. The basic outline is | ||||||||||||||||||||||||||||||||
| 56 | algorithm( function, guess). Each function below is named after the | ||||||||||||||||||||||||||||||||
| 57 | underlying algorithm. | ||||||||||||||||||||||||||||||||
| 58 | |||||||||||||||||||||||||||||||||
| 59 | =head1 PARAMETERS | ||||||||||||||||||||||||||||||||
| 60 | |||||||||||||||||||||||||||||||||
| 61 | All of the algorithms have similar parameters, so I will describe them | ||||||||||||||||||||||||||||||||
| 62 | once. Always mandatory is the function we are finding the root of. | ||||||||||||||||||||||||||||||||
| 63 | |||||||||||||||||||||||||||||||||
| 64 | =head2 I<function> Parameter | ||||||||||||||||||||||||||||||||
| 65 | |||||||||||||||||||||||||||||||||
| 66 | Functions are passed as code references. These can take the form of | ||||||||||||||||||||||||||||||||
| 67 | "\&Function" or "sub{...}". Simple function can be inlined with sub{}, with more complicated functions taking the reference is recommended. | ||||||||||||||||||||||||||||||||
| 68 | |||||||||||||||||||||||||||||||||
| 69 | # f(x) = 2x - 4 | ||||||||||||||||||||||||||||||||
| 70 | # sub{ 2*shift() - 4 used as | ||||||||||||||||||||||||||||||||
| 71 | my $root = bisection( sub{ 2*shift() - 4 }, -10, 10 ); | ||||||||||||||||||||||||||||||||
| 72 | |||||||||||||||||||||||||||||||||
| 73 | Often you will have a function of multiple variables. This can be done with a wrapper function, such as: | ||||||||||||||||||||||||||||||||
| 74 | |||||||||||||||||||||||||||||||||
| 75 | sub foo{ | ||||||||||||||||||||||||||||||||
| 76 | my ($x1,$x2) = @_; | ||||||||||||||||||||||||||||||||
| 77 | return $x1**2 + $x2**2; | ||||||||||||||||||||||||||||||||
| 78 | } | ||||||||||||||||||||||||||||||||
| 79 | |||||||||||||||||||||||||||||||||
| 80 | sub wrapper{ | ||||||||||||||||||||||||||||||||
| 81 | my $x2 = shift; | ||||||||||||||||||||||||||||||||
| 82 | return foo( 5, $x2 ); | ||||||||||||||||||||||||||||||||
| 83 | } | ||||||||||||||||||||||||||||||||
| 84 | |||||||||||||||||||||||||||||||||
| 85 | my $result = bisection( \&wrapper, -10, 10 ); | ||||||||||||||||||||||||||||||||
| 86 | |||||||||||||||||||||||||||||||||
| 87 | Whatever subroutine is passed, it will be called with one argument, | ||||||||||||||||||||||||||||||||
| 88 | and is expected to return a single result. Functions not fitting that | ||||||||||||||||||||||||||||||||
| 89 | description will need a wrapper. | ||||||||||||||||||||||||||||||||
| 90 | |||||||||||||||||||||||||||||||||
| 91 | This will find the root of f(x) = 5**2 + x**2. Different algorithms | ||||||||||||||||||||||||||||||||
| 92 | react differently to certain functions. There is some advice below on | ||||||||||||||||||||||||||||||||
| 93 | good algorithms for certain types of functions. | ||||||||||||||||||||||||||||||||
| 94 | |||||||||||||||||||||||||||||||||
| 95 | =head2 I<guess or min/max> Parameters | ||||||||||||||||||||||||||||||||
| 96 | |||||||||||||||||||||||||||||||||
| 97 | Most algorithms require an initial range or guesses. If referred to as | ||||||||||||||||||||||||||||||||
| 98 | 'guesses' then the solution (root) need not be in the range | ||||||||||||||||||||||||||||||||
| 99 | [guess1,guess2]. If a range or min and max are required, then to | ||||||||||||||||||||||||||||||||
| 100 | solution B<must> lie within [min,max]. | ||||||||||||||||||||||||||||||||
| 101 | |||||||||||||||||||||||||||||||||
| 102 | =head2 I<epsilon> and I<max_iter> Parameters | ||||||||||||||||||||||||||||||||
| 103 | |||||||||||||||||||||||||||||||||
| 104 | Epsilon (I<e>) is used to set the desired accuracy. Less accurate | ||||||||||||||||||||||||||||||||
| 105 | answers take fewer iterations and are therefore quicker to compute. In | ||||||||||||||||||||||||||||||||
| 106 | general I<e> referres to the maximum distance from the given solution | ||||||||||||||||||||||||||||||||
| 107 | to the actual solution. If you need 6 decimals of accuracy, then I<e> | ||||||||||||||||||||||||||||||||
| 108 | = .000_000_1 is appropriate, this is the default. Calculating a few | ||||||||||||||||||||||||||||||||
| 109 | decimals beyond what you need is generally recommended to prevent | ||||||||||||||||||||||||||||||||
| 110 | compounding rounding errors. I<epsilon> is a named parameter to set | ||||||||||||||||||||||||||||||||
| 111 | I<e> for that particular run of the algorithm, it should always follow | ||||||||||||||||||||||||||||||||
| 112 | mandatory parameters: | ||||||||||||||||||||||||||||||||
| 113 | |||||||||||||||||||||||||||||||||
| 114 | my $result = bisection( sub{...}, -10, 10, epsilon => .01 ); | ||||||||||||||||||||||||||||||||
| 115 | |||||||||||||||||||||||||||||||||
| 116 | The I<epsilon>() function may be used to set I<e> globally, be careful. | ||||||||||||||||||||||||||||||||
| 117 | |||||||||||||||||||||||||||||||||
| 118 | =cut | ||||||||||||||||||||||||||||||||
| 119 | |||||||||||||||||||||||||||||||||
| 120 | 7 | $E = 0.000_000_1; | |||||||||||||||||||||||||||||||
| 121 | 17 | ▶ | sub epsilon(;$){ | ||||||||||||||||||||||||||||||
|
Subroutine
epsilon: called CC=3 SCAR=11.0
Pod
documented
| |||||||||||||||||||||||||||||||||
| 122 | 17 | ▶ | if( @_ ){ | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 123 | 9 | $E = shift; | |||||||||||||||||||||||||||||||
| 124 | 9 | ▶ | $E = 0 if $E < 0; | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 125 | } | ||||||||||||||||||||||||||||||||
| 126 | 17 | return $E; | |||||||||||||||||||||||||||||||
| 127 | } | ||||||||||||||||||||||||||||||||
| 128 | |||||||||||||||||||||||||||||||||
| 129 | =pod | ||||||||||||||||||||||||||||||||
| 130 | |||||||||||||||||||||||||||||||||
| 131 | Similar to epsilon, the maximum number of iterations an algorithm | ||||||||||||||||||||||||||||||||
| 132 | should run for may be set with the I<max_iter> named parameter, or | ||||||||||||||||||||||||||||||||
| 133 | globally with I<max_iter>(i). This maximum is normally used to catch | ||||||||||||||||||||||||||||||||
| 134 | errors, i.e. when a given function doesn't converge, or when there is | ||||||||||||||||||||||||||||||||
| 135 | a bug (nah...). Do not use this to control run-time, if you need an | ||||||||||||||||||||||||||||||||
| 136 | answer faster, use a larger epsilon. The only reason to change this | ||||||||||||||||||||||||||||||||
| 137 | would be if you had a slowly converging function, and you were willing | ||||||||||||||||||||||||||||||||
| 138 | to wait for a good answer, then you could raise the maximum to allow | ||||||||||||||||||||||||||||||||
| 139 | the algorithm to continue working. Default is 5,000. | ||||||||||||||||||||||||||||||||
| 140 | |||||||||||||||||||||||||||||||||
| 141 | =cut | ||||||||||||||||||||||||||||||||
| 142 | |||||||||||||||||||||||||||||||||
| 143 | 7 | $Max_Iter = 50_000; | |||||||||||||||||||||||||||||||
| 144 | 11 | ▶ | sub max_iter(;$){ | ||||||||||||||||||||||||||||||
|
Subroutine
max_iter: called CC=3 SCAR=11.0
Pod
documented
| |||||||||||||||||||||||||||||||||
| 145 | 11 | ▶ | if( @_ ){ | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 146 | 7 | $Max_Iter = shift; | |||||||||||||||||||||||||||||||
| 147 | 7 | ▶ | $Max_Iter = 1 if ($Max_Iter < 1); | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 148 | } | ||||||||||||||||||||||||||||||||
| 149 | 11 | return $Max_Iter; | |||||||||||||||||||||||||||||||
| 150 | } | ||||||||||||||||||||||||||||||||
| 151 | |||||||||||||||||||||||||||||||||
| 152 | =head1 PERFORMANCE CHECKING | ||||||||||||||||||||||||||||||||
| 153 | |||||||||||||||||||||||||||||||||
| 154 | =head2 last_iter( ) | ||||||||||||||||||||||||||||||||
| 155 | |||||||||||||||||||||||||||||||||
| 156 | This will return the number of iterations used to find the last | ||||||||||||||||||||||||||||||||
| 157 | result. This might help to give an indication on how an algorithm | ||||||||||||||||||||||||||||||||
| 158 | performs on your data. | ||||||||||||||||||||||||||||||||
| 159 | |||||||||||||||||||||||||||||||||
| 160 | =cut | ||||||||||||||||||||||||||||||||
| 161 | |||||||||||||||||||||||||||||||||
| 162 | 7 | ▶ | sub last_iter{ | ||||||||||||||||||||||||||||||
|
Subroutine
last_iter: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||||||
| 163 | 7 | return $Last_Iter; | |||||||||||||||||||||||||||||||
| 164 | } | ||||||||||||||||||||||||||||||||
| 165 | |||||||||||||||||||||||||||||||||
| 166 | =head1 ALGORITHMS | ||||||||||||||||||||||||||||||||
| 167 | |||||||||||||||||||||||||||||||||
| 168 | Below is a listing of availible algorithms. Many have restriction on the types of functions they work on, particularly the characteristics of the function near its root. Quick summary: | ||||||||||||||||||||||||||||||||
| 169 | |||||||||||||||||||||||||||||||||
| 170 | =over 4 | ||||||||||||||||||||||||||||||||
| 171 | |||||||||||||||||||||||||||||||||
| 172 | =item * bisection - Good for general purposes, you must provide a | ||||||||||||||||||||||||||||||||
| 173 | range in which one and only one root exists. Basically a binary search | ||||||||||||||||||||||||||||||||
| 174 | for the root. | ||||||||||||||||||||||||||||||||
| 175 | |||||||||||||||||||||||||||||||||
| 176 | =item * fixed_point - Only useful on a set of functions that can be | ||||||||||||||||||||||||||||||||
| 177 | converted to a fixed-point function with certain properties, see | ||||||||||||||||||||||||||||||||
| 178 | below. Fast when it can be used. | ||||||||||||||||||||||||||||||||
| 179 | |||||||||||||||||||||||||||||||||
| 180 | =item * secant - A fast converging algorithm which bases guesses on | ||||||||||||||||||||||||||||||||
| 181 | the slope of the function. Because slope is used, areas of the | ||||||||||||||||||||||||||||||||
| 182 | function where the slope is near horizontal (f'(x) == 0) should be | ||||||||||||||||||||||||||||||||
| 183 | avoided. | ||||||||||||||||||||||||||||||||
| 184 | |||||||||||||||||||||||||||||||||
| 185 | =back | ||||||||||||||||||||||||||||||||
| 186 | |||||||||||||||||||||||||||||||||
| 187 | =cut | ||||||||||||||||||||||||||||||||
| 188 | |||||||||||||||||||||||||||||||||
| 189 | 7 | @EXPORT_OK = qw(epsilon | |||||||||||||||||||||||||||||||
| 190 | max_iter | ||||||||||||||||||||||||||||||||
| 191 | last_iter | ||||||||||||||||||||||||||||||||
| 192 | bisection | ||||||||||||||||||||||||||||||||
| 193 | fixed_point | ||||||||||||||||||||||||||||||||
| 194 | secant | ||||||||||||||||||||||||||||||||
| 195 | false_position | ||||||||||||||||||||||||||||||||
| 196 | find | ||||||||||||||||||||||||||||||||
| 197 | ); | ||||||||||||||||||||||||||||||||
| 198 | |||||||||||||||||||||||||||||||||
| 199 | =head2 bisection( I<function, min, max> ) | ||||||||||||||||||||||||||||||||
| 200 | |||||||||||||||||||||||||||||||||
| 201 | Uses the bisection algorithm. Average performance, but dependable. Min | ||||||||||||||||||||||||||||||||
| 202 | and max are used to specify a range which contains the root. To ensure | ||||||||||||||||||||||||||||||||
| 203 | this f(min) and f(max) must have opposite signs (meaning that there | ||||||||||||||||||||||||||||||||
| 204 | must be at least one root between them). Giving a range with multiple | ||||||||||||||||||||||||||||||||
| 205 | roots in it will not work in most cases. This method is dependable, | ||||||||||||||||||||||||||||||||
| 206 | because it does not care about the shape of the function. It is also a | ||||||||||||||||||||||||||||||||
| 207 | bit slower than som algorithms because it does not take hints from the | ||||||||||||||||||||||||||||||||
| 208 | shape. | ||||||||||||||||||||||||||||||||
| 209 | |||||||||||||||||||||||||||||||||
| 210 | =cut | ||||||||||||||||||||||||||||||||
| 211 | |||||||||||||||||||||||||||||||||
| 212 | 9 | ▶ | sub bisection (&$$;%){ | ||||||||||||||||||||||||||||||
|
Subroutine
bisection: called CC=8 SCAR=20.8
Pod
documented
| |||||||||||||||||||||||||||||||||
| 213 | 9 | my $f = shift; | |||||||||||||||||||||||||||||||
| 214 | 9 | my ($a,$b) = (shift, shift); | |||||||||||||||||||||||||||||||
| 215 | 9 | my %optional = @_; | |||||||||||||||||||||||||||||||
| 216 | 9 | ▶ | my $E = $optional{epsilon} || $E; | ||||||||||||||||||||||||||||||
|
Condition100%3/3
$optional{'epsilon'} || $Math::Function::Roots::E
MC/DC100%2/2
$optional{'epsilon'} || $Math::Function::Roots::E
$optional{'epsilon'}
$Math::Function::Roots::E
Truth table100%3/3
A || B
A= $optional{'epsilon'}B= $Math::Function::Roots::E
| |||||||||||||||||||||||||||||||||
| 217 | 9 | ▶ | my $Max_Iter = $optional{max_iter} || $Max_Iter; | ||||||||||||||||||||||||||||||
|
Condition66%2/3
$optional{'max_iter'} || $Math::Function::Roots::Max_Iter
MC/DC0%0/2
$optional{'max_iter'} || $Math::Function::Roots::Max_Iter
$optional{'max_iter'}
$Math::Function::Roots::Max_Iter
Truth table66%2/3
A || B
A= $optional{'max_iter'}B= $Math::Function::Roots::Max_Iter
| |||||||||||||||||||||||||||||||||
| 218 | |||||||||||||||||||||||||||||||||
| 219 | 9 | my ($ay, $by ) = ( &$f($a), &$f($b) ); | |||||||||||||||||||||||||||||||
| 220 | 9 | ▶ | if( ($ay * $by) > 0 ){ | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 221 | # This algo doesn't work if a and b don't braket the root | ||||||||||||||||||||||||||||||||
| 222 | # f(a) must have and an opposite sign from f(b) | ||||||||||||||||||||||||||||||||
| 223 | # to ensure there is an odd number of roots | ||||||||||||||||||||||||||||||||
| 224 | 1 | croak "Bad range: f($a) and f($b) have the same sign"; | |||||||||||||||||||||||||||||||
| 225 | } | ||||||||||||||||||||||||||||||||
| 226 | 8 | my $p = 0; | |||||||||||||||||||||||||||||||
| 227 | 8 | for (1..$Max_Iter){ | |||||||||||||||||||||||||||||||
| 228 | 159 | $Last_Iter = $_; | |||||||||||||||||||||||||||||||
| 229 | |||||||||||||||||||||||||||||||||
| 230 | 159 | $p = ($a+$b)/2.0; | |||||||||||||||||||||||||||||||
| 231 | 159 | my $py = &$f($p); | |||||||||||||||||||||||||||||||
| 232 | |||||||||||||||||||||||||||||||||
| 233 | 159 | ▶ | if( $py == 0 || abs( $a - $b ) <= $E ){ | ||||||||||||||||||||||||||||||
|
Branch: 2 branches
Condition100%3/3
$py == 0 or abs $a - $b <= $E
MC/DC100%2/2
$py == 0 or abs $a - $b <= $E
$py == 0
abs $a - $b <= $E
Truth table100%3/3
A or B
A= $py == 0B= abs $a - $b <= $E
| |||||||||||||||||||||||||||||||||
| 234 | #Uses relative change in p as stopping criteria | ||||||||||||||||||||||||||||||||
| 235 | #Alternative would be size of a..b range, i.e. abs(a-b) | ||||||||||||||||||||||||||||||||
| 236 | 6 | return $p; | |||||||||||||||||||||||||||||||
| 237 | } | ||||||||||||||||||||||||||||||||
| 238 | elsif( $py * $ay < 0 ){ | ||||||||||||||||||||||||||||||||
| 239 | #If f at p and a have opposite sign | ||||||||||||||||||||||||||||||||
| 240 | #then there is a root between them | ||||||||||||||||||||||||||||||||
| 241 | #next iteration should be a..p | ||||||||||||||||||||||||||||||||
| 242 | 92 | $b = $p; | |||||||||||||||||||||||||||||||
| 243 | 92 | $by = $py; | |||||||||||||||||||||||||||||||
| 244 | } | ||||||||||||||||||||||||||||||||
| 245 | else{ | ||||||||||||||||||||||||||||||||
| 246 | # If $py != 0, $ay and $by have opposite signs, $py and $ay have same sign | ||||||||||||||||||||||||||||||||
| 247 | # then $py and $by must have opposite signs | ||||||||||||||||||||||||||||||||
| 248 | 61 | $a = $p; | |||||||||||||||||||||||||||||||
| 249 | 61 | $ay = $py; | |||||||||||||||||||||||||||||||
| 250 | } | ||||||||||||||||||||||||||||||||
| 251 | } | ||||||||||||||||||||||||||||||||
| 252 | |||||||||||||||||||||||||||||||||
| 253 | 2 | carp "Maximum iterations: possible bad solution"; | |||||||||||||||||||||||||||||||
| 254 | 2 | return $p; | |||||||||||||||||||||||||||||||
| 255 | } | ||||||||||||||||||||||||||||||||
| 256 | |||||||||||||||||||||||||||||||||
| 257 | =head2 fixed_point( I<fixed point function, guess> ) | ||||||||||||||||||||||||||||||||
| 258 | |||||||||||||||||||||||||||||||||
| 259 | The Fixed-Point Iteration algorithm is a fast robust method which, | ||||||||||||||||||||||||||||||||
| 260 | unfortunately, works on a limited domain of problems, and requires | ||||||||||||||||||||||||||||||||
| 261 | some algebra. The benefits are that it can converge rapidly, and the | ||||||||||||||||||||||||||||||||
| 262 | range the root is in does not need to be known, any guess will | ||||||||||||||||||||||||||||||||
| 263 | converge, eventually. | ||||||||||||||||||||||||||||||||
| 264 | |||||||||||||||||||||||||||||||||
| 265 | A fixed-point is where g(x) = x. The method is to find a function, | ||||||||||||||||||||||||||||||||
| 266 | g(x), which has a fixed-point where f(x) has a root. This can be done | ||||||||||||||||||||||||||||||||
| 267 | trivially by using g(x) = x - f(x). In more general cases it is done | ||||||||||||||||||||||||||||||||
| 268 | by factoring an x so that g(x) = x = ff(x), where x = ff(x) is some | ||||||||||||||||||||||||||||||||
| 269 | identity derived from f(x). | ||||||||||||||||||||||||||||||||
| 270 | |||||||||||||||||||||||||||||||||
| 271 | As was mentioned there is a restriction on you choice of g(x), it is | ||||||||||||||||||||||||||||||||
| 272 | that the absolute value of the derivative of g(x) must be less than | ||||||||||||||||||||||||||||||||
| 273 | 1. Or |g'(x)| < 1 (mathematical notation I<is> handy sometimes). The | ||||||||||||||||||||||||||||||||
| 274 | closer g'(x) is to 0 the faster the rate of convergence. | ||||||||||||||||||||||||||||||||
| 275 | |||||||||||||||||||||||||||||||||
| 276 | Consider a range [a,b] which contains the fixed-point and within which | ||||||||||||||||||||||||||||||||
| 277 | |g'(x)| < 1 holds true. This might be an infinite range or a segment | ||||||||||||||||||||||||||||||||
| 278 | of the function. As long as your initial guess is within this range, | ||||||||||||||||||||||||||||||||
| 279 | the algorithm will converge. | ||||||||||||||||||||||||||||||||
| 280 | |||||||||||||||||||||||||||||||||
| 281 | I<guess> is an approximation of the answer. The algorithm will | ||||||||||||||||||||||||||||||||
| 282 | converge regardless of the relationship of I<guess> to the actual | ||||||||||||||||||||||||||||||||
| 283 | answer, just so long as I<guess> is within the range [a,b]. | ||||||||||||||||||||||||||||||||
| 284 | |||||||||||||||||||||||||||||||||
| 285 | Why go through all this hassle? Well, certain functions lend | ||||||||||||||||||||||||||||||||
| 286 | themselves to being transformed easily into fixed-point | ||||||||||||||||||||||||||||||||
| 287 | functions. Also, with a derivative near 0 the convergence is very | ||||||||||||||||||||||||||||||||
| 288 | fast, regardless of initial guess. | ||||||||||||||||||||||||||||||||
| 289 | |||||||||||||||||||||||||||||||||
| 290 | =cut | ||||||||||||||||||||||||||||||||
| 291 | |||||||||||||||||||||||||||||||||
| 292 | 2 | ▶ | sub fixed_point(&$;%){ | ||||||||||||||||||||||||||||||
|
Subroutine
fixed_point: called CC=5 SCAR=16.4
Pod
documented
| |||||||||||||||||||||||||||||||||
| 293 | 2 | my $g = shift; | |||||||||||||||||||||||||||||||
| 294 | 2 | my $guess = shift; | |||||||||||||||||||||||||||||||
| 295 | 2 | my %optional = @_; | |||||||||||||||||||||||||||||||
| 296 | 2 | ▶ | my $E = $optional{epsilon} || $E; | ||||||||||||||||||||||||||||||
|
Condition33%1/3
$optional{'epsilon'} || $Math::Function::Roots::E
MC/DC0%0/2
$optional{'epsilon'} || $Math::Function::Roots::E
$optional{'epsilon'}
$Math::Function::Roots::E
Truth table33%1/3
A || B
A= $optional{'epsilon'}B= $Math::Function::Roots::E
| |||||||||||||||||||||||||||||||||
| 297 | 2 | ▶ | my $Max_Iter = $optional{max_iter} || $Max_Iter; | ||||||||||||||||||||||||||||||
|
Condition33%1/3
$optional{'max_iter'} || $Math::Function::Roots::Max_Iter
MC/DC0%0/2
$optional{'max_iter'} || $Math::Function::Roots::Max_Iter
$optional{'max_iter'}
$Math::Function::Roots::Max_Iter
Truth table33%1/3
A || B
A= $optional{'max_iter'}B= $Math::Function::Roots::Max_Iter
| |||||||||||||||||||||||||||||||||
| 298 | |||||||||||||||||||||||||||||||||
| 299 | 2 | my ($p,$last_p) = (0,$guess); | |||||||||||||||||||||||||||||||
| 300 | 2 | for (1..$Max_Iter){ | |||||||||||||||||||||||||||||||
| 301 | 62 | $Last_Iter = $_; | |||||||||||||||||||||||||||||||
| 302 | |||||||||||||||||||||||||||||||||
| 303 | # Each iter we compute p = g(p') | ||||||||||||||||||||||||||||||||
| 304 | 62 | $p = &$g($last_p); | |||||||||||||||||||||||||||||||
| 305 | 62 | ▶ | if( abs( $p - $last_p ) <= $E ){ | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 306 | 1 | return $p; | |||||||||||||||||||||||||||||||
| 307 | } | ||||||||||||||||||||||||||||||||
| 308 | 61 | $last_p = $p; | |||||||||||||||||||||||||||||||
| 309 | } | ||||||||||||||||||||||||||||||||
| 310 | 1 | carp "Maximum iterations: divergence likely"; | |||||||||||||||||||||||||||||||
| 311 | 1 | return undef; | |||||||||||||||||||||||||||||||
| 312 | } | ||||||||||||||||||||||||||||||||
| 313 | |||||||||||||||||||||||||||||||||
| 314 | =head2 secant( I<function>, guess1, guess2 >) | ||||||||||||||||||||||||||||||||
| 315 | |||||||||||||||||||||||||||||||||
| 316 | The secant method is a simplification of the Newton method, which uses | ||||||||||||||||||||||||||||||||
| 317 | the derivitive of the function to better predict the root of the | ||||||||||||||||||||||||||||||||
| 318 | function. The secant method uses a secant (line between two points on | ||||||||||||||||||||||||||||||||
| 319 | the function) as a substitute for knowing or calculating the | ||||||||||||||||||||||||||||||||
| 320 | derivative of the function. | ||||||||||||||||||||||||||||||||
| 321 | |||||||||||||||||||||||||||||||||
| 322 | As usual, provide the function, then provide two guesses. Unlike | ||||||||||||||||||||||||||||||||
| 323 | bisection, these do not need to bracket the solution. Local minimums | ||||||||||||||||||||||||||||||||
| 324 | or maximums, where the slope is near 0, are unfriendly to this | ||||||||||||||||||||||||||||||||
| 325 | algorithm. When the two guesses are near the solution however, this | ||||||||||||||||||||||||||||||||
| 326 | algorithm gives rapid convergence. | ||||||||||||||||||||||||||||||||
| 327 | |||||||||||||||||||||||||||||||||
| 328 | =cut | ||||||||||||||||||||||||||||||||
| 329 | |||||||||||||||||||||||||||||||||
| 330 | 3 | ▶ | sub secant(&$$;%){ | ||||||||||||||||||||||||||||||
|
Subroutine
secant: called CC=6 SCAR=18.0
Pod
documented
| |||||||||||||||||||||||||||||||||
| 331 | 3 | my $f = shift; | |||||||||||||||||||||||||||||||
| 332 | 3 | my ($p0,$p1) = (shift,shift); | |||||||||||||||||||||||||||||||
| 333 | |||||||||||||||||||||||||||||||||
| 334 | 3 | my %optional = @_; | |||||||||||||||||||||||||||||||
| 335 | 3 | ▶ | my $E = $optional{epsilon} || $E; | ||||||||||||||||||||||||||||||
|
Condition66%2/3
$optional{'epsilon'} || $Math::Function::Roots::E
MC/DC50%1/2
$optional{'epsilon'} || $Math::Function::Roots::E
$optional{'epsilon'}
$Math::Function::Roots::E
Truth table66%2/3
A || B
A= $optional{'epsilon'}B= $Math::Function::Roots::E
| |||||||||||||||||||||||||||||||||
| 336 | 3 | ▶ | my $Max_Iter = $optional{max_iter} || $Max_Iter; | ||||||||||||||||||||||||||||||
|
Condition33%1/3
$optional{'max_iter'} || $Math::Function::Roots::Max_Iter
MC/DC0%0/2
$optional{'max_iter'} || $Math::Function::Roots::Max_Iter
$optional{'max_iter'}
$Math::Function::Roots::Max_Iter
Truth table33%1/3
A || B
A= $optional{'max_iter'}B= $Math::Function::Roots::Max_Iter
| |||||||||||||||||||||||||||||||||
| 337 | |||||||||||||||||||||||||||||||||
| 338 | |||||||||||||||||||||||||||||||||
| 339 | 3 | my ($q0,$q1,) = ( &$f($p0) , &$f($p1) ); | |||||||||||||||||||||||||||||||
| 340 | 3 | my $p; | |||||||||||||||||||||||||||||||
| 341 | 3 | for (1..$Max_Iter){ | |||||||||||||||||||||||||||||||
| 342 | 20 | $Last_Iter = $_; | |||||||||||||||||||||||||||||||
| 343 | |||||||||||||||||||||||||||||||||
| 344 | 20 | $p = $p1 - ($q1 * ($p1 - $p0)) / ($q1 - $q0); | |||||||||||||||||||||||||||||||
| 345 | |||||||||||||||||||||||||||||||||
| 346 | # Careful, the order of the assignments below and | ||||||||||||||||||||||||||||||||
| 347 | # following the test are important | ||||||||||||||||||||||||||||||||
| 348 | 20 | $p0 = $p1; | |||||||||||||||||||||||||||||||
| 349 | 20 | $q0 = $q1; | |||||||||||||||||||||||||||||||
| 350 | 20 | $q1 = &$f( $p ); | |||||||||||||||||||||||||||||||
| 351 | |||||||||||||||||||||||||||||||||
| 352 | 20 | ▶ | if( $q1 eq 0 || abs( $p - $p1 ) <= $E ){ | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
$q1 eq 0 or abs $p - $p1 <= $E
MC/DC100%2/2
$q1 eq 0 or abs $p - $p1 <= $E
$q1 eq 0
abs $p - $p1 <= $E
Truth table100%3/3
A or B
A= $q1 eq 0B= abs $p - $p1 <= $E
| |||||||||||||||||||||||||||||||||
| 353 | 2 | return $p; | |||||||||||||||||||||||||||||||
| 354 | } | ||||||||||||||||||||||||||||||||
| 355 | |||||||||||||||||||||||||||||||||
| 356 | 18 | $p1 = $p; | |||||||||||||||||||||||||||||||
| 357 | } | ||||||||||||||||||||||||||||||||
| 358 | 1 | carp "Maximum iterations: divergence likely"; | |||||||||||||||||||||||||||||||
| 359 | 1 | return undef; | |||||||||||||||||||||||||||||||
| 360 | } | ||||||||||||||||||||||||||||||||
| 361 | |||||||||||||||||||||||||||||||||
| 362 | =head2 false_position( I<function, min, max> ) | ||||||||||||||||||||||||||||||||
| 363 | |||||||||||||||||||||||||||||||||
| 364 | False Position is an algorithm similar to Secant, it uses secants | ||||||||||||||||||||||||||||||||
| 365 | of the function to pick better guesses. The difference is that this | ||||||||||||||||||||||||||||||||
| 366 | method incorporates the bracketing of the Bisection method, with the | ||||||||||||||||||||||||||||||||
| 367 | speed of the Secant method. | ||||||||||||||||||||||||||||||||
| 368 | |||||||||||||||||||||||||||||||||
| 369 | Bracketing is a desirable property because it makes the algorithm more | ||||||||||||||||||||||||||||||||
| 370 | dependable. Bracketing ensures that the algorithm will stay within the | ||||||||||||||||||||||||||||||||
| 371 | given range. This is useful with higer-order functions where you want | ||||||||||||||||||||||||||||||||
| 372 | to restrict your search to the area directly around the root. | ||||||||||||||||||||||||||||||||
| 373 | |||||||||||||||||||||||||||||||||
| 374 | The only restriction is that the functions derivative must not equal 0 | ||||||||||||||||||||||||||||||||
| 375 | within the range [min,max]. There must also only be one root within | ||||||||||||||||||||||||||||||||
| 376 | the range, which (as in Bisection) is ensured by requiring that f(min) | ||||||||||||||||||||||||||||||||
| 377 | and f(max) have opposite signs. | ||||||||||||||||||||||||||||||||
| 378 | |||||||||||||||||||||||||||||||||
| 379 | =cut | ||||||||||||||||||||||||||||||||
| 380 | |||||||||||||||||||||||||||||||||
| 381 | 7 | ▶ | sub false_position(&$$;%){ | ||||||||||||||||||||||||||||||
|
Subroutine
false_position: called CC=7 SCAR=19.5
Pod
documented
| |||||||||||||||||||||||||||||||||
| 382 | 7 | my $f = shift; | |||||||||||||||||||||||||||||||
| 383 | 7 | my ($a,$b) = (shift,shift); | |||||||||||||||||||||||||||||||
| 384 | |||||||||||||||||||||||||||||||||
| 385 | 7 | my %optional = @_; | |||||||||||||||||||||||||||||||
| 386 | 7 | ▶ | my $E = $optional{epsilon} || $E; | ||||||||||||||||||||||||||||||
|
Condition66%2/3
$optional{'epsilon'} || $Math::Function::Roots::E
MC/DC50%1/2
$optional{'epsilon'} || $Math::Function::Roots::E
$optional{'epsilon'}
$Math::Function::Roots::E
Truth table66%2/3
A || B
A= $optional{'epsilon'}B= $Math::Function::Roots::E
| |||||||||||||||||||||||||||||||||
| 387 | 7 | ▶ | my $Max_Iter = $optional{max_iter} || $Max_Iter; | ||||||||||||||||||||||||||||||
|
Condition33%1/3
$optional{'max_iter'} || $Math::Function::Roots::Max_Iter
MC/DC0%0/2
$optional{'max_iter'} || $Math::Function::Roots::Max_Iter
$optional{'max_iter'}
$Math::Function::Roots::Max_Iter
Truth table33%1/3
A || B
A= $optional{'max_iter'}B= $Math::Function::Roots::Max_Iter
| |||||||||||||||||||||||||||||||||
| 388 | |||||||||||||||||||||||||||||||||
| 389 | 7 | my ($ay, $by) = ( &$f($a), &$f($b) ); | |||||||||||||||||||||||||||||||
| 390 | # This algorithm requires that f(a) and f(b) | ||||||||||||||||||||||||||||||||
| 391 | # always have opposite signs | ||||||||||||||||||||||||||||||||
| 392 | 7 | ▶ | croak "Bad range: f($a) and f($b) have the same sign" | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 393 | if( $ay * $by > 0 ); | ||||||||||||||||||||||||||||||||
| 394 | |||||||||||||||||||||||||||||||||
| 395 | 6 | my ($p,$last_py) = (0,0); | |||||||||||||||||||||||||||||||
| 396 | 6 | for (1..$Max_Iter){ | |||||||||||||||||||||||||||||||
| 397 | 90 | $Last_Iter = $_; | |||||||||||||||||||||||||||||||
| 398 | |||||||||||||||||||||||||||||||||
| 399 | 90 | $p = $b - $by*($b - $a)/($by - $ay); | |||||||||||||||||||||||||||||||
| 400 | |||||||||||||||||||||||||||||||||
| 401 | 90 | my $py = &$f($p); | |||||||||||||||||||||||||||||||
| 402 | |||||||||||||||||||||||||||||||||
| 403 | 90 | ▶ | if( abs($py - $last_py) <= $E ){ | ||||||||||||||||||||||||||||||
|
Branch: 2 branches
| |||||||||||||||||||||||||||||||||
| 404 | 5 | return $p; | |||||||||||||||||||||||||||||||
| 405 | } | ||||||||||||||||||||||||||||||||
| 406 | elsif( $py * $by < 0 ){ | ||||||||||||||||||||||||||||||||
| 407 | # If $py and $by have opposite signs | ||||||||||||||||||||||||||||||||
| 408 | # Then the root is within [p..b] | ||||||||||||||||||||||||||||||||
| 409 | 82 | $a = $p; | |||||||||||||||||||||||||||||||
| 410 | 82 | $ay = $py; | |||||||||||||||||||||||||||||||
| 411 | } | ||||||||||||||||||||||||||||||||
| 412 | else{ | ||||||||||||||||||||||||||||||||
| 413 | # root is in range [a..p] | ||||||||||||||||||||||||||||||||
| 414 | 3 | $b = $p; | |||||||||||||||||||||||||||||||
| 415 | 3 | $by = $py; | |||||||||||||||||||||||||||||||
| 416 | } | ||||||||||||||||||||||||||||||||
| 417 | 85 | $last_py = $py; | |||||||||||||||||||||||||||||||
| 418 | } | ||||||||||||||||||||||||||||||||
| 419 | 1 | carp "Maximum iterations: possible bad solution"; | |||||||||||||||||||||||||||||||
| 420 | 1 | return $p; | |||||||||||||||||||||||||||||||
| 421 | } | ||||||||||||||||||||||||||||||||
| 422 | |||||||||||||||||||||||||||||||||
| 423 | =head2 find() | ||||||||||||||||||||||||||||||||
| 424 | |||||||||||||||||||||||||||||||||
| 425 | This a hybrid function which uses a combination of algorithms to find | ||||||||||||||||||||||||||||||||
| 426 | the root of the given function. Both I<guess1> and I<guess2> are | ||||||||||||||||||||||||||||||||
| 427 | optional. If one is provided, it is used as an approximate starting | ||||||||||||||||||||||||||||||||
| 428 | point. If both are given, then they are taken as a range, the root | ||||||||||||||||||||||||||||||||
| 429 | B<must> be within this range. | ||||||||||||||||||||||||||||||||
| 430 | |||||||||||||||||||||||||||||||||
| 431 | It will most likely return the root nearest your guess, but no | ||||||||||||||||||||||||||||||||
| 432 | guarantees. Don't provide a range with more than one root in it, you | ||||||||||||||||||||||||||||||||
| 433 | might find one, you might not. More information will give higher | ||||||||||||||||||||||||||||||||
| 434 | performance and more control over which root is being found, but if | ||||||||||||||||||||||||||||||||
| 435 | you don't know anything about the function, give it a try without a | ||||||||||||||||||||||||||||||||
| 436 | guess. Settings from epsilon and maximum iterations apply as normal. | ||||||||||||||||||||||||||||||||
| 437 | |||||||||||||||||||||||||||||||||
| 438 | =cut | ||||||||||||||||||||||||||||||||
| 439 | |||||||||||||||||||||||||||||||||
| 440 | 1 | ▶ | sub find(&;$$%){ | ||||||||||||||||||||||||||||||
|
Subroutine
find: called CC=12 SCAR=27.7
Pod
documented
| |||||||||||||||||||||||||||||||||
| 441 | 1 | my $f = shift; | |||||||||||||||||||||||||||||||
| 442 | 1 | my ($a,$b); | |||||||||||||||||||||||||||||||
| 443 | |||||||||||||||||||||||||||||||||
| 444 | # This is totally wrong, need to not assign to $a and $b when no | ||||||||||||||||||||||||||||||||
| 445 | # arguments | ||||||||||||||||||||||||||||||||
| 446 | |||||||||||||||||||||||||||||||||
| 447 | 1 | ▶ | if( defined $_[0] && $_[0] =~ !/epsilon|max_iter/ ){ | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition33%1/3
defined $_[0] and $_[0] =~ !/epsilon|max_iter/
MC/DC0%0/2
defined $_[0] and $_[0] =~ !/epsilon|max_iter/
defined $_[0]
$_[0] =~ !/epsilon|max_iter/
Truth table33%1/3
A and B
A= defined $_[0]B= $_[0] =~ !/epsilon|max_iter/
| |||||||||||||||||||||||||||||||||
| 448 | 0 | $a = shift; | |||||||||||||||||||||||||||||||
| 449 | } | ||||||||||||||||||||||||||||||||
| 450 | 1 | ▶ | if( defined $_[0] && $_[0] =~ !/epsilon|max_iter/ ){ | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition33%1/3
defined $_[0] and $_[0] =~ !/epsilon|max_iter/
MC/DC0%0/2
defined $_[0] and $_[0] =~ !/epsilon|max_iter/
defined $_[0]
$_[0] =~ !/epsilon|max_iter/
Truth table33%1/3
A and B
A= defined $_[0]B= $_[0] =~ !/epsilon|max_iter/
| |||||||||||||||||||||||||||||||||
| 451 | 0 | $b = shift; | |||||||||||||||||||||||||||||||
| 452 | } | ||||||||||||||||||||||||||||||||
| 453 | |||||||||||||||||||||||||||||||||
| 454 | 1 | my %optional = @_; | |||||||||||||||||||||||||||||||
| 455 | 1 | ▶ | my $E = $optional{epsilon} || $E; | ||||||||||||||||||||||||||||||
|
Condition33%1/3
$optional{'epsilon'} || $Math::Function::Roots::E
MC/DC0%0/2
$optional{'epsilon'} || $Math::Function::Roots::E
$optional{'epsilon'}
$Math::Function::Roots::E
Truth table33%1/3
A || B
A= $optional{'epsilon'}B= $Math::Function::Roots::E
| |||||||||||||||||||||||||||||||||
| 456 | 1 | ▶ | my $Max_Iter = $optional{max_iter} || $Max_Iter; | ||||||||||||||||||||||||||||||
|
Condition33%1/3
$optional{'max_iter'} || $Math::Function::Roots::Max_Iter
MC/DC0%0/2
$optional{'max_iter'} || $Math::Function::Roots::Max_Iter
$optional{'max_iter'}
$Math::Function::Roots::Max_Iter
Truth table33%1/3
A || B
A= $optional{'max_iter'}B= $Math::Function::Roots::Max_Iter
| |||||||||||||||||||||||||||||||||
| 457 | |||||||||||||||||||||||||||||||||
| 458 | 1 | ▶ | unless( defined $b ){ | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 459 | # If we don't have $b, we don't have a range, | ||||||||||||||||||||||||||||||||
| 460 | # but we might have a guess | ||||||||||||||||||||||||||||||||
| 461 | 1 | ▶ | unless( defined $a ){ | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 462 | # If we have no guess we'll use 0 for initiation | ||||||||||||||||||||||||||||||||
| 463 | 1 | $a = 0; | |||||||||||||||||||||||||||||||
| 464 | } | ||||||||||||||||||||||||||||||||
| 465 | # Start with a guess range +2 and -2 around guess | ||||||||||||||||||||||||||||||||
| 466 | 1 | $a -= 2; | |||||||||||||||||||||||||||||||
| 467 | 1 | $b = $a + 4; | |||||||||||||||||||||||||||||||
| 468 | 1 | my ($fa,$fb); | |||||||||||||||||||||||||||||||
| 469 | 1 | ▶ | do{ | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 470 | |||||||||||||||||||||||||||||||||
| 471 | # add max iteration catch to this loop | ||||||||||||||||||||||||||||||||
| 472 | # irr call to this function is causing both points to go negative | ||||||||||||||||||||||||||||||||
| 473 | |||||||||||||||||||||||||||||||||
| 474 | # Until $a and $b bracket the solution | ||||||||||||||||||||||||||||||||
| 475 | 2 | $fa = &$f($a); | |||||||||||||||||||||||||||||||
| 476 | 2 | $fb = &$f($b); | |||||||||||||||||||||||||||||||
| 477 | 2 | sleep 1; | |||||||||||||||||||||||||||||||
| 478 | #use Data::Dumper::Simple; | ||||||||||||||||||||||||||||||||
| 479 | #warn Dumper($a,$fa,$b,$fb ); | ||||||||||||||||||||||||||||||||
| 480 | 2 | $a = $a*2; | |||||||||||||||||||||||||||||||
| 481 | 2 | $b = $b*2; | |||||||||||||||||||||||||||||||
| 482 | }until( $fa * $fb < 0 ); | ||||||||||||||||||||||||||||||||
| 483 | } | ||||||||||||||||||||||||||||||||
| 484 | # Now we have a possibly large range that must bracket the solution | ||||||||||||||||||||||||||||||||
| 485 | # It might also bracket an odd number of roots, | ||||||||||||||||||||||||||||||||
| 486 | # in this case, we don't know which one we might find, | ||||||||||||||||||||||||||||||||
| 487 | # and if the user cares, he should have given more info | ||||||||||||||||||||||||||||||||
| 488 | |||||||||||||||||||||||||||||||||
| 489 | |||||||||||||||||||||||||||||||||
| 490 | 1 | my ($approx,$result); | |||||||||||||||||||||||||||||||
| 491 | 1 | ▶ | eval{ | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 492 | 1 | $approx = bisection( \&$f, $a, $b, epsilon => .1 ); | |||||||||||||||||||||||||||||||
| 493 | } || die "find: Initial bisection approximation failed: ".$@; | ||||||||||||||||||||||||||||||||
| 494 | 1 | ▶ | eval{ | ||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||
| 495 | 1 | $result = false_position( \&$f, $approx - .1, $approx + .1 ); | |||||||||||||||||||||||||||||||
| 496 | } || die "find: false_position refinement failed: ".$@; | ||||||||||||||||||||||||||||||||
| 497 | 1 | return $result; | |||||||||||||||||||||||||||||||
| 498 | } | ||||||||||||||||||||||||||||||||
| 499 | |||||||||||||||||||||||||||||||||
| 500 | |||||||||||||||||||||||||||||||||
| 501 | =head1 FUTURE IMPROVEMENTS | ||||||||||||||||||||||||||||||||
| 502 | |||||||||||||||||||||||||||||||||
| 503 | The first priority witll be adding more algorithms. Then it might be | ||||||||||||||||||||||||||||||||
| 504 | interesting to implement a mechanism where several algorithms could be | ||||||||||||||||||||||||||||||||
| 505 | tried on love data to choose the best algorithm for the | ||||||||||||||||||||||||||||||||
| 506 | domain. Lastly, using Inline::C or XS to rewrite the algos in C would | ||||||||||||||||||||||||||||||||
| 507 | be desirable for performance. Ideally I would like it to work so that | ||||||||||||||||||||||||||||||||
| 508 | if a C compiler is availible, then the C version is compiled and used, | ||||||||||||||||||||||||||||||||
| 509 | otherwise the Perl version is used. I've seen examples of this, but | ||||||||||||||||||||||||||||||||
| 510 | don't know how it is done at the moment, so this is a ways off. | ||||||||||||||||||||||||||||||||
| 511 | |||||||||||||||||||||||||||||||||
| 512 | Finish of test coverage. | ||||||||||||||||||||||||||||||||
| 513 | |||||||||||||||||||||||||||||||||
| 514 | =head1 AUTHOR | ||||||||||||||||||||||||||||||||
| 515 | |||||||||||||||||||||||||||||||||
| 516 | Spencer Ogden, C<< <spencer@spencerogden.com> >> | ||||||||||||||||||||||||||||||||
| 517 | |||||||||||||||||||||||||||||||||
| 518 | =head1 BUGS | ||||||||||||||||||||||||||||||||
| 519 | |||||||||||||||||||||||||||||||||
| 520 | The find function is broken | ||||||||||||||||||||||||||||||||
| 521 | |||||||||||||||||||||||||||||||||
| 522 | Please report any bugs or feature requests to | ||||||||||||||||||||||||||||||||
| 523 | C<bug-algorithm-bisection@rt.cpan.org>, or through the web interface | ||||||||||||||||||||||||||||||||
| 524 | at L<http://rt.cpan.org>. I will be notified, and then you'll | ||||||||||||||||||||||||||||||||
| 525 | automatically be notified of progress on your bug as I make changes. | ||||||||||||||||||||||||||||||||
| 526 | |||||||||||||||||||||||||||||||||
| 527 | =head1 COPYRIGHT & LICENSE | ||||||||||||||||||||||||||||||||
| 528 | |||||||||||||||||||||||||||||||||
| 529 | Copyright 2005 Spencer Ogden, All Rights Reserved. | ||||||||||||||||||||||||||||||||
| 530 | |||||||||||||||||||||||||||||||||
| 531 | This program is free software; you can redistribute it and/or modify it | ||||||||||||||||||||||||||||||||
| 532 | under the same terms as Perl itself. | ||||||||||||||||||||||||||||||||
| 533 | |||||||||||||||||||||||||||||||||
| 534 | =cut | ||||||||||||||||||||||||||||||||
| 535 | |||||||||||||||||||||||||||||||||
| 536 | 7 | 1; # End of Math::Bisection | |||||||||||||||||||||||||||||||