Euclidean Affine Functions and Applications to Calendar Algorithms
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2021
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910773843853312 |
|---|---|
| author | Neri, Cassio Schneider, Lorenz |
| author_facet | Neri, Cassio Schneider, Lorenz |
| contents | We study properties of Euclidean affine functions (EAFs), namely those of the form $f(r) = (α\cdot r + β)/δ$, and their closely related expression $\mathring{f}(r) = (α\cdot r + β)\%δ$, where $r$, $α$, $β$ and $δ$ are integers, and where $/$ and $\%$ respectively denote the quotient and remainder of Euclidean division. We derive algebraic relations and numerical approximations that are important for the efficient evaluation of these expressions in modern CPUs. Since simple division and remainder are particular cases of EAFs (when $α= 1$ and $β= 0$), the optimisations proposed in this paper can also be appplied to them. Such expressions appear in some of the most common tasks in any computer system, such as printing numbers, times and dates. We use calendar calculations as the main application example because it is richer with respect to the number of EAFs employed. Specifically, the main application presented in this article relates to Gregorian calendar algorithms. We will show how they can be implemented substantially more efficiently than is currently the case in widely used C, C++, C# and Java open source libraries. Gains in speed of a factor of two or more are common. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2102_06959 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Euclidean Affine Functions and Applications to Calendar Algorithms Neri, Cassio Schneider, Lorenz Data Structures and Algorithms Discrete Mathematics 65Y04 68R01 We study properties of Euclidean affine functions (EAFs), namely those of the form $f(r) = (α\cdot r + β)/δ$, and their closely related expression $\mathring{f}(r) = (α\cdot r + β)\%δ$, where $r$, $α$, $β$ and $δ$ are integers, and where $/$ and $\%$ respectively denote the quotient and remainder of Euclidean division. We derive algebraic relations and numerical approximations that are important for the efficient evaluation of these expressions in modern CPUs. Since simple division and remainder are particular cases of EAFs (when $α= 1$ and $β= 0$), the optimisations proposed in this paper can also be appplied to them. Such expressions appear in some of the most common tasks in any computer system, such as printing numbers, times and dates. We use calendar calculations as the main application example because it is richer with respect to the number of EAFs employed. Specifically, the main application presented in this article relates to Gregorian calendar algorithms. We will show how they can be implemented substantially more efficiently than is currently the case in widely used C, C++, C# and Java open source libraries. Gains in speed of a factor of two or more are common. |
| title | Euclidean Affine Functions and Applications to Calendar Algorithms |
| topic | Data Structures and Algorithms Discrete Mathematics 65Y04 68R01 |
| url | https://arxiv.org/abs/2102.06959 |