دوشنبه ۳۱ ارديبهشت ۱۴۰۳   |  كاربر مهمان  |    
 XMod FormView
اين ماژول نياز به پيكربندي دارد
 XMod
 test
 ضرب دو عدد، سریع!
ضرب دو عدد، سریع!زنگ تفريح كامپيوتر
زنگ‌تفریح شماره‌ی 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 کاهش داد. یعنی یک پیروزی بزرگ.
1389/2/14لينک مستقيم
نظر شما پس از تاييد در سايت قرار داده خواهد شد
نام :
پست الکترونيکي :
صفحه شخصي :
نظر:
تاییدانصراف
 Blog List
 New Blog
شما بايد وارد شده واجازه ساخت و يا ويرايش وبلاگ را داشته باشيد.
 ضرب دو عدد، سریع!
ضرب دو عدد، سریع!زنگ تفريح كامپيوتر
زنگ‌تفریح شماره‌ی 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 کاهش داد. یعنی یک پیروزی بزرگ.
1389/2/14لينک مستقيم
نظر شما پس از تاييد در سايت قرار داده خواهد شد
نام :
پست الکترونيکي :
صفحه شخصي :
نظر:
تاییدانصراف
 Blog Archive
 test
Use module action menu to edit content
 Bonosoft - Link
 Text/HTML
Use module action menu to edit content

سرویس‌های رشد:

فهرست:

وزارت آموزش و پرورش > سازمان پژوهش و برنامه‌ريزی آموزشی
شبکه ملی مدارس ایران (رشد)