الگوریتم ضرب

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

شیوه‌های باستانی ضرب دو عدد

شیوهٔ ضرب در مصر باستان

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

برای مثال اگر بخواهیم حاصل ضرب ۳۱ در ۴۲ را بدست آوریم جدولی به صورت زیر تشکیل می‌دهیم.

 ۳۱ ۱
 ۶۲ ۲
 ۱۲۴ ۴
 ۲۴۸ ۸
 ۴۹۶ ۱۶
 ۹۹۲ ۳۲
 ۱۹۸۴ ۶۴ <-- بزرگتر از ۴۲ است پس متوقف می‌شویم

در ستون چپ جمع اعداد ۲ و ۸ و ۳۲ عدد ۴۲ را می‌سازند پس با جمع اعداد روبرویشان یعنی ۶۲ و ۲۴۸ و ۹۹۲ حاصل ضرب بدست می‌آید.

۱۳۰۲ = ۶۲ + ۲۴۸ + ۹۹۲ = ۳۱×۴۲

شیوهٔ ضرب در چین باستان

چینیان باستان برای ضرب دو عدد از شیوه‌ای تصویری استفاده می‌کردند. برای مثال اگر بخواهیم دو عدد ۱۶ و ۲۴ را در هم ضرب کنیم خط‌هایی عمودی برای ۱۶ در نظر می‌گیریم به صورتی که خط‌های سمت چپ نشان دهندهٔ دهگان و خط‌های سمت راست نشان دهندهٔ یکان باشد. به همین طریق خط‌هایی افقی در نظر می‌گیریم به طوری که خط‌های بالا دهگان و خط‌های پایین نشان‌دهندهٔ یکان عدد ۲۴ باشد.

• 
  چینیان باستان برای ضرب دو عدد از شیوه‌ای تصویری استفاده می‌کردند. برای مثال اگر بخواهیم دو عدد ۱۶ و ۲۴ را در هم ضرب کنیم

حال تعداد برخورد خط‌ها با یک‌دیگر را بررسی می‌کنیم. اگر هر ردیف از راست به چپ نشان‌دهندهٔ یک ارزش مکانی باشد، می‌توانیم حاصل ضرب را پیدا کنیم. برای این مثال ۲۴ برخورد در ردیف ارزش مکانی یکان اتفاق افتاده است. یعنی ارزش یکان ۴ است و به ارزش دهگان ۲ واحد اضافه می‌کنیم. تعداد برخوردها در ردیف ارزش دهگان ۱۶ است و ۲ واحد هم از یکان اضافه شده پس به ارزش دهگان ۸ است و یک واحد به صدگان اضافه می‌کند. به همین طریق ارزش صدگان ۳ است. پس حاصل ضرب اعداد مثال‌زده‌شده ۳۸۴ است.[2]

• 
  تعداد برخوردها با توجه به ارزش مکانی آن‌ها در تصویر نشان داده شده‌است.

ضرب‌شبکه‌ای

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

به عنوان مثال جدول شبکه‌ای ضرب دو عدد ۳۵ و ۲۶ به صورت زیر است.[3]

×	۳۰	۵
۲۰	۶۰۰	۱۰۰
۶	۱۸۰	۳۰

با توجه به جدول بالا حاصل ضرب دو عدد ۳۵ و ۲۶ به صورت جمع زیر است.

۹۱۰ = ۳۰ + ۱۸۰ + ۶۰۰ + ۱۰۰ = ۳۵ × ۲۶

ضرب طولانی

این روش ضرب کردن همان روشی است که در مدارس به دانش‌آموزان تدریس می‌شود. این روش برای ضرب اعداد بزرگ در هم کارآمد است.[4]

الگوی انجام این روش به صورت مرحله به مرحله در زیر توضیح داده شده‌است.[4]

1. اعداد را در زیر هم می‌نویسیم و اعدادی که ارزش مکانی یکسان دارند در زیر یکدیگر قرار می‌دهیم.
2. ضرب کردن یکان عدد پایین در یکان عدد بالا و نوشتن آن عدد به عنوان یکان عددی که قرار است به دست آوریم. اگر حاصل بزرگ‌تر از نه شد یکان را نوشته و بالای ارزش مکانی قبلی مقدار دهگان حاصل را می‌نویسیم.
3. حال مرحلهٔ دو را با ضرب یکان پایین در رقم ارزش مکانی بعدی انجام می‌دهیم و این کار را آنقدر تکرار می‌کنیم تا یکان عدد او را در تمام اعداد بالا ضرب کرده باشیم.
4. مرحلهٔ دو و سه را با ضرب کردن عدد یکان عدد بالا در ارزش مکانی بعدی عدد پایین انجام می‌دهیم و حاصل را در زیر عدد بدست آمده از مرحلهٔ قبل به گونه‌ای می‌نویسیم که یکان عدد جدید زیر دهگان عدد حاصل از مرحلهٔ قبل قرار گیرد.
5. با جمع اعداد نوشته شده در زیر هم با در نظر گرفتن این نکته که اگر سمت راست عددی خالی بود در آن‌جا صفر قرار می‌دهیم حاصل ضرب دو عدد داده شده بدست می‌آید.

