자바에서 100자리 이상의 수는 어떻게 계산할까?

자바의 기본 자료형 중 가장 큰 정수형은 최댓값이 2⁶³ -1인 long이다. long은 약 920경, 19자리 수이기 때문에 기본 자료형으로는 20자리 이상의 수는 처리할 수 없다.

그럼 20자리 이상의 수는 계산이 불가능할까?

자바의 자료형에 제약이 있는거지 메모리 상으로 수를 표현할 수 있으면 컴퓨터는 계산할 수 있다고 생각했고 어떻게 하면 표현할 수 있는지 고민해보았다.

🤔배열을 메모리 공간처럼 사용해 보는건 어떨까?

boolean 타입의 배열을 선언하고 배열의 인덱스를 활용하면 2진법으로 표현할 수 있을 것 같아서 시도해보았다.

Arr index	2¹⁰⁰⁰⁰	2⁹⁹⁹⁹	2⁹⁹⁹⁸	2⁹⁹⁹⁷	...	2⁶	2⁵	2⁴	2³	2²	2¹	2⁰
boolean	1	0	0	1	...	0	1	1	1	1	0	1

하지만 너무 많은 문제가 있었다.

❌2진수 <-> 10진수 변환 불가

보통 10진수로 계산하지 2진수로 계산하지 않는다. 100자리 이상의 10진수가 문자열로 입력되었을 때 그 수를 연산 없이 2진수로 변환할 수가 없다고 판단했다.

반대 역시 마찬가지다. 어떻게든 2진수로 계산했다고 해도 계산 결과를 10진수로 출력하려면 변환이 필요하다.

😮그냥 배열로 계산하면 될 거 같은데?

첫 번째 방법 시도 후 가만히 배열을 보고있었는데 '굳이 2진수로 해야하나?', '10진수로 바로 계산해도 될 거 같은데?' 라고 생각이 들었고 바로 시도해보았다.

public class BigNumberCalc {
    public static void main(String[] args) {
        BigNumberCalc bigNumberCalc = new BigNumberCalc();
        String firstNumber = "7234432975454231216542312453421564646313113546542654531346543155648424984565426131313291658442375436399372";
        String secondNumber = "989123985665198534795873295473298672394657293850435702938547395729834679327698375993847529895321609498";

        String result = bigNumberCalc.getLongNumber(firstNumber, secondNumber); // 큰 수 반환

        String longNumber;
        String shortNumber;
        if (result.equals(firstNumber)) {
            longNumber = firstNumber;
            shortNumber = secondNumber;
        } else {
            longNumber = secondNumber;
            shortNumber = firstNumber;
        }

        // firstNumber + secondNumber
        String addResult = bigNumberCalc.add(longNumber, shortNumber);
        System.out.println("add result = " + addResult);
    }

    public String add(String longNumber, String shortNumber) {
        int offset = longNumber.length();
        char[] newShortNumber = getNewArray(shortNumber, offset); // 자릿수를 맞춘다

        int additional = 0; // 각 자리수의 합이 10 이상일 경우 1
        char[] resultArray = new char[offset + 1];

        for (int i = offset - 1; i >= 0; i--) {
            int a = Character.getNumericValue(longNumber.charAt(i));
            int b = Character.getNumericValue(newShortNumber[i]);

            int sum = additional + a + b; // additional + 각 자리수 합

            if (sum >= 10) {
                additional = 1;
                resultArray[i+1] = Character.forDigit(sum % 10, 10);
            } else {
                additional = 0;
                resultArray[i+1] = Character.forDigit(sum, 10);
            }
        }
        resultArray[0] = Character.forDigit(additional, 10);
        return String.valueOf(resultArray);
    }

    public String getLongNumber(String firstNumber, String secondNumber) {
        int firstLength = firstNumber.length();
        int secondLength = secondNumber.length();

        if(firstLength > secondLength) {
            return firstNumber;
        } else {
            return secondNumber;
        }
    }

    private char[] getNewArray(String shortNumber, int offset) {
        char[] newShortNumber = new char[offset];

        int endZero = offset - shortNumber.length();
        for (int i = 0; i < offset; i++) {
            if (i < endZero) {
                newShortNumber[i] = Character.forDigit(0, 10);
            } else {
                newShortNumber[i] = shortNumber.charAt(i - endZero);
            }
        }
        return newShortNumber;
    }
}

양의 정수의 덧셈 과정만 구현해 보았다. 천천히 살펴보자.

🤪누가 더 긴 자릿수니?

두 개의 수를 더한 결과는 둘 중, 큰 수의 자릿수 + 1 이상으로 커지지 않는다. 99 + 99의 결과가 198인 것을 보면 알 수 있다.

