Range Algebra for Safe Array Splits
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2014
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909858786181120 |
|---|---|
| author | Perisic, Aleksandar |
| author_facet | Perisic, Aleksandar |
| contents | We present a language-agnostic range algebra that derives correct index intervals for splitting arrays and implementing binary search, eliminating off-by-one and empty-range bugs. From two primitives -- $\lfloor n/2\rfloor$ and $\lceil n/2\rceil = \lfloor (n + 1)/2\rfloor$ -- we obtain four canonical splits (Natural, Left+, Right+, Center-cut) with proofs of coverage and balance for all $n \ge 0$ and any base index $b \in \mathbb{Z}$. We record invariants (normalization to left-closed/right-open intervals $[u, w)$ with len $= w - u$), document cross-language division quirks, and give drop-in code patterns and property tests. The result is a small, memorable spec that can be copied verbatim into C/C++/Java/C\#/Go/Rust/Swift/JS/Python. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1402_4843 |
| institution | arXiv |
| publishDate | 2014 |
| record_format | arxiv |
| spellingShingle | Range Algebra for Safe Array Splits Perisic, Aleksandar Programming Languages We present a language-agnostic range algebra that derives correct index intervals for splitting arrays and implementing binary search, eliminating off-by-one and empty-range bugs. From two primitives -- $\lfloor n/2\rfloor$ and $\lceil n/2\rceil = \lfloor (n + 1)/2\rfloor$ -- we obtain four canonical splits (Natural, Left+, Right+, Center-cut) with proofs of coverage and balance for all $n \ge 0$ and any base index $b \in \mathbb{Z}$. We record invariants (normalization to left-closed/right-open intervals $[u, w)$ with len $= w - u$), document cross-language division quirks, and give drop-in code patterns and property tests. The result is a small, memorable spec that can be copied verbatim into C/C++/Java/C\#/Go/Rust/Swift/JS/Python. |
| title | Range Algebra for Safe Array Splits |
| topic | Programming Languages |
| url | https://arxiv.org/abs/1402.4843 |