NCBI C++ ToolKit
njn_root.hpp
Go to the documentation of this file.

Go to the SVN repository for this file.

1 #ifndef ALGO_BLAST_GUMBEL_PARAMS__INCLUDED_NJN_ROOT
2 #define ALGO_BLAST_GUMBEL_PARAMS__INCLUDED_NJN_ROOT
3 
4 /* $Id: njn_root.hpp 50702 2011-08-01 13:59:27Z boratyng $
5 * ===========================================================================
6 *
7 * PUBLIC DOMAIN NOTICE
8 * National Center for Biotechnology Information
9 *
10 * This software/database is a "United States Government Work" under the
11 * terms of the United States Copyright Act. It was written as part of
12 * the author's offical duties as a United States Government employee and
13 * thus cannot be copyrighted. This software/database is freely available
14 * to the public for use. The National Library of Medicine and the U.S.
15 * Government have not placed any restriction on its use or reproduction.
16 *
17 * Although all reasonable efforts have been taken to ensure the accuracy
18 * and reliability of the software and data, the NLM and the U.S.
19 * Government do not and cannot warrant the performance or results that
20 * may be obtained by using this software or data. The NLM and the U.S.
21 * Government disclaim all warranties, express or implied, including
22 * warranties of performance, merchantability or fitness for any particular
23 * purpose.
24 *
25 * Please cite the author in any work or product based on this material.
26 *
27 * ===========================================================================*/
28 
29 /*****************************************************************************
30 
31 File name: njn_root.hpp
32 
33 Author: John Spouge
34 
35 Contents:
36 
37 ******************************************************************************/
38 
39 #include <corelib/ncbitype.h>
40 #include <assert.h>
41 #include <math.h>
42 
43 #include "njn_approx.hpp"
44 #include "njn_function.hpp"
45 #include "njn_ioutil.hpp"
46 
47 
48 BEGIN_NCBI_SCOPE
49 BEGIN_SCOPE(blast)
50 
51 BEGIN_SCOPE(Njn)
52 BEGIN_SCOPE(Root)
53 
54 
55  const double FAILED = HUGE_VAL;
56 
57  // All routines find roots.
58  // They return FAILED if the root is not located within *itmax_ iterations.
59  // If not a default 0 pointer, *itmax = iterations left.
60 
61  template <typename T>
62  double newtonRaphson ( // finds root f_(x_) = y_ in [p_, q_] with derivative y_'
63  double y_, // f_ (x_) = y_
64  double (*f_) (double, const T &), // function : param_ contains parameters
65  double (*df_) (double, const T &), // derivative of function
66  const T &param_, // parameters for function
67  double p_, // end-point
68  double x_, // initial guess : can be arbitrary
69  double q_, // end-point
70  double tol_, // absolute tolerance
71  double rtol_, // relative tolerance : set to 0.0 to ignore
72  Int4 *itmax_); // maximum # of permitted iterations : default = 0
73  // bisection locates x_ : f_ (x_) = y_ to within absolute error +-tol_,
74  // then uses derivative information through a Newton-Raphson alternative
75  //
76  // asserts f_ (p_) <= y_ <= f_ (q_) or f_ (q_) <= y_ <= f_ (p_)
77 
78  template <typename T>
79  double bisection ( // finds root f_ (x_) = y_ in [p_, q_]
80  double y_, // f_ (x_) = y_
81  double (*f_) (double, const T &), // function : param_ contains parameters
82  const T &param_, // parameters for function
83  double p_, // end-point
84  double q_, // end-point
85  double tol_, // absolute tolerance
86  double rtol_, // relative tolerance : set to 0.0 to ignore
87  Int4 *itmax_); // maximum # of permitted iterations : default = 0
88  // bisection locates x_ : f_ (x_) = y to within absolute error +-tol_,
89  //
90  // asserts f_ (p_) <= y_ <= f_ (q_) or f_ (q_) <= y_ <= f_ (p_)
91 
92  template <typename T>
93  double hunt ( // finds root f_(x_) = y_ in (p_, q_) by looking until mesh = tol_
94  double y_, // f_ (x_) = y_
95  double (*f_) (double, const T &), // function : param_ contains parameters
96  const T &param_, // parameters for function
97  double p_, // end-point
98  double q_, // end-point
99  double tol_, // absolute tolerance
100  double rtol_, // relative tolerance : set to 0.0 to ignore
101  Int4 *itmax_); // maximum # of permitted iterations : default = 0
102  // hunt locates x_ : f_ (x_) = y to within absolute error +-tol_,
103 
104  template <typename T>
105  double huntExtreme ( // finds root f_(x_) = y_ in (p_, q_) by looking until mesh = tol_
106  double y_, // f_ (x_) = y_
107  double (*f_) (double, const T &), // function : param_ contains parameters
108  const T &param_, // parameters for function
109  double p_, // end-point
110  double q_, // end-point
111  double tol_, // absolute tolerance
112  double rtol_, // relative tolerance : set to 0.0 to ignore
113  Int4 *itmax_, // maximum # of permitted iterations : default = 0
114  bool isLargest_); // ? find the largest root ?
115  // huntExtreme locates x_ : f_ (x_) = y to within absolute error +-tol_,
116  // finding either the largest or smallest root in the interval (p_, q_)
117  // huntExtreme looks for a change in sign, so y_ should not be an extremum.
118 
119  //
120  // Specializations of the template follow.
121  //
122 
123  inline double newtonRaphson ( // finds root f_(x_) = y_ in [p_, q_] with derivative y_'
124  double y_, // f_ (x_) = y_
125  double (*f_) (double), // function
126  double (*df_) (double), // derivative of function
127  double p_, // end-point
128  double x_, // initial guess : can be arbitrary
129  double q_, // end-point
130  double tol_, // absolute tolerance
131  double rtol_ = 0.0, // relative tolerance : set to 0.0 to ignore
132  Int4 *itmax_ = 0); // maximum # of permitted iterations : default = 0
133  // bisection routine locates x_ : f_ (x_) = y_ to within absolute error +-tol_,
134  // then uses derivative information through a Newton-Raphson alternative
135  //
136  // asserts f_ (p_) <= y_ <= f_ (q_) or f_ (q_) <= y_ <= f_ (p_)
137 
138  inline double bisection ( // finds root f_(x_) = y_ in [p_, q_]
139  double y_, // f_ (x_) = y_
140  double (*f_) (double), // function
141  double p_, // end-point
142  double q_, // end-point
143  double tol_, // absolute tolerance
144  double rtol_ = 0.0, // relative tolerance : set to 0.0 to ignore
145  Int4 *itmax_ = 0); // maximum # of permitted iterations : default = 0
146  // bisection routine locates x_ : f_ (x_) = y to within absolute error +-tol_,
147  //
148  // asserts f_ (p_) <= y_ <= f_ (q_) or f_ (q_) <= y_ <= f_ (p_)
149 
150  inline double hunt ( // finds root f_ (x_) = y_ in (p_, q_) by looking until mesh = tol_
151  double y_, // f_ (x_) = y_
152  double (*f_) (double), // function : param_ contains parameters
153  double p_, // end-point
154  double q_, // end-point
155  double tol_, // absolute tolerance
156  double rtol_ = 0.0, // relative tolerance : set to 0.0 to ignore
157  Int4 *itmax_ = 0); // maximum # of permitted iterations : default = 0
158 
159  inline double huntExtreme ( // finds root f_(x_) = y_ in (p_, q_) by looking until mesh = tol_
160  double y_, // f_ (x_) = y_
161  double (*f_) (double), // function : param_ contains parameters
162  double p_, // end-point
163  double q_, // end-point
164  double tol_, // absolute tolerance
165  double rtol_ = 0.0, // relative tolerance : set to 0.0 to ignore
166  Int4 *itmax_ = 0, // maximum # of permitted iterations : default = 0
167  bool isLargest_ = false); // ? find the largest root ?
168  // huntExtreme locates x_ : f_ (x_) = y to within absolute error +-tol_,
169  // finding either the largest or smallest root in the interval (p_, q_)
170  // huntExtreme looks for a change in sign, so y_ should not be an extremum.
171 
172 END_SCOPE(Root)
173 END_SCOPE(Njn)
174 
175 //
176 // There are no more declarations beyond this point.
177 //
178 
179 BEGIN_SCOPE(Njn)
180 BEGIN_SCOPE(Root)
181 
182  typedef double DoubleFct (double);
183 
184  DoubleFct *s_f = 0;
185  DoubleFct *s_df = 0;
186  const double ZERO = 0.0;
187 
188  double f (double x_, const double &y_) {return (*s_f) (x_);}
189  double df (double x_, const double &y_) {return (*s_df) (x_);}
190 
191  double newtonRaphson ( // finds root f_(x_) = y_ in [p_, q_] with derivative y_'
192  double y_, // f_ (x_) = y_
193  double (*f_) (double x_), // function
194  double (*df_) (double x_), // derivative of function
195  double p_, // end-point
196  double x_, // initial guess : can be arbitrary
197  double q_, // end-point
198  double tol_, // absolute tolerance
199  double rtol_, // relative tolerance
200  Int4 *itmax_) // maximum # of permitted iterations
201  {
202  s_f = f_;
203  s_df = df_;
204  return newtonRaphson (y_, f, df, ZERO, p_, x_, q_, tol_, rtol_, itmax_);
205  }
206 
207  double bisection ( // finds root f_(x_) = y_ in [p_, q_]
208  double y_, // f_ (x_) = y_
209  double (*f_) (double x_), // function
210  double p_, // end-point
211  double q_, // end-point
212  double tol_, // absolute tolerance
213  double rtol_, // relative tolerance
214  Int4 *itmax_) // maximum # of permitted iterations
215  {
216  s_f = f_;
217  return bisection (y_, f, ZERO, p_, q_, tol_, rtol_, itmax_);
218  }
219 
220  double hunt ( // finds root f_(x_) = y_ in (p_, q_)
221  double y_, // f_ (x_) = y_
222  double (*f_) (double x_), // function
223  double p_, // end-point
224  double q_, // end-point
225  double tol_, // absolute tolerance
226  double rtol_, // relative tolerance
227  Int4 *itmax_) // maximum # of permitted iterations
228  {
229  s_f = f_;
230  return hunt (y_, f, ZERO, p_, q_, tol_, rtol_, itmax_);
231  }
232 
233  double huntExtreme ( // finds root f_(x_) = y_ in (p_, q_)
234  double y_, // f_ (x_) = y_
235  double (*f_) (double x_), // function
236  double p_, // end-point
237  double q_, // end-point
238  double tol_, // absolute tolerance
239  double rtol_, // relative tolerance
240  Int4 *itmax_, // maximum # of permitted iterations
241  bool isLargest_) // ? find the largest root ?
242  {
243  s_f = f_;
244  return huntExtreme (y_, f, ZERO, p_, q_, tol_, rtol_, itmax_, isLargest_);
245  }
246 
247  template <typename T>
248  double newtonRaphson ( // finds root f_(x_) = y_ in [p_, q_] with derivative y_'
249  double y_, // f_ (x_) = y_
250  double (*f_) (double, const T &), // function : param_ contains parameters
251  double (*df_) (double, const T &), // derivative of function
252  const T &param_, // parameters for function
253  double p_, // end-point
254  double x_, // initial guess : can be arbitrary
255  double q_, // end-point
256  double tol_, // absolute tolerance
257  double rtol_, // relative tolerance : set to 0.0 to ignore
258  Int4 *itmax_) // maximum # of permitted iterations : default = 0
259  {
260  // #define F(x_) ((*f_) (x_, param_) - y_)
261  // #define DF(x_) ((*df_) (x_, param_))
262 
263  assert (p_ != HUGE_VAL && p_ != -HUGE_VAL);
264  assert (q_ != HUGE_VAL && q_ != -HUGE_VAL);
265 
266  // checks for improper bracketing and end-point root.
267  double fp = (*f_) (p_, param_) - y_;
268  double fq = (*f_) (q_, param_) - y_;
269  if (fp * fq > 0.0)
270  IoUtil::abort ("Root::newtonRaphson : root not bracketed");
271 
272  if (fp == 0.0) return p_;
273  if (fq == 0.0) return q_;
274 
275  if (p_ == q_) IoUtil::abort ("Root::newtonRaphson : p_ == q_");
276 
277  double x = x_;
278  // swaps end-points if necessary to make p_ < q_
279  if (q_ < p_) swap(p_, q_);
280 
281  // makes an initial guess within [p_, q_]
282  if (x_ < p_ || q_ < x_) x = 0.5 * (p_ + q_);
283 
284  // swaps end-points if necessary to make F (p_) < 0.0 < F (q_)
285  if (fp > 0.0) swap(p_, q_);
286 
287  // Set up the bisection & Newton-Raphson iteration.
288 
289  double dx; // present interval length
290  double dxold; // old interval length
291  double fx; // f_(x_)-y_
292  double dfx; // Df(x_)
293 
294  dxold = dx = p_ - q_;
295 
296  Int4 iter = 100; // default iterations
297  Int4 *itmax = itmax_ == 0 ? &iter: itmax_;
298 
299  for ( ; 0 < *itmax; --*itmax) {
300 
301  fx = (*f_) (x, param_) - y_;
302  if (fx == 0.0) { // Check for termination.
303  return x;
304  } else if (fx < 0.0) {
305  p_ = x;
306  } else {
307  q_ = x;
308  }
309  dfx = (*df_) (x, param_) - y_;
310 
311  // Is the root out of bounds, so bisection is faster than Newton-Raphson?
312  if ((dfx * (x-p_) - fx) * (dfx * (x - q_) - fx) >= 0.0 ||
313  2.0 * fabs (fx) > fabs (dfx * dx)) {
314 
315  // bisect
316  dx = dxold;
317  dxold = 0.5 * (p_ - q_);
318  x = 0.5 * (p_ + q_);
319 
320  if (fabs (dxold) <= tol_) return x;
321 
322  } else {
323 
324  // Newton-Raphson
325  dx = dxold;
326  dxold = fx / dfx;
327  x -= dxold;
328 
329  if (fabs (dxold) < tol_ || fabs (dxold) < rtol_ * fabs (x)) {
330  if (((*f_) ((x - Function::signum (dxold) * tol_), param_) - y_) * fx < 0.0) return x;
331  }
332  }
333  }
334 
335  return FAILED; // failure
336  }
337 
338  template <typename T>
339  double bisection ( // finds root f_ (x_) = y_ in [p_, q_]
340  double y_, // f_ (x_) = y_
341  double (*f_) (double, const T &), // function : param_ contains parameters
342  const T &param_, // parameters for function
343  double p_, // end-point
344  double q_, // end-point
345  double tol_, // absolute tolerance
346  double rtol_, // relative tolerance : set to 0.0 to ignore
347  Int4 *itmax_) // maximum # of permitted iterations : default = 0
348  {
349  assert (p_ != HUGE_VAL && p_ != -HUGE_VAL);
350  assert (q_ != HUGE_VAL && q_ != -HUGE_VAL);
351 
352  // checks for improper bracketing and end-point root.
353  double fp = (*f_) (p_, param_) - y_;
354  double fq = (*f_) (q_, param_) - y_;
355  if (fp * fq > 0.0)
356  IoUtil::abort ("Root::bisection : root not bracketed");
357 
358  if (fp == 0.0) return p_;
359  if (fq == 0.0) return q_;
360 
361  if (p_ == q_) IoUtil::abort ("Root::bisection : p_ == q_");
362 
363  // swaps end-points if necessary to make F (p_) < 0.0 < F (q_)
364  if (fp > 0.0) swap(p_, q_);
365 
366  double x = 0.0;
367  double fx = 0.0;
368 
369  Int4 iter = 100; // default iterations
370  Int4 *itmax = itmax_ == 0 ? &iter: itmax_;
371 
372  x = 0.5 * (p_ + q_);
373  for ( ; 0 < *itmax; --*itmax) {
374 
375  fx = (*f_) (x, param_) - y_;
376  if (fx < 0.0) {
377  p_ = x;
378  } else {
379  q_ = x;
380  }
381  x = 0.5 * (p_ + q_);
382 
383  if (Approx::absRelApprox <double> (p_, x, tol_, rtol_)) return x;
384  }
385 
386  return FAILED; // failure
387  }
388 
389  template <typename T>
390  double hunt ( // finds root f_(x_) = y_ in (p_, q_) by looking until mesh = tol_
391  double y_, // f_ (x_) = y_
392  double (*f_) (double, const T &), // function : param_ contains parameters
393  const T &param_, // parameters for function
394  double p_, // end-point
395  double q_, // end-point
396  double tol_, // absolute tolerance
397  double rtol_, // relative tolerance : set to 0.0 to ignore
398  Int4 *itmax_) // maximum # of permitted iterations : default = 0
399  {
400  assert (p_ != HUGE_VAL && p_ != -HUGE_VAL);
401  assert (q_ != HUGE_VAL && q_ != -HUGE_VAL);
402 
403  if (p_ == q_) IoUtil::abort ("Root::hunt : p_ == q_");
404 
405  double x0 = 0.5 * (p_ + q_);
406  double fx0 = (*f_) (x0, param_) - y_;
407  if (fx0 == 0.0) return x0;
408 
409  // swaps end-points if necessary to make p_ < q_
410  if (q_ < p_) swap(p_, q_);
411 
412  size_t pts = 2;
413  double del = 0.5 * (q_ - p_);
414  double x = 0.0;
415  double fx = 0.0;
416 
417  Int4 iter = 1000; // default iterations
418  Int4 *itmax = itmax_ == 0 ? &iter: itmax_;
419 
420  while (tol_ <= del) {
421 
422  x = p_ + 0.5 * del;
423  for (size_t i = 0; i < pts && 0 < *itmax; i++, --*itmax) {
424 
425  fx = (*f_) (x, param_) - y_;
426  if (fx * fx0 < 0.0) return bisection <T> (y_, f_, param_, x, x0, tol_, rtol_, itmax);
427  x += del;
428  }
429  if (iter == 0) return FAILED;
430 
431  pts *= 2;
432  del *= 0.5;
433  }
434 
435  return FAILED; // failure
436  }
437 
438  template <typename T>
439  double huntExtreme ( // finds root f_(x_) = y_ in (p_, q_) by looking until mesh = tol_
440  double y_, // f_ (x_) = y_
441  double (*f_) (double, const T &), // function : param_ contains parameters
442  const T &param_, // parameters for function
443  double p_, // end-point
444  double q_, // end-point
445  double tol_, // absolute tolerance
446  double rtol_, // relative tolerance : set to 0.0 to ignore
447  Int4 *itmax_, // maximum # of permitted iterations : default = 0
448  bool isLargest_) // ? find the largest root ?
449  {
450  Int4 iter = 1000; // default iterations
451  Int4 *itmax = itmax_ == 0 ? &iter: itmax_;
452 
453  // swaps end-points if necessary to make p_ < q_
454  if (q_ < p_) swap(p_, q_);
455 
456  // check there is a root
457  double x = hunt <T> (y_, f_, param_, p_, q_, tol_, rtol_, itmax);
458  double x0 = x;
459 
460  // find the extreme root
461  if (isLargest_) {
462  while (0 < *itmax && x != FAILED) {
463  x0 = x;
464  x = hunt <T> (y_, f_, param_, x, q_, tol_, rtol_, itmax);
465  }
466  } else {
467  while (0 < *itmax && x != FAILED) {
468  x0 = x;
469  x = hunt <T> (y_, f_, param_, p_, x, tol_, rtol_, itmax);
470  }
471  }
472 
473  return x0;
474  }
475 
476 
477 END_SCOPE(Root)
478 END_SCOPE(Njn)
479 
480 END_SCOPE(blast)
481 END_NCBI_SCOPE
482 
483 #endif //! ALGO_BLAST_GUMBEL_PARAMS__INCLUDED_NJN_ROOT
false
#define false
Definition: bool.h:36
T
#define T(s)
Definition: common.h:230
fp
static const char fp[]
Definition: des.c:87
swap
void swap(NCBI_NS_NCBI::pair_base_member< T1, T2 > &pair1, NCBI_NS_NCBI::pair_base_member< T1, T2 > &pair2)
Definition: ncbimisc.hpp:1508
Int4
int32_t Int4
4-byte (32-bit) signed integer
Definition: ncbitype.h:102
END_NCBI_SCOPE
#define END_NCBI_SCOPE
End previously defined NCBI scope.
Definition: ncbistl.hpp:103
END_SCOPE
#define END_SCOPE(ns)
End the previously defined scope.
Definition: ncbistl.hpp:75
BEGIN_NCBI_SCOPE
#define BEGIN_NCBI_SCOPE
Define ncbi namespace.
Definition: ncbistl.hpp:100
BEGIN_SCOPE
#define BEGIN_SCOPE(ns)
Define a new scope.
Definition: ncbistl.hpp:72
i
int i
Definition: lex.newick.cpp:1456
fabs
#define fabs(v)
Definition: ncbi_dispd.c:46
ncbitype.h
Defines Limits for the types used in NCBI C/C++ toolkit.
njn_approx.hpp
njn_function.hpp
signum
T signum(T x_)
Definition: njn_function.hpp:110
njn_ioutil.hpp
abort
void abort()
s_df
DoubleFct * s_df
Definition: njn_root.hpp:185
f
double f(double x_, const double &y_)
Definition: njn_root.hpp:188
s_f
DoubleFct * s_f
Definition: njn_root.hpp:184
huntExtreme
double huntExtreme(double y_, double(*f_)(double, const T &), const T &param_, double p_, double q_, double tol_, double rtol_, Int4 *itmax_, bool isLargest_)
Definition: njn_root.hpp:439
FAILED
const double FAILED
Definition: njn_root.hpp:55
hunt
double hunt(double y_, double(*f_)(double, const T &), const T &param_, double p_, double q_, double tol_, double rtol_, Int4 *itmax_)
Definition: njn_root.hpp:390
df
double df(double x_, const double &y_)
Definition: njn_root.hpp:189
bisection
double bisection(double y_, double(*f_)(double, const T &), const T &param_, double p_, double q_, double tol_, double rtol_, Int4 *itmax_)
Definition: njn_root.hpp:339
ZERO
const double ZERO
Definition: njn_root.hpp:186
DoubleFct
double DoubleFct(double)
Definition: njn_root.hpp:182
newtonRaphson
double newtonRaphson(double y_, double(*f_)(double, const T &), double(*df_)(double, const T &), const T &param_, double p_, double x_, double q_, double tol_, double rtol_, Int4 *itmax_)
Definition: njn_root.hpp:248
assert
#define assert(x)
Definition: srv_diag.hpp:58
const
#define const
Definition: zconf.h:230
Generated by doxygen 1.9.0
Modified on Tue Dec 05 02:11:25 2023 by modify_doxy.py rev. 669887