팩토리얼을 빠르게 계산하는 알고리즘들 — n!의 수학적 미학

팩토리얼, 그 단순해 보이는 문제

팩토리얼이라고 하면 다들 학교에서 배운 그거 떠올리실 거예요. n! = n × (n-1) × (n-2) × ... × 2 × 1. 5! = 120, 10! = 3,628,800. 코딩 입문서의 재귀 함수 예제 단골 손님이기도 하고요. 그런데 이게 "빠르게 계산하는 알고리즘"이라는 별도 연구 분야가 있다는 사실, 알고 계셨나요?

독일 수학자 Peter Luschny가 운영하는 사이트에는 팩토리얼을 빠르게 계산하는 알고리즘들이 수십 년간 정리돼 있습니다. 단순한 곱셈을 왜 굳이 빠르게 만들어야 하나 싶지만, n이 10만, 100만 단위로 커지면 이야기가 완전히 달라지거든요. 100,000!을 계산하면 결과가 약 45만 자리짜리 숫자가 됩니다. 이런 큰 수를 곱하는 건 더 이상 단순한 산수가 아니에요.

왜 단순 곱셈이 느릴까

순진하게 1부터 n까지 차례로 곱하면 어떻게 될까요? 처음에는 작은 수끼리 곱하니까 빠른데, 뒤로 갈수록 누적된 결과가 어마어마하게 커집니다. 큰 수의 곱셈은 자리수에 비례해서 시간이 더 걸리거든요. 결국 전체 연산 시간이 O(n² log n) 수준으로 늘어나요. n이 10배 커지면 시간은 100배 이상 늘어나는 거죠.

여기서 첫 번째 개선이 이진 분할(binary splitting)입니다. 아이디어는 단순해요. 1×2×3×...×100을 계산할 때 왼쪽부터 차례로 곱하지 말고, (1×2×...×50)과 (51×52×...×100)을 각각 따로 계산한 다음 마지막에 곱하는 거예요. 이걸 재귀적으로 적용하면, 비슷한 크기의 수끼리 곱하게 되면서 전체적으로 훨씬 효율적이 됩니다. 큰 수 곱셈에서는 "비슷한 크기끼리"가 중요하거든요.

더 빠른 알고리즘들

Luschny의 사이트가 진짜 흥미로운 건 여기서부터입니다. 단순 분할보다 더 빠른 알고리즘들이 줄줄이 등장하거든요.

소인수분해 기반(Prime Factorization) 방식이 대표적입니다. n!의 결과를 소수의 거듭제곱 형태로 미리 분해해두는 거예요. 예를 들어 10! = 2^8 × 3^4 × 5^2 × 7^1입니다. 어떤 소수 p가 n!에 몇 번 나타나는지는 르장드르 공식(Legendre's formula)으로 직접 계산할 수 있어요. ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + ... 이렇게요. 이렇게 모든 소수의 지수를 구한 다음, 거듭제곱을 효율적으로 계산해서 곱하면 됩니다.

또 다른 접근으로 Schönhage의 알고리즘과 그 변형들이 있습니다. 이들은 곱셈 자체를 빠르게 하기 위해 FFT(고속 푸리에 변환)나 NTT(수론적 변환)를 활용해요. FFT는 원래 신호 처리에서 쓰는 도구인데, "두 다항식의 곱셈"으로 큰 수 곱셈을 변환할 수 있다는 통찰 덕분에 정수론에서도 핵심 도구가 됐습니다. 이 기법들을 결합하면 100만!도 몇 초 안에 계산할 수 있어요.

이런 게 왜 중요한가

"근데 100만 팩토리얼을 누가 계산하나?"라는 의문이 들 수 있어요. 직접적인 용도보다는, 이게 더 큰 수학/암호학 연산의 빌딩 블록이라는 점이 핵심입니다.

예를 들어 이항계수(binomial coefficient) C(n, k)는 조합론과 확률론의 핵심인데, 정의상 팩토리얼로 표현됩니다. 큰 n에 대한 이항계수를 정확히 계산하려면 빠른 팩토리얼이 필수예요. 또 감마 함수(Gamma function)는 팩토리얼을 실수/복소수로 확장한 함수인데, 통계학과 물리학 전반에 쓰입니다. 임의 정밀도 산술 라이브러리(GMP, MPFR 같은)들은 이런 함수들을 빠르게 제공하기 위해 내부적으로 정교한 팩토리얼 알고리즘을 구현하고 있어요.

암호학에서는 RSA의 큰 수 연산, 영지식 증명의 다항식 연산 등에서 비슷한 "큰 정수의 빠른 곱셈" 문제가 끊임없이 등장합니다. 팩토리얼 알고리즘 연구에서 발전한 기법들이 그대로 쓰이는 경우가 많고요.

알고리즘 미학의 한 단면

이 주제가 매력적인 이유는, "단순해 보이는 문제도 깊이 파면 풍부한 수학이 나온다"는 걸 보여주기 때문입니다. 팩토리얼은 초등학생도 정의를 이해할 수 있지만, 이를 빠르게 계산하는 방법에는 정수론, 푸리에 분석, 재귀적 분할, 병렬화 등 컴퓨터과학의 여러 도구가 총동원돼요.

비슷한 사례로 곱셈 자체의 알고리즘 발전사도 흥미롭습니다. 학교에서 배운 자릿수별 곱셈이 O(n²)인데, Karatsuba가 O(n^1.585), Toom-Cook이 그보다 빠르고, Schönhage-Strassen이 O(n log n log log n), 그리고 2019년 Harvey-Hoeven이 마침내 이론적 하한선인 O(n log n)을 달성했어요. 곱셈 하나에 60년 넘는 연구사가 있는 거죠.

한국 개발자에게 주는 의미

실무에서 팩토리얼 알고리즘을 직접 구현할 일은 거의 없을 거예요. Python이라면 math.factorial을 쓰면 되고, 내부적으로 이미 최적화된 알고리즘이 돌아갑니다. 하지만 이런 주제를 한 번 들여다보는 게 가치 있는 이유는 "내가 매일 쓰는 라이브러리 안에 어떤 수학이 들어있는지"를 알게 되기 때문이에요.

특히 알고리즘 PS(Problem Solving)나 경시 대회를 준비하는 분, 암호학/블록체인 쪽 일을 하는 분, 과학 계산을 다루는 분이라면 이런 "큰 수 산술"의 기반 지식이 직접적인 무기가 됩니다. 분할 정복의 정수, FFT의 응용, 소인수분해의 활용 같은 개념들이 모두 한 자리에 모이는 좋은 학습 주제거든요.

마무리

팩토리얼은 단순함과 깊이가 공존하는 보기 드문 문제입니다. "n!"이라는 두 글자 뒤에 수십 년의 알고리즘 연구가 쌓여 있다는 사실은, 컴퓨터과학의 매력을 잘 보여주는 단면이라고 생각해요.

여러분이 평소 "당연하게" 쓰는 표준 라이브러리 함수 중에서, 사실 알고 보면 굉장히 정교한 알고리즘이 들어있는 게 있다면 어떤 게 있을까요? 한 번 시간 내서 내부 구현을 들여다본 적 있으세요?