고속 푸리에 변환(FFT)은 디지털 신호처리의 근간을 이루는 알고리즘이다. 신호에 담긴 주파수 성분을 뽑아내 분석·필터링·변조하는 작업의 토대가 되기 때문이다. 원래 푸리에 변환은 길이 n짜리 입력에 대해 각 주파수마다 내적(dot product)을 계산하는데, 모든 주파수 성분을 파악하려면 2𝜋/n의 배수가 되는 n개 주파수에서 내적을 구해야 한다. 각 내적이 n번의 곱셈과 덧셈을 요구하므로, 전체 변환은 겉보기에 n² 수준의 연산이 필요하다.
1965년 제임스 쿨리와 존 튜키가 고안한 FFT는 이 비용을 극적으로 낮췄다. 길이 n의 변환을 입력을 재배열해 길이 n/2짜리 변환 두 개로 쪼개고, 그 결과를 선형 개수의 연산으로 다시 합치는 재귀 구조다. 이 과정을 log₂(n)번 반복하면 전체 이산 푸리에 변환이 5·n·log₂(n) 미만의 연산으로 끝난다. n이 1,000일 때 n²은 100만, 5·n·log n은 약 5만으로 20배 빨라지고, n이 100만이면 1만 배까지 벌어진다. 이 차이는 신호처리 응용에서 변환이 '계산 가능한가 불가능한가'를 가르는 분기점이 되곤 한다.
'galactic 알고리즘'이라는 함정
FFT는 입력을 적는 데만 n단계가 드는 이론적 하한에 비해 약 5·log₂(n)배 느리다. n이 1조면 이 계수는 200에 달한다. 그렇다면 이 200이라는 앞자리 상수를 줄일 수 있을까. 원문 저자는 지난주 OpenAI가 수학계에 쏟아낸 대규모 논문 더미 중 'main.pdf'가 바로 이 log(n) 항을 아주 미세하게 줄인 '더 빠른 FFT'를 주장한다고 전한다. 저자는 논문을 직접 읽는 대신, 역설적이게도 챗봇에 그 결과물을 다시 넣어 핵심 사실을 추출하는 방식으로 분석했다고 밝힌다.
결론은 냉정하다. 이 알고리즘은 이른바 'galactic 알고리즘'이다. 리처드 립턴과 켄 리건이 붙인 이 이름은, big-O 표기 안에 터무니없이 큰 상수가 숨어 있어 현실에서는 결코 빠르지 않은 알고리즘을 가리킨다. big-O는 본래 'n이 충분히 클 때' 어떤 상수 C에 대해 연산 횟수가 C·F(n) 이하라는 점근적 성장률만을 다루는 표기다. 문제는 그 C가 50일 수도, 10의 80제곱일 수도 있다는 점이다. 10의 80제곱은 알려진 우주의 원자 수에 해당한다.
상수 안에 숨은 비현실성
OpenAI의 FFT는 N=10¹²에서 추정 상수 C가 10의 100제곱 수준이었다고 한다. 즉 n이 10의 100제곱일 때조차 전통적인 쿨리-튜키(그리고 가우스로 거슬러 올라가는) FFT가 10의 99제곱 배 더 빠르다. 점근적으로는 분명 더 빠르다고 말할 수 있지만, 실제로 더 빨라지려면 n이 상상할 수 없을 만큼 커야 한다는 뜻이다.
더 근본적인 문제는 이 알고리즘이 가정하는 계산 모델이 실제 컴퓨터와 아무 관련이 없다는 데 있다. 논문은 '정확한 복소수 산술'을 전제한다. 임의 정밀도로 복소수를 저장하고 곱할 수 있다고 가정하는 것이다. 그런데 이 알고리즘은 크기가 n에 대해 초다항적으로 커지는 복소수들을 곱해야 한다. 이를 비트로 저장하면 메모리 요구량은 사실상 입력 길이에 대해 지수적으로 폭발하며, 그런 거대한 복소수를 한 번의 연산으로 곱하는 컴퓨터는 존재하지 않는다. 설령 정리가 '참'이라 해도, 우리가 처음에 풀려던 문제를 푸는 것이 아니다.
이런 결과가 새삼스럽지 않은 이유는 이미 1973년 자크 모르겐슈테른이 복소 계수의 크기를 제한하면 ½·n·log n보다 빠른 변환이 불가능함을 증명했기 때문이다. 40년 뒤 니르 아일론은 심각한 수치적 불안정 없이는 n·log n보다 빠를 수 없음을 보였다. FFT의 속도 한계를 깨려면 비현실적인 계산 모델이 필요하다는 사실은 이론적으로 꽤 오래전에 정리된 셈이다. 저자는 OpenAI 논문 더미의 다른 '성과'들, 예컨대 두 행렬을 O(n^2.25)에 곱한다는 알고리즘 역시 숨은 상수를 추정조차 할 수 없어 같은 비판을 받는다고 지적한다.
한국 실무자에게 주는 함의
이 사례가 던지는 메시지는 분명하다. 점근 표기만 보고 '더 빠르다'는 주장을 받아들여선 안 된다는 것이다. big-O의 우위는 입력 규모가 현실 범위에 들어올 때에야 의미가 있고, 숨은 상수와 전제된 계산 모델을 확인하지 않으면 '이론상 빠름'과 '실제로 빠름'을 혼동하게 된다. 저자는 이론 전산학이 실제 컴퓨터에서 알고리즘을 돌려보는 일을 오히려 등한시하는 문화를 지적하며, AI가 이런 바람직하지 않은 관행을 자동화·증폭하고 있다고 본다. 성능 벤치마크를 검토하거나 외부 연구를 도입하려는 실무자라면, 화려한 복잡도 표기 뒤에 가려진 상수항·정밀도 가정·메모리 비용을 먼저 들여다보는 습관이 어느 때보다 중요해졌다.