مشاهده

Report
‫سال‬
‫م‬
‫طراحی الگوریتم‬
‫ارائه دهنده‪ :‬میالد صفری‬
[email protected]
‫اسفندماه ‪۱۳۹۱‬‬
‫اعمال‬
‫محاسبات‬
‫ی‬
‫روی‬
‫اعداد صحیح‬
‫بزرگ‬
‫•‬
‫•‬
‫•‬
‫•‬
‫منظور از اعداد صحیح بزرگ اعدادی هستند که سخت‬
‫افزار کامپیوتر قادر به نمایش انها نیست‪.‬‬
‫تغییر حالت به ممیز شناور نیز در صورتی که‬
‫بخواهیم تمام ارقام معنی دار در نتیجه کار حفظ‬
‫شود ارزشی ندارد‪.‬‬
‫تنها راه باقی مانده برای نمایش این اعداد و‬
‫در نتیجه انجام محاسبات روی انها استفاده از‬
‫نرم افزار و دستکاری این اعداد است‪.‬‬
‫الگوریتم استفاده شده برای انجام محاسبات روی‬
‫این اعداد‪،‬برای اعداد در پایه ی ‪ 10‬است ولی‬
‫این روش را برای هر پایه ی دیگری نیز می توان‬
‫به کار بست‪.‬‬
‫•‬
‫راه صریح برای نشان دادن یک عدد صحیح ‪،‬استفاده‬
‫••••••••••••••••••••••••••••••••••‬
‫یک ارایه از اعداد صحیح است که هر محل از آن یک‬
‫یک‬
‫از‬
‫رقم را نگهداری می کند‪.‬‬
‫‪Exp:‬‬
‫‪543127‬‬
‫‪S[1]=7, s[2]=2, s[3]=1, s[4]=3, s[5]=4, s[6]=5‬‬
‫•‬
‫•‬
‫برای نگهداری اعداد مثبت یا منفی کافیست باالترین‬
‫محل ارایه را برای عالمت عدد رزرو کنیم‪،‬که اگر ‪ 1‬در‬
‫آن محل قرار گیرد عدد منفی و اگر‪ 0‬قرار گیرد عدد‬
‫مثبت است‪.‬‬
‫از نوع داده ی ‪ large_integer‬استفاده می کنیم تا آرایه‬
‫ای را که نشان می دهیم به قدر کافی بزرگ باشد که‬
‫اعداد مورد نظر ما را در آن بگنجد‪.‬‬
‫برخی از دستورهای استفاده شده در‬
‫الگوریتم‬
‫‪1) u*10‬‬
‫‪2) u divide 10‬‬
‫‪3) u rem 10‬‬
‫ضرب اعداد صحیح بزرگ‬
‫•‬
‫الگوریتمی که در اینجا ارائه می شود مبتنی بر روش‬
‫تقسیم و حل است‪.‬‬
‫بدین صورت که یک عدد صحیح ‪n‬رقمی را به دو عدد صحیح‬
‫با حدود ‪ n/2‬رقم تقسیم‬
‫می کنیم‪.‬‬
‫‪Exp:‬‬
‫‪567832=567*103 +832‬‬
‫‪3‬‬
‫‪3‬‬
‫‪6‬‬
‫•‬
‫•‬
‫•‬
‫به طور کلی اگر ‪ n‬تعداد ارقام صحیح ‪ u‬باشد‪،‬آن را‬
‫به دو عدد صحیح که یکی دارای‬
‫‪ /2‬رقم است و دیگری دارای‬
‫‪ /2‬رقم است‬
‫تبدیل می کنیم‪:‬‬
‫‪u=x*10 + y‬‬
‫‪/2‬‬
‫•‬
‫به این ترتیب‪،‬نمای ‪m‬عبارت است از‪:‬‬
‫‪m= /2‬‬
‫‪n /2‬‬
‫•‬
‫اگر دو عدد صحیح ‪ n‬رقمی داشته باشیم‪:‬‬
‫•‬
‫‪v=w*10 + z‬‬
‫حاصل ضرب آنها طبق رابطه ی زیر بدست می آید‪:‬‬
‫ ‪u=x*10 +‬‬
‫•‬
‫‪uv=(x*10 + )*(w*10 + z)=xw*102 +(xz+wy)*10 +yz‬‬
‫در اینصورت می توانیم ‪u‬و‪ v‬را با چهار عمل ضرب روی‬
‫اعداد صحیح و با حدود نیمی از ارقام در هم ضرب‬
‫کنیم‪.‬مثال زیر مفهوم را بهتر نشان می دهد‪:‬‬
‫=)‪567832*9423723=(567*103 +832)(9423*103 +723‬‬
‫•‬
‫•‬
‫‪567*9423*106 +(567*723+9423*832)*103 +832*723‬‬
‫سپس این اعداد کوچک را می توان با تقسیم آنها به‬
‫اعداد کوچکتر‪ ،‬در هم ضرب کرد‪.‬‬
‫این فرایند انقدر ادامه می یابد تا به یک مقدار‬
‫استانه برسیم که در ان زمان عمل ضرب به طریق‬
‫•‬
‫•‬
‫•‬
‫اگر چه متد بعد را با استفاده از اعداد صحیحی‬
‫نشان می دهیم که تعداد ارقام انها تقریبا یکی‬
‫است اما در غیر اینصورت نیز قابل استفاده‬
‫است‪ (.‬به این نکته به دقت توجه کنید)‬
‫کافیست از ‪ m= /2‬برای تبدیل هر دو عدد‬
‫استفاده کنیم‪،‬که در آن ‪ m‬تعداد ارقام موجود در‬
‫عدد بزرگتر است‪.‬‬
‫الگوریتمی که ارائه می دهیم تا زمانی ادامه می‬
‫یابد که یکی از اعداد صحیح صفر شود یا به یک‬
‫مقدار استانه برای عدد صحیح بزرگتر برسیم که‬
‫در آن عمل ضرب با استفاده از سخت افزار‬
‫کامپیوتر(روش معمول) انجام شود‪.‬‬
larg_integer prod(larg_integer u, larg_integer v)
{
‫الگوریتم ضرب اعداد صحیح بزرگ‬
larg_integer x,y,w,z;
v‫و‬u ‫ اعداد صحیح بزرگ‬:‫ورودی ها‬
int n,m;
v‫و‬u ‫ حاصل ضرب‬،prod : ‫خروجی ها‬
n=maximum(number of digits in u,number of digits v)
if(u==0 ∥ v==0)
return 0;
else if(n<=threshold)
return u*v obtained in the usual way;
else{
m= /2 ;
x=u divide 10 ; y=u rem 10 ;
w=v divide 10 ; z=v rem 10 ;
return prod(x,w)*102 +(prod(x,z)+prod(w,y))*10 +prod(y,z);
}
}
‫تحلیل پیچیدگی زمانی در بدترین حالت‬
‫برای الگوریتم‬
‫•‬
‫•‬
‫زمان الزم برای ضرب دو عدد صحیح ‪ n‬رقمی را تحلیل می کنیم‪.‬‬
‫عمل اصلی‪ :‬دستکاری یک رقم دهدهی در یک عدد صحیح بزرگ‬
‫•‬
‫•‬
‫‪1) u*10‬‬
‫‪2) u divide 10‬‬
‫‪3) u rem 10‬‬
‫هر یک از سه دستور باال‪ ،‬عمل اصلی را ‪ m‬بار انجام می دهد‪.‬‬
‫اندازه ورودی‪ n:‬تعداد ارقام ورودی هر یک از دو عدد صحیح‬
‫•‬
‫•‬
‫بدترین حالت زمانی است که هر دو عدد صحیح هیچ رقم مساوی‬
‫صفر نداشته باشند‪ ،‬زیرا بازگشتی فقط زمانی پایان می یابد‬
‫که به مقدار استانه ای برسیم‪.‬‬
‫تحلیل این حالت‪:‬‬
‫فرض کنید ‪ n‬توانی از دو باشد‪ .‬در این صورت ‪ x,y,z,w‬همگی‬
‫دقیقا ‪ n/2‬رقم دارند‪،‬یعنی اندازه ورودی هر یک از چهار‬
‫فراخوانی بازگشتی به تابع‪ n/2 ، prod‬است‪.‬‬
‫چون ‪ m=n/2‬است‪ ،‬دستورات‪:‬‬
‫‪1) u*10‬‬
‫‪2) u divide 10‬‬
‫‪3) u rem 10‬‬
‫همگی دارای پیچیدگی زمانی خطی نسبت به ‪ n‬هستند‪.‬حداکثر‬
‫اندازه ورودی برای دستورات باال یکسان نیست بنابراین تعیین‬
‫زمان پیچیدگی برای الگوریتم براحتی امکان پذیر نیست‪.‬‬
‫• راه حل‪:‬‬
‫راه بسیار ساده این است که همه ی عملیات زمانی خطی را در یک‬
‫جمله ی ‪ cn‬دسته بندی کنیم که ‪ c‬یک عدد ثابت است‪.‬‬
‫نک‬
‫ته‬
‫اگر به الگوریتم کمی دقت کنیم می بینیم که عالوه بر ‪،prod‬‬
‫‪102‬و ‪ 10‬داریم که باید در تحلیل پیچیدگی در نظر گرفته شوند‪.‬‬
‫•‬
‫در این صورت دستور بازگشتی چنین خواهد بود‪:‬‬
‫‪n>s‬‬
‫‪W(n)=4w(n/2)+cn‬‬
‫‪W(s)=0‬‬
‫مقدار واقعی ‪ s‬که در آن نمونه دیگر تقسیم نمی شود‪ ،‬کوچکتر یا مساوی‬
‫مقدار استانه و توانی از ‪ 2‬است‪.‬‬
‫انگاه با توجه به قضیه ب‪ 5-‬از پیوست دوم کتاب‪:‬‬
‫‪T(n)=at(n/b)+c‬‬
‫‪T(s)=d‬‬
‫)‬
‫‬
‫ ‪log‬‬
‫(‪t(n) € Θ‬‬
‫‬
‫>‪If a‬‬
‫• بنابراین‪:‬‬
‫) ‪W(n) € Θ(4 )=Θ(2‬‬
‫••••••••••••••••••••••••••••••••••‬
‫• الگوریتم ارائه شده هنوز هم از درجه ی ‪ 2‬است‪.‬‬
‫مشکل اینجاست که این الگوریتم عمل ضرب را روی‬
‫اعداد صحیح با نیمی از ارقام اولیه انجام می‬
‫دهد‪.‬‬
‫را‬
‫ه‬
‫حل‬
‫اگر بتوانیم الگوریتمی ارائه دهیم که تعداد ضرب‬
‫ها را کاهش دهد الگوریتمی بهتر از حالت درجه دوم‬
‫بدست می آوریم‪.‬‬
‫• تابع ‪ prod‬باید موارد زیر را تعیین کند‪:‬‬
‫‪Xw,xz+yw,yz‬‬
‫• واین کار را با چهار بار فراخوانی تابع ‪prod‬‬
‫برای محاسبه ی موارد زیر انجام می دهد‪:‬‬
‫‪Xw,xz,yw,yz‬‬
‫اگر به جای ان قرار دهیم ‪:‬‬
‫‪r=(x+y)(w+z)=xw+(xz+yw)+yz‬‬
‫در اینصورت خواهیم داشت‪:‬‬
‫‪xz+yw=r-xw-yz‬‬
‫• در نتیجه داریم‪:‬‬
‫‪r=(x+y)(w+z),xw,yz‬‬
‫• یعنی سه عمل ضرب و چند عمل جمع و تفریق اضافه‬
‫که که زمان انها خطی است‪.‬‬
Large_integer prod2(Large_integer u, Large_integer v)
{
Large_integer x,y,w,z,r,p,q;
int n,m;
n=maximum(number of digits in u,number of digits v)
if(u==0 ∥ v==0)
return 0;
else if(n<=threshold)
return u*v obtained in the usual way;
else{
m= /2 ;
x=u divide 10 ; y=u rem 10 ;
w=v divide 10 ; z=v rem 10 ;
r=prod2(x+y,w+z);
p=prod2(x,w);
q=prod2(y,z);
return p*102 +(r-p-q)*10 +q;
}
2 ‫بزرگ‬
‫ اعداد صحیح بزرگ‬:‫ورودی ها‬
v‫و‬u
‫ حاصل ضرب‬،prod:‫خروجی ها‬
v‫و‬u
‫تحلیل پیچیدگی زمانی در بدترین‬
‫حالت برای الگوریتم‬
‫•‬
‫•‬
‫تمامی توضیحات داده شده در الگوریتم قبل در اینجا‬
‫نیز صادق است به جز دو مورد‪:‬‬
‫‪ <=n/2‬اندازه ورودی <=‪(n/2)+1‬‬
‫•‬
‫• پس‬
‫تعداد دفعات فراخوانی تابع ‪ prod2‬نیز ‪ 3‬بار است‪.‬‬
‫بنابراین‪:‬‬
‫‪3w(n/2)+cn <= w(n) <= 3w((n/2)+1)+cn‬‬
‫‪w(s)=0‬‬
‫• باز هم مانند الگوریتم قبل با این تفاوت‬
‫که تابع بازگشتی سه با فراخوانی شده ‪:‬‬
‫) ‪W(n) € Θ(3 )=Θ(1.58‬‬
‫• که از الگوریتم قبل بهتر است‪.‬‬
‫در آخر از استاد بیدکی و همة ي‬
‫دوستان که وقتشان‬
‫را در اختیار من قرار دادند تشکر‬
‫می نمایم‪.‬‬
‫سوا‬
‫ل؟؟‬

similar documents