نمایش مبدأ برای الگوریتم کاراتسوبا

{{تمیزکاری}}
{{جعبه اطلاعات الگوریتم
| کلاس           = [[الگوریتم ضرب چندجمله‌ای]]
| تصویر         =
| زیرنویس تصویر =
| داده‌ها        =
| زمان بدترین   = <math>n^{\log_23}</math>
| زمان بهترین   =
| زمان متوسط    =
| پیچیدگی فضایی =
}}
[[پرونده:A.A.Karatsuba graduate.jpg|بندانگشتی|آناتولی کاراتسوبا]]
'''الگوریتم کاراتسوبا''' یک الگوریتم سریع برای ضرب اعداد است. الگوریتم کاراتسوبا اولین الگوریتمی است که به صورت مجانبی سریع است.
این الگوریتم برای اولین‌بار توسط [[آناتولی کاراتسوبا]] در سال ۱۹۶۲ ارائه شد.<ref name="kara1962">
  {{cite journal
  | author = A. Karatsuba and Yu. Ofman
  | title = Multiplication of Many-Digital Numbers by Automatic Computers
  | journal = Proceedings of the USSR Academy of Sciences
  | volume = ۱۴۵
  | year = ۱۹۶۲
  | pages = ۲۹۳–۲۹۴
  | note = Translation in Physics-Doklady, 7 (1963), pp. 595–596}}</ref>
این الگوریتم با استفاده از [[روش تقسیم و حل]] تعداد عملیات ضرب لازم برای ضرب دو عدد n رقمی را کاهش می‌دهد.
{{سخ}}
در عملیات ضرب معمولی که در دبیرستان آموزش داده می‌شود، به تعداد n<sup>۲</sup> عملیات ضرب لازم است. این الگوریتم تعداد عملیات ضرب را به 3n<sup>log3<sub>۲</sub></sup> می‌رساند.
{{سخ}}
۳ سال بعد ارائه این الگوریتم توسط کاراتسوبا، الگوریتم [[:w:en:Toom-Cook multiplication|Toom-Cook algorithm]] ارائه شد که حالت کلی‌تر و سریع‌تر همین الگوریتم است.
علاوه بر این در سال ۱۹۷۱ الگوریتم [[:w:en:Schönhage–Strassen algorithm|Schönhage–Strassen algorithm]] ارائه شد که برای اعداد بزرگ از الگوریتم کاراتسوبا سریع‌تر است و بهتر عمل می‌کند.

== تاریخچه ==
در سال ۱۹۵۲ [[:w:en:Andrey Kolmogorov|آندره کولوموگوروف]] ادعا کرد که الگوریتم ضرب کلاسیک از نظر [[پیچیدگی زمانی]]
بهینه‌است و هر الگوریتم دیگری که برای ضرب دو عدد ارائه شود، حداقل <math>\Omega(n^2)</math> عملیات نیاز دارد. سپس در پاییز ۸ سال بعد یعنی سال ۱۹۶۰، در دانشکده مکانیک و ریاضی [[:w:en:Moscow State University|داشگاه مسکو]]، سمیناری برگزار و این ادعا را در زمینه [[پیچیدگی محاسباتی]] مطرح کرد.<ref>http://www.ccas.ru/personal/karatsuba/divcen.pdf</ref>
{{سخ}}
در کمتر از یک هفته، کاراتسوبا که در آن زمان ۲۳ ساله بود، الگوریتمی ارائه کرد که به <math>\Theta(n^{\log_2 3})</math> عملیات نیاز داشت و به این ترتیب فرضیه کولوموگوروف را رد کرد.
او فرضیه خود را بعد از سمینار بعدی با کولوموگوروف در میان گذاشت. کولوموگوروف از این موضوع بسیار آشفته شد، به این خاطر که این الگوریتم به‌طور کامل نظریهٔ او را رد می‌کرد.
{{سخ}}
دو سال بعد کولوموگوروف این الگوریتم به صورت مقاله‌ای کوتاه درآورد و نام کاراتسوبا را در آن قرار داد. نکته جالب توجه آن است که کاراتسوبا پس از انتشار مقاله، از آن باخبر شد.
{{سخ}}
بعد از انتشار این الگوریتم، روشی که کاراتسوبا به کار برد به نام روش تقسیم و حل ([[:w:en:Divide and conquer algorithm|divide and conquer]])
نامیده شد.
{{سخ}}
پیدایش روش تقسیم و حل، نقطه شروع [[نظریه محاسبات]] سریع بود. پژوهشگرانی مانند [[:w:en:Andrei Toom|توم]]، [[:w:en:Stephen Cook|کوک]] و [[:w:en:Volker Strassen|اشتغاسن]] تلاش‌های زیادی در این زمینه انجام دادند، که [[:w:en:Schönhage–Strassen algorithm|الگوریتم اشتغاسن]] بهترین الگوریتم از منظر زمان اجرا در این
زمینه‌است.
{{سخ}}
روش تقسیم و حل کاراتسوبا، از پایه‌ای‌ترین روش‌ها در این زمینه‌است. صدها الگوریتم بر پایهٔ این الگوریتم به وجود آمده‌اند که مهمترین و مشهورترین آنها، الگوریتم ضرب بر پایه [[تبدیل سریع فوریه]] است.

