A faster way to calculate the day of the week

A range of fast modulus techniques that beat compiler output

Converting a day-count ("rata-die") to the day-of-the-week (“weekday”) sounds like it should be so trivial, that there's almost nothing to say about it. But, as it turns out, when we look under the hood, this is a surprisingly complex problem.

Throughout this article I will present a range of really fast functions to solve this problem, tuned for different use cases (throughput vs latency, different platforms etc.). Each outperforms existing solutions, and many have a latency of just a single multiplication plus two cycles. A surprising result is presented: the weekday can be computed in ISO format ([1‥7] instead of [0‥6]), with the exact same instructions, just with tweaked constants (and zero speed penalty).

To give you a taste of the insanity, I'll highlight my favourite function here, this crazy looking 3-instruction sequence (plus a constant load) is accurate over the full signed 32-bit range (it may not be the lowest latency full-range algo in this article, but has the highest throughput for x86):

This article is for people interested in low level bit manipulation, optimising high performance date libraries / database engines, compiler authors, and crazy people in general. The techniques used here generalise to x % (2^N - 1), and new fast modulus techniques are introduced for other divisors such as x % 24 and x % 60 - applicable to timekeeping.

If you're just here to copy/paste and benchmark code in your library, you can jump to the "Function Explorer" which has all code examples on this page available to copy/paste from C++.

Simple Approaches Deep link

Given:   rd = rata-die (day-count, signed 32-Bit int), with epoch 1970-01-01 = Thursday (4)   —   Then:

  —   Where:   weekday ∈ [0‥6] (0 = Sunday)

This is what I would recommend in most non-library code where maintenance is more important than micro-optimisation.
Note that the Rust example overflows for the highest 4 inputs, but assume we don't care about those.

The addition of 4 (or 11 = 7 + 4) is due to the Unix epoch 1970-01-01 being a Thursday. If you number your weekdays differently, or use a different epoch, this might vary.

These "simple approaches" do the job, but they are quite slow, even in the case of Rust with its positive-mod function (rem_euclid), which translated back into C-style pseudocode, looks like the following:

Rust's rem_euclid (compiled pseudocode equivalent) View on Godbolt

1. i32 a = (i64(rd + 4) * -1840700269) >> 32   // Note: This pseudocode assumes

2. i32 b = rd + 4 + a                          // that overflow of signed addition

3. i32 c = (b >> 2) + (u32(b) >> 31)           // is defined as per Rust

4. i32 d = rd - c * 7                          // and two's complement, whereas

5. i32 e = d + 4                               // for C/C++ it is undefined.

6. u32 weekday = e >= 0 ? e : d + 11

A lot more steps than you might have expected, right?

Hinnant Deep link

Howard Hinnant's technique (2014) was adopted by many date libraries (see original article ).

This approach appears designed for simplicity and flexibility. It is the only algorithm from here onwards that does not rely on sign casting or overflow, nor is it bit-width specific. It will be the same logic for 8-bit through to 64-bit.

Hinnant points out in his article that this covers the full signed 32-bit range, except for the highest 4 inputs, which in C/C++ results in undefined behaviour at this extreme (> 5.8M years in the future). In practice, on 2's complement machines, it usually still works for those values, but this is not guaranteed by the compiler.

Although this is not presented as very fast in the opening bar-chart, it's very fast on Raspberry Pi Zero (and presumably also on older chips).

Neri Deep link

As usual, Cassio Neri's work is the modern gold standard. In 2024 Neri published a very clean full-range solution to this problem (see post ):

If you want something pretty fast, full-range, and not too low-level, then this is the function for you.

