72 lines
3.4 KiB
Markdown
72 lines
3.4 KiB
Markdown
# sim-numerics — similarity and analogy as step rules for root finding
|
|
|
|
A bracketing root finder derived from a similarity function, with a decision layer that recognises
|
|
multiple and fractional roots by analogy, and a worst case of twice bisection plus three evaluations
|
|
that holds whatever proposes the step.
|
|
|
|
Everything here is released under the Apache License 2.0; copyright Valeri Sitnikov (`NOTICE`).
|
|
Archive of record, with the paper, the data and the full history:
|
|
[10.5281/zenodo.22894336](https://doi.org/10.5281/zenodo.22894336) (version 1.0.0:
|
|
[10.5281/zenodo.22894337](https://doi.org/10.5281/zenodo.22894337)).
|
|
|
|
## Using the method
|
|
|
|
`lib/` builds `simbracket`, the method as a compiled library (Cython, Python 3.10 or later, wheels for
|
|
Linux and Windows in the archive). It agrees with the reference implementation bit for bit, point and
|
|
evaluation count, on all 868 problems of the six corpora.
|
|
|
|
```python
|
|
from simbracket import find_root, evaluation_bound
|
|
|
|
x, nfev, converged = find_root(f, a, b, xtol=1e-12, maxfev=200)
|
|
# f(a) and f(b) of opposite signs; stops when the bracket is no wider than xtol or f(x) == 0;
|
|
# never more than evaluation_bound(a, b, xtol) = 2*ceil(log2(|b-a|/xtol)) + 3 evaluations
|
|
```
|
|
|
|
From source instead: `simroot.pure.pure_root` with the configuration named `APRIME` in
|
|
`sweep_full.py`.
|
|
|
|
## What it costs
|
|
|
|
On the 240 problems of corpus 4, fixed before the method's code was frozen, the method needs 3656
|
|
evaluations. Chandrupatla's method needs 5717 there, ModAB 5535, Brent 8267 and TOMS 748 8084. It is
|
|
the cheapest of those methods on 77% of the problems, and on 88% of the multiple and fractional
|
|
roots.
|
|
|
|
## Reproducing
|
|
|
|
Use one platform for all numbers. The test functions call `libm`, whose last digit differs between
|
|
platforms, and the same SciPy version scores 2635 for TOMS 748 on Windows against 2636 on Linux for
|
|
the same set. The published numbers are from Linux (Ubuntu 24.04, Python 3.12.3).
|
|
|
|
```
|
|
python -m pytest tests -q # 1205 tests
|
|
python -u verify_article.py # 548 numbers of the paper against the run data
|
|
```
|
|
|
|
Any table of the paper can be recomputed from scratch with its sweep script; each script's docstring
|
|
names the table it produces. Heavy runs belong on a Linux machine, detached, with a log.
|
|
|
|
## Layout
|
|
|
|
```
|
|
simroot/pure.py the method: the similarity step, the decision layer, the projection
|
|
simroot/baselines.py bisection, the false-position family, Ridders, Brent, TOMS 748, ITP
|
|
lib/ the source of the compiled library simbracket
|
|
corpus_*.py the problem corpora, as code
|
|
sweep_*.py the runs; each writes its results file
|
|
verify_article.py every number stated in the paper, against the data
|
|
article/ the paper
|
|
PREREG_*.md POSTHOC_*.md what was recorded before each run, and what after
|
|
FINDINGS_*.md what the diagnoses found
|
|
tests/ 1205 tests; every bug found in an audit is pinned here
|
|
```
|
|
|
|
## What was refuted
|
|
|
|
The archive keeps eleven negative results in the form in which they were written, among them: a
|
|
similarity normalised by the two bracket ends is regula falsi identically; a faster-changing
|
|
similarity is not better; every safeguard that *replaces* the computed step with a midpoint destroys
|
|
the order, which is why the step is projected instead; and the phase detector whose derivation is
|
|
sound and whose estimator is not. They are kept so that they are not reopened.
|