int128_t 64 bit에서 표현을 못하는 정수형 데이터 처리 방식

int128_t 64 bit에서 표현을 못하는 정수형 데이터 처리 방식

C언어에서 int64_t로 표현할 수 없는 엄청 큰 정수를 다루기 위해서는 아래와 같은 방법을 사용할 수 있습니다.

1. 다중 정밀도 정수 라이브러리 사용 (Multiple Precision Arithmetic Library)
   • C언어에서 기본적으로 제공하는 정수 타입으로는 큰 정수를 표현하기 어렵기 때문에, 외부 라이브러리인 GMP (GNU Multiple Precision Arithmetic Library)와 같은 다중 정밀도 수학 라이브러리를 사용하는 것이 좋습니다.
   • GMP는 매우 큰 정수, 유리수, 부동 소수점 수를 효율적으로 다룰 수 있는 기능을 제공합니다.
   • 이 라이브러리를 사용하면 임의의 정밀도로 큰 정수를 계산하고 저장할 수 있습니다.
   • mpz_t 타입을 사용하여 매우 큰 정수를 저장하고, 연산을 수행할 수 있습니다.

#include <gmp.h>

int main() {
    mpz_t big_number;
    mpz_init(big_number);
    mpz_set_str(big_number, "1234567890123456789012345678901234567890", 10);

    gmp_printf("Big number: %Zd\\n", big_number);

    mpz_clear(big_number);
    return 0;
}

1. 큰 정수를 문자열로 다루기 (String Representation)
   • 정수를 문자열로 저장하고, 필요한 경우 문자열 기반으로 연산을 수행하는 방법입니다.
   • 기본적으로 덧셈, 곱셈 등 연산을 직접 구현해야 하므로 비효율적이지만, 임의 정밀도를 지원할 수 있습니다.
   • 예를 들어 두 문자열로 표현된 큰 수를 더하려면 직접 자리수 덧셈 알고리즘을 작성해야 합니다.
2. 구조체를 이용한 큰 정수 표현 (Custom Data Structure)
   • 큰 정수를 여러 개의 작은 정수로 나누어 구조체로 표현하는 방법입니다. 예를 들어, 128비트 정수를 두 개의 64비트 정수로 나누어 구조체에 저장하고, 연산을 할 때는 각각의 64비트 정수에 대해 자리 올림을 고려하여 계산할 수 있습니다.

typedef struct {
    uint64_t low;
    uint64_t high;
} uint128_t;

• 이렇게 정의된 구조체를 사용해 큰 정수의 덧셈, 곱셈 등을 구현할 수 있습니다. 이 경우 자리 올림과 같은 처리를 직접 구현해야 합니다.

여기서 구조체를 통해 곱셈과 덧셈을 자세히 확인해보겠습니다.

#include <stdio.h>
#include <stdint.h>

typedef struct {
    uint64_t low;
    uint64_t high;
} uint128_t;

// 덧셈 함수
uint128_t add_uint128(uint128_t a, uint128_t b) {
    uint128_t result;
    
    // low 부분의 덧셈과 자리 올림 계산
    result.low = a.low + b.low;
    uint64_t carry = (result.low < a.low) ? 1 : 0;
    
    // high 부분의 덧셈과 자리 올림 반영
    result.high = a.high + b.high + carry;
    
    return result;
}

// 곱셈 함수
uint128_t multiply_uint128(uint128_t a, uint128_t b) {
    uint128_t result = {0, 0};

    // low * low -> result.low에 저장
    uint64_t a_low = a.low & 0xFFFFFFFF; // 하위 32비트를 추출
    uint64_t a_high = a.low >> 32; // 오른쪽으로 32비트 시프트하여 상위 32비트 추출
    uint64_t b_low = b.low & 0xFFFFFFFF;
    uint64_t b_high = b.low >> 32;

    uint64_t low_low = a_low * b_low;
    uint64_t low_high = a_low * b_high;
    uint64_t high_low = a_high * b_low;
    uint64_t high_high = a_high * b_high;
    
    /*
     * 위의 계산 방식 12 * 34를 예로 들면 십의 자리수와 일의 자리수로 나누어 각각 계산
     * a_low = 2, b_low = 4, a_high = 1, b_high = 3
     * low_low = 2 * 4 = 8
     * low_high = 2 * 30 = 60
     * high_low = 10 * 4 = 40
     * heigh_heigh = 30 * 10 = 300
     * 전체 더하면 최종 값이 408
     * result.low => 8
     * result.heigh => 34
    */

    // 결과 조합
    result.low = low_low + (low_high << 32) + (high_low << 32);
    result.high = high_high + (low_high >> 32) + (high_low >> 32);

    return result;
}

