요일 계산을 더 빠르게 만드는 방법

32비트 날짜 카운트에서 요일을 구하는 % 7 연산을 다시 설계해, 기존 구현보다 빠른 곱셈/덧셈/비트 시프트 기반 알고리듬들을 제시함 핵심은 7 = 2^3 - 1인 메르센 수(Mersenne number) 특성을 이용해 % 7을 % 8에 가까운 연산으로 바꾸고, 나눗셈 대신 고정소수점 역수 곱셈과 비트 추출을 사용하는 것임 제한된 날짜 범위에서는 weekday = (u32(rd) * M + Z) >> 29 형태의 단 3개 연산으로 계산할 수 있으며, 32비트 전체 범위도 보정 시프트/두 개의 곱셈/곱셈 결과의 상·하위 비트를 이용하는 여러 변형으로 처리 가능함 AMD Ryzen 9과 Apple M4 Pro 벤치마크에서 새 전체 범위 알고리듬들은 기존 기준인 Neri 2024 방식의 약 0.3~0.5배 시간으로 실행됐고, ARM에서는 MADD와 시프트 결합 덕분에 특히 단순한 명령열로 컴파일될 수 있음 같은 원리를 % 3, % 15, % 31 같은 다른 메르센 수뿐 아니라 x % 24, x % 60 에도 확장할 수 있어 날짜 라이브러리/DB 엔진/시간 계산용 저수준 최적화 기법으로 활용 가능함 단순한 % 7도 실제 기계어에서는 복잡함 Unix 날짜 카운트 rd에서 1970-01-01 = Thursday(4)를 기준으로 요일 [0..6]을 구하는 가장 직관적인 방법은 ((rd % 7) + 11) % 7 같은 형태임 Rust의 rem_euclid처럼 양의 나머지를 직접 제공하는 언어에서는 (rd + 4) POSMOD 7로 표현할 수 있음 유지보수가 중요한 일반 코드에는 이런 단순한 접근을 권장하지만, 실제 컴파일 결과에서는 % 7이 여러 곱셈/시프트/보정 연산으로 풀림 특히 7은 고정 상수 나눗셈 최적화 관점에서 비협조적인 divisor라서, 32비트 레지스터에 들어가는 역수 근사값만으로는 정확한 몫을 얻기 어려워 별도 보정이 필요함 Hinnant와 Neri의 기존 방식 Howard Hinnant의 2014년 방식은 입력 부호에 따라 % 7 계산을 나누며, 8/16/32/64비트에 같은 논리를 적용할 수 있고 부호 캐스팅이나 비트폭 의존 오버플로를 사용하지 않음 다만 32비트 최대값 근처 4개 입력에서는 rd + 4가 C/C++의 signed overflow가 되어 undefined behavior가 발생할 수 있음 Cassio Neri의 2024년 방식은 signed 값을 먼저 unsigned로 변환해...