카라츠바의 빠른 곱셈 알고리즘(2) - O(N^lg3)

1. 문제 설명

(1) 카라츠바 알고리즘은 정수 두 수를 절반으로 쪼개는 것으로부터 시작됩니다.

 

(2) 다음 문제 설명은 아래의 그림을 보고 이해합니다.

 

( 이때, 카라츠바는 a x b를 네 개의 조각을 이용해 표현하면 위와 같이 표현할 수 있습니다. 

( 이 방법에서는 두 큰 정수를 한 번 곱하는 대신 네 번 곱합니다. )

( 이때, 10의 거듭제곱은 시프트 연산으로 구현하므로 곰셈으로 치지 않습니다. )

 

 

( 이해를 돕기 위해 아래의 사진을 참고하세요. )

 

( 그러나, 위 방법대로 네 번 곱하는 시간 복잡도를 구해보면 결국 O(N^2)이 됩니다. )

( O(N^2) = 덧셈과 시프트 연산(O(N)) x 2/n길이 조각들의 곱셈 네 번 by 마스터 정리 )

 

 

( 여기서 카라츠바가 발견한 것은 아래와 같이 네 번 대신 세 번의 곱셈만으로 표현할 수 있는 것입니다. )

 

 

( 그러므로, 각 조각을 표현하면 최종적으로 아래와 같이 될 수 있다. )

 

 

2. 입출력 조건 및 예제

입력 조건

X

 

출력 조건

X

 

입력 예제

1234
5678

 

출력 예제

7006652

 

 

 

 

3. 제약 조건

X

 

 

 

 

4. 가정법

X

 

 

 

 

5. 기저 사례

(1) a나 b가 비어있는 경우

(2) a가 비교적 짧은 경우 O(N^2) 곱셈으로 변경한다.

 

 

6. 코드

public class Karatsuba {
    private static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        ArrayList<Integer> a = toArrayList();
        ArrayList<Integer> b = toArrayList();

        ArrayList<Integer> c = karatsuba(a, b);
        for(int i=c.size()-1; i>=0; i--) {
            System.out.print(c.get(i) +" ");
        }
    }

    // ArrayList<Integer>로 변환하는 메서드
    private static ArrayList<Integer> toArrayList() throws IOException{
        ArrayList<Integer> c = new ArrayList<>();

        st = new StringTokenizer(sc.readLine());
        int n = st.countTokens();

        for(int j=0; j<n; j++) {
            c.add(Integer.parseInt(st.nextToken()));
        }
        return c;
    }

    // 큰 두 정수를 분할 정복으로 곱하여 반환한다.
    private static ArrayList<Integer> karatsuba(ArrayList<Integer> a, ArrayList<Integer> b){
        int an = a.size(), bn = b.size();

        // a가 b보다 짧을 경우 둘을 바꾼다.
        if(an<bn) return karatsuba(b, a);

        // 기저 사례(1): a나 b가 비어있는 경우
        if(an==0 || bn==0) return new ArrayList<Integer>();

        // 기저 사례(2): a가 비교적 짧은 경우 O(N^2) 곱셈으로 변경한다.
        if(an<=50) return multiply(a,b);
        int half = an/2;

        // a와 b를 밑에서 half 자리와 나머지로 분리한다.
        ArrayList<Integer> a0 = new ArrayList<Integer>(a.subList(0, half));
        ArrayList<Integer> a1 = new ArrayList<Integer>(a.subList(half, an));
        ArrayList<Integer> b0 = new ArrayList<Integer>(b.subList(0, Math.min(bn,half)));
        ArrayList<Integer> b1 = new ArrayList<Integer>(b.subList(Math.min(bn, half), bn));

        // z2 = a1*b1
        ArrayList<Integer> z2 = karatsuba(a1, b1);

        // z0 = a0*b0
        ArrayList<Integer> z0 = karatsuba(a0, b0);

        // z1 = (a0*b0) - z0 - z2
        ArrayList<Integer> z1 = karatsuba(a0, b0);
        subFrom(z1, z0);
        subFrom(z1, z2);

        // ret = z0 + z1*10^half + z2*10^(half*2)
        ArrayList<Integer> ret = new ArrayList<>();
        addTo(ret, z0, 0);
        addTo(ret, z1, half);
        addTo(ret, z2, half+half);

        return ret;
    }

    // a += b*(10^k)를 구현한다.
    private static ArrayList<Integer> addTo(ArrayList<Integer> a, ArrayList<Integer> b, int k){
        a = ensureSize(a, Math.max(a.size(), b.size()+k));

        for(int i=0; i<b.size(); i++) {
            a.set(i+k, a.get(i+k) + b.get(i));
        }
        a=normalize(a);
        return a;
    }

    // a -= b를 구현한다. a >= b를 가정한다.
    private static ArrayList<Integer> subFrom(ArrayList<Integer> a, ArrayList<Integer> b){
        a = ensureSize(a, Math.max(a.size(), b.size()+1));

        for(int i=0; i<b.size(); i++) {
            a.set(i, a.get(i) - b.get(i));
        }
        a=normalize(a);
        return a;
    }

    // 자릿수 올림을 처리하는 메서드
    private static ArrayList<Integer> normalize(ArrayList<Integer> num) {

        // 마지막 자리 수가 올림을 할 경우를 대비하여 0 삽입
        // ex) 9 14 -> 1 0 4 (여기서 마지막 자리수는 9 왼쪽을 의미함)
        num.add(0);

        for(int i=0; i<num.size()-1; i++) {

            // 음수일 경우
            if(num.get(i)<0) {
                int borrow = (Math.abs(num.get(i))+9)/10;
                num.set(i+1, num.get(i+1) - borrow);
                num.set(i, num.get(i) + borrow*10);
            }else { // 양수일 경우
                num.set(i+1, num.get(i+1) + num.get(i)/10);
                num.set(i, num.get(i)%10);
            }
        }
        // 마지막 자리수가 0 그대로라면 0을 삭제
        while(num.size()>1 && num.get(num.size()-1)==0) num.remove(num.size()-1);

        return num;
        }

    // 두 큰 정수를 삭제하는 메서드
    // 시간 복잡도: O(N^2)
    private static ArrayList<Integer> multiply(ArrayList<Integer> a, ArrayList<Integer> b) {
        ArrayList<Integer> c = new ArrayList<>();

        // 각 size를 알기 위해 0을 a,b 사이즈만큼 삽입
        for(int i=0; i<a.size()+b.size(); i++) {
            c.add(0);
        }

        // 계산 수행
        for(int i=0; i<a.size(); i++) {
            for(int j=0; j<b.size(); j++) {
                c.set(i+j, c.get(i+j) + a.get(i)*b.get(j));
            }
        }

        // 자릿수 올림하고 결과값 리턴
        c = normalize(c);
        return c;
    }

    // 입력받은 c를 size만큼 용량을 높이고 size를 올린다.
    private static ArrayList<Integer> ensureSize(ArrayList<Integer> c, int size){
        c.ensureCapacity(size);
        while(c.size()<size) {
            c.add(0);
        }
        return c;
    }
}

 

 

 

7. 시간 복잡도 분석

- O(3^k) = (3^lgn) = O(n^lg3)