// 결과 출력 함수
void print_uint128(uint128_t num) {
    printf("High: %llu, Low: %llu\\n", num.high, num.low);
}

int main() {
    uint128_t num1 = {0xFFFFFFFFFFFFFFFF, 0x0000000000000001};
    uint128_t num2 = {0x0000000000000001, 0x0000000000000000};

    // 덧셈 결과
    uint128_t sum = add_uint128(num1, num2);
    printf("덧셈 결과:\\n");
    print_uint128(sum);

    // 곱셈 결과
    uint128_t product = multiply_uint128(num1, num2);
    printf("곱셈 결과:\\n");
    print_uint128(product);

    return 0;
}

위 코드에서는 uint128_t 구조체를 사용하여 두 개의 128비트 정수의 덧셈과 곱셈을 수행하는 함수를 구현하였습니다.

• 덧셈 함수 (add_uint128):
  • low 부분을 먼저 더하고, 자리 올림이 발생하면 carry 값을 high 부분의 덧셈에 반영합니다.
• 곱셈 함수 (multiply_uint128):
  • 64비트 곱셈을 다루기 위해 low와 high 부분을 나누어 계산합니다.
  • 간단히 low와 high 부분을 조합하여 최종 결과를 얻습니다.

32비트로 절반씩 나누어 계산을 진행한 이유는 다음과 같습니다:

1. 단순화된 계산 처리: 64비트 값끼리 직접 곱하면 결과는 128비트가 되어야 하지만, C 언어에서는 기본적으로 128비트 정수를 다룰 수 있는 데이터 타입이 없기 때문에 계산이 복잡해집니다. 이를 해결하기 위해 64비트를 32비트씩 나누어 처리하면 각 부분에 대해 더 쉽게 관리할 수 있습니다.
2. 자리 올림과 정밀도 관리: 64비트 정수 곱셈의 결과는 최대 128비트가 될 수 있으므로, a.low와 b.low를 각각 상위 32비트와 하위 32비트로 나누어 처리하면 자리 올림을 보다 명확히 계산하고, 필요한 위치에 더할 수 있습니다. 이는 곱셈 연산의 결과를 두 부분으로 나누어 저장하고 올바르게 조합하는 데 유리합니다.
3. 메모리 관리와 효율성: 64비트 전체를 곱하는 대신 32비트 단위로 곱하면, 계산 결과를 더 작은 단위로 나눠서 부분적으로 관리하고 처리할 수 있어 메모리 사용 측면에서 더 효율적입니다.

이와 같은 방법으로 연산을 나눔으로써 결과를 두 부분(low와 high)으로 구분하여 조합할 수 있으며, 각각의 계산에서 발생하는 자리 올림을 반영하여 정확한 결과를 얻을 수 있습니다.

이 코드에서는 간단한 덧셈과 곱셈의 구현을 보여주었으며, 실제 큰 정수의 연산을 다룰 때는 더 많은 자리수 및 최적화가 필요할 수 있습니다.

128비트로 표현할 수 있는 정수의 범위는 다음과 같습니다:

• 부호 없는 128비트 정수 (uint128_t):
  • 최소값: 0
  • 최대값: 2^128 - 1, 즉 340,282,366,920,938,463,463,374,607,431,768,211,455입니다.
• 부호 있는 128비트 정수 (int128_t 가정):
  • 최소값: 2^127
  • 최대값: 2^127 - 1, 즉 170,141,183,460,469,231,731,687,303,715,884,105,727입니다.

128비트 정수는 매우 큰 수의 범위를 표현할 수 있어 암호학, 매우 큰 숫자의 계산, 과학적 계산 등에 유용합니다.

경을 훨씬 넘는 크기

• 해: 10^20
• 자: 10^24
• 양: 10^28
• 구: 10^32
• 간: 10^36
• 정: 10^40

부호가 없는 128 정수의 경우 3.4 * 10^38 정도 이므로 간 단위가 넘는 구간입니다.

이와 같은 방법을 통해 int64_t로 표현할 수 없는 큰 정수를 처리할 수 있습니다. 가장 일반적인 접근 방식은 GMP와 같은 외부 라이브러리를 사용하는 것이며, 이는 성능과 편의성 면에서 가장 뛰어납니다.