[](https://travis-ci.org/nieksand/rootfind)
[](https://crates.io/crates/rootfind)
[](http://docs.rs/rootfind)
# Root Finding
***Work in progress. Not ready for production use!***
Root finding algorithms implemented in Rust.
This package aims to provide robust numerical methods suitable for production
use. It includes extensive documentation and test coverage.
Currently features:
* Bracket generation
* Bisection
* False Position, Illinois method
Some additional methods are only available in their "naive" form at this time.
These are suitable for reproducing results from academic literature but not for
production use:
* Newton-Raphson
* Halley's Method
Work is in progress on production-suitable variants which hybridize these
higher order methods with bisection to ensure convergence.
Custom convergence criteria can be supplied by the IsConverged trait. Some
reasonable canned implementations are provided.
As with most numerical methods, root finding algorithms require that you
understand what you're trying to achieve, the nature of the input function, the
properties of the algorithm being used, and more.
Feedback is greatly appreciated.
# Usage
See the rustdocs for detailed documentation.
This quick example is an excerpt from tests/integration.rs.
extern crate rootfind;
use rootfind::bracket::{Bounds, BracketGenerator};
use rootfind::solver::bisection;
use rootfind::wrap::RealFn;
// roots at 0, pi, 2pi, ...
let f_inner = |x: f64| x.sin();
// rootfind determines via traits what is f(x), df(x), d2f(x), etc.
// the RealFn wrapper annotates our closure accordingly.
let f = RealFn::new(&f_inner);
// search for root-holding brackets
let window_size = 0.1;
let bounds = Bounds::new(-0.1, 6.3);
for (i, b) in BracketGenerator::new(&f, bounds, window_size)
.into_iter()
.enumerate()
{
// find root using bisection method
let max_iterations = 100;
let computed_root = bisection(&f, &b, max_iterations).expect("found root");
// demonstrate that we found root
let pi = std::f64::consts::PI;
let expected_root = (i as f64) * pi;
assert!(
(computed_root - expected_root).abs() < 1e-9,
format!("got={}, wanted={}", computed_root, expected_root)
);
}
# Remaining Work
## Algorithms
1. "Safe" variants of Newton-Raphson and Halley's Method which hybridize with a
bracketing method to ensure global convergence.
2. A TOMS-748 implementation for finding roots when no analytic derivatives are
available. (This provides a good default choice with bisection and
false-position as fall back options).
3. Specialized routines for finding roots of Polynomials.
## Design
1. Provide visibility into the solver state as it runs.
2. Allow optimized Newton-Raphson where the fraction f(x)/f'(x) is supplied
directly rather than being computed at runtime. Cancellation of terms
provides an opportunity for performance optimization.
3. Convergence criteria for bracketing methods.
4. Check if converged brackets actually closed on a root rather than jump
discontinuity.
## Cross Validation
I want to cross-validate both the design and implementation against the C++
Boost, SciPy, and GSL root finding implementations.
## Road to 1.0.0
This project uses semantic versioning (major.minor.patch). The remaining work
mostly falls under 'minor' increments. When that's all done, I would like some
external review or feedback before cutting the official 1.0.0 release.
# References
The Numerical Recipes book covers both implementation and methodology for
root-finding in depth:
William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P.
Flannery. 2007. Numerical Recipes 3rd Edition: The Art of Scientific Computing
(3 ed.). Cambridge University Press, New York, NY, USA.
This is a top resource for practioners. However, the code examples are
encumbered by copyright so the Rust rootfind library steers clear of NR's
implementations.
Another reasonable introduction to root finding can be found in:
Recktenwald, G. W. (2000). Numerical methods with MATLAB: implementations and
applications. Upper Saddle River, NJ: Prentice Hall.
Wikipedia's "Root-finding algorithm" page provides a high-level overview of
root-finding techniques, but it lacks the guidance and detail for practioners.
The algorithm specific pages are worth looking at.
I have also found the Boost, SciPy, and Gnu Scientific Library root-finding
implementations and documentation to be helpful.
# Author
This was written by Niek Sanders (niek.sanders@gmail.com).
# Unlicense
This is free and unencumbered software released into the public domain.
Anyone is free to copy, modify, publish, use, compile, sell, or distribute this
software, either in source code form or as a compiled binary, for any purpose,
commercial or non-commercial, and by any means.
In jurisdictions that recognize copyright laws, the author or authors of this
software dedicate any and all copyright interest in the software to the public
domain. We make this dedication for the benefit of the public at large and to
the detriment of our heirs and successors. We intend this dedication to be an
overt act of relinquishment in perpetuity of all present and future rights to
this software under copyright law.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS BE
LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
For more information, please refer to <http://unlicense.org/>