C++에서 팩토리얼을 계산할 수 있는 최대 정수 값 구하기

문제 개요

팩토리얼(계승)은 해당 숫자까지의 모든 양의 정수를 곱한 값이므로, 입력 값이 조금만 커져도 결과가 기하급수적으로 증가합니다. 예를 들어 20!은 약 243경(2.43 × 10¹⁸)에 달합니다. 따라서 C++의 데이터 타입으로는 일정 크기 이상의 팩토리얼을 더 이상 저장할 수 없는데, 이번 글에서는 현재 사용 중인 머신에서 팩토리얼을 계산할 수 있는 최대 정수 값을 찾는 프로그램을 만들어 보겠습니다.

해결 접근 방식

부호 있는(signed) 정수 데이터 타입은 저장할 수 있는 최대값을 초과하면 오버플로우가 발생하여 음수가 되는 성질을 가지고 있습니다. 이 특성을 활용하면 반복문 안에서 팩토리얼 값이 음수로 바뀌는 시점을 감지하는 방식으로 간단히 한계를 찾을 수 있습니다.

C++에서 가장 큰 기본 데이터 타입인 long long int(64비트)를 사용해 구현해 보겠습니다.

예제 코드

#include <iostream>
using namespace std;
int calcMaxFactVal(){
    int maxVal = 1;
    long long int maxFactorial = 1;
    while (true){
        if (maxFactorial < 0)
            return (maxVal - 1);
        maxVal++;
        maxFactorial *= maxVal;
    }
    return -1;
}
int main(){
    cout<<"팩토리얼을 계산할 수 있는 최대 정수 값은 "<<calcMaxFactVal();
    return 0;
}

실행 결과

팩토리얼을 계산할 수 있는 최대 정수 값은 20

결과 분석

long long int가 표현할 수 있는 최대값은 9,223,372,036,854,775,807(약 9.22 × 10¹⁸)입니다. 실제 계산 결과를 비교해 보면 다음과 같습니다.

• 20! = 2,432,902,008,176,640,000 → 표현 가능 범위 내
• 21! = 51,090,942,171,709,440,000 → 최대값 초과로 오버플로우 발생

따라서 이 머신에서 팩토리얼을 정확하게 계산할 수 있는 최대 정수는 20입니다.

참고로, C++ 표준에서 부호 있는 정수의 오버플로우는 엄밀히 말해 미정의 동작(undefined behavior)입니다. 하지만 대부분의 컴파일러와 환경에서는 2의 보수 방식으로 값이 순환(wrap-around)되어 음수가 나타나므로, 위 코드는 실제 환경에서 의도한 대로 동작합니다. 더 안전한 방법을 원한다면 곱셈 전에 maxFactorial > LLONG_MAX / maxVal 조건으로 오버플로우 여부를 미리 검사하는 방식을 사용할 수 있습니다.