분할 정복 알고리즘으로 두 이진수를 빠르게 곱하는 방법

두 개의 이진수(binary) 문자열로 표현된 숫자가 주어졌을 때, 기존의 단순 곱셈 방식보다 더 빠르고 효율적으로 두 수의 곱을 계산하는 것이 이 글의 목표입니다. 자릿수를 하나씩 곱하는 전통적인 방법은 숫자의 길이가 길어질수록 성능이 급격히 떨어집니다.

분할 정복(Divide and Conquer) 전략을 활용하면 이 문제를 훨씬 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 숫자를 절반 크기의 두 부분으로 나눈 뒤 재귀적으로 곱하는 것입니다.

첫 번째 수 X를 왼쪽 절반 X_left와 오른쪽 절반 X_right로 나누고, 두 번째 수 Y도 마찬가지로 Y_left, Y_right로 나누면 두 수의 곱은 다음과 같이 표현할 수 있습니다.

위 식을 그대로 계산하면 부분 곱셈이 네 번 필요하지만, 카라추바(Karatsuba)가 제안한 아래와 같은 변형을 적용하면 곱셈 횟수를 세 번으로 줄일 수 있습니다.

분할 정복 알고리즘으로 두 이진수를 빠르게 곱하는 방법

이 기법의 시간 복잡도는 O(n^log₂3) ≈ O(n^1.585)로, 일반적인 방식의 O(n²)보다 월등히 빠릅니다.

입력 및 출력

입력:
두 이진수: 1101, 0111
출력:
결과: 91

알고리즘

addBitString(num1, num2) — 이진수 문자열 덧셈

입력: 더할 두 개의 이진수

출력: 덧셈 결과 문자열

Begin
    adjust num1 and num2 lengths
    length := length of num1
    carry := 0

    for i := length -1 down to 0, do
        num1Bit := num1[i]
        num2Bit := num2[i]
        sum := num1Bit XOR num2Bit XOR carry
        finalSum := sum + finalSum
        carry := (num1Bit AND num2Bit) OR (num2Bit AND carry) OR (num1Bit AND carry)
    done

    if carry ≠ 0, then
        finalSum := 1 + finalSum
    return finalSum
End

multiply(num1, num2) — 분할 정복 곱셈

입력: 곱할 두 개의 이진수

출력: 곱셈 결과

Begin
    adjust num1 and num2 lengths
    length := length of num1
    if n = 0, then
        return 0
    if n = 1, then
        return (num1[0] * num2[0])
    firstHalf := n/2
    secondHalf := (n - firstHalf)

    n1Left := substring of (0 to firstHalf) from num1
    n1Right := substring of (firstHalf to secondHalf) from num1
    n2Left := substring of (0 to firstHalf) from num2
    n2Right := substring of (firstHalf to secondHalf) from num2

    p1 := multiply(n1Left, n2Left)
    p2 := multiply(n1Right, n2Right)

    add1 := addBitString(n1Left, n1Right)
    add2 := addBitString(n2Left, n2Right)
    p3 := multiply(add1, add2)

    mask1 := shift 1 to left for 2*secondHalf bits
    mask2 := shift 1 to left for secondHalf bits
    return P1*mask1 + (p3 – p1 – p2)*mask2 + p2
End

C++ 구현 예제

#include<iostream>
using namespace std;

int lengthAdjust(string &num1, string &num2) {     //adjust length of binary string and send length of string
    int len1 = num1.size();
    int len2 = num2.size();

    if (len1 < len2) {
        for (int i = 0 ; i < len2 - len1 ; i++)
            num1 = '0' + num1; //add 0 before the first string
    } else if (len1 > len2) {
        for (int i = 0 ; i < len1 - len2 ; i++)
            num2 = '0' + num2; //add 0 before the second string
    }
    return num1.size();
}

string addBitStrings(string num1, string num2) {
    string finalSum;

    int length = lengthAdjust(num1, num2);     //adjust and update number lengths and store length
    int carry = 0;      // Initialize carry

    for (int i = length-1 ; i >= 0 ; i--) {
        int num1Bit = num1[i] - '0';
        int num2Bit = num2[i] - '0';

        int sum = (num1Bit ^ num2Bit ^ carry)+'0';     //we know sum = A XOR B XOR C

        finalSum = (char)sum + finalSum;
        //the carry = (A AND B) OR (B AND C) OR (C AND A)
        carry = (num1Bit&num2Bit) | (num2Bit&carry) | (num1Bit&carry);
    }

    if (carry)   //when carry is present
        finalSum = '1' + finalSum; //add carry as MSb
    return finalSum;
}

long int multiply(string num1, string num2) {
    int n = lengthAdjust(num1, num2);     //find length after adjusting them
    if (n == 0)     //when there is 0 length string, return 0
        return 0;
    if (n == 1)
        return (num1[0] - '0')*(num2[0] - '0');     //perform single bit multiplication

    int firstHalf = n/2;   // First half range
    int secondHalf = (n-firstHalf);     // Second half range

    string num1Left = num1.substr(0, firstHalf);     //first half of number 1
    string num1Right = num1.substr(firstHalf, secondHalf);     //second half of number 1
    string num2Left = num2.substr(0, firstHalf);
    string num2Right = num2.substr(firstHalf, secondHalf);

    // find left right multiplication, and multiply after adding left and right part
    long int P1 = multiply(num1Left, num2Left);
    long int P2 = multiply(num1Right, num2Right);
    long int P3 = multiply(addBitStrings(num1Left, num1Right), addBitStrings(num2Left, num2Right));

    return P1*(1<<(2*secondHalf)) + (P3 - P1 - P2)*(1<<secondHalf) + P2;
}

int main() {
    string num1, num2;
    cout << "Enter First number in Binary: "; cin >>num1;
    cout << "Enter Second number in Binary: "; cin >>num2;
    cout << "The result is: " << multiply(num1, num2);
}

실행 결과

Enter First number in Binary: 1101
Enter Second number in Binary: 0111
The result is: 91

이처럼 분할 정복 기반의 곱셈은 큰 이진수를 다룰 때 성능상 큰 이점을 제공하며, 실제로 다양한 암호학 라이브러리에서도 유사한 원리가 활용되고 있습니다.