== الگوریتم ==
=== حالت خاص ===
الگوریتم به روش تقسیم و حل عمل می‌کند. به این معنا که ابتدا هر کدام از اعداد را به قسمت‌های کوچکتر تقسیم کرده و سپس به صورت بازگشتی، روی آن‌ها ضرب را انجام می‌دهد.
{{سخ}}
ابتدا حالت ساده‌ای را در نظر می‌گیریم. این حالت به راحتی قابل تعمیم به روش کلی است.
{{سخ}}
فرض کنید عدد اول X و عدد دوم Y است. هر دو [[عدد صحیح]] و در [[مبنای دو]] و دارای n رقم که n توانی از ۲ است.
در ابتدا دو عدد مطابق شکل به دو قسمت تقسیم می‌شوند. X<sub>۱</sub> قسمت پرارزش و X<sub>۰</sub> قسمت کم‌ارزش است. به صورت مشابه، برای Y هم به همین صورت است.
پس داریم:
[[پرونده:Dividing karatsuba.jpg|بندانگشتی|وسط|300px|تقسیم عددها به دو قسمت]]{{سخ}}
{{چپ‌چین}}
X = X<sub>۱</sub> ۲<sup>(n/2)</sup> + X<sub>۰</sub>
{{سخ}}
Y= Y<sub>۱</sub> ۲<sup>(n/2)</sup> + Y<sub>۰</sub>
{{سخ}}
{{پایان چپ‌چین}}
به این ترتیب ضرب ''XY'' به صورت زیر در می‌آید:
{{سخ}}
{{سخ}}
{{چپ‌چین}}
XY = (X<sub>۱</sub> ۲<sup>(n/2)</sup> + X<sub>۰</sub>) (Y<sub>۱</sub> ۲<sup>(n/2)</sup> + Y<sub>۰</sub>)
{{سخ}}
XY = x<sub>۱</sub>y<sub>۱</sub>۲<sup>n</sup> + (x<sub>۱</sub>y<sub>۰</sub> + x<sub>۰</sub>y<sub>۱</sub>)۲<sup>(n/2)</sup> + x<sub>۰</sub>y<sub>۰</sub>
{{پایان چپ‌چین}}

در مبنای ۲، ضرب یک عدد در توانی از ۲، به صورت عملیات شیفت در کامپیوتر به راحتی انجام می‌شود. عملیات شیفت و جمع، در مقابل عملیات ضرب، زمان اجرای بسیار کمی دارند. به همین
خاطر، زمان اجرای آن را از (1)[[:w:en:Big O notation|O]] در نظر می‌گیرند.
حال مسئله به ۴ زیرمسئله با اندازهٔ نصف مسئله قبلی تبدیل شده‌است؛ بنابراین می‌توان این ۴ مسئله را به روش بازگشتی حل و در زمان خطی، عبارت کلی را محاسبه کرد. پیچیدگی
زمانی رابطه بالا به صورت زیر است:
{{سخ}}
{{سخ}}
{{چپ‌چین}}
T(n) = 4T(n/2) + O(n)

