ریاضی‌دانان الگوریتم جدیدی برای ضرب اعداد بزرگ ارائه دادند

[Mohammad Aref 120452]

تیمی از ریاضی‌دانان دانشگاه نیو ساوت ولز در استرالیا و دانشگاه پلی تکنیک اکول در فرانسه، معمای ریاضیاتی که چندین دهه حل‌نشده باقی مانده بود را حل کردند که باعث می‌شود ضرب اعداد بزرگ در زمان ِ بسیار سریع‌تری انجام شود.

هاروی و ون هوون مسئله‌ای ریاضیاتی ۵۰ ساله‌ای را حل کردند که به کامپیوترها این امکان را می‌دهد تا اعداد بزرگ را بسیار سریع‌تر ضرب کنند.

دکتر دیوید هاروی از دانشکده ریاضی و آمار دانشگاه نیو ساوت ولز، بیان داشت: «به لحاظ فنی، ما حدسی که در سال ۱۹۷۱ توسط شونهاگ و استراسن در مورد پیچیدگی ضرب عدد صحیح مطرح شده بود را اثبات کردیم. آنها پیش‌بینی کرده بودند که باید الگوریتمی وجود داشته باشد که اعدادِ n رقمی را با استفاده از عملیات اصلیِ n* log(n) ضرب کند.»

وی افزود: «مقالۀ ما اولین مثال از الگوریتمی را ارائه می‌دهد که به این حدس دست یافته است. به بیان دیگر، اگر بخواهیم اعداد ۳۱۴ و ۱۵۹ را با روش ابتدایی مدرسه‌ای ضرب کنیم، باید حاصل‌ضرب‌های ۹ رقمی را محاسبه کنیم. به طور کلی اگر n بیانگر تعداد رقم‌ها در هر عدد باشد، می‌توان در عملیات n2 به پاسخ دست یافت.» شونهاگ و استراسن خودشان الگوریتمی را ابداع کردند که به عملیاتی کمتر از n2 نیاز داشت اما نتوانستند به الگوریتم n* log(n) برسند.

دکتر هاروی افزود: «الگوریتم شونهاگ- استراسن بسیار سریع است: کامپیوتری که از روش ابتدایی مدرسه‌ای استفاده می‌کند ماه‌ها طول می‌کشد تا دو عدد یک میلیارد رقمی را ضرب کند، اما کامپیوتری که از روش شونهاگ- استراسن استفاده می‌کند در کمتر از ۳۰ ثانیه این ضرب را انجام می‌دهد.»

اما برای اعدادی که رقم‌های کافی دارند- میلیارد، تریلیون یا حتی بیشتر- الگوریتم جدیدی که توسط دکتر هاروی و دکتر جوریس ون در هوون از دانشگاه پلی تکنیک اکول ارائه شده، می‌تواند حتی بهتر از الگوریتم شونهاگ و استراسن عمل کند. شونهاگ و استراسن همچنین پیش‌بینی کردند که n* log(n) بهترین نتیجۀ ممکن است- و هیچکس دیگری هرگز الگویی سریع‌تر از این برای ضرب پیدا نخواهد کرد.

دکتر هاروی گفت: «بنابراین انتظار می‌رود که کار ما انتهای راه برای این مسئله باشد، اگر چه هنوز نمی‌دانیم که چطور این را ثابت کنیم.» گرچه هنوز روزهای اول است اما این پیشرفت، پیامدهای بی‌شماری خواهد داشت. این بدان معنی است که می‌توانیم هر نوع محاسباتی مثل تقسیم و جذر را به طور مؤثرتری انجام دهیم. همچنین می‌توانیم رقم‌های pi را بهتر از قبل حساب کنیم. این الگوریتم حتی در مسائلی که دارای اعداد اول بزرگ هستند نیز کاربرد دارد.» مقاله این تیم در آرشیو چندرسانه‌ایِ HAL با دسترسی آزاد، منتشر شده است.

ترجمه: زهرا جهانبانی - بیگ بنگ