Euclidean affine functions and their application to calendar algorithms. (3rd December 2022)

• Record Type: Journal Article
• Authors: Neri, Cassio; Schneider, Lorenz
• Is Part Of: Software, practice & experience. Volume 53:Number 4(2023)
• Page Start: 937
• Page End: 970
• Publication Date: 2022-12-03
• Subjects: Euclidean affine functions -- integer division -- calendar algorithms; Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.3172
• Languages: English
• ISSNs: 0038-0644

Abstract

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 $$ f(n)=\left(a\cdotp n+b\right)/d $$, where n $$ n $$, a $$ a $$, b $$ b $$, and d $$ 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 $$ a=1 $$ and b = 0 $$ 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.