ویکی‌پدیا

الگوریتم کاراتسوبا: تفاوت میان نسخه‌ها

نمایش تاریخچه به صورت تعاملی
→ تفاوت قدیمی‌ترتفاوت جدیدتر ←
محتوای حذف‌شده محتوای افزوده‌شده
دیداریویکی‌متن
Sadeghedayat (بحث | مشارکت‌ها)
۵۲ ویرایش‌ها
بدون خلاصۀ ویرایش
برچسب: نیازمند بازبینی
علیرضا (بحث | مشارکت‌ها)
۱۷٬۷۰۷ ویرایش‌ها
خط ۲:
{{جعبه اطلاعات الگوریتم
| کلاس = [[الگوریتم ضرب چندجمله‌ای]]
| تصویر =
| زیرنویس تصویر =
| داده‌ها =
| زمان بدترین = <math>n^{\log_23}</math>
| زمان بهترین =
| زمان متوسط =
| پیچیدگی فضایی =
}}
[[پرونده:A.A.Karatsuba graduate.jpg|بندانگشتی| آناتولی کاراتسوبا]]
'''الگوریتم کاراتسوبا''' یک الگوریتم سریع برای ضرب اعداد است. الگوریتم کاراتسوبا اولین الگوریتمی است که به صورت مجانبی سریع است.
این الگوریتم برای اولین‌بار توسط [[:w:en:Anatolii_Alexeevitch_Karatsuba|آناتولی کاراتسوبا]] در سال ۱۹۶۲ ارایه شد.<ref name="kara1962">
{{cite journal
| author = A. Karatsuba and Yu. Ofman
خط ۲۰:
| year = ۱۹۶۲
| pages = ۲۹۳–۲۹۴
| note = Translation in Physics-Doklady, 7 (1963), pp. 595–596}}</ref>
این الگوریتم با استفاده از [[روش تقسیم و حل]] تعداد عملیات ضرب لازم برای ضرب دو عدد n رقمی را کاهش می‌دهد.▼
</ref>
▲این الگوریتم با استفاده از [[روش تقسیم و حل]] تعداد عملیات ضرب لازم برای ضرب دو عدد n رقمی را کاهش می‌دهد.
{{سخ}}
در عملیات ضرب معمولی که در دبیرستان آموزش داده می‌شود، به تعداد n<sup>۲</sup> عملیات ضرب لازم است. این الگوریتم تعداد عملیات ضرب را به 3n<sup>log3<sub>۲</sub></sup> می‌رساند.
{{سخ}}
3۳ سال بعد ارایه این الگوریتم توسط کاراتسوبا، الگوریتم [[: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> عملیات نیاز داشت و به این ترتیب فرضیه کولوموگوروف را رد کرد.
سطر ۵۲ ⟵ ۵۱:
ابتدا حالت ساده‌ای را در نظر می‌گیریم. این حالت به راحتی قابل تعمیم به روش کلی است.
{{سخ}}
فرض کنید عدد اول X و عدد دوم Y است. هر دو [[عدد صحیح]] و در [[مبنای دو]] و دارای n رقم که n توانی از ۲ است.
در ابتدا دو عدد مطابق شکل به دو قسمت تقسیم می‌شوند. X<sub>۱</sub> قسمت پرارزش و X<sub>۰</sub> قسمت کم‌ارزش است. به صورت مشابه، برای Y هم به همین صورت است.
پس داریم:
[[پرونده:Dividing karatsuba.jpg|بندانگشتی|وسط|300px|تقسیم عددها به دو قسمت]]{{سخ}}
سطر ۶۲ ⟵ ۶۱:
{{سخ}}
{{پایان چپ‌چین}}
به این ترتیب ضرب ''XY'' به صورت زیر در می‌آید:
{{سخ}}
{{سخ}}
سطر ۷۲ ⟵ ۷۱:
 
در مبنای ۲، ضرب یک عدد در توانی از ۲، به صورت عملیات شیفت در کامپیوتر به راحتی انجام می‌شود. عملیات شیفت و جمع، در مقابل عملیات ضرب، زمان اجرای بسیار کمی دارند. به همین
خاطر، زمان اجرای آن را از (1)[[:w:en:Big_O_notation|O]] در نظر می‌گیرند.
حال مساله به ۴ زیرمساله با اندازهٔ نصف مساله قبلی تبدیل شده‌است.شده‌است؛ بنابراین می‌توان این ۴ مساله را به روش بازگشتی حل و در زمان خطی، عبارت کلی را محاسبه کرد. پیچیدگی
زمانی رابطه بالا به صورت زیر است:
{{سخ}}
{{سخ}}
{{چپ‌چین}}
T(n) = 4T(n/2) + O(n)
 
{{پایان چپ‌چین}}
سطر ۹۴ ⟵ ۹۳:
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>
سطر ۱۰۵ ⟵ ۱۰۴:
پس زمان اجرا به صورت زیر در می‌آید:
{{چپ‌چین}}
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 است.
بنابراین ارتفاع درخت برابر (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)
سطر ۱۲۸ ⟵ ۱۲۶:
در این قسمت حالت کلی الگوریتم کاراتسوبا توضیح داده می‌شود.
{{سخ}}
فرض کنید 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>)
سطر ۱۳۷ ⟵ ۱۳۵:
 
مشابه ایده‌ای که در بالا گفته شد می‌توان این ۴ ضرب را تنها با ۳ ضرب و چند عملیات جمع اضافه انجام داد. کافی است به جای (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 را نیز ۲ انتخاب می‌کنیم.
{{چپ‌چین}}
 
:12۱۲ 34۳۴ = ۱۲ × ۱۰<sup>۲</sup> + ۳۴
:56۵۶ 78۷۸ = ۵۶ × ۱۰<sup>۲</sup> + ۷۸
:''x''<sub>۱</sub>y''<sub>۱</sub> = 12۱۲ × 56۵۶ = ۶۷۲
:''x''<sub>۰</sub>y''<sub>۰</sub> = 34۳۴ × 78۷۸ = ۲۶۵۲
:''(x''<sub>۱</sub> + ''x''<sub>۰</sub>)(''y''<sub>۱</sub> + ''y''<sub>۰</sub>) = (12۱۲ + 34۳۴)(56۵۶ + 78۷۸) = ۲۸۴۰
 
:result = 672 × 10000۱۰۰۰۰ + 2840۲۸۴۰ × 100۱۰۰ + 2652۲۶۵۲ = '''۷۰۰۶۶۵۲'''.
{{پایان چپ‌چین}}
 
=== پیاده سازیپیاده‌سازی ===
[[شبه‌کد]] الگوریتم به صورت زیر است:
{{چپ‌چین}}
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>
سطر ۱۷۶ ⟵ ۱۷۳:
16 '''end'''
{{پایان چپ‌چین}}
پیاده‌سازی الگوریتم با استفاده از [[جاوا]]: <ref>[http://introcs.cs.princeton.edu/java/78crypto/Karatsuba.java.html Karatsuba.java<!-- عنوان تصحیح شده توسط ربات -->]</ref>
{{چپ‌چین}}
<source lang="java">
سطر ۲۳۱ ⟵ ۲۲۸:
</source>
{{پایان چپ‌چین}}
پیاده‌سازی الگوریتم با استفاده از [[پایتون]]:<ref>http://nayuki.eigenstate.org/res/karatsuba-multiplication/karatsuba.py</ref>:
{{چپ‌چین}}
<source lang="python">
سطر ۲۶۷ ⟵ ۲۶۴:
به همین خاطر در عمل لازم نیست که به صورت بازگشتی با زیر مساله‌ای با اندازه ۱ پایین برویم. با داشتن آگاهی نسبت به معماری پردازنده، می‌توان B و m را به گونه‌ای انتخاب کرد که کارایی و زمان اجرای بهتری از الگوریتم بدست آید.
 
== جستارهای وابسته ==
* [[روش تقسیم و حل]]
* [[ضرب]]
برگرفته از «https://fa.wikipedia.org/wiki/الگوریتم_کاراتسوبا»