الگوریتم کاراتسوبا

تاریخچه

در سال ۱۹۵۲ آندره کولوموگوروف ادعا کرد که الگوریتم ضرب کلاسیک از نظر پیچیدگی زمانی
بهینه‌است و هر الگوریتم دیگری که برای ضرب دو عدد ارائه شود، حداقل  عملیات نیاز دارد. سپس در پاییز ۸ سال بعد یعنی سال ۱۹۶۰، در دانشکده مکانیک و ریاضی داشگاه مسکو، سمیناری برگزار و این ادعا را در زمینه پیچیدگی محاسباتی مطرح کرد.

در کمتر از یک هفته، کاراتسوبا که در آن زمان ۲۳ ساله بود، الگوریتمی ارائه کرد که به  عملیات نیاز داشت و به این ترتیب فرضیه کولوموگوروف را رد کرد.
او فرضیه خود را بعد از سمینار بعدی با کولوموگوروف در میان گذاشت. کولوموگوروف از این موضوع بسیار آشفته شد، به این خاطر که این الگوریتم به‌طور کامل نظریهٔ او را رد می‌کرد.

دو سال بعد کولوموگوروف این الگوریتم به صورت مقاله‌ای کوتاه درآورد و نام کاراتسوبا را در آن قرار داد. نکته جالب توجه آن است که کاراتسوبا پس از انتشار مقاله، از آن باخبر شد.

بعد از انتشار این الگوریتم، روشی که کاراتسوبا به کار برد به نام روش تقسیم و حل (divide and conquer)
نامیده شد.

پیدایش روش تقسیم و حل، نقطه شروع نظریه محاسبات سریع بود. پژوهشگرانی مانند توم، کوک و استراسن تلاش‌های زیادی در این زمینه انجام دادند، که الگوریتم استراسن بهترین الگوریتم از منظر زمان اجرا در این
زمینه‌است.

روش تقسیم و حل کاراتسوبا، از پایه‌ای‌ترین روش‌ها در این زمینه‌است. صدها الگوریتم بر پایهٔ این الگوریتم به وجود آمده‌اند که مهمترین و مشهورترین آنها، الگوریتم ضرب بر پایه تبدیل سریع فوریه است.

تحلیل دقیق‌تر زمان اجرا

