Euclidean Affine Functions and their Application to Calendar Algorithms

Cassio Neri and Lorenz Schneider
Additional contact information
Lorenz Schneider: EM - EMLyon Business School

Post-Print from HAL

Abstract: "In everyday life, dates are specified in terms of year, month and day, but this is not how digital devices represent them. Such devices continuously count elapsed days since a certain reference date, usually 1 January 1970. Accordingly, the date exactly one year after this reference is 1 January 1971 and digital devices represent it as 365. Conversions between machine and human formats are, arguably, amongst the most common operations performed by digital devices and constitute the subject of this article. We introduce Euclidean affine functions (EAFs) and study their properties. EAFs are of the form f(n) = (a.n+b)/d , where n, a, b, and d are integers and where denotes the quotient of Euclidean division. We derive algebraic relations and numerical approximations that are important for the efficient evaluation of these expressions in modern CPUs. Since division is a particular case of an EAF (when a = 1 and b = 0 ), the optimisations proposed in this article can also be applied to division. The main application presented in this article is the derivation of conversion algorithms for the Gregorian calendar. We will show that 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. These algorithms have been implemented in GCC, the Linux Kernel and .NET."

Keywords: Euclidean Affine Functions; Integer Division; Calendar Algorithms (search for similar items in EconPapers)
Date: 2023-04-01
Note: View the original document on HAL open archive server: https://hal.science/hal-04346335
References: View complete reference list from CitEc
Citations:

Published in Software: Practice and Experience, 2023, 53 (4), pp.937-970

Downloads: (external link)
https://hal.science/hal-04346335/document (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:hal-04346335

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().