Een snellere manier om de dag van de week te berekenen

Het omzetten van een dagtelling ("rata-die") naar de dag van de week ("weekday") klinkt zo triviaal dat er bijna niets over te zeggen valt. Maar wanneer we onder de motorkap kijken, blijkt dit een verrassend complex probleem te zijn.

In dit artikel presenteer ik een reeks zeer snelle functies om dit probleem op te lossen, afgestemd op verschillende gebruiksscenario's (doorvoersnelheid versus latentie, verschillende platforms, etc.). Elk algoritme voor het volledige 32-bit bereik presteert beter dan bestaande oplossingen, en velen hebben een latentie van slechts één vermenigvuldiging plus twee cycli. Een verrassend resultaat is dat de dag van de week kan worden berekend in ISO-formaat ([1..7] in plaats van [0..6]) met exact dezelfde instructies, enkel met aangepaste constanten (zonder snelheidspenaliteit).

Om een idee te geven van de complexiteit, highlight ik hier mijn favoriete functie. Deze ogenschijnlijk krankzinnige sequentie van drie instructies (plus het laden van een constante) is accuraat over het volledige signed 32-bit bereik (het is wellicht niet de laagste latentie, maar heeft de hoogste doorvoersnelheid voor x86):

Unix Weekday [0..6] / ISO Weekday [1..7] Gegeven: input (rd = signed 32-bit Unix dagtelling); Bereken weekday [0..6]:

mov   eax, 613566756              ; Constante laden: u32 M = (1 << 32) / 7
imul  ecx                         ; rd * M (u32 a = lage bits, i32 b = hoge bits)
lea   eax, [eax-1828716544+edx*4] ; u32 r = a + 4 * b + (Z = 0x93000000)
shr   eax, 29                     ; weekday = r >> 29

Je hebt geen voorkennis van assembly nodig om dit artikel te volgen; aan het einde zul je begrijpen waarom bovenstaande code werkt.

Dit artikel is bedoeld voor mensen die geïnteresseerd zijn in low-level bitmanipulatie, het optimaliseren van high-performance datum-bibliotheken of database-engines, compiler-auteurs en enthousiastelingen in het algemeen. De gebruikte technieken zijn generaliseerbaar naar x % (2^N - 1), en er worden nieuwe snelle modulus-technieken geïntroduceerd voor andere delers zoals x % 24 en x % 60, wat toepasbaar is voor tijdregistratie.

Relatieve snelheden van de snelste algoritmen voor het volledige 32-bit bereik

(Getest op AMD Ryzen 9 en Apple M4 Pro processoren; lagere getallen = sneller)

AlgoritmeRelatieve Snelheid
Overigen (double-mod, Rust:rem_euclid, Hinnant)~1.5-3+×
Neri (2024)1×
Nieuwe Algoritmen (2026)~0.3-0.5×

---

Eenvoudige benaderingen

Gegeven: rd = rata-die (dagtelling, signed 32-bit int), met epoch 1970-01-01 = donderdag (4).

Double-mod (talen met signed "%", bijv. C/C++) weekday = ((rd % 7) + 7 + 4) % 7

Talen met speciale positive-mod (bijv. Rust) weekday = (rd + 4) POSMOD 7 (Waarbij: weekday ∈ [0..6] (0 = zondag))

Dit is wat ik zou aanbevelen in de meeste code waar onderhoud belangrijker is dan micro-optimalisatie. Let op dat het Rust-voorbeeld overflow vertoont bij de hoogste 4 inputs.

De toevoeging van 4 (of 11 = 7 + 4) is nodig omdat de Unix epoch (1970-01-01) een donderdag is. Afhankelijk van de nummering van de weekdagen of het gebruikte epoch kan dit variëren.

Hoewel deze benaderingen werken, zijn ze relatief traag. Zelfs de rem_euclid functie van Rust vertaalt zich in C-stijl pseudocode naar een complexer proces:

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 + 11

Hinnant

De techniek van Howard Hinnant (2014) is door veel datum-bibliotheken overgenomen.

Hinnant's Algoritme (onafhankelijk van bit-grootte) Bereik: INT32MIN → INT32MAX − 4 weekday = rd >= -4 ? (rd + 4) % 7 : (rd + 5) % 7 + 6

Deze aanpak is ontworpen voor eenvoud en flexibiliteit. Het is het enige algoritme in dit artikel dat niet vertrouwt op sign casting of overflow, en het is niet specifiek voor een bepaalde bit-breedte. Hinnant merkt op dat dit het volledige signed 32-bit bereik dekt, behalve voor de hoogste 4 inputs, wat in C/C++ resulteert in ongedefinieerd gedrag (meer dan 5,8 miljoen jaar in de toekomst).

Neri

Het werk van Cassio Neri is de moderne standaard voor het volledige bereik. In 2024 publiceerde Neri een zeer schone oplossing:

Cassio Neri: 32-bit versie (Bereik: Volledige signed 32-bit) weekday = (u32(rd) + (rd >= 0 ? 4 : 0)) % 7

Cassio Neri: 64-bit versie (Bereik: Volledige signed 64-bit) weekday = (u64(rd) + (rd >= 0 ? 4 : -5)) % 7