مثال

برای ضرب دو عدد ۲۳۹۵۸۲۳۳ و ۵۸۳۰ در هم اعداد را به صورت زیر نوشته و حاصل ضرب را بدست می‌آوریم.

 ۲۳۹۵۸۲۳۳
 ۵۸۳۰ ×
 ———————————————
 ۰۰۰۰۰۰۰۰ (= ۲۳٬۹۵۸٬۲۳۳ × ۰)
 ۷۱۸۷۴۶۹۹ (= ۲۳٬۹۵۸٬۲۳۳ × ۳۰)
 ۱۹۱۶۶۵۸۶۴ (= ۲۳٬۹۵۸٬۲۳۳ × ۸۰۰)
 ۱۱۹۷۹۱۱۶۵ (= ۲۳٬۹۵۸٬۲۳۳ × ۵٬۰۰۰)
 ———————————————
 ۱۳۹۶۷۶۴۹۸۳۹۰ (= ۱۳۹٬۶۷۶٬۴۹۸٬۳۹۰)

محاسبهٔ پیچیدگی الگوریتم طولانی ضرب

اگر دو عددی که در هم ضرب می‌کنیم به طول n بود در هر مرحله n ضرب انجام می‌دهیم و تعداد مراحل n است، پس پیچیدگی این الگوریتم ${\displaystyle o(n^{2})}$است.

ضرب با استفاده از جدول مشبکی

شیوه‌ای برای ضرب کردن است که از یک جدول مشبکی استفاده می‌کند. این شیوه در زمان قرون وسطی به‌وجود آمده و در سرزمین‌های مختلفی از آن استفاده می‌شد. امروزه نیز این روش در برنامهٔ درسی بعضی کشورها تدریس می‌شود.

در این روش یک جدول مشبکی کشیده می‌شود و رقم‌های دو عددی که می‌خواهیم آن‌ها را در هم ضرب کنیم در بالا و سمت راست جدول کشیده می‌شود. جدول مشبکی ضرب دو عدد ۵۸ و ۲۱۳ به صورت زیر (تصویر مرحلهٔ اول) است. ما باید هر خانهٔ آن را به صورتی پر کنیم که با ضرب عدد بالای ستون و سمت راست سطر یکان عدد حاصل در پایین و دهگان آن در بالای خط موجود در خانه نوشته شود.

• 
  مرحلهٔ اول

پس از پر کردن تمامی خانه‌های جدول، جدول به تصویر مرحلهٔ دوم تبدیل می‌شود؛ که بعد از این مرحله باید از پایین راست جدول به سمت بالا حرکت کنیم و سپس به سمت چپ برویم و در هر مرحله جمع خانه‌های مثلثی همسایه (خانه‌های همسایه مثلث‌هایی هستند ساق‌هایشان مشترک است) را حساب کنیم. اگر این جمع بیشتر از نه شد یکان آن را نوشته و عدد دهگان را با عدد مرحلهٔ بعد جمع می‌کنیم.

• 
  مرحلهٔ دوم

در آخر تصویر جدول به شکل جدول آمده در مرحلهٔ سوم است.

• 
  مرحلهٔ سوم

همان‌طور که مشاهده می‌کنید جواب بدست آمده ۱۲۳۵۴ است.

الگوریتم‌های سریع ضرب برای ورودی‌های بزرگ

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

الگوریتم کاراتسوبا یک الگوریتم سریع برای ضرب است که از الگوریتم تقسیم و حل برای ضرب دو عدد استفاده می‌کند.[5] اگر x و y بیانگر دو عدد در مبنای b به طول n باشند، ما هر کدام از این اعداد را به دو قسمت پرارزش(H) و کم ارزش (L) تقسیم می‌کنیم. به این ترتیب حاصل ضرب به صورت زیر می‌شود.

X = X_H b^(n/2) + X_L

Y= Y_H b^(n/2) + Y_L

