کشف Anatoly Karatsuba باور چندصدساله درباره سریع‌ترین روش ضرب را تغییر داد، اما دانشمندان هنوز به اثبات نهایی محدودیت سرعت ضرب نرسیده‌اند.
- روش سنتی ضرب دارای پیچیدگی زمانی O(n²) است.
- الگوریتم Karatsuba با جایگزینی بخشی از ضرب‌ها با جمع، سرعت محاسبات را افزایش می‌دهد.
- الگوریتم Harvey–van der Hoeven با پیچیدگی O(n×log n) رکورد نظری جدیدی ثبت کرده، اما تنها برای اعداد بسیار عظیم کاربرد دارد.
سریع‌ترین روش ضرب؛ معمایی که پس از دهه‌ها هنوز بی‌پاسخ مانده است
قرن‌ها تصور می‌شد روشی که در دبستان برای ضرب اعداد آموزش داده می‌شود، سریع‌ترین شیوه ممکن است. اما در سال ۱۹۶۰، کشف یک دانشجوی ۲۳ ساله این باور را رد کرد، جست‌وجویی را آغاز کرد که هنوز یکی از مهم‌ترین معماهای ریاضیات و علوم کامپیوتر محسوب می‌شود.
اهمیت این موضوع تنها به ریاضیات محدود نیست. رمزنگاری، رباتیک، هوش مصنوعی، پردازش صدا، طراحی تراشه‌های رایانه‌ای، تقریباً تمام پردازش‌های سنگین رایانه‌ای به ضرب مکرر اعداد بسیار بزرگ وابسته هستند. در چنین مقیاسی، حتی کوچک‌ترین افزایش بهره‌وری می‌تواند تأثیرات اقتصادی گسترده‌ای در سطح جهان داشته باشد.
هزینه پنهان روش سنتی ضرب اعداد
در روشی که در مدارس آموزش داده می‌شود، برای ضرب دو عدد دو رقمی باید چهار ضرب تک‌رقمی انجام شود. اگر دو عدد سه رقمی باشند، این تعداد به ۹ ضرب تک‌رقمی افزایش پیدا می‌کند. به عبارت دیگر، میزان عملیات موردنیاز با مجذور تعداد رقم‌های اعداد رشد می‌کند.
دانشمندان علوم کامپیوتر این رشد را با نماد Big O نمایش می‌دهند. روش سنتی دارای پیچیدگی زمانی O(n²) است؛ یعنی:
- اگر تعداد رقم‌ها دو برابر شود، حجم محاسبات چهار برابر خواهد شد.
- اگر تعداد رقم‌ها هزار برابر شود، میزان عملیات تقریباً یک میلیون برابر افزایش پیدا می‌کند.
دانشجوی ۲۳ ساله‌ای که فرضیه Kolmogorov را رد کرد
از دوران باستان، بسیاری از ریاضیدانان تصور می‌کردند پیچیدگی O(n²) سریع‌ترین حد ممکن برای ضرب اعداد است.
در سال ۱۹۶۰، ریاضیدان مشهور شوروی، Andrey Kolmogorov، در سمیناری در دانشگاه دولتی مسکو این فرضیه را به‌صورت رسمی مطرح کرد.
در میان حاضران، دانشجوی ۲۳ ساله‌ای به نام Anatoly Karatsuba حضور داشت. او تنها یک هفته بعد بازگشت و نشان داد که فرضیه Kolmogorov نادرست است.
Kolmogorov از این نتیجه شگفت‌زده شد. نکته جالب اینکه متن رسمی اثبات را خودش نوشت، نام Karatsuba را به‌عنوان نویسنده اصلی مقاله قرار داد، سپس آن را منتشر کرد. Karatsuba زمانی از انتشار مقاله مطلع شد که نسخه چاپ‌شده آن از طریق پست به دستش رسید.
الگوریتم Karatsuba چگونه سرعت ضرب را افزایش داد؟
نبوغ Karatsuba در این بود که بخشی از عملیات پرهزینه ضرب را با عملیات بسیار ارزان‌تر جمع جایگزین کرد.
جمع دو عدد n رقمی تنها دارای پیچیدگی O(n) است، زیرا کافی است فقط یک بار روی رقم‌ها حرکت شود.
نمونه محاسبه ۱۲ × ۳۴
ابتدا اعداد به رقم دهگان و یکان تقسیم می‌شوند:
- برای ۱۲: a=1 ، b=2
- برای ۳۴: c=3 ، d=4
در نتیجه:
(10a+b) × (10c+d)
که پس از بسط به عبارت زیر تبدیل می‌شود:
100(ac) + 10(ad+bc) + (bd)
در روش سنتی باید چهار ضرب مستقل انجام شود:
- ac = 3
- ad = 4
- bc = 6
- bd = 8
ترفند Karatsuba این بود که مقدار (ad+bc) را تنها با یک ضرب محاسبه کرد:
(ad+bc) = ((a+b) × (c+d)) − ac − bd
در این مثال:
((1+2) × (3+4)) − 3 − 8 = 21 − 11 = 10
بنابراین با داشتن:
- ac = 3
- bd = 8
- ad+bc = 10
نتیجه نهایی همچنان برابر با ۴۰۸ خواهد بود، اما این بار به‌جای چهار ضرب، تنها سه ضرب انجام شده است.
هرچه اعداد بزرگ‌تر شوند، این روش به‌صورت بازگشتی (Recursive) بارها تکرار می‌شود، سود حاصل از کاهش تعداد ضرب‌ها نیز به شکل چشمگیری افزایش پیدا می‌کند.
امروزه این الگوریتم پایه بسیاری از نرم‌افزارها است. برای مثال، زبان برنامه‌نویسی Python زمانی که اندازه اعداد از حدود ۶۳۰ رقم ده‌دهی عبور کند، به‌صورت خودکار از روش Karatsuba استفاده می‌کند.
رکورد «کهکشانی» سال ۲۰۱۹
کشف Karatsuba رقابتی چند ده‌ساله را برای یافتن سریع‌ترین روش ممکن ضرب آغاز کرد.
این رقابت در سال ۲۰۱۹ به نقطه عطف مهمی رسید؛ زمانی که ریاضیدانان David Harvey و Joris van der Hoeven الگوریتمی بسیار پیشرفته معرفی کردند که از تمام روش‌های قبلی سریع‌تر بود.
این الگوریتم دارای پیچیدگی زمانی O(n×log n) است. به این معنا که ضرب دو عدد بسیار بزرگ تقریباً به اندازه خواندن یا جمع کردن آن‌ها زمان نیاز دارد.
چرا این الگوریتم هنوز کاربرد عمومی ندارد؟
با وجود این موفقیت، محدودیتی مهم وجود دارد.
- الگوریتم Karatsuba فقط برای اعداد نسبتاً بزرگ از روش سنتی سریع‌تر است.
- الگوریتم Harvey–van der Hoeven تنها برای اعدادی با اندازه‌ای تقریباً غیرقابل تصور برتری خود را نشان می‌دهد.
در علوم کامپیوتر به چنین روش‌هایی الگوریتم‌های کهکشانی (Galactic Algorithms) گفته می‌شود؛ زیرا تنها در اندازه‌هایی کارآمد هستند که در عمل تقریباً هیچ‌گاه مورد استفاده قرار نمی‌گیرند.
آیا سریع‌ترین حد ممکن برای ضرب پیدا شده است؟
بیشتر پژوهشگران علوم کامپیوتر نظری معتقدند پیچیدگی O(n×log n) سریع‌ترین حد ممکن برای ضرب اعداد است.
با این حال، اثبات رسمی این موضوع هنوز انجام نشده، این مسئله یکی از مهم‌ترین چالش‌های حل‌نشده ریاضیات به شمار می‌رود. تاریخ نیز نشان داده است که اجماع میان دانشمندان الزاماً به معنای اثبات ریاضی نیست؛ همان‌طور که فرضیه‌های پیشین درباره محدودیت سرعت ضرب نیز در گذشته رد شده‌اند.
سوالات متداول
الگوریتم Karatsuba چیست؟
الگوریتمی برای ضرب اعداد بزرگ است که بخشی از عملیات ضرب را با عملیات جمع جایگزین می‌کند تا تعداد ضرب‌های موردنیاز کاهش یابد.
چرا سرعت ضرب اعداد اهمیت دارد؟
زیرا رمزنگاری، هوش مصنوعی، پردازش صدا، طراحی تراشه‌ها، بسیاری از محاسبات رایانه‌ای به ضرب مکرر اعداد بسیار بزرگ وابسته هستند.
پیچیدگی O(n²) به چه معناست؟
یعنی با افزایش تعداد رقم‌های اعداد، میزان عملیات لازم متناسب با مربع آن رشد می‌کند.
الگوریتم Harvey–van der Hoeven چه مزیتی دارد؟
این الگوریتم دارای پیچیدگی زمانی O(n×log n) است، اما مزیت آن تنها برای اعدادی با اندازه بسیار بزرگ نمایان می‌شود.
جمع‌بندی
کشف Anatoly Karatsuba یکی از مهم‌ترین تحول‌های تاریخ الگوریتم‌های ریاضی بود و نشان داد باور چندصدساله درباره سریع‌ترین روش ضرب نادرست بوده است. با وجود پیشرفت‌های بزرگی مانند الگوریتم Harvey–van der Hoeven، اثبات نهایی سریع‌ترین حد ممکن برای ضرب همچنان یکی از مهم‌ترین مسائل باز ریاضیات و علوم کامپیوتر باقی مانده است.
اگر به تازه‌ترین اخبار فناوری، ریاضیات، هوش مصنوعی، علوم کامپیوتر علاقه‌مند هستید، مطالب بعدی ما را نیز دنبال کنید.
