Faster Day-of-Week Calculation with Magic Numbers
Tomohiko Sakamoto’s method is a well-known algorithm for calculating the day of the week of a given date.
This article restricts the supported year range to 1 through 9999 and replaces the constant divisions and modulo operation in Sakamoto’s calculation with multiplication, bit shifts, and bit extraction.
In an inlined batch benchmark written in C and run on Apple Silicon, this implementation was approximately 30% faster than the ordinary Sakamoto implementation.
I will first show the finished implementation and then explain why the constants 5243 and 74899 work.
Implementations
TypeScript
/** Returns 0=Sunday, ..., 6=Saturday.
*
* Preconditions:
* - year: 1..9999
* - month: 1..12
* - day: 1..31
*/
const SCALED_MONTH_TERM = new Uint32Array([
0, 224_697, 149_798, 374_495, 0, 224_697, 374_495, 74_899, 299_596, 449_394, 149_798, 299_596,
]);
export function weekdayBoundedDistributed(year: number, month: number, day: number): number {
year -= Number(month < 3);
const product = Math.imul(year, 5_243);
const base = year + (year >>> 2) - (product >>> 19) + (product >>> 21) + day;
return ((Math.imul(base, 74_899) + SCALED_MONTH_TERM[month - 1]) >>> 16) & 7;
}The TypeScript implementation uses Math.imul to explicitly perform 32-bit integer multiplication. It also uses the unsigned right-shift operator >>>.
Rust
/// Returns 0=Sunday, ..., 6=Saturday.
///
/// Preconditions:
/// - year: 1..9999
/// - month: 1..12
/// - day: 1..31
#[inline]
pub fn weekday_bounded_distributed(
mut year: u32,
month: u32,
day: u32,
) -> u32 {
const SCALED_MONTH_TERM: [u32; 12] = [
0, 224_697, 149_798, 374_495,
0, 224_697, 374_495, 74_899,
299_596, 449_394, 149_798, 299_596,
];
year -= (month < 3) as u32;
let product = year * 5_243;
let base = year
+ (year >> 2)
- (product >> 19)
+ (product >> 21)
+ day;
(
(
base * 74_899 +
SCALED_MONTH_TERM[(month - 1) as usize]
) >> 16
) & 7
}C
#include <stdint.h>
/*
* Returns 0=Sunday, ..., 6=Saturday.
*
* Preconditions:
* - year: 1..9999
* - month: 1..12
* - day: 1..31
*/
static inline uint32_t weekday_bounded_distributed(
uint32_t year,
uint32_t month,
uint32_t day
) {
static const uint32_t scaled_month_term[12] = {
0u, 224697u, 149798u, 374495u,
0u, 224697u, 374495u, 74899u,
299596u, 449394u, 149798u, 299596u
};
year -= month < 3;
const uint32_t product = year * 5243u;
const uint32_t base = year
+ (year >> 2)
- (product >> 19)
+ (product >> 21)
+ day;
return (
(
base * 74899u +
scaled_month_term[month - 1]
) >> 16
) & 7u;
}The ordinary Sakamoto method
Sakamoto’s method uses the following month offsets:
0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4A basic C implementation looks like this:
static uint32_t weekday_sakamoto(
uint32_t year,
uint32_t month,
uint32_t day
) {
static const uint8_t month_term[12] = {
0, 3, 2, 5, 0, 3,
5, 1, 4, 6, 2, 4
};
year -= month < 3;
return (
year
+ year / 4
- year / 100
+ year / 400
+ month_term[month - 1]
+ day
) % 7;
}January and February are treated as the thirteenth and fourteenth months of the previous year. Therefore, the year is decremented when month < 3.
The algorithm then evaluates:
year
+ floor(year / 4)
- floor(year / 100)
+ floor(year / 400)
+ month term
+ dayThe remainder after division by seven is the day of the week.
The following page provides another explanation and implementation of Sakamoto’s method:
Replacing the divisions with magic numbers
This investigation was inspired by Falk Hüffner’s article:
That article restricts the input range and transforms leap-year testing into a short expression involving multiplication, masking, and comparison.
I wondered whether restricting the input range could similarly turn the constant divisions and remainder operation in Sakamoto’s formula into shorter integer operations.
This implementation supports years from 1 through 9999.
After decrementing the year for January and February, the adjusted year remains within the following range:
0 <= year <= 9999This bounded range allows the following two transformations:
const uint32_t product = year * 5243u;
product >> 19; // year / 100
product >> 21; // year / 400If value is the intermediate result of Sakamoto’s expression, value % 7 can also be calculated as follows:
((value * 74899u) >> 16) & 7uThe two important constants are therefore:
5243
74899Using 5243 to replace division by 100 for inputs between 0 and 9999 is not new. It is a previously known optimization that replaces division by a constant with multiplication and a bit shift.
One published example is:
https://www.moria.us/blog/2023/01/optimizing-numtostring
The implementation in this article additionally obtains both year / 100 and year / 400 from the same product, year * 5243.
Distributing the month term
The first version of this implementation added the ordinary month term before multiplying the complete intermediate value by 74899.
value =
year_term
+ month_term[month - 1]
+ day;
weekday =
((value * 74899u) >> 16) & 7u;This was already faster than the ordinary Sakamoto implementation. However, the month-term addition remained in the dependency chain before the final multiplication.
The multiplication can be distributed:
(year term + month term + day) * 74899
= (year term + day) * 74899
+ month term * 74899There are only twelve month terms, so their scaled values can be stored directly.
The ordinary month terms are:
0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4After multiplication by 74899, they become:
0, 224697, 149798, 374495,
0, 224697, 374495, 74899,
299596, 449394, 149798, 299596This transformation moves the month-term addition after the final multiplication.
On Apple Silicon, Clang compiled this part of the C implementation into a multiply-add instruction.
The month table grows from 12 bytes to 48 bytes. On typical desktop and server processors, it still fits within a single cache line. In an environment where memory or code size is more important, the earlier implementation with the 12-byte unscaled month table can be used instead.
Why 5243 performs division by 100
Let year be the adjusted year.
Its range is:
0 <= year <= 9999Write year as:
year = 100 * q + r
0 <= r < 100We have:
5243 * 100
= 524300
= 2^19 + 12Therefore:
5243 * year
= 5243 * (100 * q + r)
= 2^19 * q
+ 12 * q
+ 5243 * rBecause year <= 9999, both q <= 99 and r <= 99.
The largest possible value of the remaining terms is:
12 * 99 + 5243 * 99
= 520245
< 2^19The expression 12 * q + 5243 * r therefore cannot carry into bit 19.
Consequently:
(year * 5243u) >> 19is exactly equal to year / 100 throughout the supported range.
Why the same product performs division by 400
Now write year as:
year = 400 * q + r
0 <= r < 400We have:
5243 * 400
= 2097200
= 2^21 + 48Therefore:
5243 * year
= 2^21 * q
+ 48 * q
+ 5243 * rBecause year <= 9999, we have q <= 24 and r <= 399.
The largest possible value of the remaining terms is:
48 * 24 + 5243 * 399
= 2093109
< 2^21These terms cannot carry into bit 21.
Consequently:
(year * 5243u) >> 21is exactly equal to year / 400 throughout the supported range.
A single multiplication can therefore provide both quotients:
const uint32_t product = year * 5243u;
const uint32_t century = product >> 19;
const uint32_t four_centuries = product >> 21;Why 74899 calculates mod 7
Let value be the intermediate result of Sakamoto’s expression.
Under the stated input conditions:
0 <= value < 13000Write value as:
value = 7 * q + r
0 <= r < 7The constant 74899 has the following properties:
7 * 74899
= 8 * 2^16 + 5and:
74899
= 2^16 + 9363Expanding the multiplication gives:
74899 * value
= 74899 * (7 * q + r)
= (8 * q + r) * 2^16
+ 5 * q
+ 9363 * rBecause value < 13000, we have q <= 1857.
The largest possible value of the remaining terms is:
5 * 1857 + 9363 * 6
= 65463
< 2^16The expression 5 * q + 9363 * r therefore cannot carry into bit 16.
Consequently:
(74899 * value) >> 16
= 8 * q + rThe lowest three bits of 8 * q are always zero. Extracting the lowest three bits therefore leaves only r:
((value * 74899u) >> 16) & 7uThis is exactly equal to value % 7 throughout the supported range.
No 32-bit overflow is required
This implementation does not depend on 32-bit integer overflow.
The largest first product is:
9999 * 5243
= 52424757
< 2^32Using the slightly wider bound value < 13000, the largest final product is:
12999 * 74899
= 973612101
< 2^32All products fit within an unsigned 32-bit integer.
Exhaustive verification
Because the supported year range is finite, every input in the stated domain can be compared with the ordinary Sakamoto implementation.
The following TypeScript program performs the exhaustive comparison:
const MONTH_TERM = [0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4] as const;
function weekdaySakamoto(year: number, month: number, day: number): number {
year -= Number(month < 3);
return (
(year +
Math.floor(year / 4) -
Math.floor(year / 100) +
Math.floor(year / 400) +
MONTH_TERM[month - 1] +
day) %
7
);
}
for (let year = 1; year <= 9_999; year++) {
for (let month = 1; month <= 12; month++) {
for (let day = 1; day <= 31; day++) {
const expected = weekdaySakamoto(year, month, day);
const actual = weekdayBoundedDistributed(year, month, day);
if (actual !== expected) {
throw new Error(`mismatch: ${year}-${month}-${day}: ` + `${actual} !== ${expected}`);
}
}
}
}
console.log("verified");The number of compared inputs is:
9999 * 12 * 31
= 3,719,628The optimized implementation matched the ordinary Sakamoto formula for every year from 1 through 9999, every month from 1 through 12, and every day from 1 through 31.
The test deliberately checks every day through 31 without considering the actual length of each month. It therefore verifies a larger input set than the set of valid calendar dates.
The function itself does not reject nonexistent dates such as April 31. Date validation remains the caller’s responsibility.
Searching for the constants
I also searched the constants and shift amounts for the expression forms used by this implementation.
For the shared-product form:
product = year * C;
year / 100 = product >> shift;
year / 400 = product >> (shift + 2);the smallest shift that works for every year from 0 through 9999 is 19.
At that shift, 5243 is the only valid constant.
For the final remainder form:
((value * C) >> shift) & 7the smallest shift that works throughout the required intermediate-value range is 16.
Within the fundamental multiplier range, 74899 is the only valid constant.
These are conditional minimality results. They apply to the two expression forms above and do not prove that this program is optimal among all possible straight-line programs.
I also tested more aggressive forms that attempted to directly combine the year and month/day terms into one multiply-shift expression, but did not find a solution in the searched expression families.
Benchmark
The C benchmark was run on Apple Silicon with Clang using:
-O3 -march=nativeRandom years, months, and days were generated in advance and repeatedly processed from arrays.
The approximate inlined batch results were:
| Implementation | Time |
|---|---|
| Ordinary Sakamoto | 0.528 ns/item |
| Initial magic-number version | 0.430 ns/item |
| Distributed month-term version | 0.370–0.373 ns/item |
The distributed version was approximately 29–30% faster than the ordinary Sakamoto implementation in this benchmark.
The scalar version was also faster, although the improvement depends on inlining, calling conventions, compiler decisions, and the generated instruction sequence.
The same percentage should not be assumed for Intel x86-64, Rust, Node.js, or browser JavaScript. The Rust and TypeScript implementations shown above were exhaustively verified for correctness, but performance should be measured independently on the target CPU, compiler, or JavaScript engine.
Prior work and the scope of this result
Replacing division by 100 with multiplication by 5243 and a right shift is a known optimization for inputs between 0 and 9999.
For example, the following expression appears in work on fast integer-to-decimal conversion:
(value * 5243) >> 19See:
The constant 5243 and the division-by-100 transformation are therefore not new.
On August 17, 2026, Ben Joffe published an article describing how the fact that seven equals 2^3 - 1 can be used to calculate a bounded remainder using multiplication and shifts:
The general idea of replacing bounded constant division and remainder operations with multiplication and shifts is also established work.
The contribution of the implementation in this article is the particular specialization of these ideas to Sakamoto’s formula for years 1 through 9999:
- obtain both
year / 100andyear / 400from the same product,year * 5243; - convert the final
mod 7into a three-bit extraction using74899; - pre-scale the month terms;
- move the month-term addition out of the critical dependency chain.
I did not find an earlier implementation using this same combination of constants and transformations for Sakamoto’s algorithm. This is not, however, a claim that the underlying multiplication-and-shift techniques are new.
Conclusion
By restricting the supported year range to 1 through 9999, the constant divisions and final mod 7 in Sakamoto’s day-of-week calculation can be replaced with multiplication, shifts, and bit extraction.
The two central transformations are:
const uint32_t product = year * 5243u;
product >> 19; // year / 100
product >> 21; // year / 400and:
((value * 74899u) >> 16) & 7uPre-scaling the month terms additionally moves the month-term addition out of the critical dependency chain.
On my Apple Silicon system, the C implementation was approximately 30% faster than the ordinary Sakamoto implementation in an inlined batch benchmark.
The implementation has an explicit year range of 1 through 9999, and performance depends on the CPU, compiler, JIT, and surrounding code.
For most application code, the ordinary Sakamoto formula is simpler and sufficiently fast. This bounded implementation is most appropriate when day-of-week calculation is on a hot path, the input range is known, and the performance benefit has been measured on the target system.
This article is the English version of the original article written in Japanese, available here.