De truc om overflow te voorkomen is de cast van signed naar unsigned vóórdat er bewerkingen plaatsvinden. In de 32-bit versie geldt voor negatieve getallen een toevoeging van nul vanwege de eigenschap: $2^{32} \pmod 7 = 4$.

Om dit te versnellen, moeten we naar de assembly kijken. GCC en Clang genereren code die het volgende berekent: u32 a = u32(rd) + (rd >= 0 ? 4 : 0) u32 b = ((u64) a 613566757) >> 32 (ruwe quotiënt) u32 c = (((a - b) >> 1) + b) >> 2 (gecorrigeerd quotiënt) u32 weekday = a - c 7

De correctie op regel 3 is nodig omdat 7 een "niet-coöperatieve" deler is, waardoor de magic reciprocal multiplier niet in een 32-bit register past.

Het onredelijk snelle Mul-Add-Shift-algoritme

Het blijkt mogelijk om de dag van de week over een beperkt maar nuttig bereik te berekenen met slechts één vermenigvuldiging, één optelling en één right-shift.

32-bit versie (beperkt bereik) Input bereik: -89.434.796 tot 89.522.175 Geldige datums: -242.895-11-06 tot 247.073-05-23

const u32 M = (1 << 32) / 7 + 1  // 613,566,757
const u32 Z = 0x94920000         // 2,492,596,224
weekday = (u32(rd) * M + Z) >> 29

Hoe werkt dit?

De reden dat we met zo weinig operaties toe kunnen, is dat 7 een Mersenne-getal is (van de vorm $2^N - 1$). Bij dergelijke getallen kunnen we identiteiten gebruiken zoals: $N \pmod 7 = \lfloor N \cdot 8 / 7 \rfloor \pmod 8$.

We implementeren $\cdot 8 / 7$ als een vermenigvuldiging met $\approx 1,142857\dots$, benaderd door één vermenigvuldiging en een right-shift. Door de waarde $Z$ toe te voegen vóór de right-shift, roteren we de outputwaarden om deze in lijn te brengen met de Unix epoch (donderdag).

Dit algoritme is extreem snel, vooral op ARM, waar de vermenigvuldiging en optelling gefuseerd kunnen worden in één MADD assembly-operatie.

Snel volledige bereik via 64-bit verbreding

De eenvoudigste manier om het bereik uit te breiden naar het volledige 32-bit domein is door te verbreden naar 64-bit:

64-bit widen versie Input bereik: Volledige 32-bit ($-2^{31}$ tot $2^{31}-1$)

const u64 M = 0x2492492493000000  // ceil(240 / 7) × 2^24
const u64 Z = 0x9400 << 48
weekday = (u64(rd) * M + Z) >> 61

Door de extra precisie van 64-bit verdwijnt de "fanning out" (afwijking) die we zagen bij de 32-bit beperkte versie.

Eerder werk: "The Unreasonably Fast"

Tijdens het onderzoek bleek dat deze Mersenne-truc ook in Hacker's Delight (§10–20) voorkomt. Het boek gebruikt echter een round-down multiplier, wat een correctie op de tweede regel vereist, wat de snelheidswinst vermindert.

Hacker's Delight - Onsigned N mod 7 (volledig bereik): u32 n = u32(x * 613566756 + (x >> 1) + (x >> 4)) >> 29 xmod7 = n & (i32(n - 7) >> 31)

We maken gebruik van deze correctietermen ((x >> 1) + (x >> 4)), maar combineren ze met onze Z-rotatie in plaats van de correctie-mapping.

Snel volledig bereik (Variant 1: Shifts)

Met de correctietermen uit Hacker's Delight en een round-down multiplier krijgen we het volgende:

Volledige 32-bit versie (Variant 1) Bereik: Volledige 32-bit

const u32 M = (1 << 32) / 7    // 613,566,756
const u32 Z = 0x95000000       // 2,499,805,184
const u32 a = u32(rd) * M + Z
const u32 b = (rd >> 1) + (rd >> 4)
weekday = (a + b) >> 29

Op moderne x86-processors kan b parallel aan de vermenigvuldiging rd * M worden berekend omdat ze onafhankelijk zijn. Dit minimaliseert de latentie.

Snel volledig bereik (Variant 2: Twee vermenigvuldigingen)

Voor een hogere doorvoersnelheid (throughput) kunnen we de verschuivingen vervangen door een handmatige deling, waardoor we twee vermenigvuldigingen kunnen uitvoeren die niet van elkaar afhankelijk zijn.

Volledige 32-bit versie (Variant 2) Bereik: Volledige 32-bit

const u32 M = (1 << 32) / 7 + 1  // 613,566,757
const i32 N = i32(M * 4)         // -1,840,700,268
const u32 a = u32(rd) * M + N
const u32 b = u64(rd) * N >> 32  // ≈ rd * -3 / 7
weekday = (a + b) >> 29

Deze variant is geoptimaliseerd voor doorvoersnelheid in plaats van latentie, omdat processoren meerdere vermenigvuldigingen tegelijk kunnen overlappen.

