BigInteger 구조체(큰 정수의 처리)

높은 정확도의 자료 처리를 위해 float, double과 같은 부동소수점 자료형과 decimal 자료형을 사용할 수 있다. 그런데 소수점 아래의 정확도가 아닌 큰 수의 정확한 처리는 어떨까. 자주 사용하는 정수형 int보다 더 큰 값은 long, 더 큰 값은 ulong, 그보다 더 큰 값은 어떻게 처리할까. 한 때는 오버플로우 되는 값을 미리 처리하기 위해 최대값의 절반 범위에서 넘어간 값을 다른 변수에 옮겨담아 자리올림 같은 개념으로 구현한 적이 있다.

 

A0 = 1,073,741,823 ( int.Maxvalue / 2 )일 때 A0 값이 1 증가하면 A1 = 1, A0 = 0 이 되는 식

 

이렇게 하면 물론 간단한 덧셈 뺄셈은 쉽게 구현 가능하지만 곱셈은? 나눗셈은? 답이 안나온다. 심지어 저런 식으로 하면 출력조차 어렵다. 출력할 때 어차피 큰 수의 원형을 뽑아내야하게 되는데 그게 또 답없다. 아무튼 큰 수의 곱셈을 하기 위한 카라추바 알고리즘이 있다. 그걸 이용하면 어떻게 연산까지는 하겠다. 근데 큰 수의 나눗셈은? 진짜 이제는 머리가 어질어질해진다.

하지만 C#은 큰 정수의 처리를 위한 BigInteger 구조체를 제공하고 있다. 다른 자료형처럼 사용 가능하며 연산 시간도 빠르다. BigInteger 자료형은 System.Numerics 를 참조한다. 혹시 네임스페이스를 못찾겠다는 에러가 발생하면 어셈블리>프레임워크에서 System.Numerics를 찾아 참조를 추가해주자.

using System;
using System.Numerics;

class Program
{
    static void Main()
    {
        BigInteger big = new BigInteger();
        big = 1;
        Console.WriteLine(big);
        big = ulong.MaxValue;
        Console.WriteLine(big);
        // big = ulong.MaxValue + 1;
        // ulong 최대값을 넘어간 값은 컴파일타임에 에러가 생긴다.
        // 이런 값은 문자열 형태로 Parse 메소드를 쓰거나
        // 연산을 통해 입력시켜줘야한다.
        big++;
        Console.WriteLine(big);
    }
}
// 결과
// 1
// 18,446,744,073,709,551,615
// 18,446,744,073,709,551,616

이걸 활용할 수 있는 문제를 풀어보자. 백준 10826번 피보나치 수 4 문제다.

10826번: 피보나치 수 4

최대 10000번째 피보나치 수를 구해야하는 문제다. 10000이라는 수치가 별거 없어보이지만 피보나치 수는 94번째에 ulong범위를 넘어가버리고 1000번째 피보나치 수는 200자리를 넘는다. 나머지를 구하는 문제도 아닌 수 자체를 구하는 이 문제는 여러 테크닉을 요구하는 것 같지만 BigInteger를 쓰면 아주 간단한 문제가 되어버린다.

using System;
using System.Numerics;
class Program
{
    static int n;
    static BigInteger[] f = new BigInteger[10001];
    static void Main()
    {
        n = int.Parse(Console.ReadLine());
        f[0] = 0; f[1] = 1;
        for(int i = 2; i <= n; i++)
            f[i] = f[i - 1] + f[i - 2];
        Console.WriteLine(f[n]);
    }
}

 

0번부터 10000번 피보나치 수를 저장할 BigInteger 형식 배열만 만들어주면 된다. 메모리를 조금 많이 먹긴 하지만 연산 시간은 압도적으로 빠르다. 그리고 Math 클래스를 사용하지 않고도 거듭제곱, 대소비교 등 다양한 메소드를 바로 사용할 수 있어서 편하다. 당연히 Math 클래스를 거치지 않으니 Parse를 해줄 필요도 없다. 이런거 생각해보면 Math 클래스의 메소드를 많이 사용하는 코드에서는 작은 수를 다루더라도 BigInteger를 쓰는게 나을지도 모르겠다.