Boost 다중 정밀도 라이브러리로 큰 수의 팩토리얼(계승) 계산하기

C++에서 매우 큰 수의 팩토리얼(계승)을 구하려면 일반적인 정수형으로는 부족합니다. 64비트 정수(long long)조차 21! 이상의 값은 담지 못하고 오버플로가 발생합니다. 이럴 때 Boost 라이브러리의 다중 정밀도(multiprecision) 기능을 활용하면 64비트 한계를 넘어서는 임의 정밀도 정수를 손쉽게 다룰 수 있습니다.

cpp_int란?

boost::multiprecision::cpp_int는 값의 크기에 따라 자동으로 확장되는 임의 정밀도 정수 타입입니다. 별도의 자릿수 제한 없이 메모리가 허용하는 범위까지 정수 연산이 가능하기 때문에, 100!처럼 자릿수가 매우 많은 팩토리얼 계산에 특히 적합합니다.

예제 코드

#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using boost::multiprecision::cpp_int;
using namespace std;

cpp_int Large_Fact(int number) {
    cpp_int fact = 1;
    for (int i = 1; i <= number; i++)
        fact *= i;
    return fact;
}

int main() {
    int number = 100;
    cpp_int fact = Large_Fact(number);
    cout << fact << endl;
}

실행 결과

9332621544394415268169923885626670049071596826438162146859296389521759999322
9915608941463976156518286253697920827223758251185210916864000000000000000000
000000

코드 설명

먼저 <boost/multiprecision/cpp_int.hpp> 헤더를 포함하여 다중 정밀도 정수 기능을 사용할 수 있도록 준비합니다. Large_Fact 함수는 결과값을 저장할 변수 fact를 1로 초기화한 뒤, 1부터 입력받은 숫자까지 차례대로 곱해 나가며 팩토리얼을 계산합니다.

main 함수에서는 100을 인자로 전달해 100!을 구하고 그 결과를 출력합니다. 만약 이 계산을 int나 long long으로 처리했다면 오버플로로 인해 잘못된 값이 출력되었겠지만, cpp_int를 사용하면 위 실행 결과와 같이 158자리에 달하는 정확한 값을 얻을 수 있습니다.