Karatsuba, Karatsuba algorithm, 카라츠바 알고리즘, 카라츠바 곱셈, fast multiplication, big integer multiplication, subquadratic multiplication
정의
Karatsuba 알고리즘 은 두 큰 정수의 곱셈 을 분할 정복 으로 풀어 O(n^log₂3) ≈ O(n^1.585) 시간에 처리하는 알고리즘. 1962년 Anatoly Karatsuba (당시 23세 학생) 가 Kolmogorov 의 “곱셈은 Ω(n²) 이다” 추측을 반박 한 결과물.
IMPORTANT
“곱셈은 더 빨라질 수 없다” 라고 믿어진 수십 년의 추측을 깬 알고리즘. 분할 정복으로 산술 자체를 가속할 수 있다 는 패러다임 전환. 이후 Toom-Cook, FFT 기반 Schönhage-Strassen, 2019 Harvey-Hoeven 의 O(n log n) 으로 이어진다.
n이 커질수록 Karatsuba 가 압도. FFT 는 더 큰 n에서 더 빠름 (threshold ~10⁵).
n
Naive
Karatsuba
FFT
Naive / Karatsuba
10
100
38
33
2.6×
100
10K
1.4K
664
7.2×
1K
1M
50K
10K
20×
10K
100M
1.8M
133K
55×
100K
10B
66M
1.7M
152×
1M
1T
2.4B
20M
416×
n = 1M 자리 (RSA-4096 같은 거대 정수) 에서 Karatsuba 는 400배 이상 빠르다.
알고리즘 (의사 코드)
function karatsuba(x, y): # Base case: 작은 수는 일반 곱셈 if x < BASE or y < BASE: return x * y n = max(digits(x), digits(y)) m = ⌈n / 2⌉ B^m = base^m # 시프트 단위 # 1. Divide: x, y 를 각각 상/하위로 분할 a, b = divmod(x, B^m) # x = a · B^m + b c, d = divmod(y, B^m) # y = c · B^m + d # 2. Conquer: 3번의 재귀 호출 (4번 → 3번) z2 = karatsuba(a, c) z0 = karatsuba(b, d) z1 = karatsuba(a + b, c + d) - z2 - z0 # 3. Combine: 시프트 + 덧셈 return z2 · B^(2m) + z1 · B^m + z0
재귀 트리 시각화
위는 일반 분할 정복 의 동작. Karatsuba 도 같은 흐름 이지만 2개가 아닌 3개로 분기.
def karatsuba(x: int, y: int) -> int: # base case if x < 10 or y < 10: return x * y n = max(len(str(x)), len(str(y))) m = n // 2 B = 10 ** m a, b = divmod(x, B) c, d = divmod(y, B) z2 = karatsuba(a, c) z0 = karatsuba(b, d) z1 = karatsuba(a + b, c + d) - z2 - z0 return z2 * (B * B) + z1 * B + z0print(karatsuba(1234, 5678))print(karatsuba(12345678, 87654321))
// BigInt 로 임의 크기 정수 지원function karatsuba(x, y) {if (x < 10n || y < 10n) return x * y;const n = Math.max(x.toString().length, y.toString().length);const m = BigInt(Math.floor(n / 2));const B = 10n ** m;const a = x / B, b = x % B;const c = y / B, d = y % B;const z2 = karatsuba(a, c);const z0 = karatsuba(b, d);const z1 = karatsuba(a + b, c + d) - z2 - z0;return z2 * (B * B) + z1 * B + z0;}console.log(karatsuba(1234n, 5678n).toString());console.log(karatsuba(12345678n, 87654321n).toString());
import java.math.BigInteger;class Karatsuba {static BigInteger karatsuba(BigInteger x, BigInteger y) { final BigInteger TEN = BigInteger.TEN; if (x.compareTo(TEN) < 0 || y.compareTo(TEN) < 0) return x.multiply(y); int n = Math.max(x.toString().length(), y.toString().length()); int m = n / 2; BigInteger B = TEN.pow(m); BigInteger[] xs = x.divideAndRemainder(B); BigInteger[] ys = y.divideAndRemainder(B); BigInteger a = xs[0], b = xs[1]; BigInteger c = ys[0], d = ys[1]; BigInteger z2 = karatsuba(a, c); BigInteger z0 = karatsuba(b, d); BigInteger z1 = karatsuba(a.add(b), c.add(d)) .subtract(z2).subtract(z0); return z2.multiply(B.pow(2)) .add(z1.multiply(B)) .add(z0);}public static void main(String[] args) { System.out.println(karatsuba( BigInteger.valueOf(1234), BigInteger.valueOf(5678)));}}
// num-bigint crate 사용use num_bigint::BigInt;use num_traits::Zero;fn karatsuba(x: &BigInt, y: &BigInt) -> BigInt { let ten = BigInt::from(10); if x < &ten || y < &ten { return x * y; } let n = x.to_string().len().max(y.to_string().len()); let m = n / 2; let b = BigInt::from(10).pow(m as u32); let (a, b_lo) = (x / &b, x % &b); let (c, d) = (y / &b, y % &b); let z2 = karatsuba(&a, &c); let z0 = karatsuba(&b_lo, &d); let z1 = karatsuba(&(&a + &b_lo), &(&c + &d)) - &z2 - &z0; z2 * b.pow(2) + z1 * &b + z0}
package mainimport ( "fmt" "math/big")func karatsuba(x, y *big.Int) *big.Int { ten := big.NewInt(10) if x.Cmp(ten) < 0 || y.Cmp(ten) < 0 { return new(big.Int).Mul(x, y) } n := max(len(x.String()), len(y.String())) m := n / 2 B := new(big.Int).Exp(ten, big.NewInt(int64(m)), nil) a, b := new(big.Int).DivMod(x, B, new(big.Int)) c, d := new(big.Int).DivMod(y, B, new(big.Int)) z2 := karatsuba(a, c) z0 := karatsuba(b, d) sum := karatsuba(new(big.Int).Add(a, b), new(big.Int).Add(c, d)) z1 := new(big.Int).Sub(sum, z2) z1.Sub(z1, z0) // z2*B^2 + z1*B + z0 res := new(big.Int).Mul(z2, new(big.Int).Mul(B, B)) res.Add(res, new(big.Int).Mul(z1, B)) res.Add(res, z0) return res}
💬 댓글