Karatsuba alqoritmi

"Daha yaxşı" vurma

Sizdən soruşsaydım ki, $1934 \times 5667$ neçə edir, necə hesablayardınız? Böyük ehtimal, birinci ədədin hədlərini hər dəfəsində sola sürüşdürməklə bir-bir ikinci ədədin hədlərinə vurardınız. Əlbəttə, burda böyük nöqsan yoxdur, lakin bu üsulun zaman mürəkkəbliyinə baxsaq, $O(n^2)$ olduğunu görərik, çünki bütün hədlər bir-birinə vurulur. Bəs bunu daha sürətli etməyin bir yolu varmı?

Əvvəlcə, gəlin, ədədləri tən ortadan ikiyə parçalayaq və hər bir hissəyə ad verək:

$$\begin{array}{r} {\color{blue} 19} {\color{green} 34} \\ \times \quad {\color{red} 56} {\color{orange} 67} \end{array} \Rightarrow \begin{array}{r} {\color{blue} a} {\color{green} b} \\ \times \quad {\color{red} c} {\color{orange} d} \end{array}$$

Beləliklə, vurma əməlimiz nəticəsi aşağıdakı kimi olur:

$$(100a+b) \cdot (100c+d) = ac \cdot 10^4 + (ad+bc) \cdot 100 + bd$$

Hələ də 4 vurma əməli yerinə yetiririk, bəs onu artırmaqla azaltmaq olar? Bunun üçün mötərizə daxilindəki ifadəmizi genişləndirək:

$$ac \cdot 10^4 + (ad+bc+ac+bd-ac-bd) \cdot 100 + bd \\ = ac \cdot 10^4 + (a \cdot (d+c)+b\cdot(d+c) - ac - bd) \cdot 100 + bd$$

Və, nəhayət, ifadəmiz belə olur:

$$ac \cdot 10^4 + ((a+b) \cdot (c+d) - ac - bd)) \cdot 100 + bd$$

Oxucu sual edə bilər ki, əvvəl 4 vurma əməlimiz var idi, indi isə 5, bəs məqsədimiz onu azaltmaq deyildi? Düzdür, vurma əməlimizin sayı artıb, lakin diqqət yetirsək, görərik ki, $ac$ və $bd$ hədləri iki dəfə təkrarlanır və onları ikinci dəfə hesablamağımıza ehtiyac yoxdur, buna görə də vurmaların sayını dörddən üçə endirdiyimizi deyə bilərik. Üsul çox sadə görünsə də, zaman mürəkkəbliyini $O(n^{\log_2{3}}) \approx O(n^{1.58})$-ə qədər azalda bilir və yalnız 1960-da sovet alimi Anatoli Karatsuba tərəfindən kəşf edilib və Karatsuba alqoritmi adlanır.

İndi isə yuxarıdakı addımları istənilən uzunluqlu ədədlər üçün ümumiləşdirək. Hesab edək ki, hər iki ədədin $n$ rəqəmi var, bu halda ədədi $\left\lceil \frac{n}{2} \right\rceil$ uzunluqlu 2 hissəyə ayıra bilərik. Burada yuxarı yuvarlaqlaşdırmadan istifadə edirik, çünki ayırarkən ədədin heç bir həddi kənarda qalmamalıdır və ədədin uzunluğu $2\cdot\left\lceil \frac{n}{2} \right\rceil$-dən kiçik olarsa, asanlıqla ədədin soluna $0$ əlavə edərək istənilən uzunluğa çatdıra bilərik. Lakin növbəti abzaslarda və proqram nümunəsində görəcəyiniz kimi aşağı və ya yuxarı yuvarlaqlaşdırmanın, adətən, bir fərqi yoxdur. Bundan sonra işlər sadələşir:

$$(10^{\left\lceil \frac{n}{2} \right\rceil} a+b) \cdot (10^{\left\lceil \frac{n}{2} \right\rceil}c+d) \\ = ac \cdot 10^{2\cdot\left\lceil \frac{n}{2} \right\rceil} + (ad+bc) \cdot 10^{\left\lceil \frac{n}{2} \right\rceil} + bd$$

Beləcə, son düsturumuz:

$$ac \cdot 10^{2\cdot\left\lceil \frac{n}{2} \right\rceil} + ((a+b)\cdot(c+d)-ac-bd) \cdot 10^{\left\lceil \frac{n}{2} \right\rceil} + bd$$

olur.

Diqqət yetirsəniz, görərsiniz ki, parçalanmış hissələr üzərində də ($ac, bd, (a+b)\cdot(c+d)$) rekursiv olaraq Karatsuba alqoritmini tətbiq etmək olar, ta ki ədədləri vurmaq asanlaşana qədər.

Proqramlaşdırmada tətbiqi

Bildiyimiz kimi, kriptoqrafiyada istifadə olunan sadə ədədlər 384 bit və ya 116 rəqəmə çata bilir. Digər riyazi əməllərin də ağırlığını və vurmanın həddən artıq istifadəsini nəzərə alsaq, adi vurma alqoritminin kriptoqrafiyanı nə qədər yavaşladacağını düşünmək çətin olmaz. Məhz bu səbəbdən müasir kriptoqrafiyada böyük ədədləri vurarkən Karatsuba alqoritmi istifadə edilir.

İndi isə Python-da Karatsuba alqoritminin necə tətbiq edildiyinə baxaq:

def karatsuba(num1: str, num2: str) -> int:
    # Vurmaq asandırsa, adi şəkildə vuraq
    if len(num1) < 2 or len(num2) < 2:
        return int(num1) * int(num2)
    
    n = max(len(num1), len(num2))
    n_2 = n // 2
    
    # Ədədləri n uzunluğa tamamlayaq
    num1 = num1.zfill(n) 
    num2 = num2.zfill(n)
    
    # Ədədləri iki hissəyə parçalayaq
    a, b = num1[:-n_2], num1[-n_2:] 
    c, d = num2[:-n_2], num2[-n_2:]
    
    bd = karatsuba(b, d)
    ac = karatsuba(a, c)
    
    # a+b
    s1 = str(int(a) + int(b)) 
    # c+d
    s2 = str(int(c) + int(d)) 
    # (a+b)*(c+d) - ac - bd
    z0 = karatsuba(s1, s2) - ac - bd 
    
    # Sonda isə ədədi bərpa edirik
    return (ac * 10**(2 * n_2)) + (z0 * 10**n_2) + bd 

La Fin

Əlqərəz, Karatsuba alqoritmi göstərir ki, bəzən düsturu fərqli şəkildə yazmaq və yaxud ona kiçik bir düzəliş etmək məsələni həll edir. Qaqalar demişkən,

"Nöqtə kiçik də olsa, cümlə bitirir".

Görüşənədək.