رفتن به مطلب
Mohammad Aref

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

پست های پیشنهاد شده

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

do.php?imgf=155574773953931.jpg

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

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

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

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

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

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

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

به اشتراک گذاری این ارسال


لینک به ارسال
به اشتراک گذاری در سایت های دیگر

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

مهمان
ارسال پاسخ به این موضوع ...

×   شما در حال چسباندن محتوایی با قالب بندی هستید.   حذف قالب بندی

  تنها استفاده از ۷۵ اموجی مجاز می باشد.

×   لینک شما به صورت اتوماتیک جای گذاری شد.   نمایش به عنوان یک لینک به جای

×   محتوای قبلی شما بازگردانی شد.   پاک کردن محتوای ویرایشگر

×   شما مستقیما نمی توانید تصویر خود را قرار دهید. یا آن را اینجا بارگذاری کنید یا از یک URL قرار دهید.


×
×
  • جدید...