나머지 연산 없는 빠른 요일 계산, 곱셈 한 번이면 됩니다
날짜에서 요일을 구할 때 흔히 쓰는 % 7 없이, 곱셈 한 번과 시프트만으로 요일을 구하는 방법을 Ben Joffe의 글 Fast day-of-week computation을 바탕으로 정리합니다.
날짜에서 요일을 구하는 코드는 대개 % 7로 끝납니다. 그런데 요일 계산은 곱셈 1번 + 덧셈 1번 + 시프트 1번, 총 3연산으로도 끝낼 수 있습니다. 기존에 가장 빠르다고 알려진 방법(Neri, 2024) 대비 4~6배 빠릅니다.
// rd: 1970-01-01 기준 경과 일수 (rata die), 결과: 0=일요일 ~ 6=토요일
uint32_t weekday(int32_t rd) {
const uint32_t M = 613566757; // (2^32 / 7) + 1
const uint32_t Z = 0x94920000; // 에포크(1970-01-01 = 목요일) 정렬용
return ((uint32_t)rd * M + Z) >> 29;
}
이 글의 상수와 항등식은 파이썬으로 전 구간 재검증을 했고, 모두 원문 주장대로 동작했습니다.
요일 계산은 왜 % 7 인가
요일 계산의 출발점은 rata die, 즉 기준일로부터의 경과 일수입니다. 유닉스 에포크(1970-01-01)는 목요일이므로, 일요일을 0으로 두면 요일은 이렇게 구합니다.
weekday = ((rd % 7) + 7 + 4) % 7 // C/C++: 음수 나머지 보정 때문에 두 번
weekday = (rd + 4).rem_euclid(7) // Rust: 양수 나머지 한 번
읽기 쉽고 유지보수도 편합니다. 다만 % 7 자체가 CPU 입장에서 싼 연산이 아닙니다.
% 7 은 왜 느린가
나눗셈은 CPU에서 가장 느린 산술 연산에 속합니다. 그래서 컴파일러는 상수 나눗셈을 "역수 곱셈"으로 바꿉니다. x / 7을 x * (2^32 / 7) >> 32 비슷한 형태로 바꾸는 것으로, Hacker's Delight라는 책으로 잘 알려진 고전 기법입니다.
그런데 7은 이 변환이 깔끔하게 떨어지지 않습니다. 2^32 / 7 = 613566756.57...처럼 소수부가 남아서, 컴파일러가 만든 코드에 오차 보정용 연산이 몇 개 더 붙습니다. 나머지(% 7)까지 구하려면 x - (x/7)*7을 또 해야 하니 연산이 더 늘어납니다.
핵심 아이디어: 7일짜리 주를 8칸에 얹기
7은 메르센 수(2³ - 1)입니다. 그래서 다음 항등식이 성립합니다.
N % 7 == floor(N × 8 / 7) % 8
% 8은 하위 3비트만 읽으면 되는 공짜 연산입니다. 7로 나눈 나머지 문제가, 8/7배로 늘린 다음 하위 3비트를 읽는 문제로 바뀝니다.
7일마다 반복되는 달력을, 한 주가 8칸인 공책에 글자 폭을 8/7배로 늘려서 옮겨 적습니다. 어떤 날이 무슨 요일인지 알고 싶으면 나눗셈 없이 "몇 번째 칸인가"만 보면 됩니다.
고대 로마에는 실제로 8일마다 장이 서는 눈디눔(nundinum) 주기가 있었고, 원문 저자는 여기서 이름을 따 이 기법을 "Nundinal Map"이라 부릅니다.
맨 위의 3연산 코드는 이 그림 그대로입니다.
rd * M: M ≈ 2²⁹ × 8/7 이므로, "8/7배 늘리기"와 "상위 비트로 밀어올리기"를 곱셈 한 번에 합니다.+ Z: 결과를 에포크 요일(목요일)에 맞게 회전시키는 오프셋입니다.>> 29: 상위 3비트만 남깁니다. 이게% 8, 곧 요일입니다.
유효 범위: 약 ±24만 년
M이 8/7의 근사값이라서 입력이 커질수록 오차가 쌓입니다. 그래서 3연산 버전은 ±8,900만 일(약 ±24만 년) 범위 안에서만 정확합니다. 직접 검증해 보니 첫 오답은 +89,522,176일과 -89,434,797일에서 나왔습니다.
24만 년이면 부족할 일이 없어 보이지만, 라이브러리는 int32 전체 범위(±58억 년 상당)를 받는 경우가 있어 원문은 전체 범위 변형도 함께 제시합니다.
전체 범위가 필요하면: 시프트 보정 변형
int32 전체 범위를 커버하는 변형 중 가장 단순한 쪽은, 반올림 대신 내림 상수를 쓰고 부족분을 시프트 두 번으로 채웁니다.
uint32_t weekday_full(int32_t rd) {
const uint32_t M = 613566756; // 2^32 / 7 내림
const uint32_t Z = 0x95000000;
uint32_t a = (uint32_t)rd * M + Z;
uint32_t b = (rd >> 1) + (rd >> 4); // 4/7 ≈ 1/2 + 1/16 근사 보정
return (a + b) >> 29;
}
내림으로 잘려 나간 소수부는 정확히 4/7입니다. (x >> 1) + (x >> 4)는 0.5 + 0.0625 = 0.5625, 즉 4/7(0.5714...)의 근사값이라 이 부족분을 메워 줍니다. 시프트는 곱셈이 도는 동안 병렬로 실행되므로 추가 비용이 거의 없습니다.
이 변형도 int32 전체 범위에서 랜덤 50만 건과 경계값으로 검증했고 전부 정확했습니다.
이 밖에도 64비트 곱으로 정밀도를 올린 변형, 곱셈 2개를 파이프라인으로 겹치는 변형, x86의 LEA 명령어 하나에 곱셈·덧셈·상수를 욱여넣는 3연산 변형이 있습니다. 자세한 내용은 원문을 보시면 됩니다.
일반화: 2의 거듭제곱 패딩 (x % 24, x % 60)
같은 패딩을 다른 나눗수에도 쓸 수 있습니다.
x mod D == (x + c × floor(x / D)) mod (D + c) (D + c 가 2의 거듭제곱이 되도록 c 선택)
나눗수를 2의 거듭제곱까지 "패딩"하면 나머지 연산이 비트 AND로 바뀝니다. 시간 계산에 바로 써먹을 수 있습니다.
| 계산 | 패딩 공식 | 비고 |
|---|---|---|
x % 24 (시) | (x + (x/24 << 3)) & 31 | 24 + 8 = 32 |
x % 60 (분·초) | (x + (x/60 << 2)) & 63 | 60 + 4 = 64 |
x / 24는 어차피 날짜 계산에서 함께 구하는 값이라, 그 부산물로 나머지를 공짜에 가깝게 얻습니다. 두 공식 모두 0부터 200만까지 전수 검증했습니다.
얼마나 빠른가
원문 벤치마크(AMD Ryzen 9, Apple M4 Pro)입니다. 기준은 기존 최고 기록인 Neri(2024) = 1.0, 숫자가 작을수록 빠릅니다.
| 알고리즘 | 상대 처리량 | 유효 범위 |
|---|---|---|
순진한 이중 % 7 | ~2.8 | 전체 |
| Hinnant (2014) | ~2.9 | 거의 전체 |
| Neri (2024) | 1.0 (기준) | 전체 |
| 3연산 버전 | 0.17 ~ 0.27 | ±24만 년 |
| 시프트 보정 변형 | 0.39 ~ 0.55 | 전체 |
주의사항
- 3연산 버전에는 범위 제한이 있습니다. ±24만 년을 넘는 입력이 들어올 수 있으면 전체 범위 변형을 쓰거나 입력을 걸러야 합니다. Rust의 Jiff처럼 ±1만 년만 지원하는 라이브러리에는 그대로 안전합니다.
- 부호 있는 정수를 unsigned로 캐스팅하는 부분은 2의 보수 래핑을 전제합니다. Rust에서는 정의된 동작이지만 C/C++에서는 캐스팅 방식을 지켜야 합니다.
- 전체 범위 변형들은 컴파일러가 최적 코드로 구워 주지 않는 경우가 있어, 원문은 x86 어셈블리 수준의 배치까지 다룹니다. 여기까지 가기 전에, 마이크로 최적화가 필요한 상황인지부터 따져 보는 게 순서겠지요.
Q&A
- 요일 계산에 % 7 을 안 쓰고 계산하는 방법이 있나요?
- 있습니다. 7이 2³ - 1이라는 성질을 이용하면
N % 7 == floor(N × 8 / 7) % 8이 성립하고, 이를 곱셈 1번 + 덧셈 1번 + 시프트 1번으로 구현할 수 있습니다. 위의 3연산 코드가 그 구현입니다.
- 있습니다. 7이 2³ - 1이라는 성질을 이용하면
- 이 최적화가 실제로 의미가 있나요?
- 날짜 라이브러리나 대량 데이터 처리처럼 요일 계산이 핫패스에 있으면 의미가 있습니다. 한 번 호출하고 마는 애플리케이션 코드라면 읽기 쉬운
% 7이 낫습니다.
- 날짜 라이브러리나 대량 데이터 처리처럼 요일 계산이 핫패스에 있으면 의미가 있습니다. 한 번 호출하고 마는 애플리케이션 코드라면 읽기 쉬운
- 7 말고 다른 수에도 쓸 수 있나요?
- 나눗수를 2의 거듭제곱까지 패딩하는 일반형으로 확장됩니다.
x % 24는 32로,x % 60은 64로 패딩해서 비트 AND로 바꿀 수 있습니다.
- 나눗수를 2의 거듭제곱까지 패딩하는 일반형으로 확장됩니다.
마무리
"컴파일러가 알아서 최적화해 주겠지" 하는 영역에도 사람 손으로 짜낼 여지가 남아 있다는 게 재미있었습니다. 나눗수를 8로 바꿔치기한다는 발상이 오래 기억에 남을 것 같아 레퍼런스로 남깁니다.
- 원문: Fast day-of-week computation (Ben Joffe)
- 코드: benjoffe/fast-world-calendars (MIT)