[큰 수]자바와 파이썬 그리고 BigInteger

현업에서 파이썬 서비스를 jvm환경으로 이관하면서 파이썬에서 적용되던 코드를 이관하고 있었습니다. 이때 파이썬의 int는 무한한 길이의 숫자를 사용할 수 있어서 자바의 기본적인 long, double로는 처리가 안되는 문제를 발견했습니다. 이러한 이유에 대해서 분석한 내용을 기록합니다.

 

자바에서는 아래의 사진처럼 긴 정수는 컴파일이 되지 않는 현상이 있습니다. 하지만 파이썬에서는 어떻게 가능할까요?

파이썬이 무한한 길이의 정수가 가능한 이유

Arbitrary Precision(임의의 정확도)

• 파이썬의 int는 C 언어의 long 타입을 기반으로 구현되어있습니다. 
• 각 자리수를 배열에 담아서 처리하며 배열에 각 자릿수를 담을때는 2^30 진법으로 변환함으로써 수행합니다.
• ob_digit이라는 배열에 해당 값을 담습니다.

예시

123456789101112131415와 같이 자바에서 처리하지 못하는 변수를 파이썬에서는 아래와 같이 처리합니다.

(437976919∗2^30∗0)+(87719511∗2^30∗1)+107∗2^30∗2

ob_diti: [437976919 / 87719511 / 107]

 

정리

즉, 배열에 무수히 많은 숫자가 들어가고 각 자리수가 2^30을 담을 수 있으므로 무한한 숫자를 표현이 가능하다고 한것입니다.

c 정수 -> python 정수

SHIFT = 30  # 각 자릿수를 나타낼 비트 갯수
MASK = (2 ** SHIFT)
bignum = 18446744073709551615

def split_number(bignum):
    t = abs(bignum)

    num_list = []
    while t != 0:
        # 나머지를 얻는다
        small_int = t % MASK  # 좀 더 효율적인 비트 연산: (t & (MASK-1))
        num_list.append(small_int)

        # 나눗셈의 정수부를 얻는다 (나눗셈 내림)
        t = t // MASK  # 좀 더 효율적인 비트 연산: t >>= SHIFT

    return num_list

def restore_number(num_list):
    bignum = 0
    for i, n in enumerate(num_list):
        bignum += n * (2 ** (SHIFT * i))
    return bignum

num_list = split_number(bignum)
assert bignum == restore_number(num_list)

그렇다면 자바에서도 파이썬처럼 배열로 표현하면 가능하지 않을까 싶은 생각이 듭니다. 자바는 어떻게 처리가 될까요?

자바의 BigInteger

aribitrary-precision

역시 문서 첫페이지에 임의의 정밀도가 보입니다. 자바의 BigInteger또한 파이썬과 비슷하게 동작하며 숫자를 비트 기반 배열에 저장합니다. 자세한건 코드를 보면서 확인해보겠습니다.

BigInteger 생성자는 여러 개의 부생성자들을 가지고 있습니다. 대표적으로 2개의 생성자를 살펴보겠습니다.

첫 번째는 BigInteger.valueOf()를 호출할때 내부에서 사용되는 생성자입니다.

long값을 받기에 최대 배열2개만을 이용하는 것을 알 수 있습니다.

private BigInteger(long val) {
    if (val < 0) {  // 부호 결정 
        val = -val;
        signum = -1;
    } else {
        signum = 1;
    }

    int highWord = (int)(val >>> 32); ----(1)
    if (highWord == 0) { -----------------(2)
        mag = new int[1];
        mag[0] = (int)val;
    } else {------------------------------(3)
        mag = new int[2];
        mag[0] = highWord;
        mag[1] = (int)val;
    }
}

(1) 상위 32비트를 추출하여 highWord에 저장합니다.

(2) 상위 32비트가 0인 경우

• long 값이 32비트 이하라는 뜻이므로, 크기 1의 배열을 생성합니다.
• 배열의 첫 번째 요소에 val의 하위 32비트를 저장합니다.

(3) 상위 32비트가 0이 아닌 경우

• long 값이 32비트를 초과하므로, 크기 2의 배열을 생성합니다.
• 배열의 첫 번째 요소에 highWord(상위 32비트)를 저장합니다.
• 배열의 두 번째 요소에 val의 하위 32비트를 저장합니다.

두 번째는 public 생성자를 통해 무수히 큰 수를 처리하는 방식입니다. 

radix는 디폴트값이 10입니다.(10진법을 의미)

/**
 * Translates the String representation of a BigInteger in the
 * specified radix into a BigInteger.  The String representation
 * consists of an optional minus or plus sign followed by a
 * sequence of one or more digits in the specified radix.  The
 * character-to-digit mapping is provided by {@link
 * Character#digit(char, int) Character.digit}.  The String may
 * not contain any extraneous characters (whitespace, for
 * example).
 *
 * @param val String representation of BigInteger.
 * @param radix radix to be used in interpreting {@code val}.
 * @throws NumberFormatException {@code val} is not a valid representation
 *         of a BigInteger in the specified radix, or {@code radix} is
 *         outside the range from {@link Character#MIN_RADIX} to
 *         {@link Character#MAX_RADIX}, inclusive.
 */
