ν° μ리μμ κ³±μ μκ³ λ¦¬μ¦μΈ μΉ΄λΌμΈ λ° μκ³ λ¦¬μ¦μ λν΄μ ν΅μ¬λ§ μ 리ν΄λ³Έλ€.
ꡬνκ³ μ νλ κ³±μ μ΄ μΈ κ²½μ°λ₯Ό μκ°νμ. μ¬κΈ°μ , λ μμ°μμ΄λ€. νΈμμ λ μμ μ리μκ° κ°λ€κ³ νμ. (λ§μ½ κ°μ§ μμ κ²½μ°λΌλ©΄, μμ λ μμ ν° λ μμ ν¬κΈ°λ‘ λ§μΆκ³ paddingμ μΆκ°νλ©΄ λλ€) κ·Έλ¬λ©΄, , λ μλμ²λΌ λ€μ μΈ μ μλ€.
μμμΌλ‘ 보면 볡μ‘ν΄ λ³΄μ΄λλ°, μ΄λ λ¨μν μ²λΌ νΉμ μλ₯Ό high
, low
λ‘ λλ κ² λΏμ΄λ€. high
μ ν΄λΉνλ κ²μ΄ , μ΄κ³ , low
μ ν΄λΉνλ κ²μ΄ , μ΄λ€. μ΄λ₯Ό formal
νκ² λνλΈ κ²μ΄ μ μμμ΄κ³ , λ μ§λ²μ λνλ΄κ³ , μ ν° μμ μ΄ μλ¦Ώμκ° μ΄λΌκ³ ν λ μ λ°μΌλ‘ λλ κ°μ΄λ€. (, μ λ°μΌλ‘ λλλ©΄ μ’μ§ μκ² λκ°?) κ·Έλ¬λ©΄ ꡬνκ³ μ νλ κ³±μ
μ μλμ²λΌ λ€μ μΈ μ μλ€.
μ΄κ²μ μ΄λλ‘ κ³μ°νλ©΄, κ³±μ μ ꡬκ°μ μ λ°μΌλ‘ μ€μΈ λμ , κ³±μ μ΄ νμκ° 4λ²μΌλ‘ λμ΄λ¬κΈ° λλ¬Έμ μκ°λ³΅μ‘λ κ³μ°μ ν΄λ³΄λ©΄ μ΄ λκΈ° λλ¬Έμ Naiveνκ² κ΅¬νλ κ²½μ°λ λ€λ₯Όκ² μλ€. κ·Έλ°λ°, λ§μ½μ μ μμμ κ³μ°νλλ°μ κ³±μ μ νμκ° 3λ²λ§ νμνλ€λ©΄ μ΄λ¨κΉ? μ리μκ° μμ κ²½μ°μλ μ λ°©μμ΄ μμνμ λ리기 λλ¬Έμ ν¬κ² μλ―Έκ° μμ§λ§, μ리μκ° ν΄ κ²½μ°(μ΄ ν΄ κ²½μ°)μλ μΆ©λΆν μλ―Έκ° μλ€. μΉ΄λΌμΈ λ° μκ³ λ¦¬μ¦μ ν΅μ¬μ μ κ³μμ λΆμ΄μλ λ μμ μλμ²λΌ λ³ννλλ°μ μλ€.
κ³±μ μ μ€μΈλ€λλ λλ²μμ μ€νλ € μΈλ²μΌλ‘ λλ¦¬κ³ μλ€ λΌκ³ ν μ μλ€. κ·Έλ°λ° μμ μμΈν 보μ. κ³Ό μ μ΄μ°¨νΌ κ³μ°ν΄μΌν κ°μ΄μλ€. μ¦, μΆκ°λ‘ κ³μ°ν΄μΌν κ³±μ μ νλλ€.
μ μκ³ λ¦¬μ¦μ κ°λ¨νκ² μ¬κ·λ‘ μλμ²λΌ ꡬνμ΄ κ°λ₯νλ€. λΆλΆμ νΉμ μ리μ λΆλΆμλ€κ° λνλ κ²μ΄λ―λ‘, λ°°μ΄μ μ μ κ·Όνλ κ²μΌλ‘ μ²λ¦¬κ° κ°λ₯νλ€. λν, μΉ΄λΌμΈ λ°λ μμνμ΄ ν° μκ³ λ¦¬μ¦μ΄κΈ° λλ¬Έμ, μ€μ λ‘ μ¨λ¨Ήμλ§ν ꡬνμ naive
ν κ³±μ
ꡬνμ μμ΄μ νλ€.
// naive ν κ³±μ ꡬν, μκ°λ³΅μ‘λ O(N^2)void naive_mult(ull r[], ull x[], ull y[], int n) {for(int i = 0; i < n; ++i) {ull cur = x[i];ull* rp = &r[i]; ull* yp = &y[0];for(int j = 0; j < n; ++j, ++rp, ++yp) {*rp += *yp * cur;}}}void karatsuba(ull r[], ull x[], ull y[], int n) {if (n < 50) {naive_mult(r, x, y, n); return; // μΌμ μ리μ μ΄νλ‘ λ΄λ €κ°λ©΄ karatsubaλ λΉν¨μ¨μ μ΄λ€. naiveν κ³±μ μ μ°μ}int m = n >> 1; // Nλ κ°λ₯νν N / 2 λ± λ¨μ΄μ§κ²λλ κ°μ₯ μ’μ μλ₯Ό μ ννμ.ull xs[SZ], ys[SZ], tmp[SZ];for(int i = 0; i < m; ++i) xs[i] = x[i] + x[i + m], ys[i] = y[i] + y[i + m];for(int i = 0; i < n; ++i) tmp[i] = 0;// 4κ°μ κ³±μ -> 3κ°μ κ³±μ μΌλ‘ μ€μ΄λ¬karatsuba(tmp, xs, ys, m);karatsuba(r, x, y, m);karatsuba(r + n, x + m, y + m, m); // B^2m ꡬκ°μ κ²°κ³Όλ μ¬κΈ°λ‘ λ€μ΄κ°λ€.for(int i = 0; i < n; ++i) tmp[i] -= r[i] + r[i + n]; // (x0 + x1)(y0 + y1) - x0y0 - x1y1for(int i = 0; i < n; ++i) r[i + m] += tmp[i]; // * B^m}
μ΄ μκ³ λ¦¬μ¦μ ꡬνμ μ΄ν΄λ³΄λ©΄, λΆν μ 볡μ νλ κ²½μ°μ μκ°λ³΅μ‘λ κ³μ°μ μ΄μ©νμ¬ μκ°λ³΅μ‘λλ₯Ό ꡬν μ μλ€. κ·Έλ΄λ―νκ² μκ³ λ¦¬μ¦μ μ΄λ»κ² λΆν νλ©΄μ νκ³ μλλ νλ©΄, ꡬκ°μ΄ λ‘ μ€μ΄λ€ λλ§λ€, κ°μ νμ λ¬Έμ κ° μκΈ°κ³ μλ€. λν, μ΄λ¬ν νμλ¬Έμ λ₯Ό ν©μΉλλ° κ±Έλ¦¬λ μκ°μ΄ μ΄λ€. μ΄ κ²½μ°λ, μΈ κ²½μ°μ μνκΈ° λλ¬Έμ, μκ°λ³΅μ‘λλ μ΄ λ¬Έμμμ λ³Έ κ²μ²λΌ κ³μ°ν μ μλ€. κ²°κ³Όλ§ λ³΄λ©΄,
μ΄ λλ€.