زنگ‌تفریح شماره‌ی 58
زمان حل مساله
ضرب دو عدد، سریع!
همگی شما احتمالاً با طریقه‌ی ضرب دو عدد آشنا هستید. حال اگر از شما پرسیده شود «آیا می‌توانید هر دو عددی که به شما داده می‌شود را در هم ضرب کنید؟» چه جوابی می‌دهید. جواب منطقی این می‌تواند باشد: «اگر دو عدد زیاد بزرگ نباشند حتماً!». اما چه‌قدر بزرگ؟
البته مخاطب ما در اینجا انسان‌ها نیستند، بلکه این سوال معمولاً در مورد کامپیوتر پرسیده می‌شود و معمولاً سازندگان کامپیوتر جواب سریعی برای این سوال دارند: «کامپیوتری که ما ساخته‌ایم می‌تواند عددهای تا n رقم را محاسبه و ذخیره کند و هر عمل را در مدت زمان t انجام می‌دهد.» با این اطلاعات شما می‌توانید با یک دو دو تا چار تای ساده، یک تقریب خوب از توانایی کامپیوتر برای انجام یک عمل ضرب و حتی تقریب مدت زمان محاسبه‌ی آن به‌دست آورید. پس شاید همیشه خود را در قید و بند میزان تکنولوژی ببینید.
اما ذهن‌های خلاق و زیبااندیش همیشه برای کم کردن این محدودیت‌ها چاره‌ای پیدا می‌کنند. در واقع آنها الگوریتم محاسبه را تغییر می‌دهند تا کمی به کامپیوتر و محدودیت‌های آن دک و پُزی نشان دهند. یک نمونه‌ی بسیار ساده و در عین حال کارآمد را در اینجا می‌خواهیم به شما نشان دهیم.
می‌خواهیم دو عدد در مبنای دو را در هم ضرب کنیم. این دو عدد خیلی بزرگ هستند و اگر آن را با الگوریتم معمول ضرب انجام دهیم ممکن است ساعت‌ها به‌طول انجامد و برای این‌که حوصله‌مان بیش از حد سر نرود با یک تغییر در روش محاسبه‌مان مقدار زیادی در زمان صرفه‌جویی می‌کنیم. حداقل 25% !
فرض کنید می‌خواهیم عدد a را در عدد b ضرب کنیم که هر یک از آنها 2n-رقمی هستند و البته در مبنای 2. خیلی راحت و بدون نگرانی هر دو عدد را از وسط نصف می‌کنیم، در واقع هریک را دو شقّه می‌کنیم! اگر هر شقّه از a را با 'a و "a و هر شقّه از b را با 'b و "b نشان دهیم خواهیم داشت:
a = 2na' + a"
b = 2nb' + b"
و بخش خوب قضیه رابطه‌ی زیر است:
ab = (22n + 2n)ab + 2n(a − a′)(b − b′) + (2n + 1)a′b′
خُب! حالا باید ادعای خودمان را ثابت کنیم.
در ضرب دو عدد 2n-رقمی به‌طور عادی در حدود 2n)2 = 4n2) عمل ضرب تک-رقمی انجام می‌شود به‌اضافه‌ی تعداد کمی عدد جمع. می‌توانید بگویید چرا!؟ اما با الگوریتم ضرب جدیدمان چه‌طور؟
این الگوریتم از دو عمل جمع کلی تشکیل شده که هر عامل جمع، حاصل‌ضرب دو عدد n-رقمی در یک‌دیگر است، به‌اضافه‌ی تعداد کمی عمل جمع و چند بار عمل ضرب در توان‌های عدد 2 که می‌توان آنها را در نظر نگرفت. دقت کنید که توان‌های عدد 2 در مبنای 2 از یک رقم 1 و مابقی از صفر تشکیل شده‌اند.
بسیار خُب! با این اوصاف می‌توانید بگویید در این الگوریتم چند بار از عمل ضرب یک-رقمی استفاده کرده‌ایم؟ احسنت! 3n2 بار! پس در مقایسه با ضرب عادی 25% در زمان سود کرده‌ایم.
آیا این پایان کار است؟ مسلماً نه! می‌توان این الگوریتم را دوباره برای ضرب کردن عددهای n-رقمی به‌کار ببریم. محاسبات نشان می‌دهد که می‌توان برای یک عدد n-رقمی که تعداد عمل‌های ضرب در آن تقریباً n2 است را با تکرار این عمل به حدود 585/n1 کاهش داد. یعنی یک پیروزی بزرگ.