엄청나게 빠름(Blazingly Fast)의 진정한 의미

이 영상은 프로그래밍 미디어에서 흔히 쓰이는 엄청나게 빠름(Blazingly Fast) 이라는 표현의 실체를 탐구하며, 대규모 피보나치 수를 1초 안에 계산하는 도전을 통해 성능 최적화의 단계를 보여줍니다. 단순한 마케팅 용어를 넘어 수학적 원리인 고속 푸리에 변환(FFT) 과 넘버 테오레틱 트랜스폼(NTT) 을 프로그래밍에 적용하여 파이썬의 성능을 압도하고 하드웨어의 한계를 돌파하는 과정을 상세히 기록합니다.

1. 하드웨어 환경과 파이썬의 성능 한계

• 장비의 하향 평준화: 기존 메인 PC 대신 형의 오래된 PC를 활용해 우분투 서버를 구축하여 테스트 환경을 구성했습니다.
• 파이썬의 선전: 파이썬은 대형 정수 계산 시 점근적으로 빠른 카라추바 곱셈 알고리즘을 사용하므로, 초보적인 정수 곱셈 방식을 쓰는 C 언어 코드보다 때때로 더 나은 성능을 보여주기도 합니다.
• 목표 설정: 단순히 파이썬을 이기는 것이 아니라, 이론적으로 가장 효율적인 곱셈 알고리즘을 구현하여 성능의 격차를 벌리는 것이 목표입니다.

2. 고속 푸리에 변환과 복소수의 한계

• 곱셈의 변환: 큰 정수의 곱셈은 다항식의 곱셈과 같으며, 이를 주파수 영역으로 변환하여 요소별 곱셈을 수행한 뒤 다시 역변환하는 것이 훨씬 빠릅니다.
• 복소수 구현의 문제: 기존에 구현한 복소수 기반 고속 푸리에 변환은 정밀도의 한계로 인해 약 600만 번째 피보나치 수 이상을 계산할 때 오차 발생 위험이 있었습니다.
• 대안의 필요성: 무한 정밀도 부동 소수점을 사용하는 대신, 정수론적 접근을 통해 오차 없는 계산 방식을 모색합니다.

3. 넘버 테오레틱 트랜스폼: 오차 없는 정수 변환

• 정수 고리에서의 변환: 복소수 대신 특정 소수(P)에 대한 ** 나머지 연산 고리** 위에서 계산을 수행합니다. 이를 통해 부동 소수점 오차를 완전히 제거합니다.
• 단위근의 선택: 복소수 평면이 아닌 정수 고리 위에서도 단위근이 존재하며, 이를 활용해 동일한 분할 정복 방식의 변환을 적용할 수 있습니다.
• 적용된 수치: 약 1.5경에 달하는 거대한 소수를 선택하고, 이에 대응하는 원시 단위근을 사용하여 변환을 수행합니다.

4. 성능 극대화를 위한 로우 레벨 최적화

• 나눗셈 최적화: 128비트 정수의 나머지 연산(나눗셈)은 매우 비싼 작업입니다. 컴파일러가 최적화하지 못하는 부분에 대해 ** 역수 곱셈과 비트 시프트** 기법을 직접 적용했습니다.
• 매직 콘스탄트: 나눗셈을 곱셈으로 대체하기 위한 상수를 산출하여 어셈블리 수준의 성능 향상을 이끌어냈습니다. 이 최적화만으로 400만 번째 피보나치 수 계산 속도가 1.5초에서 비약적으로 단축되었습니다.
• 메모리 패딩: 변환 효율을 높이기 위해 피보나치 수의 자릿수를 2의 거듭제곱 형태로 채워 넣어 분할 정복의 이점을 극대화했습니다.

5. 멀티스레딩과 최종 성능 측정

• 병렬 처리: 단일 스레드 작업에서 벗어나 CPU의 여러 코어를 활용하는 멀티스레딩 기법을 적용했습니다.
• 결과 수치:
  • 4,800만 번째 피보나치 수를 1초 이내에 계산하는 데 성공했습니다.
  • 이 숫자는 약 4MB 크기이며, 1,000만 자 이상의 10진수 자릿수를 가집니다.
  • 동일한 계산에 대해 파이썬은 약 27초가 소요되어 압도적인 성능 차이를 증명했습니다.

6. 결론: 진정한 속도에 대한 성찰

• 하이브리드 개발: 빌드 타임에 복잡한 상수(원시 단위근의 거듭제곱 등)를 미리 계산하기 위해 ** 파이썬으로 헤더 파일을 자동 생성**하고, 실제 계산은 C로 수행하는 효율적인 방식을 택했습니다.
• 알고리즘의 승리: 성능의 핵심은 단순히 사용하는 언어의 종류가 아니라, 문제의 본질을 파고드는 수학적 알고리즘(NTT)과 이를 하드웨어에 맞춰 최적화하는 구현 능력에 있음을 보여줍니다.