Python Karatsuba(카라추바) 곱셈 알고리즘

@wikipedia

Karatsuba 알고리즘

1. 소개

카라추바 알고리즘이란, 큰 수에 대해 효과적인 곱셉 알고리즘이다.

(23살에 1주일 만에 발견한 알고리즘)

(보통 두 수 곱 시간 복잡도는 $O(n^2)$ 이지만 카라추바 알고리즘을 사용하면 O(n^1.585)가 나온다.)

(실제로 파이썬도 일반적인 곱셉 알고리즘을 사용하지만, 매우 큰 수에 대해선 카라추바 알고리즘을 사용)

(2019년에 나온 Harvey and van der Hoeven의 $O(nlogn)$ 곱셈이 가장 빠른데,

이 기법은, 10^850억 자리 이상의 수에서 작동한다.

카라추바처럼 수를 작은 파트로 쪼개지만, FFT (Fast Fourier Transform)를 사용해서 합친다. )

 

2. 작동 방식

@wikipedia, m = 제곱 수

 

카라추바 알고리즘의 기본 단계는 큰 두 수 x와 y의 곱을 자릿수가 x, y의 절반인 수들의 곱 3번과

덧셈과 시프트 연산을 이용해 계산하는 것이다.

(한마디로 곱 횟수 줄이려고 덧셈 몇 번 추가해서 계산을 더 빠르게 만듦)

플로우차트 @Can Eyupoglu (2015) 논문

 

우선 97, 98를 곱한다고 했을 때 알고리즘은 다음과 같다.

(10^m 은 진법(base)에 따라 달라질 수 있음)

플로우차트 @Can Eyupoglu (2015) 논문

# 12345 x 6789 예제

12345 * 6789 (B=10, m=3)
= 12_345 * 6_789  # a1=12, a2=345, b1=6, b2=789

A = a1 * b1 = 12 * 6 = 72
B = a2 * b2 = 345 * 789 = 272,205
C = (a1 + a2) * (b1 + b2) = (12 + 345) * (6 + 789) = 357 * 795 = 283,815
D = C - A - B = 283,815 - 72 - 272,205 = 11,538

# Result = A * 10^(2*m) + D * 10^m + B
Result = 72 * 10^6 + 11,538 * 10^3 + 272,205

 

3. 파이썬 코드

# x << y는 x * 2^y와 같음
100 << 4  # 결과 = 1600

# x >> y는 x / 2^y와 같음
100 >> 4  # 결과 = 6

def karatsuba(num1: int, num2: int) -> int:
    # 숫자의 길이를 찾기 위해 문자열로 변환
    strNum1 = str(num1)
    strNum2 = str(num2)

    # 두 숫자 중 최대 길이 찾기
    m = max(len(strNum1), len(strNum2))

    # 재귀의 기본 경우
    if m < 2:
        return num1 * num2

    # m의 절반 크기로 m2 계산, 홀수 길이를 위해 조정
    m2 = m // 2

    # m2를 기반으로 숫자를 높은 부분과 낮은 부분으로 분리
    high1, low1 = divmod(num1, 10**m2)
    high2, low2 = divmod(num2, 10**m2)

    # 재귀 단계
    z0 = karatsuba(low1, low2)
    z2 = karatsuba(high1, high2)
    z1 = karatsuba((low1 + high1), (low2 + high2)) - z0 - z2

    # 결과 결합
    return (z2 * 10**(2*m2)) + (z1 * 10**m2) + z0


if __name__ == "__main__":
    print(karatsuba(12345, 6789))

 

참고

위키피디아

카라추바 알고리즘 - 위키백과, 우리 모두의 백과사전

Can Eyupoglu's Performance Analysis of Karatsuba Multiplication Algorithm for Different Bit Lengths

Can Eyupoglu's Performance Analysis of Karatsuba Multiplication Algorithm for Different Bit Lengths