public BigInteger(String val, int radix) {
    int cursor = 0, numDigits;
    final int len = val.length();

    if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
        throw new NumberFormatException("Radix out of range");
    if (len == 0)
        throw new NumberFormatException("Zero length BigInteger");

    // Check for at most one leading sign
    int sign = 1;
    int index1 = val.lastIndexOf('-');
    int index2 = val.lastIndexOf('+');
    if (index1 >= 0) {
        if (index1 != 0 || index2 >= 0) {
            throw new NumberFormatException("Illegal embedded sign character");
        }
        sign = -1;
        cursor = 1;
    } else if (index2 >= 0) {
        if (index2 != 0) {
            throw new NumberFormatException("Illegal embedded sign character");
        }
        cursor = 1;
    }
    if (cursor == len)
        throw new NumberFormatException("Zero length BigInteger");

    // Skip leading zeros and compute number of digits in magnitude
    while (cursor < len &&
           Character.digit(val.charAt(cursor), radix) == 0) {
        cursor++;
    }

    if (cursor == len) {
        signum = 0;
        mag = ZERO.mag;
        return;
    }

    numDigits = len - cursor;
    signum = sign;

    // Pre-allocate array of expected size. May be too large but can
    // never be too small. Typically exact.
    long numBits = ((numDigits * bitsPerDigit[radix]) >>> 10) + 1;
    if (numBits + 31 >= (1L << 32)) {
        reportOverflow();
    }
    int numWords = (int) (numBits + 31) >>> 5;
    int[] magnitude = new int[numWords];

    // Process first (potentially short) digit group
    int firstGroupLen = numDigits % digitsPerInt[radix];
    if (firstGroupLen == 0)
        firstGroupLen = digitsPerInt[radix];
    String group = val.substring(cursor, cursor += firstGroupLen);
    magnitude[numWords - 1] = Integer.parseInt(group, radix);
    if (magnitude[numWords - 1] < 0)
        throw new NumberFormatException("Illegal digit");

    // Process remaining digit groups
    int superRadix = intRadix[radix];
    int groupVal = 0;
    while (cursor < len) {
        group = val.substring(cursor, cursor += digitsPerInt[radix]);
        groupVal = Integer.parseInt(group, radix);
        if (groupVal < 0)
            throw new NumberFormatException("Illegal digit");
        destructiveMulAdd(magnitude, superRadix, groupVal);
    }
    // Required for cases where the array was overallocated.
    mag = trustedStripLeadingZeroInts(magnitude);
    if (mag.length >= MAX_MAG_LENGTH) {
        checkRange();
    }
}

복잡해보이기때문에 예시를 보면서 핵심만 짚고 넘어가겠습니다. (설명이 생략된 부분은 검증과 0 생략처리 부분입니다.)

예시

123456789101112131415

디버깅 정보

1. numDigits는 숫자 자릿수를 계산합니다. 123456789101112131415의 경우 자릿수는 21입니다.

2. numBits는 숫자를 표현하기 위한 비트 수를 계산하는 데 사용됩니다. 각 자릿수는 radix(여기서는 10진법)에 맞는 비트 수를 가집니다. 이 과정에서, 각 숫자가 bitsPerDigit[10]에 따라 몇 비트로 표현되는지 계산됩니다. ((21 * 3402) >>> 10) + 1 = 70

3. 결국에는 int numWords = (int) (numBits + 31) >>> 5; 파이썬과 비슷하게 2^5= 32비트 정수 배열에 필요한 크기를 구합니다.(=3)

3개의 배열에 32비트로 변환한 값들을 담습니다. 앞의 그룹부터 처리하고 남은 크기가 있으면 반복하면서 그룹에 값을 담습니다.

 

 

mag

• 6: 숫자의 상위 32비트.
• -1320247403: 숫자의 중간 32비트 (음수는 2의 보수 표현으로 저장됨).
• -635764905: 숫자의 하위 32비트 (음수는 2의 보수 표현).

bitCountPlusOne = 0

• 숫자의 1로 설정된 비트 개수를 저장하는 캐시입니다. 이 값은 아직 계산되지 않았기 때문에 기본값 0입니다.

bitLengthPlusOne = 68

• 비트 길이가 68로 저장되었습니다.
  • 이는 123456789101112131415의 2진수 표현에서 가장 높은 비트까지의 길이를 나타냅니다.
  • 실제 비트 길이는 68 - 1 = 67 비트입니다.

lowestSetBitPlusTwo = 0

• 숫자의 가장 낮은 1의 위치를 나타내는 필드입니다.
• 아직 계산되지 않았고, 기본값 0으로 표시됩니다.

firstNonzeroIntNumPlusTwo = 0

• mag 배열에서 가장 처음으로 0이 아닌 값이 나타나는 위치입니다.
• 아직 계산되지 않았기 때문에 기본값 0입니다.

 

정리

결국에는 파이썬과 비슷하게 숫자를 32비트로 표현하는 배열에 담아서 무한한(배열이 메모리를 초과하지 않는 이상) 숫자를 가질 수 있게 된 것입니다. (숫자를 쪼개서 저장)

 

Reference

https://peps.python.org/pep-0237/

https://docs.python.org/3/c-api/structures.html

Common Object Structures

 

https://velog.io/@toezilla/1D1Q-001.-Python%EC%9D%98-int-%EC%9E%90%EB%A3%8C%ED%98%95%EC%9D%80-%EC%96%B4%EB%96%BB%EA%B2%8C-%EB%B2%94%EC%9C%84%EA%B0%80-%EB%AC%B4%EC%A0%9C%ED%95%9C%EC%9D%BC%EA%B9%8C#02-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%B3%80%EC%88%98%EC%9D%98-%ED%8A%B9%EC%A7%95