A faster way to calculate the day-of-the-week

Other Date/Time Articles:Article 1: The Julian MapArticle 2: Overflow Safety (32-Bit)Article 3: Very Fast Date (64-Bit)Article 4: Fast Leap YearArticle 5: Fast Day-of-WeekSmoital System - Time on MarsWeekle - Weekday Guessing GameA range of fast modulus techniques that beat compiler output17 August 2026Converting 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): Unix Weekday [0‥6] ISO Weekday [1‥7]Given: input (rd = signed 32-Bit Unix day-count); Compute weekday [0‥6]:mov eax, 613566756 u32 M = (1 << 32) / 7imul ecx rd * M lea eax, [eax-1828716544+edx*4] u32 r = a + 4 * b + (Z = 0x93000000)shr eax, 29 weekday = r >> 29You 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++.Approx. Relative Speeds of Fastest AlgorithmsAs tested on AMD Ryzen 9 and Apple M4 Pro processors(smaller numbers = faster)See benchmark sectionfor specific results.Others(double-mod, Rust:rem_euclid, Hinnant)~1.5-3+×Neri(2024)1×New Algos(2026)~0.3-0.5×Article Sections:Simple ApproachesHinnantNeriThe Unreasonably Fast Mul-Add-Shift AlgorithmFast Full Range via 64-Bit WideningFast Full Range (Variant 1: Shifts)Fast Full Range (Variant 2: Two Muls)Fast Full Range (Variant 3: High + Low Bits)The Function ExplorerGeneralisationClosing ThoughtsAnnexure A. Benchmark ResultsAnnexure B. Proof of modulus by power-of-2 paddingSimple Approaches Deep linkGiven: rd = rata-die (day-count, signed 32-Bit int), with epoch 1970-01-01 = Thursday (4) — Then:Double-mod (languages with signed "%", eg. C/C++)weekday = ((rd % 7) + 7 + 4) % 7Languages with special positive-mod (eg. Rust)weekday = (rd + 4) POSMOD 7 — 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 i32 a = (i64(rd + 4) * -1840700269) >> 32 i32 b = rd + 4 + a i32 c = (b >> 2) + (u32(b) >> 31) i32 d = rd - c * 7 i32 e = d + 4 u32 weekday = e >= 0 ? e : d + 11A lot more steps than you might have expected, right?Hinnant Deep linkHoward Hinnant's technique (2014) was adopted by many date libraries (see original article ).Hinnant's Algorithm (bit-size independent)Range: INT32_MIN → INT32_MAX − 4weekday = rd >= -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).Neri Deep linkAs 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 ):Cassio Neri: 32-bit version(Range: Full signed 32-bit)weekday = (u32(rd) + (rd >= 0 ? 4 : 0)) % 7Cassio Neri: 64-bit version(Range: Full signed 64-bit)weekday = (u64(rd) + (rd >= 0 ? 4 : -5)) % 7If 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 u32 a = u32(rd) + (rd >= 0 ? 4 : 0)u32 b = ((u64) a * 613566757) >> 32 u32 c = (((a - b) >> 1) + b) >> 2 u32 weekday = a - 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...The Unreasonably Fast Mul-Add-Shift Algorithm Deep linkIt turns out we can calculate the weekday over a restricted-but-useful range with just a multiplication, addition, and a right-shift: Unix Weekday [0‥6] ISO Weekday [1‥7]32-bit version (restricted range)Input range: -89,434,796 to 89,522,175Valid dates: -242,895-11-06 (Mon: 1) to 247,073-05-23 (Fri: 5)const u32 M = (1 << 32) / 7 + 1 const u32 Z = 0x94920000 weekday = (u32(rd) * M + Z) >> 29For 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: 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: Unix Weekday [0‥6] ISO Weekday [1‥7]rata_dieWeekdaya = u32(rata_die* 613566757)r =