Snel volledig bereik (Variant 3: Hoge + Lage Bits)

Dit is het voorbeeld uit de introductie. In plaats van een benadering van rd (4/7) te maken, gebruiken we het resultaat van rd M en benutten we zowel de lage als de hoge bits van het resultaat.

Given: input (rd = signed 32-bit Unix dagtelling); Bereken weekday [0..6]:

mov   eax, 613566756              ; Constante laden: u32 M = (1 << 32) / 7
imul  ecx                         ; rd * M (u32 a = lage bits, i32 b = hoge bits)
lea   eax, [eax-1828716544+edx*4] ; u32 r = a + 4 * b + (Z = 0x93000000)
shr   eax, 29                     ; weekday = r >> 29

Op x86 wordt de vermenigvuldiging imul opgeslagen in eax (lage bits) en edx (hoge bits). De LEA instructie kan vervolgens a + 4 * b + Z in één enkele cyclus berekenen.

---

C++ Implementatie (Voorbeeld Variant 1)

inline uint8_t get_weekday_32unix(int32_t rd) {
    const uint32_t M = (1ull << 32) / 7;  // 613,566,756
    const uint32_t Z = 0x95000000;        // 2,499,805,184
    const uint32_t a = uint32_t(rd) * M + Z;
    const uint32_t b = (rd >> 1) + (rd >> 4);
    return uint32_t(a + b) >> 29; // top 3 bits
}

---

Generalisatie

Deze technieken zijn generaliseerbaar naar modulus van andere Mersenne-getallen ($2^N - 1$), zoals $D = 3, 15, 31\dots$, mits $D < 2^{(\text{BitWidth}/2-1)}$.

Een alternatieve methode voor volledige 32-bit bereik

Een andere benadering maakt gebruik van een "range-compression trick" en een "power-of-2 padding trick":

u32 n = u32(rd) + (rd >= 0 ? 4 : (9 << 28))
u32 q = (u64) n * 2454267027 >> 34
weekday = (n + q) & 7

Trick #1: Range-compression Door een groot getal ($9 \cdot 2^{28}$) op te tellen bij negatieve getallen, worden deze gemapt naar een aaneengesloten blok in de unsigned 32-bit ruimte zonder wraparound-punten. Hierdoor kunnen we een standaard round-up magic multiplier gebruiken die normaal slechts over 80% van het bereik accuraat is.

Trick #2: Nundinal Map (Power-of-2 padding) In plaats van n - (n/7)*7, berekenen we (n + n/7) % 8. Dit vervangt een vermenigvuldiging door een bit-mask. Dit is gebaseerd op de formule: $x \pmod D = (x + c \lfloor x/D \rfloor) \pmod{D+c}$ Voor $D=7$ en $c=1$ wordt dit $\pmod 8$.

Toepassing op andere delers ($2^N - 2^K$)

De algemene formule kan worden gebruikt voor getallen van de vorm $2^N - 2^K$:

  • Uren berekenen: x % 24 = (x + ((x / 24) << 3)) & 31
  • Minuten/seconden berekenen: x % 60 = (x + ((x / 60) << 2)) & 63

---

Slotgedachten

De 7-daagse week is het oudste deel van onze kalender en heeft het grootste wereldwijde bereik. De fascinatie voor deze optimalisaties komt voort uit het verkennen van culturele kalenders (zoals de Koptische en Hebreeuwse kalender), waarbij de 7-daagse week centraal staat in de berekeningen.

---

Bijlage A: Benchmark Resultaten

De benchmarks meten scalaire prestaties. Latentie-modus voorkomt parallelle executie door resultaten via bitwise-XOR door te geven. Lagere getallen = sneller.

(Selectie uit resultaten)

ProcessorNaiveHinnantNeriNew Full (V1)New Full (V3)
Apple M4 Pro1.32x2.84x1.00x0.39x0.25x
Ryzen 9 9950X3D (GCC)-2.92x1.00x0.27x0.59x0.48x
Raspberry Pi Zero1.03x0.96x1.00x0.85x0.56x

---

Bijlage B: Bewijs van modulus via power-of-2 padding

Voor elke integer $x$, positieve deler $D$, en niet-negatieve integer $c$: $(1) \quad x \pmod D = (x + c \lfloor x/D \rfloor) \pmod{D+c}$

Bewijs: Schrijf $x \pmod D = r$ in termen van quotiënt en rest: $x = Dq + r$, waarbij $q = \lfloor x/D \rfloor$ en $r = x \pmod D$.

$(2) \quad x + c \lfloor x/D \rfloor = Dq + r + cq = (D+c)q + r$

Neem $\pmod{D+c}$ van beide zijden: $(3) \quad (x + c \lfloor x/D \rfloor) \pmod{D+c} = ((D+c)q + r) \pmod{D+c}$

Aangezien $(D+c)q$ een exact veelvoud is van $D+c$, wordt dit geëlimineerd door de modulus. Omdat $r = x \pmod D < D < D+c$, blijft $r$ behouden: $(4) \quad (x + c \lfloor x/D \rfloor) \pmod{D+c} = r = x \pmod D \quad \square$