덧셈 결과를 담을 배열의 크기를 지정하기 위해 먼저 둘 중 자릿수가 더 큰 수를 반환하는 getLongNumber() 메소드를 생성했다. 둘 중 문자열 길이가 더 긴 것을 반환하며, 자릿수가 동일하다면 둘 중 아무 거나 반환되어도 상관없다.

😬이제 더해볼까?

둘 중 짧은 수는 getNewArray() 메소드로 긴 수와 자릿수를 맞춘다. 결과를 담을 배열은 더 긴 수의 자릿수 + 1의 크기로 생성하고 각 자릿수의 합을 저장한다. 이때 각 자릿수의 합이 10 이상인 경우 지역 변수 additional로 다음 자릿수에 값을 추가할 수 있도록 하고 int형과 char형 사의 변환은 Character 클래스를 활용했다.

😨덧셈은 잘 된다! 그러나...

위와 같은 방법으로 계산은 잘 된다. 하지만 위의 계산만 잘 된다. 다시 말하면 덧셈을 제외한 나머지 연산과 음의 정수에 대한 고려가 전혀 되어있지 않다. 물론 더 많은 문제가 있다...

어떻게든 붙잡고 있으면 조금은 더 나은 방법을 찾을 수 있을 것 같지만... '바퀴를 다시 발명하지 마라.'는 말이 떠올라 자바에서 큰 수의 처리는 어떻게 하는지 찾아보았다.

BigInteger

역시 바퀴는 이미 있었다.
API 문서를 보면 비트 관련 내용이 많은데 내부적으로는 비트로 계산되는 것 같다.

'Semantics of arithmetic operations exactly mimic those of Java's integer arithmetic operators, as defined in The Java Language Specification.'
자바의 integer 연산과 동일하게 작동하며,

'BigInteger must support values in the range -2Integer.MAX_VALUE (exclusive) to +2Integer.MAX_VALUE (exclusive) and may support values outside of that range.'
해당 범위를 벗어나는 값을 지원한다는 말만 있는걸 보면 제한 길이는 없는 듯하다.
(구글링 해보니 무한대에 가깝다고 한다.)

그래서 어떻게 사용하는데?

여러 생성자가 있지만 String을 매개 변수로 사용하는 생성자를 많이 사용할 듯하다.

Constructor	Description
BigInteger(String val)	Translates the decimal String representation of a BigInteger into a BigInteger.

integer 연산과 동일하게 작동한다고 해서 +, -와 같은 기호로 연산하는 것은 아니다.

Modifier and Type	Method	Description
BigInteger	add(BigInteger val)	Returns a BigInteger whose value is (this + val).
BigInteger	subtract(BigInteger val)	Returns a BigInteger whose value is (this - val).
BigInteger	multiply(BigInteger val)	Returns a BigInteger whose value is (this * val).
BigInteger	divide(BigInteger val)	Returns a BigInteger whose value is (this / val).
BigInteger	remainder(BigInteger val)	Returns a BigInteger whose value is (this % val).

위 표는 산술 연산자만 나타낸 것이며 실제로는 다양한 연산을 지원한다.

BigInteger를 사용해볼까?

위에서 했던 계산을 BigInteger를 사용해서 해보자.

public class BigIntegerTest {
    public static void main(String[] args) {
        BigInteger firstNumber = new BigInteger("7234432975454231216542312453421564646313113546542654531346543155648424984565426131313291658442375436399372");
        BigInteger secondNumber = new BigInteger("989123985665198534795873295473298672394657293850435702938547395729834679327698375993847529895321609498");

        BigInteger addResult = firstNumber.add(secondNumber);
        System.out.println("addResult = " + addResult);

        BigInteger subtractResult = firstNumber.subtract(secondNumber);
        System.out.println("subtractResult = " + subtractResult);

        BigInteger multiplyResult = firstNumber.multiply(secondNumber);
        System.out.println("multiplyResult = " + multiplyResult);

        BigInteger divideResult = firstNumber.divide(secondNumber);
        System.out.println("divideResult = " + divideResult);

        BigInteger remainderResult = firstNumber.remainder(secondNumber);
        System.out.println("remainderResult = " + remainderResult);
    }
}

덧셈 과정이 위와 비교도 안될 정도로 간단해졌다. 그리고 덧셈 이외의 연산도 간편하게 수행할 수 있다.

정리

만약 스스로 구현해보는 과정 없이 그냥 '큰 수는 어떻게 처리하지?'하고 BigInteger를 사용했다면 별 감흥이 없었을 것 같다. 그냥 큰 수 처리해주는 클래스라고 생각하고 넘어갔을 것 같다.

하지만 어떻게든 비슷하게 흉내내보려고 한 다음 BigInteger 클래스를 사용해 보니까 감탄밖에 안 나온다. 아직 내부적으로 어떻게 동작하는지는 모르지만 기회가 된다면 슬쩍 알아보는 것도 좋을 것 같다.

참고

https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/math/BigInteger.html