3개의 명령어로 윤년 여부를 확인하기

(hueffner.de)

4P by GN⁺ 20시간전 | ★ favorite | 댓글 1개

3개의 CPU 명령어만으로 윤년을 판별하는 함수를 구현함
이 방법은 비트 연산과 곱셈을 이용하여 전통적 분기 없이 동작
이 방식은 0~102499년 범위에서 정확함
벤치마크 결과 기존 방법 대비 3.8배 가량 빠른 성능

개요 및 문제 제시

0에서 102499년 사이의 년도에 대해, 단 3개의 CPU 명령어만 사용하여 윤년을 판별하는 함수
- 사용되는 실제 함수는 ((y * 1073750999) & 3221352463) <= 126976 구조임
이 비트 트위들링(bit-twiddling) 기법의 원리와 동작, 실질적인 효용성에 대해 설명

전통적인 윤년 판별 방법

보통 윤년 판별은 나눗셈(modulo)와 조건분기로 구현함
- 4로 나누어 떨어지는지, 100으로 안 나누어지는지, 400으로 나누어 떨어지는지 검사함
- 예시 코드:
```
if ((y % 4) != 0) return false  
if ((y % 100) != 0) return true  
if ((y % 400) == 0) return true  
return false  
```

표준 접근 방식의 최적화

(y % 100) 검사를 (y % 25)로, (y % 400) 검사를 (y % 16)으로 대체 가능함
- 그 이유는 앞서 4로 이미 나누었으므로, 25 및 16 곱셈 관계로 변경 가능
(y % 25) 연산을 나눗셈 없이 곱셈과 비교로 변환하는 마법 상수
- 예: x * 3264175145 > 171798691로 변환 가능
비트마스크를 더해 (y & 3)이나 (y & 15)로 4 또는 16의 나눗셈 대체 가능
컴파일러는 이러한 변환을 자동화하지만, 직접 다른 언어에서 활용할 수도 있음

분기 없는(branchless) 구현법

분기가 없는 형태로도 변환 가능함:
```
return !(y & ((y % 25) ? 3 : 15))  
```
이러한 방식은 코드 골프(coding golf)와 같이 코드 길이 줄이기에 적합

매직 상수 찾기: 비트 트위들링 접근법

윤년 판별식을 더욱 간단하게 만들기 위해 조합적 탐색과 SMT Solver인 Z3를 활용
- 형태: ((y * f) & m) <= t
요구 조건을 만족시키는 상수 f, m, t를 Z3로 탐색
- 0~102499 범위에서 정확한 결과를 얻을 수 있는 값 발굴
- 최종 결과가 (y * 1073750999) & 3221352463 <= 126976임

함수 원리 및 내부 구조 해설

상수를 이진수로 분석하여, 세 개의 주요 비트 영역 A, B, C로 구분함
- 각 영역의 비트 상태에 따라 윤년 판별의 3가지 조건을 포괄함
함수의 논리적 분해:
- A 영역: (y % 4) != 0 여부를 비롯한 4의 배수 조건 확인
- B 영역: (y % 100) != 0여부를 다양한 패턴(예: 뒷자리 14, 57, 71 등)로 필터링
- C 영역: (y % 16) == 0의 즉, 16의 배수 확인
곱셈이 실제로 나머지 계산 없이 다양한 조건을 결합해내는 원리 해설
- 매직 상수를 곱할 때, 100의 배수 등에서 특이적인 비트 패턴이 형성됨
- 추가적으로, 곱셈 오차와 여러 자리 숫자 패턴이 등장하는 수학적 내부 구조 분석이 포함됨

추가 범위 및 비트폭 확장 가능성

64비트로 확장할 경우 적합한 매직 상수 조합 탐색법도 제시
- f, m, t값을 다양하게 바꿔보며 최장 범위를 찾을 수 있음
- StackExchange에서도 최적 조합 및 Z3 활용 증명 사례가 있음

벤치마크 및 실제 성능 비교

벤치마크 결과:
- 2025년 등 예측 가능한 값에서는 0.65~0.69ns로 차이가 거의 없음
- 무작위 입력시 is_leap_year_fast가 3.8배 정도 빠른 성능을 보임
- 입력 패턴에 따라 분기(branching) 방식이 예측 불가할 때 상당한 이점이 있음

결론 및 실제 적용 여부

실제 응용에서 값이 예측가능할 때는 이득 적음, 하지만 대량의 무작위 데이터 상황에선 매우 유용
실제 파이썬이나 C# 등 표준 라이브러리 교체 시에는 현실적인 전체 프로그램 벤치마크가 필요함
아이디어와 구현 방법 자체가 흥미롭고, 특정 상황에서는 성능상 매력적인 솔루션임

▲

GN⁺ 20시간전 [-]

Hacker News 의견

