최근 제안된 o(n log n) 정수 곱셈 알고리즘

정수 곱셈의 기존 O(n log n) 시간 경계를 처음으로 o(n log n)으로 낮췄다는 알고리즘을, 기존 알고리즘의 저자인 David Harvey가 검토합니다. 직접 증명을 완전히 확인하지는 못했지만 AI의 설명을 바탕으로 주장이 그럴듯하다고 판단하며, 가속화 아이디어와 검증의 과제를 설명합니다.

주제: 알고리즘 AI 수학

에디터 노트

이 결과의 가장 큰 쟁점은 상계의 크기보다 검증 경로입니다. Harvey는 해당 분야의 기존 알고리즘을 만든 전문가지만 새 논문을 직접 확인하지 않았고, AI가 설명한 논증을 일부 이해한 수준에서 타당성을 잠정 판단합니다. 본문에 제시된 gadget은 절약이 가능한 구조를 구체적으로 설명하지만, 저자 자신도 확장 과정의 세부 추정과 전체 증명을 확인하지 않았다고 밝힙니다. 댓글의 Lean 형식화 완료 주장은 검증 수단을 보완하는 정보지만, 본문 작성 시점의 서술과 다르며 댓글만으로 형식화 범위나 정리 진술의 일치를 확인할 수는 없습니다. 따라서 이 자료가 뒷받침하는 결론은 해당 알고리즘의 증명이 독립 검증을 마쳤다는 것이 아니라, 원 알고리즘의 전문가가 AI의 설명을 거쳐 주장을 그럴듯하다고 본다는 데까지입니다. 댓글에서도 형식 검증의 가치와 AI가 논문을 이해했다는 판단의 신뢰성이 갈립니다. 실제 구현 성능이나 통상적인 정수 크기에서의 속도 향상은 주장되지 않으며, 이 결과의 직접적인 의미는 점근 복잡도 경계에 있습니다.

AI 요약

David Harvey는 자신과 Joris van der Hoeven이 제시한 O(n log n) 정수 곱셈 알고리즘을 바탕으로, 최근 발표된 o(n log n) 알고리즘의 주장이 타당할 가능성이 있다고 봅니다. 다만 관련 논문 세 편을 직접 읽거나 증명을 꼼꼼히 확인하지는 못했고, AI 모델 Fable의 설명을 질문을 거듭하며 검토한 뒤 내린 잠정적 판단이라고 선을 긋습니다. 제안된 상계는 O(n(log n)^(1-ε)) 꼴이며, 최초 ε은 2^-182입니다. 이 수치 자체는 매우 작지만, 저자는 기존 점근 복잡도 개선과 견주면 큰 진전이라고 설명합니다.

기존 알고리즘과 병목

2021년 알고리즘은 여러 환원 뒤에 복소수 계수 환 C=C[y]/(y^r+1)에서 다차원 DFT를 계산합니다. FFT의 butterfly 연산 수가 O(n log n)을 만들며, Boolean circuit 모델에서는 이 산술 연산이 주요 비용입니다. Turing machine 모델에서는 배열 전치 같은 데이터 재배치도 같은 차수의 비용을 냅니다. 새 접근은 재귀 곱셈 자체보다 butterfly 계산량을 줄이는 데 초점을 둡니다.

여러 butterfly 계산을 묶는 증폭

Harvey는 2×2 butterfly 행렬 A를 m차 텐서곱 A⊗m으로 확장해 설명합니다. 기존 방식은 m개 방향에 각각 연산해 비용을 냅니다. 어떤 구조화된 프로그램이 이를 g회 호출로 계산하고 g<m이라면, 그 프로그램을 큰 텐서곱에 반복 대입해 절약을 재귀적으로 증폭할 수 있습니다. n=m^k일 때 호출량 비율은 (g/m)^k가 되고, 결과적으로 입력 크기 N에 대해 N(log N)^α 꼴의 비용이 나옵니다. 여기서 α=log(g)/log(m)<1입니다.

하지만 단일 배열에 대해 g<m인 프로그램을 찾은 것은 아닙니다. 대신 W개의 독립 배열을 함께 처리할 때 slice call 수를 줄이는 gadget을 구성하는 구상입니다. 저자는 이를 복수의 행렬-벡터 곱을 묶으면 행렬 곱셈으로 처리할 수 있다는 사례와 비교합니다. gadget은 배열을 레지스터로 두고, 각 레지스터에 적용된 부분 변환을 부분공간으로 추적합니다. butterfly와 동등한 행렬 C를 Hadamard 기저에서 보면 여러 방향 연산이 대각화되고, 직교 부분공간에서는 가중치 mod 4가 더해집니다. 이에 따라 부분공간을 한 차원씩 늘리거나 줄이는 연산을 slice call로 구현합니다.

