Suppose you have a number of seconds *n* and you want to convert it to hours and seconds. If you divide *n* by 3600, the quotient is the number of hours and the remainder is the number of seconds.

For example, suppose *n* = 8072022. Here’s the obvious way to do the calculation in Python:

def div3600(n): return (n // 3600, n % 3600)

This returns (242, 822) if we pass in 872022, and so 872022 seconds equals 242 hours and 822 seconds.

However, as is often the case, the most obvious approach is not the fastest. In general, division is much slower than multiplication and addition, though division by powers of 2 is very fast. So we could speed up our calculation if we had a way to change the problem to one that requires dividing by powers of 2 rather than dividing by 3600.

Here’s another Python program that computes the same result a very different way.

def div3600(n): assert(0 <= n < 2255761) t = 1193047*n q = t >> 32 r = 3600*(t & 4294967295) >> 32 assert(q == n // 3600) assert(r == n % 3600) return (q, r)

This algorithm does not work for all *n*, hence the assert statement at the top of the function verifying that *n* is in range. Notice that there are no explicit division statements. There is a bit shift, which amounts to a division by 2^{32}, and there is a bitwise and, which amounts to taking the remainder after dividing by 2^{32}.

The Python code is a prototype. If we cared so much about performance that we would consider using this algorithm, we shouldn’t be using Python. Here is a C implementation that would be more realistic.

void div3600(long n, long* q, long* r) { long t = 1193047*n; *q = t >> 32; *r = 3600*(t & 4294967295) >> 32; }

The algorithm presented above is a example from [1]. In that paper the authors study integer functions of the form

(α*r* + β) // δ

and

(α*r* + β) % δ

and their application to speeding up software [2], especially calendar algorithms. The authors include benchmarks in several programming languages that verify that their algorithms are indeed significantly faster than the direct approach.

Of course most applications would do well to use direct calculations which are obviously correct. But a large scale application that does these kinds of calculations over and over might benefit from an obfuscated but more efficient algorithm.

***

[1] Cassio Neri and Lorenz Schneider. Euclidean Affine Functions and Applications to Calendar Algorithms. Arxiv 2102.06959v1.

[2] Here I’ve used Python’s integer division notation `//`

. The author’s use C notation, where `/`

means quotient because the context is integer arguments. I prefer Python’s notation because it is more explicit.

This is so tedious but is 242 or 2242 hours? High school teacher here. Love reading your blog.

Thanks for catching the typo.

Isn’t this just a way of using the fact that 1/3600 is approximately 1193047/(2^32) ? Replacing division by a constant with multiplication by a reciprocal is nearly always going to be faster… (Although full disclosure I haven’t read the linked to site.)

That’s an interesting way to look at it. The arXiv article is more general, but also harder to follow.