(XY = (X_H b^(n/2) + X_L) (Y_H b^(n/2) + Y_L

XY = x_Hy_Hbⁿ + (x_Hy_L + x_Ly_H)b^(n/2) + x_Ly_L

به این ترتیب مسئله به چهار زیرمسئله تقسیم می‌شود؛ و این تقسیم ادامه پیدا می‌کند تا به زیرمسئله‌های ساده‌برسد. حاصل ضرب به صورت بازگشتی به دست می‌آید.

با یک راه حل ساده می‌توان تعداد ضرب‌های انجام شده (زیرمسئله‌ها) را از ۴ به ۳ رساند.

${\displaystyle a=x_{H}\times y_{H}}$

${\displaystyle d=x_{L}\times y_{L}}$

${\displaystyle e=(x_{h}+x_{l})(y_{h}+y_{l})-a-d}$

${\displaystyle xy=ab^{n}+eb^{n/2}+d}$

با داشتن a و b می‌توان تنها با استفاده از ۳ جمله این ضرب را انجام داد.

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

فرض کنید می‌خواهیم عدد ۱۲۳۴ را در ۴۳۲۱ ضرب کنیم. برای اینکار به صورت زیر عمل می‌کنیم.[6]

${\displaystyle x=1234}$

${\displaystyle y=4321}$

${\displaystyle n=4}$

ابتدا a و b و e را بدست می‌آوریم.

${\displaystyle a=12\times 43}$

${\displaystyle d=34\times 21}$

${\displaystyle e=(12+34)(43+21)-a-d}$

حال بدست آوردن هر کدام از این ضرب‌ها خود یک زیر مسئله است. برای بدست آوردن حاصل ضرب ۱۲ و ۴۳ داریم

${\displaystyle a=1\times 4=4}$

${\displaystyle d=2\times 3=6}$

${\displaystyle e=(1+2)(4+3)-4-6=11}$

${\displaystyle 12\times 43=4\times 10^{2}+11\times 10+6=516}$

به همین روش برای مسئلهٔ اصلی ۷۱۴ = d و e با توجه به مقدار بدست آمده برای a و d، برابر ۱۷۱۴ است.

پس نتیجه می‌شود که

${\displaystyle 1234\times 4321=516\times 10^{4}+1714\times 10^{2}+714=5332114}$

تحلیل زمان اجرای الگوریتم

این الگوریتم هر مسئله را به ۳ زیر مسئله به طول نصف مسئله-- قبلی تقسیم می‌کند پس زمان اجراء آن به صورت زیر است.

${\displaystyle T(n)=3T(n/2)+O(n)}$

با توجه به قضیه اصلی در الگوریتم‌ها می‌توانیم زمان اجرای این الگوریتم را بدست آوریم.

${\displaystyle T(n)=3^{logn}+O(n)}$

${\displaystyle T(n)=O(n^{log3})=O(n^{1.59})}$

پس به اندازهٔ ${\displaystyle O(n^{1.59})}$ طول می‌کشد تا بتوانیم حاصل این ضرب را بدست آوریم.[7]

الگوریتم توم ـ کوک

الگوریتم توم ـ کوک که گاهی با نام توم ـ ۳ شناخته می‌شود، ابتدا توسط اندری توم ارائه شد و سپس استفان کوک آن را به صورت شفاف‌تر در پایان‌نامه دکتری خود بیان کرد.[8]الگوریتم توم ـ کوک انواع مختلفی دارد که الگوریتم توم ـ ۳ یکی از آن‌هاست. این الگوریتم تعمیم داده شدهٔ الگوریتم کاراتسوبا است. به‌طور دقیق‌تر الگوریتم کاراتسوبا حالت خاصی از الگوریتم توم ـ کوک است. پیچیدگی یک الگوریتم توم ـ k به صورت ${\displaystyle O(n^{log_{k}(2k-1)})}$ است.[9]

جستارهای وابسته

• الگوریتم کاراتسوبا
• الگوریتم تقسیم و حل
• تبدیل سریع فوریه

منابع

1. «Egyptian Multiplication». www.cut-the-knot.org. دریافت‌شده در ۲۰۱۹-۰۳-۲۷.
2. «Chinese Stick Multiplication». jwilson.coe.uga.edu. دریافت‌شده در ۲۰۱۹-۰۳-۲۷.
3. "Grid multiplication explained | Helping with maths at home". www.mumsnet.com. Retrieved 2019-03-27.
4. "How to Do Long Multiplication". wikiHow. Retrieved 2019-03-27.
5. «Karatsuba algorithm for fast multiplication using Divide and Conquer algorithm». GeeksforGeeks (به انگلیسی). ۲۰۱۳-۰۴-۱۸. دریافت‌شده در ۲۰۱۹-۰۳-۲۸.
6. «Karatsuba Algorithm | Brilliant Math & Science Wiki». brilliant.org (به انگلیسی). دریافت‌شده در ۲۰۱۹-۰۳-۲۸.
7. «How do we derive the runtime cost of Karatsuba's algorithm?». Computer Science Stack Exchange. دریافت‌شده در ۲۰۱۹-۰۳-۲۸.
8. http://cs.indstate.edu/~syedugani/ToomCook.pdf
9. https://services.math.duke.edu/~bray/Courses/89s-MOU/2016-Fall/Papers/CL_Paper3_MultiplicationandDivisionAlgorithms.docx