{{پایان چپ‌چین}}
{{سخ}}
که '' (T(n '' زمان اجرای برای ضرب دو عدد '' n ''بیتی است. زمان اجرای آن از (O(n است.
{{سخ}}
پس هنوز بهبودی صورت نیافته‌است.
{{سخ}}
با یک راه حل ساده می‌توان تعداد ضرب‌های انجام شده را از ۴ به ۳ رساند.
{{سخ}}
فرض کنید:
{{چپ‌چین}}
x<sub>۲</sub> = x<sub>۱</sub> + x<sub>۰</sub>
{{سخ}}
y<sub>۲</sub> = y<sub>۱</sub> + y<sub>۰</sub>
{{پایان چپ‌چین}}
با داشتن x<sub>۲</sub> و y<sub>۲</sub> می‌توان تنها با استفاده از ۳ جمله این ضرب را انجام داد. به این ترتیب که به جای جملهٔ (x<sub>۱</sub>y<sub>۰</sub> + x<sub>۰</sub>y<sub>۱</sub>)
از(x<sub>۲</sub>y<sub>۲</sub> – x<sub>۰</sub>y<sub>۰</sub> - x<sub>۱</sub>y<sub>۱</sub>) استفاده کنیم.
{{سخ}}
به این ترتیب برای انجام مرحلهٔ بازگشتی تنها به ۳ جمله نیاز است:
{{چپ‌چین}}
* x<sub>۰</sub>y<sub>۰</sub>
* x<sub>۱</sub>y<sub>۱</sub>
* x<sub>۲</sub>y<sub>۲</sub>
{{پایان چپ‌چین}}
پس زمان اجرا به صورت زیر در می‌آید:
{{چپ‌چین}}
T(n) = 3T(n/2) + O(n)
{{سخ}}-->T(n) = O(n<sup>log3<sub>۲</sub></sup>)
{{پایان چپ‌چین}}
با این ترفند ساده به راحتی زمان اجرا بهبود یافت.

=== تحلیل دقیق‌تر زمان اجرا ===
با رسم [[:w:en:Recursive tree|درخت بازگشت]] این الگوریتم، شهود بهتری نسبت به آن در این حالت خاص، بدست می‌آید. درخت بازگشت را در شکل زیر در نظر بگیرید.

{{سخ}}[[پرونده:Level karat.jpg|بندانگشتی|وسط|700px|درخت بازگشت در الگوریتم کاراتسوبا<ref>http://www.cs.berkeley.edu/~vazirani/algorithms/chap2.pdf</ref>]]
در هر عمق از این درخت مسئله به ۳ مسئله با اندازه نصف تبدیل می‌شود. در عمق (log<sub>۲</sub>(n به زیر مسئله‌ای با اندازه یک تبدیل می‌شود و روند بازگشتی متوقف می‌شود؛ بنابراین ارتفاع درخت برابر (log<sub>۲</sub>(n است.
{{سخ}}
اگر عمقی مانند k را در نظر گرفته شود، ۳<sup>k</sup> زیر مسئله با اندازه n /2<sup>k</sup> وجود دارد. برای هر کدام از این زیر مسئله‌ها، کافی است عملیاتی با هزینهٔ خطی بپردازیم. این عملیات شامل جمع کردن زیرمسئله‌ها و تقسیم‌کردن هر کدام به زیرمسئله‌هایی کوچکتر است؛ بنابراین، در عمق kام هزینه‌ای معادل زیر پرداخت می‌کنیم:
{{چپ‌چین}}
۳<sup>k</sup>O(n/2<sup>k</sup>) = (۳/۲)<sup>k</sup> O(n)

{{پایان وسط‌چین}}
حال اگر همهٔ هزینه‌ها را در عمق‌های مختلف جمع کنیم، هزینه کل برابر (O(n<sup>log3<sub>۲</sub></sup> خواهد شد. در حالیکه اگر در هر مرحله به ۴ زیرمسئله تقسیم می‌شد و از این نکته استفاده نمی‌شد، زمان اجرا برابر (O(n<sup>۲</sup> می‌شود.
به کمک [[:w:en:Master theorem|قضیهٔ اصلی]] نیز می‌توان زمان اجرا را محاسبه کرد که به همین نتیجه ختم خواهد شد.

=== حالت کلی ===
در این قسمت حالت کلی الگوریتم کاراتسوبا توضیح داده می‌شود.
{{سخ}}
فرض کنید X و Y دو عدد n رقمی در مبنای B هستند. به ازای هر m کوچکتر از n می‌توان این دو عدد را به صورت زیر نوشت:
{{چپ‌چین}}
XY = (x<sub>۱</sub>B<sup>m</sup> + x<sub>۰</sub>) (y<sub>۱</sub>B<sup>m</sup> + y<sub>۰</sub>)
{{سخ}}
XY = x<sub>۱</sub>y<sub>۱</sub>B<sup>2m</sup> + (x<sub>۱</sub>y<sub>۰</sub> + x<sub>۰</sub>y<sub>۱</sub>)B<sup>m</sup> + x<sub>۰</sub>y<sub>۰</sub>
{{سخ}}
{{پایان چپ‌چین}}

مشابه ایده‌ای که در بالا گفته شد می‌توان این ۴ ضرب را تنها با ۳ ضرب و چند عملیات جمع اضافه انجام داد. کافی است به جای (x<sub>۱</sub>y<sub>۰</sub> + x<sub>۰</sub>y<sub>۱</sub>)
از x<sub>۱</sub>+x<sub>۰</sub>) (y<sub>۱</sub>+y<sub>۰</sub>) - x<sub>۰</sub>y<sub>۰</sub> - x<sub>۱</sub>y<sub>۱</sub>) استفاده کنیم؛ بنابراین:
{{چپ‌چین}}
XY = x<sub>۱</sub>y<sub>۱</sub>B<sup>2m</sup> + ((x<sub>۱</sub>+x<sub>۰</sub>)(y<sub>۱</sub>+y<sub>۰</sub>) - (x<sub>۰</sub>y<sub>۰</sub>) - (x<sub>۱</sub>y<sub>۱</sub>)B<sup>m</sup> + x<sub>۰</sub>y<sub>۰</sub>
{{پایان چپ‌چین}}

=== مثال ===
فرض کنید می‌خواهیم حاصل‌ضرب دو عدد ۱۲۳۴ و ۵۶۷۸ را بدست آوریم. دو عدد دهدهی هستند پس B = ۱۰ است. m را نیز ۲ انتخاب می‌کنیم.
{{چپ‌چین}}

:۱۲ ۳۴ = ۱۲ × ۱۰<sup>۲</sup> + ۳۴
:۵۶ ۷۸ = ۵۶ × ۱۰<sup>۲</sup> + ۷۸
:''x''<sub>۱</sub>y''<sub>۱</sub> = ۱۲ × ۵۶ = ۶۷۲
:''x''<sub>۰</sub>y''<sub>۰</sub> = ۳۴ × ۷۸ = ۲۶۵۲
:''(x''<sub>۱</sub> + ''x''<sub>۰</sub>)(''y''<sub>۱</sub> + ''y''<sub>۰</sub>) = (۱۲ + ۳۴)(۵۶ + ۷۸) = ۲۸۴۰

:result = 672 × ۱۰۰۰۰ + ۲۸۴۰ × ۱۰۰ + ۲۶۵۲ = '''۷۰۰۶۶۵۲'''.
{{پایان چپ‌چین}}

=== پیاده‌سازی ===
[[شبه‌کد]] الگوریتم به صورت زیر است:
{{چپ‌چین}}
  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<sub>۱</sub> = X>> n/2
  7 x<sub>۰</sub> = X mod 2 <sup>n/2</sup>
  8 y<sub>۱</sub> = Y>> n/2
  9 y<sub>۰</sub> = Y mod 2 <sup>n/2</sup>
  10 x<sub>۲</sub> = x<sub>۱</sub> + x<sub>۰</sub>
  11 y<sub>۲</sub> = y<sub>۱</sub> + y<sub>۰</sub>
  12 R<sub>۱</sub> = multiply(x<sub>۱</sub> , y<sub>۱</sub>)
  13 R<sub>۲</sub> = multiply(x<sub>۰</sub> , y<sub>۰</sub>)
  14 R<sub>۳</sub> = multiply(x<sub>۲</sub> , y<sub>۲</sub>)
  15 '''return''' R<sub>۱</sub> × ۲<sup>n</sup> + (R<sub>۳</sub> − R<sub>۱</sub> − R<sub>۲</sub>) × ۲<sup>n/2</sup> + R<sub>۲</sub>
  16 '''end'''
{{پایان چپ‌چین}}
پیاده‌سازی الگوریتم با استفاده از [[جاوا (زبان برنامه‌نویسی)|جاوا]]:<ref>{{یادکرد وب |url=http://introcs.cs.princeton.edu/java/78crypto/Karatsuba.java.html |title=Karatsuba.java<!-- عنوان تصحیح شده توسط ربات --> |accessdate=۷ دسامبر ۲۰۱۱ |archiveurl=https://web.archive.org/web/20110625095620/http://introcs.cs.princeton.edu/java/78crypto/Karatsuba.java.html |archivedate=۲۵ ژوئن ۲۰۱۱ |dead-url=yes }}</ref>
{{چپ‌چین}}
<syntaxhighlight lang="java">

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)));
   }
}
</syntaxhighlight>
{{پایان چپ‌چین}}
پیاده‌سازی الگوریتم با استفاده از [[پایتون]]:<ref>http://nayuki.eigenstate.org/res/karatsuba-multiplication/karatsuba.py</ref>
{{چپ‌چین}}
<syntaxhighlight lang="python">
_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
</syntaxhighlight>
{{پایان چپ‌چین}}

== الگوریتم کاراتسوبا در عمل ==
همان طور که دیدیم الگوریتم به صورت بازگشتی مسئله را به زیر مسئله‌هایی با اندازه نصف مسئله اولیه تبدیل کرده و این کار را تا
تبدیل آن به زیر مسئله‌ای با اندازه یک ادامه می‌دهد. دلیل این کار این است که فرض شده‌است عمل ضرب دو عدد یک رقمی در(1)O
انجام می‌گیرد.
{{سخ}}

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

== جستارهای وابسته ==
* [[روش تقسیم و حل]]
* [[ضرب]]
* [[تبدیل سریع فوریه]]

== منابع ==
{{پانویس}}

== پیوند به بیرون ==
{{ویکی‌انبار-رده|Algorithms}}
* [http://www.cs.pitt.edu/~kirk/cs1501/animations/Karatsuba.html  الگوریتم کاراتسوبا یه همراه اپلت جاوا]
* [http://www.javamex.com/tutorials/math/karatsuba.shtmlتوضیحات  الگوریتم به همراه مثال]{{پیوند مرده|date=اکتبر ۲۰۱۹ |bot=InternetArchiveBot }}
* [http://nayuki.eigenstate.org/page/karatsuba-multiplication توضیحات الگوریتم به همراه کد و مقایسه آن با روش عادی ضرب]
* [http://www.cs.cmu.edu/~cburch/251/karat کد الگوریتم به زبان ++C  و مقایسه آن با روش عادی ضرب]

[[رده:الگوریتم‌های محاسباتی رایانه]]
[[رده:ضرب (ریاضی)]]
[[رده:علوم نظری رایانه]]