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 in this article, but has the highest throughput for x86):
input weekday [0â¥6]:mov eax, 613566756 ; Constant Load: u32M= (1 << 32) / 7
mul ecx ;rd*M(u32a= low bits, u32b= high bits)
lea eax, [eax-1828716544+edx4] ; u32r=a+ 4 b+ (Z = 0x93000000)
shr eax, 29 ;weekday=r>> 29
You don't need prior understanding of assembly to follow this blog post.
By the end, you will understand why this code above works.
Visualisation of how the function above produces the desired output. The constant on line-3 acts as a rotation angle.
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++.
Given: * rd* =
1970-01-01 = Thursday (4) â Then:= ((weekdayrd% 7) + 7 + 4) % 7
= (rd + 4) POSMOD 7weekday
â Where: * weekday* â
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:
i32a= (i64(rd+ 4) * -1840700269) >> 32 //
i32b=rd+ 4 +a//
i32c= (b >> 2) + (u32(b) >> 31) //
i32d=rd-c* 7 //
i32e=d+ 4 //
u32=weekdaye>= 0 ?e: d + 11
A lot more steps than you might have expected, right?
Howard Hinnant's technique (2014) was adopted by many date libraries (see original article ).
=weekdayrd>= -4 ? (rd + 4) % 7
: (rd + 5) % 7 + 6This 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).
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 ):
= (u32(rd) + (weekdayrd>= 0 ? 4 : 0)) % 7
= (u64(rd) + (weekdayrd>= 0 ? 4 : -5)) % 7
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:
u32a= u32(rd) + (rd>= 0 ? 4 : 0)
u32b= ((u64)a* 613566757) >> 32 //
u32c= (((a-b) >> 1) +b) >> 2 //
u32=weekdaya-c* 7 //
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...
It turns out we can calculate the weekday over a restricted-but-useful range with just a multiplication, addition, and a right-shift:
-89,434,796 to 89,522,175``-242,895-11-06 (Mon: 1) to 247,073-05-23 (Fri: 5)const u32M= (1 << 32) / 7 + 1 //
const u32Z= 0x94920000 //
= (u32(weekdayrd) *M+Z) >> 29
For a C++ version, see #fn=32unix_narrow in the Function Explorer.
Just three operations. Clearly this is going to run fast, but how on Earth does it work?
Visualisation of how the function to the left produces the desired output. The constant âZâ acts as a rotation angle.
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: 2. With such numbers, we can utilise identities like: N â 1N % 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:
| rata_die | Weekday | a = u32(rata_die * 613566757) | r = u32( a + 0x94920000 (2,492,596,224) | r as Binary | r >> 29 | Correct? |
|---|---|---|---|---|---|---|
| 5 | 2 | 3,067,833,785 | 1,265,462,713 | 01001011011011010110110110111001 | 2 | Pass |
| 4 | 1 | 2,454,267,028 | 651,895,956 | 00100110110110110010010010010100 | 1 | Pass |
| 3 | 0 | 1,840,700,271 | 38,329,199 | 00000010010010001101101101101111 | 0 | Pass |
| 2 | 6 | 1,227,133,514 | 3,719,729,738 | 11011101101101101001001001001010 | 6 | Pass |
| 1 | 5 | 613,566,757 | 3,106,162,981 | 10111001001001000100100100100101 | 5 | Pass |
| 0 | 4 | 0 | 2,492,596,224 | 10010100100100100000000000000000 | 4 | Pass |
| -1 | 3 | 3,681,400,539 | 1,879,029,467 | 01101111111111111011011011011011 | 3 | Pass |
| -2 | 2 | 3,067,833,782 | 1,265,462,710 | 01001011011011010110110110110110 | 2 | Pass |
| -3 | 1 | 2,454,267,025 | 651,895,953 | 00100110110110110010010010010001 | 1 | Pass |
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.
The easiest way to extend the range to the full 32-bit input domain is to widen to 64-bit:
-231 to 231-1-5,877,641-06-23 (Tue: 2) to 5,881,580-07-11 (Fri: 5)const u64M= 0x2492492493000000 //40/ 7) Ã 224
const u64Z= 0x9400 << 48
= (u64(weekdayrd) * M +Z) >> 61
For a C++ version, see #fn=32unix_widen in the Function Explorer.
Visualisation of how the function to the left produces the desired output. The constant âZâ acts as a rotation angle.
The 64-bit widen version has a tweaked multiplier, instead of ceil(2 I have used 64 / 7)ceil(2. Again, low bits have been zeroed for more compact ARM assembly: using trial and error to find the minimum number of bytes required.40 / 7) Ã 224
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).
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:
x Integer [0 .. 134,217,734] â Then:u32n= u32(x* 613566756) >> 29 //
=x_mod_7n& (i32(n - 7) >> 31) //
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:
xu32n= u32(x* 613566756 + (x>> 1) + (x>> 4)) >> 29
=x_mod_7n& (i32(n - 7) >> 31) //
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 = closely approximate the "ideal" shortfall.0.5625
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.
Using the correction terms from Hacker's Delight (along with a round-down multiplier) we get the following:
-231 to 231-1-5,877,641-06-23 (Tue: 2) to 5,881,580-07-11 (Fri: 5)const u32M= (1 << 32) / 7 //
const u32Z= 0x95000000 //
const u32a= u32(rd) *M+Z
const u32b= (rd>> 1) + (rd>> 4)
= (weekdaya+b) >> 29
For a C++ version, see #fn=32unix in the Function Explorer.
Visualisation of how the function to the left produces the desired output. The constant âZâ acts as a rotation angle.
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.
The key is that unlike with standard division-by-7, the computation of the corrections, such as: b = (rd >> 1) + (rd >> 4) are dependent only on the input value, not on any prior computations. This allows b to be calculated while the multiplication rd * M is underway.
Modern x86 processors are superscalar, and can usually perform a shift at the same time as a multiplication. Since multiplications usually take 3 cycles, rd * M and b are ready at the same time. The LEA assembly instruction allows adding these two results and Z in one step (although on some chips this might be two cycles).
This superscalar aspect can be confirmed by observing benchmarks with and without the calculation of b, which show the same latency results in many cases from my testing. Now, if your date library has a smaller date-range, you might still prefer one of the reduced-range 32-bit algorithms; not because they have reduced latency, but because they can have higher throughput, meaning your code can be doing something else while the multiplication occurs, such as starting a time-of-day computation etc.
| Superscalar x86 Assembly Steps | ||
|---|---|---|
| Step | Computation 1 | Computation 2 |
| 1 | a = rd * M | t |
| 2 | mul-latency | t |
| 3 | mul-latency | b = t |
| 4 | a + b + Z(LEA instruction) | |
| 5 | ... >> 29 | |
The situation is even better on ARM.
Many ARM assembly instructions allow a fused right-shift to occur in the same instruction cycle. This allows the computation of b to be made in just two-cycles. As such, the processor does not need to have any superscalar features in order to hide b within the shadow of the multiplication.
This has been observed on the Raspberry Pi Zero, which again has the same latency whether or not b is included in the function.
Finally, since the algorithm ends with a right-shift, if your subsequent code does something like add or subtract the returned value (as is often the case when computing the Nth weekday of a month etc.), then the final shift also gets fused with that subsequent operation.
| ARM Optimal Assembly Steps | ||
|---|---|---|
| Step | No parallel steps other than overlapping multiplier | |
| 1 | a = rd * M + Z(MADD instruction) | |
| 2 | t | mul-latency |
| 3 | b = t(fused shift-add) | mul-latency |
| 4 | a + b | |
| 5 | ... >> 29(potentially fused with next operation) | |
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.
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.
-231 to 231-1-5,877,641-06-23 (Tue: 2) to 5,881,580-07-11 (Fri: 5)const u32M= (1 << 32) / 7 + 1 //
const i32N= i32(M * 4) //
const u32a= u32(rd) *M+N//
const u32b= u64(rd) *N>> 32 //
= (weekdaya+b) >> 29
For a C++ version, see #fn=32unix_v2 in the Function Explorer.
Note: i32(M * 4) overflows to give a negative multiplier, resulting in subtraction of 3 / 7 *.rd
Visualisation of how the function to the left produces the desired output. The constant âZâ acts as a rotation angle.
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?
| x86 Optimal Assembly Steps | ||
|---|---|---|
| Step | Computation 1 | Computation 2 |
| 1 | rd * N | |
| 2 | a = rd * M | mul-latency |
| 3 | mul-latency | mul-latency |
| 4 | mul-latency | b = ... >> 32 |
| 5 | a + b + u32(N)("LEA") | |
| 6 | ... >> 29 | |
| ARM Optimal Assembly Steps | ||
|---|---|---|
| Step | Computation 1 | Computation 2 |
| 1 | rd * N | |
| 2 | a = rd * M + u32(N)("MADD") | mul-latency |
| 3 | mul-latency | mul-latency |
| 4 | mul-latency | - |
| 5 | a + (b >> 32)(fused shift-add) | |
| 6 | ... >> 29 | |
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 observation suggests the claim of better throughput but worse latency, which is reflected in the benchmark results.
asm("" : "+r"(a));.Despite suboptimal compiler assembly, these variants are all still lightning fast, perhaps just 1-2 cycles slower than possible.
movsxd rax, edi ; Register shufflingimul edi, edi, 613566757
imul rax, rax, -1840700268
sar rax, 32
lea eax, [rdi-1840700268+rax]
shr eax, 29
ret
mov w8, #18725 ; Const load``mov w9, #9364 ; Const load``movk w8, #9362, lsl #16 ; Const load``movk w9, #37449, lsl #16 ; Const loadmadd w8, w0, w8, w9
smull x9, w0, w9
add x8, x8, x9, lsr #32
lsr w0, w8, #29
ret
Finally, we get to the example shown at the start of this article, full-range in three x86 assembly operations:
input weekday [0â¥6]:mov eax, 613566756 ; Constant Load: u32M= (1 << 32) / 7
mul ecx ;rd*M(u32a= low bits, u32b= high bits)
lea eax, [eax-1828716544+edx4] ; u32r=a+ 4 b+ (Z = 0x93000000)
shr eax, 29 ;weekday=r>> 29
A C++ implementation of this is available as #fn=32unix_v3 in the Function Explorer below.
Recall why we are adding correction terms: due to the multiplier being unable to represent the fractional part of: 2^32 / 7 = 613566756.5714...
Visualisation of how the function above produces the desired output. The constant on line-3 acts as a rotation angle.
We have handled this by:
(rd >> 1) + (rd >> 4) = 1/2 + 1/16 =0.5625 â 4/73/7ths of N.An alternative is to revert to the round-down multiplier, but instead of patching together an approximation of N * (4. / 7.), we will find an existing approximation to N / 7 and then multiply it by 4.
Where can we find such an "existing approximation" to N / 7?
rd * M:u32(rd) * M...w = u64(rd) * M a = u32(w)b = w >> 32r = a + 4 * b + Zweekday = r >> 29*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.
You have seen many code examples throughout this article, this widget below combines them all in a single "Function Explorer", where you can configure the bit-width, epoch, range and variant. There are a total of 280 hand-tuned permutations, and they are all fully tested.
// MIT License ``// ``// Copyright (c) 2026 - Ben Joffe <https://www.benjoffe.com/>``// ``// Permission is hereby granted, free of charge, to any person obtaining a copy``// of this software and associated documentation files (the "Software"), to deal``// in the Software without restriction, including without limitation the rights``// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell``// copies of the Software, and to permit persons to whom the Software is``// furnished to do so, subject to the following conditions:``// ``// The above copyright notice and this permission notice shall be included in``// all copies or substantial portions of the Software.``// ``// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR``// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,``// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE``// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER``// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,``// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE``// SOFTWARE.`` ``// Given: rd = rata-die (day-count), Unix epoch 1970-01-01: 4``// Compute: Day of week: (rd + 4) POS_MOD 7``// Range: Full signed 32-bit``// Output: [0..6]``// Min Date: -5,877,641-06-23 (Tue: 2)``// Max Date: 5,881,580-07-11 (Fri: 5)``//Optional Ref: https://www.benjoffe.com/fast-day-of-week#fn=32unixinline uint8_t get_weekday_32unix(int32_trd) {
const uint32_tM= (1ull << 32) / 7; //
const uint32_tZ= 0x95000000; //
const uint32_ta= uint32_t(rd) *M+Z;
const uint32_tb= (rd>> 1) + (rd>> 4);
returnuint32_t(a+b) >> 29; // top 3 bits
}
The chart above visualises how inputs map from an idealised angle around the circle, to 8 segments (representing the top 3-bits of the final computation).
It will animate upon form changes.
All 280 permutations of the above function can be generated into a single file for testing purposes. This is then copy/pasted into the test repo at: https://github.com/benjoffe/fast-world-calendars (the repo already has a copy).
Functions of bit-width 8, 16 and 32 are exhaustively tested over the stated range.
Functions in the 64-bit range would be prohibitively slow to exhaustively test, so are instead tested in four 1-billion-date chunks: around zero, up to max, down to min, and a random selection.
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):
u32n= u32(rd) + (rd>= 0 ? 4 : (9 << 28)) //
u32q= (u64)n* 2454267027 >> 34 //
= (weekdayn+q) & 7 //
There are two tricks here:
u32n= u32(rd) + (rd>= 0 ? 4 : (9 << 28)) //
u32q= (u64)n* 2454267027 >> 34 //
This is similar to the start of Neri, but instead of adding 0 for negative inputs, we are adding a big number:9 Ã 2 or 280x90000000. 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:
4 (mod 7) (the previous value of 0 can be considered as 2^32 = 4 (mod 7))[-232..-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Ã2. 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.28-1]
So, why 9 Ã 2 instead of a smaller number?28
It is true that we can pick many other choices for this addition, the smallest option would be 2.31 + 4 = 0x80000004
Using that constant would be just as fast on x86, however ARM processors would take two assembly operations to load this constant.9 Ã 2 is a neat number with the lower 16-bits zeroed out, which means it is loaded in only 1 assembly operation for ARM.28
Now onto the next step:
= (weekdayn+q) & 7 //
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
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...
The general formula above can be used for numbers of the form
Some interesting use cases in this form include:
x % 24 = (x + ((x / 24) << 3)) & 31``x % 60 = (x + ((x / 60) << 2)) & 63From 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 (x + (x / 7) * (2^32 - 7)) % (2^32). I.e. in 32-bit 2's complement: -7 = 2^32 - 7
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.
Revision history:
-
27 June 2026 - Soft release draft
-
17 August 2026 - First release
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 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:
| Algorithm: | base-line | naive | rust | Hinnant | Neri | New Narrow | New Medium | New Full (Widen) | New Full (V1) | New Full (V2) | New Full (V3) | (V3) forced asm | "1st attempt" |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| MacBook Pro 2024 (MacOS 15.6.1) Apple M4 Pro Compiler: Apple clang 17.0.0 | - (14640) | 2.78x(59014) | 1.32x(35634) | 2.84x(59889) | 1.00x(30587) | 0.17x(17388) | 0.23x(18387) | 0.18x(17465) | 0.39x(20788) | 0.35x(20266) | 0.25x(18624) | 0.36x(20331) | 0.48x(22304) |
| AMD Ryzen 9 9950X3D Ubuntu 24.04.3 LTS Compiler: GCC14.2.0 (x86_64) | - (5746) | 1.84x(72955) | - | 2.92x(112071) | 1.00x(42185) | 0.27x(15478) | 0.42x(21012) | 0.33x(17870) | 0.55x(25608) | 0.59x(27395) | 0.50x(24010) | 0.48x(23191) | - |
| AMD Ryzen 9 9950X3D Ubuntu 24.04.3 LTS Compiler: Clang18.1.3 (x86_64) | - (11556) | 2.30x(90156) | 1.72x(70542) | 3.90x(144980) | 1.00x(45787) | 0.23x(19556) | 0.31x(22334) | 0.28x(21301) | 0.47x(27721) | 0.53x(29548) | 0.41x(25722) | 0.41x(25738) | 0.57x(30965) |
| MacBook Pro 2016 (MacOS 12.7.6) Intel Core i7 @ 2.7 GHz Compiler: Apple clang 14.0.0 | - (23209) | 1.84x(171955) | 1.46x(141247) | 3.71x(323632) | 1.00x(104158) | 0.39x(54856) | 0.30x(47357) | 0.39x(54907) | 0.49x(63104) | 0.44x(58613) | 0.85x(91688) | 0.28x(45984) | 0.56x(68224) |
| Raspberry Pi Zero 32-Bit ARM Raspbian GNU/Linux 13 (trixie) Compiler: GCC 14.2.0 (armv6l) | - (6222) | 1.30x(59627) | 1.03x(48624) | 0.96x(45630) | 1.00x(47294) | 0.75x(37029) | 0.75x(37016) | 0.85x(41138) | 0.70x(34961) | 0.85x(41140) | 0.55x(28802) | 0.56x(29086) | 0.65x(32954) |
For any integer
Proof.
Write
Taking
Since
The value of AND.
The Hacker's Delight (§10â20, Remainder by Multiplication and Shifting Right), which presents:
Warren demonstrates fast approximations of the fixed-point constant
The direct form