مسئلهای که در پرسش پست قبلیم مطرح کردم الگوریتم محاسبهی حاصل ضرب دو عدد n رقمی است.
ورودیها دو عدد N رقمی مثبت میباشند که به صورت زیر نمایش داده میشوند:
و خروجی یک عدد 2N رقمی خواهد بود که به صورت زیر نمایش داده میشود:
طبق الگوریتمی که در مدرسه ابتدایی آموختهایم برای برای بدست آوردن حاصل ضرب دو عدد، تک تک ارقام یک عدد را در عدد دیگر ضرب کرده و حاصلها را با هم جمع میکنیم تا حاصل ضرب نهایی دو عدد را بیابیم. این الگوریتم به <span dir=ltr>O(N^2)</span> مرحله برای ضرب دو عدد N رقمی نیاز دارد.
منظور از مرحله در عبارت بالا عملیات پایهی ریاضی است که بر روی دو رقم (عدد تک رقمی) صورت میگیرد. مانند 3+4 یا 5*6.
در سال 1992 فردی به نام <span dir=ltr>A.A. Karatsuba</span> الگوریتم ضرب سریعتری به روش تقسیم و تسخیر یافت که به نام او الگوریتم ضرب کاراتسوبا <span dir=ltr>Karatsuba Multiplication</span> نامیده میشود. تعداد مراحل مورد نیاز این الگوریتم <span dir=ltr>O(N^(log 3))</span> یا به عبارتی <span dir=ltr>O(N^1.59)</span> است. الگوریتم کاراتسوبا برای تمام مبناهای عددی معتبر است.
حالا ببینیم این الگوریتم بر چه اساسی بدست آمده است. اعداد ورودی x و y را در نظر بگیرید:
واضح است که این دو عدد را میتوان بصورت زیر هم نمایش داد:
و نتیجه حاصل ضرب <span dir=ltr>z = x * y</span> را بصورت زیر بیان کرد:
به عنوان مثال:
حال فرض کنید که ما ارقام اعداد x و y را به دو قسمت تقسیم کنیم:
اکنون میتوانیم اعداد x و y را با استفاده از اعداد a و b و c و d به صورت زیر بیان کنیم:
با این نگرش به اعداد x و y حاصل ضرب آنها را میتوانیم به صورت زیر بدست آوریم:
که در آن عبارتهای (a*c) و (a*d) و (b*c) و (b*d) حاصل ضرب دو عدد N/2 رقمی میباشند.
بدین ترتیب حاصل ضرب دو عدد x و y با استفاده از ترمهای a و b و c و d بدین صورت بیان میشود که:
- دو عدد تک رقمی بیدرنگ با هم ضرب میشوند. (مبنای بازگشت)
- اگر <span dir=ltr>N > 1</span> بود در اینصورت حاصل ضرب دو عدد N رقمی میتواند بصورت ترمهایی از 4 عمل ضرب بر روی دو عدد N/2 رقمی بیان شود. (مرحله تقسیم و تسخیر)
- برای محاسبه نتیجه حاصل ضرب اعداد x و y داده شده٬ تنها نیاز به جمع 4 حاصل ضرب بدست آمده در مرحله قبل (که در <span dir=ltr>O(N)</span> مرحله صورت میگیرد) و ضرب کردن در توانی از 10 هست (که این هم میتواند در <span dir=ltr>O(N)</span> مرحله صورت بگیرد٬ زیرا که تنها نیاز است به تعداد لازم صفر در انتهای عدد قرار گیرد). (مرحله ترکیب)
به عنوان مثال اگر داشته باشیم:
n = 4
x = 1026
y = 7329
در اینصورت خواهیم داشت:
a = 10
b = 26
c = 73
d = 29
پس اعداد x و y بصورت زیر قابل نمایش خواهند بود:
و در نتیجه حاصل ضرب x و y بصورت زیر محاسبه خواهد شد:
کاراتسوبا فهمید که میتوان 4 عمل ضرب موجود در مرحلهی تقسیم و تسخیر الگوریتم سادهی بالا را به 3 عمل ضرب کاهش داد. البته کاهش یک عمل ضرب در مرحله تقسیم و تسخیر باعث افزایش جزئی تعداد عملیات پایه در مرحله ترکیب میشود (هرچند باز به <span dir=ltr>O(N)</span> مرحله نیاز خواهد داشت).
چگونه 4 عمل ضرب میتواند به 3 عمل ضرب تبدیل شود؟ یک جایگزینی ساده. :idea:
U = a * c
V = b * d
W = (a + b) * (c + d)
با استفاده از U و V و W خواهیم داشت:
a * d + b * c = W - U - V
به همین سادگی 4 عمل ضرب به 3 عمل ضرب تبدیل شد و اکنون میتوانیم حاصل ضرب دو عدد N رقمی x و y را بصورت زیر بیان کنیم:
الگوریتم ضرب کاراتسوبا بطور کامل:
function Karatsuba (xunder, yunder : n-digit integer;
n : integer)
return (2n)-digit integer
a, b, c, d : (n/2)-digit integer
U, V, W : n-digit integer
begin
if n = 1 then
return x(0) * y(0)
else
a := x(n-1) ... x(n/2)
b := x(n/2-1) ... x(0)
c := y(n-1) ... y(n/2)
d := y(n/2-1) ... y(0)
U := Karatsuba ( a, c, n/2 )
V := Karatsuba ( b, d, n/2 )
W := Karatsuba ( a+b, c+d, n/2 )
return U * 10^n + (W-U-V) * 10^(n/2) + V
end if
end Karatsuba