OpenAI가 주장하는 더 빠른 푸리에 변환의 수학 살펴보기

OpenAI의 새 FFT 결과에 대한 핵심 비판은 점근적 속도 개선이 실제 컴퓨터에서 더 빠른 계산을 뜻하지 않는다는 것임 빅오 표기법에 숨은 상수가 너무 커서, 이론적 개선이 있더라도 기존 FFT보다 빨라지려면 현실적으로 불가능한 크기의 입력이 필요하다는 비판을 받음 계산 모델은 임의 정밀도의 복소수를 저장하고 곱할 수 있으며, 매우 큰 복소수의 곱셈도 단일 연산으로 처리한다고 가정함 기존 연구는 계수 크기 제한이나 수치 안정성 조건 아래에서 FFT의 속도 한계를 밝혔으며, 이번 결과가 실제 계산 문제를 해결했는지는 이런 제약과 함께 살펴야 함 비판의 초점은 정리의 참/거짓보다 이론과 실제 컴퓨터의 괴리에 있으며, AI가 실행이나 실용적 효과를 요구하지 않는 연구 관행을 증폭할 수 있음 FFT가 줄여 온 계산량 고속 푸리에 변환(FFT) 은 신호의 주파수 성분을 빠르게 추출해 주파수 대역별 분석, 필터링, 조작을 가능하게 하는 알고리듬임 길이 n의 디지털 신호는 2π/n의 정수배에 해당하는 주파수에서 내적 n개를 계산해 전체 주파수 성분을 파악할 수 있음 각 내적에 n번 규모의 곱셈과 덧셈이 필요하므로, 단순한 구현에는 전체적으로 n² 규모의 산술 연산이 필요함 이 내적 계산은 오늘날의 코사인 유사도에 빗댈 수 있음 Cooley-Tukey FFT는 입력을 재배열하고 길이 n/2의 푸리에 변환 두 개를 계산한 뒤 결과를 합치는 재귀적 절차를 사용함 재배열과 결합에는 선형 개수의 연산이 들며, 이를 log₂(n)단계 반복하면 전체 변환을 계산할 수 있음 총 산술 연산 수는 5n log₂(n) 미만임 James Cooley와 John Tukey가 1965년에 고안했으며, Wikipedia는 1805년 Gauss에게 공을 돌림 연산 수 감소는 실제 신호 처리에서 계산 가능 여부를 바꿀 만큼 큼 n=1,000이면 약 100만 회에서 5만 회로 줄어 약 20배 빨라짐 n=1,000,000이면 약 1만 배의 차이가 남 더 빠른 FFT라는 질문 출력 자체를 쓰는 데 n단계가 필요하므로, 적어도 n번의 연산은 필요해 보임 기존 FFT는 이 기준보다 5 log₂(n)배 느리며, n이 1조이면 이 배수는 약 200임 더 빠른 FFT 연구는 이 격차를 줄일 수 있는지 묻고 있음 OpenAI가 공개한 대규모 수학 자료의 main.pdf 는 기존 FFT보다 이론적으로 로그 항을 아주 조금 줄인 결과를 주장함 Ben Recht의 검토는...