최신 컴파일러인 gcc나 clang 같은 경우 is_leap_year1 같은 코드를 is_leap_year2처럼 자동으로 최적화해준다는 사실에 놀라움 느낌, 그래서 C 소스 단계에서 직접 최적화할 필요는 크게 없다는 생각, 하지만 다른 언어에는 여전히 유용함이 있을 수 있음, 특히 cal 프로그램의 최신 버전 소스코드에서 leap year 체크를 아주 간단하게 처리하는 점이 인상적임
- linux 코드가 세 가지 연속된 조건을 매번 반전시키고 기본값 반환을 쓰지 않아 이해하기 훨씬 쉽다는 점이 마음에 듦, 이런 복잡한 코드 구조가 있으면 디버깅할 때 정말 미치는 경험임
((y * 1073750999) & 3221352463) <= 126976 이 코드가 어떻게 동작하는지에 대한 설명이 복잡할 수밖에 없다는 데에 전혀 놀라움 없음, 오히려 그게 당연함
이해하기 어려운 매직 넘버 최적화 기법을 정말 좋아함, 이런 걸 볼 때마다 예전 어셈블리로 내부 루프 짜던 시절에 얼마나 많은 최적화 기법을 놓쳤을지 궁금함, 혹시 이런 테크닉 모아둔 컬렉션이 있다면 공유 요청
- 여러 비트 조작 트릭 모음 링크 공유, UNIX 스타일 비교에 효율적인 CMP(X, Y) 매크로, signum 함수 최적화 예시, Motorola 68000용 어셈블리 코드 예시 링크, OpenSolaris에서 유래된 비트 매크로 모음 등 다양한 최적화 기법 링크 제공, Open Solaris 블로그는 사라졌다는 아쉬움도 언급, 코드 최적화에 관심 있는 사람들에게 추천
- "Hacker's Delight" 책 추천, 다양한 비트 트릭과 저수준 최적화 기법이 가득함
- supercompilation 기법 찾아보라는 제안
- 예전에는 이런 기법을 놓친 게 아니고, 당시엔 곱셈이 워낙 비쌌기 때문에 저런 게 곧 최적화였음
윤년 체크가 이렇게 흥미로울 줄 전혀 예상 못함, 아마 저수준 프로그래머들은 이미 오래전에 이런 트릭을 찾았지만 기록을 남기지 않았던 게 아닐까 하는 생각, 이런 게 아직도 옛 코드 속에 숨어 있을지도 모른다는 느낌, 이런 기법 컬렉션 있으면 정말 탐구해보고 싶다는 열의
- 80년대 z80에서 집에서 직접 배운 것들이 있었는데 대부분 잊어버림, 가끔씩 20대 자녀들에게 보여주면 마치 마술을 부리는 듯한 느낌
6000년 이전의 윤년을 알아야 한다면 직접 만든 인터랙티브 계산기와 가시화 도구 사용, 비록 기계 명령어 수는 좀 많지만 아주 빠르게 수천 번의 계산 처리 가능, 수학적 트릭 역시 감탄 포인트
비트 조작 챕터를 읽다 "혹시 솔버 쓸 수 있지 않을까" 라는 생각이 들었고, 실제로 글쓴이가 딱 그 방법을 사용해서 깜짝 놀람, 세밀한 접근 방식에 만족
이런 윤년 체크 함수를 current-time-api에 추가하는 게 좋겠다는 제안
숫자를 이진수로 보면 재미있는 패턴들이 보임, 모든 소수는 2를 제외하면 1로 끝난다는 점이 흥미로웠음
- 재밌게 보일 수 있지만, 모든 홀수가 1로 끝나고 소수가 본질적으로 2를 제외하면 짝수가 될 수 없으니, 별다른 의미를 못 느끼겠다는 의문 제기
윤년 문제에서 0이 없다는 지적이 등장, 사실 "0년"은 없고 1 BC에서 바로 1 AD로 넘어가서 0 체크는 의미 없다는 이야기
- 글 맨 처음을 보면 윤년 알고리즘 설계의 전제가 proleptic 그레고리력과 천문학적 연도를 쓴다는 점이라 설명, 이 조건이 없다면 윤년 체크는 로케일마다 복잡해진다는 점을 강조
- 천문학적 연도 표기를 쓰면 0년이 등장하게 되고, 연/월 관리 등에서는 그렇게 처리하는 것이 오히려 깔끔함, 내부 데이터는 천문학적 표기, 외부 출력만 BCE/CE 변환 제안
- 그레고리력 도입 이전의 달력은 기준 자체가 모호하고 지역마다 다름, 1582년에는 하루에 열흘을 건너뛴 '10일 삭제'도 있었으니, 그 이전 날짜의 연산은 신뢰 불가, 로마 시대 사제들은 윤년을 미신/뇌물 등으로 임의조정하기도 해서 더욱 복잡함
- ISO8601 표준에서는 0년을 허용하고, 천문학적 달력에서 0년은 1 BC의 의미, BCE 연도는 전부 -1만큼씩 오프셋 됨
소스코드가 실제로 웃음을 터뜨리게 만드는 경우는 드물기 때문에 아주 즐거운 경험임

답변달기