무슨 일이 있었나요?
2019년에 수학자 데이비드 하비(David Harvey)와 요리스 반 데어 회번(Joris van der Hoeven)이 두 정수를 O(n log n) 시간에 곱하는 알고리즘을 발표했어요. 반세기 가까이 풀리지 않던 숙제를 풀었다는 평가를 받았고, 많은 연구자가 “이게 정수 곱셈의 끝일 것”이라고 생각했죠.
그런데 최근 하비의 홈페이지에 새로 제안된 o(n log n) 정수 곱셈 알고리즘을 다루는 문서가 올라왔어요. 여기서 소문자 o가 핵심이에요. 대문자 O(n log n)는 ‘n log n과 비슷하거나 더 빠르다’는 뜻이에요. 소문자 o(n log n)는 ‘n이 커질수록 n log n과의 차이가 계속 벌어질 만큼 확실히 더 빠르다’는 뜻이고요. 이게 맞다면 다들 최종 답이라고 생각했던 선을 넘는 셈이에요.
다만 이런 큰 주장은 꼼꼼한 검증을 거쳐야 확정돼요. 지금은 ‘제안’ 단계로 보는 게 맞고, 증명의 세부 내용과 어떤 계산 모델을 전제로 하는지는 원문에서 직접 확인하시길 권해요. 여기서는 이게 왜 그렇게 큰 이야기인지 배경부터 풀어볼게요.
곱셈 알고리즘 60년의 역사
초등학교에서 배운 세로 곱셈부터 생각해볼게요. n자리 수 두 개를 곱하려면 모든 자리끼리 한 번씩 곱해야 하니까 대략 n × n번, 즉 O(n²) 번의 연산이 필요해요. 100만 자리 수라면 1조 번이에요.
1960년, 모스크바의 대학생이던 카라추바(Karatsuba)가 이 한계를 깼어요. 숫자를 반으로 쪼개면 원래 4번 해야 하는 곱셈을 3번으로 줄일 수 있다는 트릭이었어요. 이걸 재귀적으로 반복하면 O(n^1.585) 정도가 돼요. ‘곱셈은 n²보다 빠를 수 없다’고 추측했던 콜모고로프의 세미나에서 반례로 나온 거라 더 유명해졌죠.
다음 도약은 1971년의 쇤하게-슈트라센(Schönhage–Strassen) 알고리즘이에요. 핵심은 고속 푸리에 변환(FFT)인데요, 이게 뭐냐면 숫자를 ‘여러 파동의 조합’처럼 다른 형태로 바꿔서 표현하는 기법이에요. 이렇게 바꾸면 복잡하게 얽힌 곱셈이 칸끼리의 단순 곱셈으로 바뀌어서 훨씬 빨라져요. 결과는 O(n log n log log n) 수준이었어요. 두 사람은 이때 이미 “최적은 n log n일 것”이라고 추측했고요. 이후 2007년 퓌러(Fürer)가 이를 더 개선했고, 2019년 하비와 반 데어 회번이 무려 1729차원 푸리에 변환까지 동원해서 마침내 O(n log n) 시간 복잡도에 도달했어요.
n log n은 정말 ‘벽’이었을까
n log n은 비교 기반 정렬의 하한으로 익숙한 숫자예요. 정렬은 이게 한계라는 게 증명돼 있죠. 그런데 정수 곱셈은 n log n이 하한이라는 게 아직 조건 없이 증명된 적이 없어요. 2019년의 한 연구가 보여준 건, ‘네트워크 코딩 추측’이라는 다른 미해결 가설이 참이라면 특정 회로 모델에서 n log n이 하한이라는 것뿐이었어요. 그러니까 n log n이 벽이라는 건 강한 ‘믿음’이었지 확정된 사실은 아니었던 거예요.
그래서 o(n log n) 제안을 볼 때는 계산 모델을 꼭 따져봐야 해요. 계산 모델이 뭐냐면 ‘어떤 연산을 한 걸음으로 칠 것인가’에 대한 약속이에요. 하비와 반 데어 회번의 결과는 다중 테이프 튜링 기계라는 엄격한 모델을 기준으로 해요. 큰 단위를 한 번에 연산할 수 있는 RAM 같은 모델에서는 같은 표기라도 의미가 달라지거든요.
실무에서는 뭘 쓸까
솔직히 말하면 O(n log n) 알고리즘조차 실무에서는 쓰이지 않아요. 이 알고리즘이 이득을 보려면 숫자가 대략 2^(1729¹²) 비트보다 커야 한다고 알려져 있어요. 우주에 있는 원자를 다 써도 그 자릿수를 다 적을 수 없을 만큼 큰 수예요. 이렇게 이론상으로는 최고지만 현실의 입력에서는 쓸모없는 알고리즘을 은하 알고리즘(galactic algorithm)이라고 불러요.
실제 라이브러리는 숫자 크기에 따라 알고리즘을 바꿔가며 써요.
- CPython의 int: 작은 수는 일반 곱셈, 일정 크기 이상은 카라추바
- Java BigInteger: 일반 곱셈 → 카라추바 → 툼-쿡(카라추바를 3분할로 일반화한 방식)
- GMP: 여기에 더해 아주 큰 수에서는 FFT 기반의 쇤하게-슈트라센 계열까지 사용
한국 개발자에게 주는 시사점
첫째, 빅오를 다시 보게 돼요. 점근적으로 빠르다고 실제로도 빠른 건 아니에요. 상수 계수와 실제 입력 크기를 함께 봐야 한다는 교훈은 코딩 테스트뿐 아니라 실무 성능 튜닝에서도 그대로 통해요.
둘째, 큰 수 연산을 다룬다면 라이브러리 내부 구현을 알아두세요. 암호, 블록체인, 과학 계산처럼 큰 정수를 많이 쓰는 분야에서는 카라추바에서 FFT로 넘어가는 지점 하나가 성능을 크게 바꿔요.
셋째, FFT는 꼭 한번 공부해볼 만해요. 곱셈뿐 아니라 신호 처리, 이미지 압축, 다항식 연산, 알고리즘 대회 문제까지 정말 많은 곳에서 쓰이거든요.
마무리
한줄 정리: 정수 곱셈의 최종 답처럼 보였던 n log n에 도전하는 제안이 나왔어요. 아직은 결론보다 질문이 더 흥미로운 단계예요.
여러분은 현실에서 쓸 수 없는 ‘은하 알고리즘’도 충분히 연구할 가치가 있다고 보시나요? 실무에서 빅오와 실제 성능이 크게 달랐던 경험이 있다면 공유해주세요.
🔗 출처: Hacker News