با رسم درخت بازگشت این الگوریتم، شهود بهتری نسبت به آن در این حالت خاص، بدست می‌آید. درخت بازگشت را در شکل زیر در نظر بگیرید.
در هر عمق از این درخت مسئله به ۳ مسئله با اندازه نصف تبدیل می‌شود. در عمق (log۲(n به زیر مسئله‌ای با اندازه یک تبدیل می‌شود و روند بازگشتی متوقف می‌شود؛ بنابراین ارتفاع درخت برابر (log۲(n است.

اگر عمقی مانند k را در نظر گرفته شود، ۳ᵏ زیر مسئله با اندازه n /2ᵏ وجود دارد. برای هر کدام از این زیر مسئله‌ها، کافی است عملیاتی با هزینهٔ خطی بپردازیم. این عملیات شامل جمع کردن زیرمسئله‌ها و تقسیم‌کردن هر کدام به زیرمسئله‌هایی کوچکتر است؛ بنابراین، در عمق kام هزینه‌ای معادل زیر پرداخت می‌کنیم:
۳ᵏO(n/2ᵏ) = (۳/۲)ᵏ O(n)
حال اگر همهٔ هزینه‌ها را در عمق‌های مختلف جمع کنیم، هزینه کل برابر (O(nˡᵒᵍ³۲ خواهد شد. در حالیکه اگر در هر مرحله به ۴ زیرمسئله تقسیم می‌شد و از این نکته استفاده نمی‌شد، زمان اجرا برابر (O(n۲ می‌شود.
به کمک قضیهٔ اصلی نیز می‌توان زمان اجرا را محاسبه کرد که به همین نتیجه ختم خواهد شد.

حالت کلی

در این قسمت حالت کلی الگوریتم کاراتسوبا توضیح داده می‌شود.

فرض کنید X و Y دو عدد n رقمی در مبنای B هستند. به ازای هر m کوچکتر از n می‌توان این دو عدد را به صورت زیر نوشت:
XY = (x۱Bᵐ + x۰) (y۱Bᵐ + y۰)

XY = x۱y۱B²ᵐ + (x۱y۰ + x۰y۱)Bᵐ + x۰y۰
مشابه ایده‌ای که در بالا گفته شد می‌توان این ۴ ضرب را تنها با ۳ ضرب و چند عملیات جمع اضافه انجام داد. کافی است به جای (x۱y۰ + x۰y۱)
از x۱+x۰) (y۱+y۰) - x۰y۰ - x۱y۱) استفاده کنیم؛ بنابراین:
XY = x۱y۱B²ᵐ + ((x۱+x۰)(y۱+y۰) - (x۰y۰) - (x۱y۱)Bᵐ + x۰y۰

پیاده‌سازی

شبه‌کد الگوریتم به صورت زیر است:
 1 Algorithm karatsuba_multiplication(X,Y)
 2 Input: X and Y two binary number)
 3 Output: product of X and Y
 4 begin
 5 if n = 1: return xy
 6 x۱ = X>> n/2
 7 x۰ = X mod 2 n/2
 8 y۱ = Y>> n/2
 9 y۰ = Y mod 2 n/2
 10 x۲ = x۱ + x۰
 11 y۲ = y۱ + y۰
 12 R۱ = multiply(x۱ , y۱)
 13 R۲ = multiply(x۰ , y۰)
 14 R۳ = multiply(x۲ , y۲)
 15 return R۱ × ۲ⁿ + (R۳ − R۱ − R۲) × ۲n/2 + R۲
 16 end
پیاده‌سازی الگوریتم با استفاده از جاوا:
import java.math.BigInteger;import java.util.Random;class Karatsuba {
    private final static BigInteger ZERO = new BigInteger("0");

    public static BigInteger karatsuba(BigInteger x, BigInteger y) {

        // cutoff to brute force
        int N = Math.max(x.bitLength(), y.bitLength());
        if (N <= 2000) return x.multiply(y);                // optimize this parameter

        // number of bits divided by 2, rounded up
        N = (N / 2) + (N % 2);

        // x = a + 2^N b,   y = c + 2^N d
        BigInteger b = x.shiftRight(N);
        BigInteger a = x.subtract(b.shiftLeft(N));
        BigInteger d = y.shiftRight(N);
        BigInteger c = y.subtract(d.shiftLeft(N));

        // compute sub-expressions
        BigInteger ac    = karatsuba(a, c);
        BigInteger bd    = karatsuba(b, d);
        BigInteger abcd  = karatsuba(a.add(b), c.add(d));

        return ac.add(abcd.subtract(ac).subtract(bd).shiftLeft(N)).add(bd.shiftLeft(2*N));
   }

    public static void main(String[] args) {
        long start, stop, elapsed;
        Random random = new Random();
        int N = Integer.parseInt(args[0]);
        BigInteger a = new BigInteger(N, random);
        BigInteger b = new BigInteger(N, random);

        start = System.currentTimeMillis();
        BigInteger c = karatsuba(a, b);
        stop = System.currentTimeMillis();
        System.out.println(stop - start);

        start = System.currentTimeMillis();
        BigInteger d = a.multiply(b);
        stop = System.currentTimeMillis();
        System.out.println(stop - start);

        System.out.println((c.equals(d)));
   }}
پیاده‌سازی الگوریتم با استفاده از پایتون:
_CUTOFF = ۱۵۳۶;def multiply(x, y):
    if x.bit_length() <= _CUTOFF or y.bit_length() <= _CUTOFF:  # Base case
        return x * y;

    else:
        n = max(x.bit_length(), y.bit_length())
        half = (n + 32) / 64 * 32
        mask = (۱ <<half) - 1
        xlow = x & mask
        ylow = y & mask
        xhigh = x>> half
        yhigh = y>> half

        a = multiply(xhigh, yhigh)
        b = multiply(xlow + xhigh, ylow + yhigh)
        c = multiply(xlow, ylow)
        d = b - a - c
        return (((a <<half) + d) <<half) + c

الگوریتم کاراتسوبا در عمل

همان طور که دیدیم الگوریتم به صورت بازگشتی مسئله را به زیر مسئله‌هایی با اندازه نصف مسئله اولیه تبدیل کرده و این کار را تا
تبدیل آن به زیر مسئله‌ای با اندازه یک ادامه می‌دهد. دلیل این کار این است که فرض شده‌است عمل ضرب دو عدد یک رقمی در(1)O
انجام می‌گیرد.
در حالیکه در پردازنده‌های امروزی این گونه نیست بسیاری از پردازنده‌ها ضرب ۱۶ بیتی یا ۳۲ بیتی را در یک عملیات انجام می‌دهند.
یعنی در معماری این پردازنده‌ها واحد ضرب‌کننده ۳۲ بیتی یا ۱۶ بیتی وجود دارد.
به همین خاطر در عمل لازم نیست که به صورت بازگشتی با زیر مسئله‌ای با اندازه ۱ پایین برویم. با داشتن آگاهی نسبت به معماری پردازنده، می‌توان B و m را به گونه‌ای انتخاب کرد که کارایی و زمان اجرای بهتری از الگوریتم بدست آید.