팩토리얼은 얼마나 클까 — 계산기 없이 자릿수를 추정하는 수학

본문

저자 Eli Bendersky는 어느 날 문득 52!(52 팩토리얼)이 얼마나 큰 수인지 궁금해졌고, 계산기나 컴퓨터 없이 팩토리얼의 크기, 즉 자릿수를 합리적인 정확도로 추정하는 방법에 흥미로운 수학이 숨어 있음을 발견했다고 글을 시작합니다. 글은 먼저 추정 방법 자체를 제시하고, 궁금한 독자를 위해 수학적 배경을 뒤이어 풀어내는 구조입니다.

핵심 근사는 n!의 자릿수가 대략 n·log10(n/e)에 가깝다는 것입니다. 52!에 적용해 보면, 52를 e로 나누면 대략 20 정도이고 log10(20)은 약 1.3이므로, 추정치는 52 × 1.3 ≈ 68 근처가 됩니다. 실제 답은 68자리로 거의 정확합니다. 저자는 이런 천문학적 크기를 다루는 추정에서는 한두 자리 정도의 오차는 대개 문제가 되지 않는다고 덧붙입니다.

감마 함수: 팩토리얼의 실수 확장

배경 설명은 감마 함수에서 시작합니다. 실수 s에 대해 Γ(s)는 0부터 무한대까지 t^(s−1)e^(−t)를 적분한 값으로 정의됩니다(정확히는 복소수까지 정의되지만 이 글의 목적에는 실수만으로 충분하다고 합니다). 이 적분은 일반적인 해석적 표현이 없지만, 부분적분을 적용하면 Γ(s+1) = s·Γ(s)라는 유용한 점화식이 나옵니다. 또한 Γ(1)은 해석적으로 계산 가능한 특수 경우로 값이 1입니다. 이 둘을 결합하면 귀납법에 의해 양의 정수 n에 대해 Γ(n+1) = n!이 성립합니다. 즉 감마 함수는 팩토리얼을 모든 양의 실수로 보간한 함수라는 것입니다. 저자는 함수의 급격한 증가 때문에 y축을 로그 스케일로 둔 감마 함수 그래프도 함께 보여 줍니다.

라플라스 방법으로 유도하는 스털링 근사

다음으로 익숙한 스털링 근사 n! ≈ √(2πn)·(n/e)^n이 감마 함수에서 어떻게 유도되는지를 개관합니다. Γ(n+1)의 적분식에서 피적분함수를 t^n·e^(−t) = e^(n·ln t − t) 형태로 변형하고, t = n·u로 변수 치환을 하면 적분이 e^(n·f(u)) 꼴의 정적분이 됩니다. 이런 형태의 적분에는 라플라스 방법을 적용할 수 있는데, 이 방법은 f가 두 번 미분 가능하고 어떤 큰 수 n에 대해 적분이 f의 전역 최댓값 근처에서 지배된다는 사실을 이용해 근사값을 얻는 기법입니다. 이 경우 f(u) = ln u − u이고, 이 함수는 u = 1에서 전역 최댓값을 가지며 f(1) = −1, f''(1) = −1입니다. 이 값들을 라플라스 근사식에 대입하면 스털링 공식이 도출됩니다. 저자는 이 근사가 왜 성립하는지 깊이 파고드는 것은 이 글의 범위를 넘는다며 각주로 처리했습니다.

자릿수 계산과 잔여 보정항

자릿수는 스털링 공식에 밑이 10인 로그를 취해 구할 수 있습니다. 정리하면 자릿수 ≈ (n + 0.5)·log10(n) − n·log10(e) + 0.5·log10(2π)입니다. 첫 항의 0.5와 마지막 상수항은 n 자체에 곱해지지 않기 때문에 n이 커질수록 상대적으로 덜 눈에 띄지만, 그래도 한두 자리를 더해 주므로 더 정확한 추정을 원하면 고려해야 한다고 설명합니다. 각주에 따르면 이 보정은 n이 약 1600 미만일 때 최대 2자리, 160000까지는 3자리를 넘지 않는 수준입니다. 저자는 1600!(약 4450자리)이나 160000!의 자릿수를 추정하고 싶어 할 사람이 있을지 의문이라며 농담을 곁들입니다. 또 다른 각주에서는 log10(e) ≈ 0.43 같은 값을 기억해 두고 로그 법칙으로 배수를 추정하는 암산 요령도 언급합니다.

Hacker News 반응

• @brudgers — n > 24일 때 n!은 10^n보다 큽니다.
• @saalweachter — 24!은 대략 아보가드로 수(Avogadro's number)와 비슷합니다(약 3% 차이).
• @pagade — 이런 기억이 나네요: 교수님이 C 프로그래밍 언어로 계산 가능한 가장 큰 팩토리얼을 구하라고 하셨고, 그다음 LISP로 똑같이 하라고 하셨습니다. 우리가 얼마나 놀랐는지 상상해 보세요.
• @pkaye — Prime Swing Factorial이라는 알고리즘이 있는데, 소인수분해를 이용해 임의 정밀도 연산으로 큰 팩토리얼을 정확하게 계산할 수 있습니다. 수학 라이브러리가 얼마나 최적화됐는지에 따라 다르지만 10000000!도 1초 안에 계산됩니다. 일반적인 방법보다 아마 100배쯤 빠를 겁니다.
• @anthk — Lisp에서도 반복 알고리즘을 쓰면 1초 안에 처리할 수 있습니다. SBCL은 엄청나게 빠를 수 있고, 정수 연산에 맞춰 컴파일을 최적화하면 속도가 그 해법에 아주 가까워집니다.

원문: thegreenplace.net (via Hacker News) / 번역·요약: Trawling