Karatsuba大整数乗算アルゴリズム

私たちが普段接触している長乗算は,ビットで乗算され,時間的複雑度がO(n^2)のアルゴリズムである.今日は、時間複雑度O(n^log 3)の大きな整数乗算(logは2をベースとした対数を表す)について紹介します.
原理を紹介する
karatsubaアルゴリズムは乗数と被乗数が以下のいくつかの条件を満たすことを要求し、第一に、乗数は被乗数の桁数と同じである.第二に、乗数と被乗数の桁数は2乗でなければならない.すなわち、2^2、2^3、2^4、2^nなどの数値である.
次に、いくつかの簡単な例を見て、karatsubaアルゴリズムの使用方法を理解します.
2桁乗算
被乗数A=85,乗数B=41とする.次の手順について説明します.
A,Bを二つに分けて,p＝Aの前半＝8,q＝Aの後半＝5,r＝Bの前半＝4,s＝Bの後半＝1,n＝2とする.簡単な数学演算により、
A * B = pq * rs = (p * 10 + q) * (r * 10 + s) = p * r * 10 ^ 2 + (p * s + q * r ) * 10 + q * s.u=p*r,v=
(p - q) * (s - r),w = q * s. だからA*B=u*10^2+(u+v+w)*10+w.
数値に変換して解く過程は以下の通りです.
A * B = 85 * 41 = (8 * 10 + 5) * ( 4 * 10 + 1) = 8 * 4 * 10 * 10 + (8 * 1 + 5 * 4) * 10 + 5 * 1.ここで,u＝8＊4＝32,v＝(8−5)(1−4)＝−9,w＝5＊1＝5である.したがって、A*B=32*100+(32-9+5)*10+5=3485である.長乗算で得られた結果と一致した.
4桁の乗算
被乗数A=8537,乗数B=4123とする.次の手順について説明します.
A,Bを二つに分けて,p＝Aの前半＝85,q＝Aの後半＝37,r＝Bの前半＝41,s＝Bの後半＝23,n＝4とした.
=>>ここで、u=85*41、v=(85-37)*(23-41)、w=37*23である.
==> A * B = 8537 * 4123 = u * 10 ^ 4 + (u + v + w) * 10 ^ 2 + w = 3485_0000 +34_7200 + 851 = 35198051.
u,v,wを計算する過程でまた2桁の乗算に関与し,Karatsubaアルゴリズムを用いて2桁の乗算結果を得続けた.
Nビット数乗算
nを乗数と被乗数の桁数とし,p=Aの前半,q=Aの後半,r=Bの前半,s=Bの後半とする.
==>ここで、u=p*r、v=(p−q)*(s−r)、w=q*sである.だからA*B=u*10^n+(u+v+w)*10^(n/2)+w.
u,v,wは2つのn/2ビットの乗算である.Karatsubaアルゴリズムjを呼び出してu,v,wの数値を計算し続けた.次に、n/2乗算を計算する過程でn/4ビットの乗算に遭遇します......このように、2つのビット数の乗算に遭遇するまで、私たちは直接この2つのビット数乗算の結果を返します.各層が戻り,最終的にNビット数の乗算結果が得られる.
時間の複雑さ
私たちが普段使っている長乗算は、O(n^2)の時間的複雑さです.例えば、2つのNビット数を乗算するには、各ビットを規則的に乗算する必要があるので、N*N乗算を計算する必要があります.一方,Karatsubaアルゴリズムを用いると,各層に3回の乗算,2回の加算,およびいくつかの加算が必要であり,karatsubaアルゴリズムを用いるたびに乗算規模は半分に減少する.したがって,2つのn=2^Kビット数乗算に対して,3^k回の乗算を計算する必要がある.一方、K=log n(ベース数2)、3^K=3^log n=2^(log 3*log n)=2^(log n*log 3)=n^log 3(ベース数2).
コード実装

#        ：Python    
from math import log2, ceil

def pad(string: str, real_len: int, max_len: int) -> str:
    pad_len: int = max_len - real_len
    return f"{'0' * pad_len}{string}"


def kara(n1: int, n2: int) -> int:
    if n1 < 10 or n2 < 10:
        return n1 * n2
    n1_str: str = str(n1)
    n2_str: str = str(n2)
    n1_len: int = len(n1_str)
    n2_len: int = len(n2_str)
    real_len: int = max(n1_len, n2_len)
    max_len: int = 2 ** ceil(log2(real_len))
    mid_len: int = max_len >> 1
    n1_pad: str = pad(n1_str, n1_len, max_len)
    n2_pad: str = pad(n2_str, n2_len, max_len)
    p: int = int(n1_pad[:mid_len])
    q: int = int(n1_pad[mid_len:])
    r: int = int(n2_pad[:mid_len])
    s: int = int(n2_pad[mid_len:])
    u: int = kara(p, r)
    v: int = kara(q-p, r-s)
    w: int = kara(q, s)
    return u * 10 ** max_len + (u+v+w) * 10 ** mid_len + w

出力結果:
==> kara(123456, 9734) == 123456 * 9734
==> kara(1234233456756, 32459734) == 1234233456756 * 32459734