Harvey, 공개된 o(n log n) 정수 곱셈 알고리즘 주장이 그럴듯하다고 평가
- 데이비드 하비(David Harvey)는 o(n log n) 정수 곱셈 알고리즘의 주장이 그럴듯하다고 평가함, 다만 세부 내용은 대부분 검증하지 않았다고 밝힘
- 주장된 복잡도는 O(n(log n)^(1-ε)) 형태이고 ε는 2^-182 수준이라 이전 최고 기록인 O(n log n)보다 아주 조금 빠름
- 새 결과는 하비와 판 데어 회벤(van der Hoeven)이 2021년 낸 O(n log n) 알고리즘 위에 직접 쌓인 것임
- 저자는 이 개선 폭이 2007년 퓌러(Fürer)의 개선보다 지수적으로 크다고 설명함, 퓌러의 개선은 log log n보다 작았음
- 해당 논문은 미국 기업이 GitHub에 공개한 수학 논문 묶음 중 TC26a로 표기된 것임
Hacker News opinions
제목은 O(n log n)인데 진짜 중요한 건 소문자 o임. FFT로 O(n log n) 곱셈은 이미 알고 있었음.
O랑 o 차이 모르는 사람 있어서 말하면, O는 k(n log n) 이하로 자라는 거고 o는 어떤 k를 잡아도 그보다 확실히 느리게 자라는 거임.
다항식 곱셈 쪽은 원 논문 결과가 바로 안 이어진다고 적혀 있음. 그래도 나랑 platypii는 F2[x]는 빼고 소수 위수 유한체 DFT 개선을 Lean으로 증명해봤음.
글 문체 진짜 좋더라. 동료들 얘기하는 부분도 솔직하고 깔끔하게 정리돼 있음.
좋긴 한데 회사 욕하는 사람들을 '중요한 건 그게 아니다'로 넘기는 건 좀 쉬운 태도 아님? 결국 월급 주는 쪽이잖아.
나도 3쪽 넘어가면서부터 못 따라가겠더라.
저자가 논문 안 읽고 AI한테 설명 듣고 맞다고 판단했다는 게 좀 찝찝함. 근데 수학은 그래도 Lean이라도 있으니까 에이전트 코드보다는 낫다고 봄.
증명이 Lean으로 검증되면 사람이 다 이해 못 해도 되는 거 아님? 기계가 맞다고 확인해주는 게 핵심이지.