The real trick to avoiding overflow here is the cast from signed to unsigned before doing any work.
Interestingly, in the 32-bit version, an addition of zero applies for negative numbers due to the property: 2^32 % 7 = 4, and thus the addition of 4 is already baked-in. Note that if this were not zero (eg. if you don't treat Sunday as 0), it would be no slower. To calculate what this 2nd constant should be for different bit-widths, use: - ((3 + 2^BIT_WIDTH) % 7)

Seems like it should be pretty much as fast as possible right?
To speed things up, we'll need to look at the assembly. GCC and Clang both emit assembly that computes the following:

Neri, 32-bit (compiled pseudocode equivalent) View on Godbolt

1. u32 a = u32(rd) + (rd >= 0 ? 4 : 0)

2. u32 b = ((u64) a * 613566757) >> 32 // ≈ a / 7 (rough quotient)

3. u32 c = (((a - b) >> 1) + b) >> 2  // corrected quotient

4. u32 weekday = a - c * 7            // alternatively: a + c - (c << 3)

Note that line-3 contains four serially dependent operations, just to correct the initial approximation to a / 7. Correction terms like these are required because 7 is an uncooperative divisor, requiring more than 32-bits in its magic reciprocal multiplier which doesn't fit in a 32-bit register.

There is a faster way, using the "libdivide" technique presented by ridiculousfish in 2011 . It eliminates the whole correction line by making a saturating-increment to the input and using the round-down multiplier. We could use that, and it measures around 10% faster for me, but there are even faster ways, which we'll first explore by reducing our range requirement...

The Unreasonably Fast Mul-Add-Shift Algorithm Deep link

It turns out we can calculate the weekday over a restricted-but-useful range with just a multiplication, addition, and a right-shift:

Modulus usually requires many more steps. The reason we can get away with so few operations is due to 7 being a Mersenne number, i.e. of the form: 2N − 1. With such numbers, we can utilise identities like: N % 7 = floor(N * 8 / 7) % 8 (see Annexure B for the proof of this equality).

We then implement * 8 / 7 as multiplication by ~1.142857... approximated by a single multiplication and right-shift. Usually mul-shifts take the high bits, but we'll take the low bits, ensuring the right-shift is exactly 3 less than the register-size. The final % 8 is then given for free, by virtue of only 3 bits remaining.

By adding the value of Z to the result before the right-shift, we effectively rotate the output values to align with the Unix epoch being a Thursday. A value of Z = 0x90000000 rotates it such that the output values are ISO formatted [1..7], with a balanced input range within exactly ±89,478,489 (1/24th of 32-bit space). For the Unix format [0..6] variant, I chose Z = 0x94920000, which gives a nearly-but-not-perfectly balanced range, but comes with a minor speed advantage on ARM, by virtue of the low two bytes being zero.

The diagram to the right of the code shows visually how this multiplier strikes the 8 different segments of the circle (top 3 bits), skipping one value each cycle. The arrows "fan out" slightly; this is a representation of how our multiplier is only an approximation of 2^29 * 8 / 7. Eventually this fanning out causes an incorrect return value, hence the restricted range.

This algorithm is super fast everywhere, but particularly fast on ARM, where the multiply and addition are fused into a single MADD assembly operation. Additionally, many operations on ARM allow a fused right-shift, so there's a good chance that downstream code also fuses with the >> 29 term. This means in practice that it might compile to effectively a single ARM assembly operation!

An alternative visual guide to the validity of this technique is via the table below, where you can see that the output value 111 (7) is skipped each cycle in Unix mode, and the output value 000 is skipped in ISO mode:

If your date library only needs to support a range smaller than ±242,000 years, then you can probably just use this technique noted above. An example is the Rust Jiff date/time library which supports a range of ±10,000 years. The adoption of this algorithm yielded a 40% speed-improvement for upstream functions such as nth_weekday_of_month, which previously used Rust's rem_euclid function.

The rest of this article will be aimed at achieving similar speed for full range date libraries.

Fast Full Range via 64-Bit Widening Deep link

The easiest way to extend the range to the full 32-bit input domain is to widen to 64-bit:

The 64-bit widen version has a tweaked multiplier, instead of ceil(264 / 7) I have used ceil(240 / 7) × 224. Again, low bits have been zeroed for more compact ARM assembly: using trial and error to find the minimum number of bytes required.

Notice the arrows in the circle-chart no longer fan-out? That is due to the extra bits of precision afforded by this technique.

The Function Explorer has a variant adjusted for 64-bit inputs (see #fn=64unix_narrow), where the non-rounded multiplier is used for a wider range, covering over one quadrillion years (that ought to be enough for anybody).

"The Unreasonably Fast" - Prior Work

While researching for this article, I found that I am not the first to recognise this Mersenne number trick. A technique very much like this first appeared in Hacker's Delight, 2nd Edition (§10–20, Remainder by Multiplication and Shifting Right). The book has examples like the following:

The book uses the round-down multiplier in all cases, rather than the round-up multiplier. Not only does this multiplier give a worse range in many cases (including mod 7), but it necessitates the correction on line-2, which removes a chunk of the speed advantage of this technique.

I am glad I came across this book though, as I learned the following technique to expand to full-range:

The highlighted correction terms relate to the fractional part of the "ideal" multiplier 2^32 / 7 = 613566756.5714...
This fractional part is exactly 4 / 7. The corrections (x >> 1) + (x >> 4) = 1/2 + 1/16 = 0.5625 closely approximate the "ideal" shortfall.

We are going to make use of these corrective terms, but instead of using that correction mapping on line-2, we'll continue to use our Z-rotation.

Fast Full Range (Variant 1: Shifts) Deep link

Using the correction terms from Hacker's Delight (along with a round-down multiplier) we get the following:

In theory, this can sometimes be as low-latency as a single multiplication plus two cycles. Whether it is in practice will depend on how well the compiler optimises the assembly output (GCC seems best), and the performance characteristics of the target processor.

Medium Range Variant

If the rd >> 4 term is dropped, leaving only rd >> 1, then the function can have slightly higher throughput, and a range of around ±1.46M years. You can find tuned variants of this nature in the Function Explorer. See #fn=32unix_medium.

Fast Full Range (Variant 2: Two Muls) Deep link

There is a way to get a potentially even faster result. We recall that multiplication is slow, but has a high throughput in cases where the multiplications do not depend on each other. By replacing the terms: (rd >> 1) + (rd >> 4) with a hand-rolled division, we get a new fast full-range variant, this time optimised for throughput instead of latency.

This function below switches to the round-up multiplier, so instead of adding 4 / 7, we'll aim to subtract 3 / 7.

Even a simple in-order processor such as the 32-bit ARM chip in Raspberry Pi Zero can overlap these multiplications. We can see how by viewing the steps in the table below. Notice that, although there are two columns in each table, there is never a row with two computations on it?

Latency vs Throughput

Notice that the tables above have 6-rows, whereas the algorithm in the previous section (Variant 1) has 5-rows?
But conversely, they have one fewer operation overall in each case (X86: 6 → 5; ARM: 5 → 4).
This suggests better throughput at the cost of latency, but it depends largely on the target platform and how well the compiler does its job.

Compiler Performance

• For x86: Unfortunately only GCC takes advantage of the high-throughput 3-component LEA instruction.
• For ARM: Only Clang produces the optimal 4-instruction sequence (plus const loads), and only if forced to by inserting asm("" : "+r"(a));.

Despite suboptimal compiler assembly, these variants are all still lightning fast, perhaps just 1-2 cycles slower than possible.

Fast Full Range (Variant 3: High + Low Bits) Deep link

Finally, we get to the example shown at the start of this article, full-range in three x86 assembly operations:

We have handled this by:

1. using the round-down multiplier with correction: (rd >> 1) + (rd >> 4) = 1/2 + 1/16 = 0.5625 ≈ 4/7
2. using the round-up multiplier with a multiplier correction that effectively subtracted 3/7ths of rd.

An alternative is to revert to the round-down multiplier, but instead of patching together an approximation of rd * (4. / 7.), we will find an existing approximation to rd / 7 and then multiply it by 4.

Where can we find such an "existing approximation" to N / 7?
Well it's been there all along, it's the high 32-bit result of what we've always been calculating: rd * M:

• Instead of calculating u32(rd) * M...
• one calculates w = u64(rd) * M [operation #1]
  • the low result is then a = u32(w) - extracted for "free" in 32-bit x86 by accessing "eax" register
  • and high result is b = w >> 32 - extracted for "free" in 32-bit x86 by accessing "edx" register
  • then: r = a + 4 * b + Z - a single LEA operation* [operation #2]
  • and finally: weekday = r >> 29 [operation #3]

*the term a + 4 * b + Z fits the format of a single x86 "LEA" operation. If you haven't seen this operator before, it probably looks like a super-power. It's very specific in what it can handle. It can take two registers, multiply one of them by (1, 2, 4 or 8), and sum them together with another constant. Originally designed to help with memory access patterns, it is available to use and abuse in low level algorithms.

Unfortunately, as before, compilers are not likely to produce the optimal assembly (View x86 on Godbolt ), which is why the introduction presented it in raw assembly, rather than as source code. This approach is still worth benchmarking and likely optimal for x86 SIMD implementations for databases.

Generalisation Deep link

The techniques presented in this article generalise to modulus of other Mersenne numbers, i.e. of the form 2^N - 1, such as D = 3, 15, 31..., but only so long as D < 2^(BitWidth/2-1). That means D < 32,768 in 32-bit space. That's probably enough for most practical use cases, but for other Mersenne numbers, an alternative option exists.

The function below is that first solution I found to the general day-of-week problem (which builds directly on Neri's):

There are two tricks here:

This is similar to the start of Neri, but instead of adding 0 for negative inputs, we are adding a big number:
9 × 228 or 0x90000000. We are also using a round-up magic multiplier to implement correction-free division by 7.

We can use this large addition instead of 0, because:

1. This number is equal to 4 (mod 7) (the previous value of 0 can be considered as 2^32 = 4 (mod 7))
2. It maps negative numbers in the range of [-231..-1] to a contiguous block of numbers in unsigned 32-bit space: [228.. 9×228-1], meaning there's no wraparound point to worry about.

Why do this? Well, the standard round-up magic for divide-by-7 is only accurate over 80% of the 32-bit input range. This is why the clean version of Neri's algorithm outputs extra assembly to correct the initial estimated quotient for division-by-7, and the reason that a libdivide-style technique was suggested previously as a potential optimisation.

With this new technique, rd has been mapped to a smaller range than it would otherwise, the overall value of n is within range of [4..9×228-1]. This range is smaller than 80% of the 32-bit input range, meaning we can use the standard round-up magic number for division. Compilers are not smart enough to recognise the reduced input range, requiring us to hand-roll the division via the custom mul-shift.

So, why 9 × 228 instead of a smaller number?
It is true that we can pick many other choices for this addition, the smallest option would be 231 + 4 = 0x80000002.
Using that constant would be just as fast on x86, however ARM processors would take two assembly operations to load this constant.
9 × 228 is a neat number with the lower 16-bits zeroed out, which means it is loaded in only 1 assembly operation for ARM.

Now onto the next step:

This is computing (n + n / 7) % 8 instead of the traditional n - n / 7 * 7, replacing a multiplication with a bit-mask.

I refer to this trick as the "Nundinal Map" (similar to the "Julian Map" introduced in article 1).
Nundinal refers to the ancient Roman 8-day week.
Essentially, every time a 7-day week elapses, we pad the number n with an additional phantom day.
It is not too hard to see that n / 7 will bump 7 to 8, and 14 to 16 etc.
Once the number has been mapped to this fake 8-day week, we can extract the true weekday by just inspecting the lowest 3-bits.

It is pretty clear why this would be faster on x86, the alternative usually compiles as n + q - (q << 3), which is 3 cycles instead of 2.
It is less obvious why this is faster on ARM, as ARM has a fused multiply-add operation called MADD which can perform n + q * -7 in one assembly instruction with a 3-cycle latency, but a throughput of just 1 cycle. The reason it's also fast here is because on ARM, this line partly fuses with the previous code's line, which can perform n + (w >> 34) (where w is the prior multiply result) in a single assembly instruction. Thus, this final line is a true single-cycle operation on ARM: just the bit-mask.

I have not seen this particular transformation before.

The mathematical basis for this is:

Which is a special case of the following formula, where $c=1$ and $D=2^N-1$:

The proof of this general formula is stated in Annexure B. - Proof of modulus by power-of-2 padding.

This technique is not just restricted to Mersenne numbers...

Fast Modulus of Divisors in the form 2^N - 2^K

The general formula above can be used for numbers of the form $2^N-2^K$.

Some interesting use cases in this form include:

• Calculating hours:     x % 24 = (x + ((x / 24) << 3)) & 31
• Calculating min/sec: x % 60 = (x + ((x / 60) << 2)) & 63

From my research, these formulas appear novel. They are particularly fast on x86 processors due to the LEA assembly instruction, which can multiply a value by 2, 4 or 8, as well as add another variable, in a single cycle.

Interestingly, even the standard approach of x - x / 7 * 7 is technically a special-case of this general formula where $c=2^{32}-7$:
(x + (x / 7) * (2^32 - 7)) % (2^32). I.e. in 32-bit 2's complement: -7 = 2^32 - 7

Closing thoughts Deep link

Why did I bother with all this?
Well, if you can't tell by now, I just find this stuff all terribly interesting. The 7-day week is the oldest part of our calendar, and the one with the most truly global reach, surpassing the scope of even the Gregorian calendar. One can imagine that if we undergo civilisational collapse, or if we spread to new planets, the calendar may change, but the 7-day week might not.

The rabbit hole that led to all this was exploring optimisations for cultural calendars, like the Coptic calendar and in particular the Hebrew calendar, which uses the 7-day week more than once in its computation of general dates. Some future blog posts will cover those.

The very next article in this series will be on fast time-of-day, using the "Fast Modulus" techniques above.

If you found this interesting, you should follow me on X to get notified when I publish more date and algorithm related articles.

Revision history:
* 27 June 2026 - Soft release draft
* 17 August 2026 - First release

No, not a real artefact...

---

Annexure A - Benchmark Results

Exhaustive tests of the ranges asserted in this article can be verified via the testcase code: https://github.com/benjoffe/fast-world-calendars .

The same repository is used for benchmarking, where a large set of random dates are loaded into memory and tested. Latency mode feeds the results into the next computation via bitwise-XOR to ensure no parallel execution:

git clone git@github.com:benjoffe/fast-world-calendars.git
cd fast-world-calendars
cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build -j
./build/bin/weekday_bench
./build/bin/weekday_bench -latency
./build/bin/weekday_bench -batch

The above commands were used with the -repeat=5 flag, and for Raspberry Pi Only: -count=256 (others are 65536 random dates). The median results were saved to the table below:

Annexure B. Proof of modulus by power-of-2 padding Deep link

For any integer $x$, positive divisor $D$, and non-negative integer $c$, where $\lfloor \frac{x}{D}\rfloor$ denotes floor division:

Proof.
Write $xmodD=r$ in terms of quotient and remainder: $x=Dq+r$,  where $q=\lfloor \frac{x}{D}\rfloor$ and $r=xmodD$:

Taking $mod(D+c)$ of both sides:

Since $(D+c)q$ is an exact multiple of $D+c$, it is eliminated by the modulus, and $r$ is not eliminated due to $r=xmodD<D<D+c$:

The value of $c$ is a free parameter. The useful choices are positive values that make $D+c$ a power of 2, so that $mod(D+c)$ becomes a free bitwise AND.

The $c=1$ case appears in Warren's Hacker's Delight (§10–20, Remainder by Multiplication and Shifting Right), which presents:

Warren demonstrates fast approximations of the fixed-point constant $(D+1)/D$ via multiply-and-shift as used throughout this article.
The direct form $x+\lfloor x/D\rfloor$ is not analysed in Hacker's Delight.