작은 gadget의 구성

h≥8일 때 크기 3 부분집합 T마다 데이터 레지스터 xT와 yT를 두고, 교집합 크기가 0 또는 2인 쌍 (S,T)에 보조 레지스터 AS,T를 둡니다. 중앙 레지스터 ci와 c*도 사용합니다. 변환 단계 사이에 같은 부분공간을 가진 레지스터끼리 선형 결합을 하며, 보조 레지스터와 중앙 레지스터의 값을 잠시 섞었다가 되돌립니다. 이 과정에서 데이터 값은 원하는 형태로 바뀌고, 일부 레지스터는 전체 변환을 수행합니다. slice call 총수는 Wh−2|T|+2(h²+h)로 정리됩니다. 예상 비용 Wh에서 절약되는 항 2|T|가 손실 항 2(h²+h)보다 커지면 기본 방식보다 호출 수가 적습니다. 하위 절에서는 이 구상을 h³차원으로 확장하는 본 프로그램의 레지스터 구성과 부분공간 기초를 제시하지만, 제공된 본문은 실제 실행 단계 설명에 들어가는 지점에서 끝납니다.

결과의 범위와 검증

저자는 주장된 결과가 맞더라도 정수 곱셈의 이론적 복잡도 개선이지, 현실의 크기에서 CPU 정수 곱셈보다 빨라진다는 뜻은 아니라고 설명합니다. 고정 유한체 위의 다항식 곱셈으로 결과가 바로 이어지지도 않는다고 적습니다. 본문 작성 시점에는 Lean 형식화 증명이 없다고 했으며, 그런 형식화가 생기면 신뢰가 크게 높아질 것이라고 말합니다.

Hacker News 반응

@flebron — 제목에서 중요한 것은 O(n log n)이 아니라 o(n log n)입니다. 전자는 FFT로 이미 알고 있었습니다.
- @onionisafruit — 잘 모르는 사람을 위해 O와 o의 차이는 무엇인가요?
- @npinsker — O(n)은 충분히 큰 n에서 어떤 상수 K에 대해 f(n)≤Kn이라는 뜻입니다. o(n)은 모든 K에 대해 충분히 큰 n에서 f(n)≤Kn이라는 뜻입니다.
@jdb1729 — prime-order 유한체의 DFT에서 같은 개선을 Lean으로 증명했습니다. 정수 곱셈 상계의 Lean 형식화도 @platypii와 함께 완료했으며 지수 개선을 계속하고 있습니다.
@Kapura — 논문을 읽지 않은 저자가 AI 설명을 믿고 타당하다고 말하는 상황은 건강해 보이지 않습니다.
- @jrflo — 해당 분야 수학자들이 논문을 이해하지 못하고 도구가 이해한다면 왜 도구를 쓰면 안 되나요?
- @20k — 도구는 상당한 비율로 틀리고 복잡도 한계도 있습니다. AI가 쓴 논문을 AI로 검증하는 방식은 좋지 않습니다.
- @krackers — AI가 사람의 논문 이해를 도왔다는 점에서, 설명을 시도해도 모두 환각인 상황보다는 낫습니다. 사람이 집중해서 몇 달 공부하면 증명을 이해할 장애물이 뚜렷해 보이지는 않습니다.
@Eji1700 — 컴퓨팅을 바꿀 실용적 돌파구인가요? 제한된 이해로는 이론 결과라 당장 실용적인 변화는 아닌 것 같습니다.
- @atzeus — 이론 결과입니다. 저자가 인용한 농담처럼 실제 정수 곱셈보다 논문에 복잡도 표기를 쓰기 편해지는 쪽이 실용적일 수 있습니다.
@DannyBee — slice call 한 번은 비영 원소 수를 최대 두 배로만 늘릴 수 있으므로, 순열만 허용하는 초기 모델에서 m번보다 적게 호출할 수 없다는 간단한 논증이 있어 보입니다.
@MiroslavPokorny — 저자가 논문을 읽지 않았다는 대목이 걸립니다.
- @krackers — 기존 FFT와 정수 곱셈의 비트 비용부터 시작해 설명하면, 여러 butterfly 층을 함께 계산해 재귀 단계마다 아주 작은 절약을 누적하는 발상이라고 이해했습니다.

원문: David Harvey의 UNSW 웹사이트 PDF / 번역·요약: Trawling

원문 보기 ↗토론 보기 ↗