# 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.