🧮 یک مسئلهٔ هزارساله؛ یک دانشجوی 23 ساله!
✴️ ضرب کردن دو عدد؟ کاری که همه‌مان از دبستان یاد گرفته‌ایم.
مثلاً اگر دو عدد دو رقمی را در هم ضرب کنید، 4 ضرب لازم است.
برای دو عدد سه‌رقمی؟ 9 ضرب.
به طور کلی، هرچه تعداد رقم‌ها بیشتر شود، تعداد عملیات تقریباً با مجذور تعداد رقم‌ها رشد می‌کند.
در علوم کامپیوتر می‌گویند مرتبهٔ این الگوریتم:
O(n²)
یعنی با بزرگ‌تر شدن اعداد، تعداد محاسبات خیلی سریع افزایش پیدا می‌کند.
⁉️ اما آیا واقعاً راه بهتری وجود ندارد؟
🌟 سال 1960، ریاضیدان بزرگ روس، آندری کولموگروف ، همین سؤال را در یک سمینار در مسکو مطرح کرد و حدس زد که شاید نتوان ضرب را سریع‌تر انجام داد.
فقط یک هفته بعد، دانشجوی 23 ساله‌ای به نام آناتولی کاراتسوبا (Anatoly Karatsuba) به دیدن او رفت و گفت:
🔮 "فکر می‌کنم راه بهتری پیدا کرده‌ام!"
ایده‌اش ساده اما درخشان بود؛ تعداد ضرب‌ها را کم کنیم و به جایش از جمع و تفریق استفاده کنیم.
در روش معمول برای ضرب دو عدد دو رقمی به 4 ضرب نیاز داریم:
[(10a+b)(10c+d)=100ac+10(ad+bc)+bd]
اما کاراتسوبا نشان داد که جملهٔ میانی را می‌توان این‌گونه نوشت:
[ad+bc=(a+b)(c+d)-ac-bd]
در نتیجه، به جای 4 ضرب فقط 3 ضرب لازم است!
🌟 شاید برای اعداد کوچک تفاوت چندانی احساس نشود، اما وقتی اعداد صدها یا هزاران رقم داشته باشند، همین ایده باعث صرفه‌جویی عظیمی در زمان محاسبه می‌شود.
به این ترتیب، مرتبهٔ الگوریتم از
O(n²)
به
O(n^1.585)
کاهش پیدا کرد؛ جهشی بزرگ برای یکی از قدیمی‌ترین عملیات ریاضی.
و داستان همین‌جا تمام نشد...
در سال 2019، پژوهشگران الگوریتمی ارائه کردند که مرتبهٔ زمانی ضرب را به
O(n log n)
رساندند؛ چیزی که سال‌ها رؤیای دانشمندان علوم کامپیوتر و ریاضیات بود.
✨ گاهی کافی است یک نفر از خودش بپرسد:
⁉️ "آیا روشی که هزار سال است انجام می‌دهیم، واقعاً بهترین روش ممکن است؟"
همین سؤال، تاریخ محاسبات را تغییر داد...
🔗 برای مطالعه بیشتر اینجا کلیک کنید.
❖⟡❖───⟢❁⟡❁⟣───❖⟡❖
انجمن علمی دانشجویی ریاضی دانشگاه بوعلی‌سینا
📐 @math_Bu_Ali
•───⟢❁⟡❁⟣───•
