blib/lib/Math/Function/Roots.pm

filter: Statementstmt 98.4% 128 / 130 Branchbran 84.2% 32 / 38 Conditioncond 54.7% 23 / 42 MC/DCmcdc 28.5% 8 / 28 Subroutinesub 100% 13 / 13 Podpod 100% 8 / 8 totaltotal 81.8% 212 / 259 CC 38 SCAR 20.6
CC
38
Cov
87%
find
16.0
bisection
8.0
false_position
7.0
CRAP 7.8
↑ Summary
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
BranchTrueFalseTotal
if (@_) 9 8 17
123 9 $E = shift;
124 9 ▶ $E = 0 if $E < 0;
Branch: 1 branch
BranchTrueFalseTotal
if $Math::Function::Roots::E < 0 1 8 9
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
BranchTrueFalseTotal
if (@_) 7 4 11
146 7 $Max_Iter = shift;
147 7 ▶ $Max_Iter = 1 if ($Max_Iter < 1);
Branch: 1 branch
BranchTrueFalseTotal
if $Math::Function::Roots::Max_Iter < 1 2 5 7
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
l!l&&r!l&&!r
225
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
ABresult
1X1
011
000
217 9 ▶ my $Max_Iter = $optional{max_iter} || $Max_Iter;
Condition66%2/3
$optional{'max_iter'} || $Math::Function::Roots::Max_Iter
l!l&&r!l&&!r
180
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
ABresult
1X1
011
000
218  
219 9 my ($ay, $by ) = ( &$f($a), &$f($b) );
220 9 ▶ if( ($ay * $by) > 0 ){
Branch: 1 branch
BranchTrueFalseTotal
if ($ay * $by > 0) 1 8 9
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
BranchTrueFalseTotal
if ($py == 0 or abs $a - $b <= $E) { } 6 153 159
elsif ($py * $ay < 0) { } 92 61 153
Condition100%3/3
$py == 0 or abs $a - $b <= $E
l!l&&r!l&&!r
42153
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
ABresult
1X1
011
000
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
l!l&&r!l&&!r
002
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
ABresult
1X1
011
000
297 2 ▶ my $Max_Iter = $optional{max_iter} || $Max_Iter;
Condition33%1/3
$optional{'max_iter'} || $Math::Function::Roots::Max_Iter
l!l&&r!l&&!r
020
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
ABresult
1X1
011
000
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
BranchTrueFalseTotal
if (abs $p - $last_p <= $E) 1 61 62
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
l!l&&r!l&&!r
012
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
ABresult
1X1
011
000
336 3 ▶ my $Max_Iter = $optional{max_iter} || $Max_Iter;
Condition33%1/3
$optional{'max_iter'} || $Math::Function::Roots::Max_Iter
l!l&&r!l&&!r
030
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
ABresult
1X1
011
000
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
BranchTrueFalseTotal
if ($q1 eq 0 or abs $p - $p1 <= $E) 2 18 20
Condition100%3/3
$q1 eq 0 or abs $p - $p1 <= $E
l!l&&r!l&&!r
1118
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
ABresult
1X1
011
000
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
l!l&&r!l&&!r
043
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
ABresult
1X1
011
000
387 7 ▶ my $Max_Iter = $optional{max_iter} || $Max_Iter;
Condition33%1/3
$optional{'max_iter'} || $Math::Function::Roots::Max_Iter
l!l&&r!l&&!r
070
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
ABresult
1X1
011
000
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
BranchTrueFalseTotal
if $ay * $by > 0 1 6 7
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
BranchTrueFalseTotal
if (abs $py - $last_py <= $E) { } 5 85 90
elsif ($py * $by < 0) { } 82 3 85
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
BranchTrueFalseTotal
if (defined $_[0] and $_[0] =~ !/epsilon|max_iter/) 0 1 1
Condition33%1/3
defined $_[0] and $_[0] =~ !/epsilon|max_iter/
!ll&&!rl&&r
100
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/
ABresult
0X0
100
111
448 0 $a = shift;
449 }
450 1 ▶ if( defined $_[0] && $_[0] =~ !/epsilon|max_iter/ ){
Branch: 1 branch
BranchTrueFalseTotal
if (defined $_[0] and $_[0] =~ !/epsilon|max_iter/) 0 1 1
Condition33%1/3
defined $_[0] and $_[0] =~ !/epsilon|max_iter/
!ll&&!rl&&r
100
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/
ABresult
0X0
100
111
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
l!l&&r!l&&!r
001
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
ABresult
1X1
011
000
456 1 ▶ my $Max_Iter = $optional{max_iter} || $Max_Iter;
Condition33%1/3
$optional{'max_iter'} || $Math::Function::Roots::Max_Iter
l!l&&r!l&&!r
010
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
ABresult
1X1
011
000
457  
458 1 ▶ unless( defined $b ){
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $b) 1 0 1
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
BranchTrueFalseTotal
unless (defined $a) 1 0 1
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
BranchTrueFalseTotal
$fa * $fb < 0 or do { do { $fa = &$f($a); $fb = &$f($b); sleep 1; $a = $a * 2; $b = $b * 2 } } 1 1 2
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
BranchTrueFalseTotal
eval { do { $approx = &bisection(\&$f, $a, $b, "epsilon", "0.1") } } or die 'find: Initial bisection approximation failed: ' . $@ 1 0 1
492 1 $approx = bisection( \&$f, $a, $b, epsilon => .1 );
493 } || die "find: Initial bisection approximation failed: ".$@;
494 1 ▶ eval{
Branch: 1 branch
BranchTrueFalseTotal
eval { do { $result = &false_position(\&$f, $approx - "0.1", $approx + "0.1") } } or die 'find: false_position refinement failed: ' . $@ 1 0 1
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
↑ Summary