Day 143-Q5 | Karatsuba法

問題

2つの非負整数$A,B$（10進数文字列、それぞれ最大$10^5$桁）が与えられる。$A\times B$を求めよ。

Karatsuba法の手順

$x,y$をそれぞれ桁数の半分$m$で上位・下位に分割：$x=x_1\cdot10^m+x_0$、$y=y_1\cdot10^m+y_0$。

素朴には4回の乗算（$x_1y_1,x_1y_0,x_0y_1,x_0y_0$）が必要だが、次の3回で済ませられる：

$$z_2=x_1y_1,\quad z_0=x_0y_0,\quad z_1=(x_1+x_0)(y_1+y_0)-z_2-z_0$$

このとき$x_1y_0+x_0y_1=z_1$が成り立つ。よって$x\times y=z_2\cdot10^{2m}+z_1\cdot10^m+z_0$を再帰的に計算する。桁数が十分小さくなったら（本問では64桁未満）直接乗算に切り替えて再帰を打ち切る。

入力形式

A
B

制約

$A,B$は非負整数の10進表記

桁数はそれぞれ最大$10^5$

入出力例

入力例1

1234
5678

出力例1

入力例2

0
999

出力例2

概念図：4回の乗算を3回に減らす

ヒント（段階的開示）

ヒント1（方向性）

筆算による多倍長乗算は$O(n^2)$。単純に4分割すると$T(n)=4T(n/2)+O(n)$となり結局$O(n^2)$のまま。乗算の回数そのものを4回から3回に減らす工夫が核心。

ヒント2（アプローチ）

$x_1y_0+x_0y_1$という「本来2回の乗算が必要な項」を、$(x_1+x_0)(y_1+y_0)$という1回の乗算から$z_2,z_0$を引くことで復元できる。これにより$T(n)=3T(n/2)+O(n)$、マスター定理より$O(n^{\log_2 3})\approx O(n^{1.585})$。

ヒント3（誘導）

THRESHOLD = 64

def digit_len(x):
    return len(str(x)) if x else 1

def karatsuba(x, y):
    if x < 10 ** THRESHOLD or y < 10 ** THRESHOLD:
        return x * y  # 基底ケース

    n = max(digit_len(x), digit_len(y))
    m = n // 2
    scale = 10 ** m

    x1, x0 = divmod(x, scale)
    y1, y0 = divmod(y, scale)

    z2 = karatsuba(x1, y1)
    z0 = karatsuba(x0, y0)
    z1 = karatsuba(x1 + x0, y1 + y0) - z2 - z0

    return z2 * (10 ** (2 * m)) + z1 * scale + z0

模範解答 (Python)

import sys

sys.setrecursionlimit(10000)

THRESHOLD = 64

def digit_len(x):
    return len(str(x)) if x else 1

def karatsuba(x, y):
    if x < 10 ** THRESHOLD or y < 10 ** THRESHOLD:
        return x * y

    n = max(digit_len(x), digit_len(y))
    m = n // 2
    scale = 10 ** m

    x1, x0 = divmod(x, scale)
    y1, y0 = divmod(y, scale)

    z2 = karatsuba(x1, y1)
    z0 = karatsuba(x0, y0)
    z1 = karatsuba(x1 + x0, y1 + y0) - z2 - z0

    return z2 * (10 ** (2 * m)) + z1 * scale + z0

def main():
    A = int(sys.stdin.readline().strip())
    B = int(sys.stdin.readline().strip())
    print(karatsuba(A, B))

main()

Step-by-Step 解説

14回の乗算を3回に減らす代数トリック
$(x_1+x_0)(y_1+y_0)=x_1y_1+x_1y_0+x_0y_1+x_0y_0$を展開して$z_2,z_0$を引けば$x_1y_0+x_0y_1$が得られる。乗算はこの1回とz2,z0の合計3回。

2再帰の漸化式とマスター定理
$T(n)=3T(n/2)+O(n)$（$\log_2 3\approx1.585>1$）より$T(n)=O(n^{\log_2 3})$。筆算のO(n²)より漸近的に高速。

3基底ケースの重要性
再帰を桁数1まで続けると関数呼び出しオーバーヘッドが支配的になる。ある桁数以下（本解答は64桁）で直接乗算に切り替える。

4NTTとの違い
より大規模な乗算ではO(n log n)のNTTが使われるが、Karatsuba法は実装が単純で定数倍が小さく中規模乗算で有利。

5具体例のトレース
A=1234,B=5678はともに10^64未満のため即座に基底ケースに入り、直接1234*5678=7006652を計算する。

よくあるミス

ミス	原因	正しい書き方
4分割のまま単純に再帰してしまう	桁を半分にすることだけに気を取られ乗算回数削減を忘れる	(x1+x0)(y1+y0)-z2-z0で中間項を1回の乗算にまとめる
分割位置mを固定し桁数の違いを考慮しない	桁数が大きく異なる2数の乗算で非効率になる	m=max(digit_len(x),digit_len(y))//2のように大きい方に合わせる
基底ケースの閾値を設けず桁数1まで再帰	理論的な速さと実際の速さを混同	ある程度小さい桁数で直接乗算に切り替える閾値を設ける
10*(2m)のような累乗計算を毎回内側で行う	桁シフトのコストを軽視	実運用では文字列/配列のインデックスシフトで実装する
z1が負になり得ることを他言語移植時に見落とす	Pythonのintは任意精度で負数も正しく扱えるため意識しにくい	C++等固定長整数への移植時はz1の符号処理を明示する

次のステップ

発展: Karatsuba法を3分割・4分割に一般化したToom-Cook法を調べ、乗算回数と定数倍のトレードオフを比較せよ。
発展2: 2進数ビット列としてKaratsuba法を実装し、Pythonの組み込みint乗算と実行時間を比較せよ。

自己評価

完全理解おおむね理解要復習

Day 143-Q5 — Karatsuba法（分割統治による大整数高速乗算）

問題