Hacker News 2026.06.02 40

64비트 정수의 단 17%만이 32비트 두 개의 곱이다, 의외로 중요한 수학적 사실

갑자기 무슨 소리냐면

Daniel Lemire라는 유명한 컴퓨터 과학자(고성능 SIMD 처리, JSON 파서 simdjson으로 유명해요)가 블로그에 흥미로운 분석을 올렸어요. 제목 그대로예요. 64비트 정수 전체 중에서 단 17%만이 두 개의 32비트 정수의 곱으로 표현될 수 있다는 거예요.

처음 들으면 "그래서 뭐?" 싶을 수 있는데요, 이게 컴퓨터 내부의 곱셈·나눗셈 동작 방식과 깊이 연결돼 있어서 성능 최적화나 자료구조 설계에 의외로 큰 영향을 줍니다. 한 번 풀어볼게요.

직관적으로 이해해보기

32비트 정수는 약 42억 개(2³²)예요. 그러니까 32비트 × 32비트 곱셈의 "가능한 입력 조합"은 약 42억 × 42억 = 약 1.8 × 10¹⁹개 정도예요. 결과는 최대 64비트 안에 들어가요(2³² × 2³² = 2⁶⁴).

그러면 "입력 조합이 1.8 × 10¹⁹개니까 64비트 정수(약 1.8 × 10¹⁹개) 거의 다 채울 수 있는 거 아냐?" 싶죠. 그런데 그게 아니에요. 중복이 엄청 많거든요. 예를 들어 12 = 2×6 = 3×4 = 1×12, 이렇게 같은 결과를 만드는 입력 조합이 여러 개 존재해요. 그래서 "실제로 도달 가능한 64비트 값의 개수"는 훨씬 적어집니다.

Lemire의 분석에 따르면 32비트 × 32비트 곱셈으로 만들 수 있는 서로 다른 64비트 값의 개수는 전체 64비트 공간의 약 17%에 불과하다는 거예요. 나머지 83%는 "32비트 두 개를 곱해서는 결코 만들 수 없는 값"이라는 뜻이죠.

왜 중요하냐면

이게 그냥 수학 퀴즈 같지만, 실제로는 해시 함수, 난수 생성, 모듈로 연산 최적화 같은 곳에서 핵심적인 의미를 가져요.

예를 들어 빠른 해시 함수들은 종종 곱셈을 이용한 비트 섞기를 써요. wyhash, xxhash, MurmurHash 같은 모던 해시 함수들이 대표적이죠. 입력값에 큰 소수를 곱한 다음 상위/하위 비트를 섞어서 분포를 균등하게 만드는 식이에요. 그런데 만약 "32비트 × 32비트 곱셈"으로만 비트 섞기를 하면, 결과 분포가 64비트 공간의 17%에 편향될 수 있어요. 그래서 좋은 해시 함수는 곱셈 후에 추가로 XOR이나 시프트로 더 섞어주는 거예요.

또 다른 예는 나머지 연산 최적화예요. CPU에서 나눗셈은 곱셈보다 훨씬 느려요. 그래서 컴파일러나 라이브러리는 상수 나눗셈을 "미리 계산한 곱셈"으로 바꿔치기하는 트릭(Granlund-Montgomery 방식)을 자주 써요. 이때 어떤 값의 범위가 32비트 곱셈으로 정확히 표현 가능한지 따져야 정확도가 보장되는데, 이번 분석이 바로 그런 경계를 명확히 해주는 거죠.

자세한 수학적 배경

좀 더 깊이 들어가면 이건 수론(Number Theory)의 오래된 주제와 연결돼요. "어떤 수가 작은 인수들의 곱으로 표현 가능한가"라는 문제는 정수론에서 multiplication table problem이라고 불리고, Paul Erdős가 1955년에 처음 깊이 다뤘어요. 1990년대에 케빈 포드(Kevin Ford)가 이 문제의 점근적 분포를 정확히 밝혔는데, Lemire의 17%라는 수치도 이 결과와 맞닿아 있어요.

수학적 직관은 이래요. 소수(prime number) 같이 인수가 적은 수는 32비트 두 개의 곱으로 표현되기 어렵고, 작은 인수가 많은 합성수일수록 표현하기 쉬워요. 그런데 큰 64비트 정수 중에는 작은 인수가 없는 "성긴" 수가 의외로 많아서, 결과적으로 17%라는 비율이 나오는 거예요.

실무에서 어디까지 영향을 주냐면

솔직히 일상적인 웹 개발에서는 거의 영향이 없어요. 그런데 다음과 같은 영역에서는 정말 중요해요. 고성능 데이터베이스 엔진(ClickHouse, DuckDB 같은), 암호학 라이브러리, 게임 엔진의 난수 생성기, 컴파일러 백엔드의 산술 최적화, 빅데이터 해시 조인, 이런 곳에서는 이런 수학적 디테일이 성능 차이를 만들거든요.

또 한 가지 재밌는 응용은 버그 검출이에요. 어떤 함수가 "64비트 정수를 32비트 두 개의 곱으로 분해해서 처리한다"고 가정하고 짠 코드가 있다면, 입력의 83%에서는 그 분해가 불가능하기 때문에 가정 자체가 깨질 수 있어요. 이런 코드를 리뷰할 때 이번 분석이 머릿속에 있으면 "어, 이거 모든 64비트 정수를 커버 못 하는 거 아냐?" 하는 경고등이 켜질 수 있죠.

한국 개발자에게 주는 의미

이런 글의 가치는 "당장 써먹는 코드"보다는 컴퓨터에 대한 직관을 다듬는 데 있어요. 우리가 매일 쓰는 곱셈, 나눗셈, 해시 함수 안에 이렇게 풍부한 수학이 숨어 있다는 걸 알면, 라이브러리를 고를 때나 성능 문제를 디버깅할 때 한 단계 더 깊이 볼 수 있어요.

특히 시스템 프로그래밍, DB 엔진, 인프라 쪽 일하시는 분들은 이런 "비트 수준의 수학" 감각이 정말 중요해요. C++ 표준 위원회나 LLVM 컴파일러 기여자들이 자주 하는 토론도 이런 결의 내용이거든요. 평소에 Lemire의 블로그를 구독해두면 비슷한 결의 인사이트를 꾸준히 얻을 수 있어요.