64비트 부호있는 정수 나눗셈을 더 빠르게 하는 새로운 알고리즘

핵심 요약

• 부호있는 정수 나눗셈(floor division)은 결과를 −∞ 방향으로 반올림하는 방식으로, 0 방향으로 반올림하는 표준 나눗셈과 다르며 타임스탬프·각도·타일 위치 같은 반복 패턴 추적에 유용합니다.
• 컴파일 타임에 나누는 수가 정해진 경우, 기존 방법은 곱셈 1회 + 2~3 사이클 또는 나머지 계산이 필요했으며, 음수 처리를 위해 추가 분기나 비교가 들어갑니다.
• 1994년 Granlund·Montgomery 논문의 기법을 확장하면 양수 나눗셈을 부호 반사로 처리해 5~6 사이클을 3 사이클로 단축할 수 있고, 2005년 Arch D. Robison 논문은 곱셈-더하기-시프트 조합으로 더 단순한 구현을 제시했습니다.
• Robison 방식은 32비트 나눗셈과 작은 나눗셈에서 이상적이지만, 64비트에서는 128비트 곱셈이 필요한 경우가 많아 ARM64에서 여러 곱셈 명령이 필요해지는 문제가 있습니다.
• 저자는 나눗셈을 두 개의 다른 승수를 선택하는 '부호-선택-승수' 방식을 제안하며, 이는 양수와 음수에 각각 최적화된 라운드 승수를 사용하되 모두 사용 가능한 경우에만 적용됩니다.
• 각 나누는 수마다 어느 방식(라운드-업, 라운드-다운, 부호-선택)이 최적인지는 컴파일 타임에 최악 시나리오를 반복 테스트해 결정되며, 음수 나누는 수도 같은 원리로 작동합니다.
• Floor 나머지는 나눗셈에서 자연스럽게 유도되고, 2^N−2^K 형태 나누는 수는 더하기-시프트-마스크로 더 빠르게 계산할 수 있으며, 유클리드 나눗셈도 음수 나누는 수용 항등식으로 최소 추가 비용으로 구현됩니다.
• 저자는 ARM64 M4, Snapdragon X1, AMD Ryzen, Intel Core i7 등에서 벤치마크했고, 부호-선택 방식이 대부분 가장 빠르지만 x86에서는 라운드-다운이 더 나을 수 있으며 구체적 선택은 플랫폼마다 다릅니다.
• Google TensorFlow는 2017년 출시부터 4년간 이 함수에 버그를 가지고 있다가 2021년에 수정했으며, 이는 정확한 구현이 얼마나 까다로운지와 표준 라이브러리에 이 함수가 필요한 이유를 보여줍니다.
• 저자는 65535개 나누는 수(32비트 범위 -32768~32767)에 대한 자동 테스트 생성기와 재사용 가능한 C++ 템플릿 함수를 제공하며, 코드를 그대로 복사하면 라이선스 조건이 적용되지만 로직을 다시 작성하면 라이선스 불필요합니다.