박종훈 기술블로그

[Java] BigInteger 의 내부는 어떤 식으로 동작할까?

개요

java의 int는 4byte의 크기를 가진다. long은 8byte의 크기를 가진다.

타입메모리 크기범위
int4byte-2^31 ~ (2^31 - 1) / -2,147,483,648 ~ 2,147,483,647
long8byte-2^63 ~ (2^63 - 1) / -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807

그럼 그보다 큰 수는 어떻게 표현할까?

본문

자바에서는 이러한 사이즈 제한을 벗어나야 할 때 biginteger를 사용한다.

임의 정밀도 (arbitrary-precision)

biginteger 와 bigdecimal에 대한 정보를 찾아보면 임의 정밀도에 대한 내용이 나온다. 임의 정밀도에 대한 부분을 먼저 찾아보면 다음같은 설명을 찾아볼 수 있다. (출처 : wikipedia)

In computer science, arbitrary-precision indicates that calculations are performed on numbers whose digits of precision are limited only by the available memory of the host system

쉽게 이야기 하면 메모리에 의한 제한이 아니라면 얼마든지 큰 자리수를 저장할 수 있는 방식이다.

자바에서는 이것을 어떤 방식으로 달성하였는지 클래스 내부를 살펴보자.

biginteger

Immutable arbitrary-precision integers

big integer 는 불변 객체이다.

BigInteger 클래스는 다음과 같은 변수를 가지고 있다.

쉽게 이해할 수 있도록 PlusOne, PlusTwo 를 제외하고 설명한다. 이에 대해서는 하단에 추가적으로 정리한다.

bitCount, bitLength, lowestSetBit, firstNonzeroIntNum 의 경우 lazy하게 필요할때만 값이 할당된다.

64

debug biginteger 64

-64

debug biginteger -64

bitCount와 bitLength 의 차이

왜 PlusOne 과 PlusTwo 가 붙는걸까?

이 이유를 찾으려고 정말 많은 시간이 들었다. 해당 변경은 java 9 로 넘어가면서 진행되었다.

근데 java 8 때도 일단 deprecated 되어 있다는 것을 확인할 수 있었다. (java 6 까지도 확인해봤는데 이때도 deprecated 였다. 꽤 오랜 세월동안 deprecated 상태였나보다.) 비교해 본 결과 로직은 변경되지 않았고, 이름을 좀 더 명확하게 하기 위해서 java9 부터 이름을 변경한 것 같다.

public int bitCount() {
    int bc = bitCountPlusOne - 1;
    if (bc == -1) {

        // 중략 ...

        bitCountPlusOne = bc + 1;
    }
    return bc;
}

biginteger 에서는 성능을 위해서 필요시에 값을 갱신하는 방식을 채택하였다.

그래서 1 더 추가한 상태로 보관하고, 함수가 호출되었을 때 -1 하고 함수가 끝나기 전에 +1 해서 저장을 한다. 그러면 bit가 없는 0이 들어왔다고 하더라도 bc 값은 -1 이 아닌 0이 되기 때문에 다시 계산할 필요 없이 그냥 bc를 반환하면 된다.

정리

BigInteger의 내부 변수들의 상태가 어떻게 변경되는지 확인하였으나, 왜 이렇게 작성된 것인지는 다음에 기회가 되면 더 파봐야 할 것 같다.

참고