Fast Rational Search via Stern-Brocot Tree
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917159642333184 |
|---|---|
| author | Weyers, Connor Vinodchandran, N. V. |
| author_facet | Weyers, Connor Vinodchandran, N. V. |
| contents | We revisit the problem of rational search: given an unknown rational number $α= \frac{a}{b} \in (0,1)$ with $b \leq n$, the goal is to identify $α$ using comparison queries of the form ``$β\leq α$?''. The problem has been studied several decades ago and optimal query algorithms are known. We present a new algorithm for rational search based on a compressed traversal of the Stern--Brocot tree, which appeared to have been overlooked in the literature. This approach also naturally extends to two related problems that, to the best of our knowledge, have not been previously addressed: (i) unbounded rational search, where the bound $n$ is unknown, and (ii) computing the best (in a precise sense) rational approximation of an unknown real number using only comparison queries. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_18036 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fast Rational Search via Stern-Brocot Tree Weyers, Connor Vinodchandran, N. V. Data Structures and Algorithms Combinatorics We revisit the problem of rational search: given an unknown rational number $α= \frac{a}{b} \in (0,1)$ with $b \leq n$, the goal is to identify $α$ using comparison queries of the form ``$β\leq α$?''. The problem has been studied several decades ago and optimal query algorithms are known. We present a new algorithm for rational search based on a compressed traversal of the Stern--Brocot tree, which appeared to have been overlooked in the literature. This approach also naturally extends to two related problems that, to the best of our knowledge, have not been previously addressed: (i) unbounded rational search, where the bound $n$ is unknown, and (ii) computing the best (in a precise sense) rational approximation of an unknown real number using only comparison queries. |
| title | Fast Rational Search via Stern-Brocot Tree |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2512.18036 |