فرض کنید یک عدد خیلی بزرگ (مثلا 30 رقم !) رو به یه روشی توی حافظه ی کامپیوتر ذخیره کردیم .(مثلا بردن به مبنای 256 یا تبدیل به کاراکتر و ....)
حالا می خوایم این عدد رو بر یک عدد دیگه تقسیم کنیم !( اجازه ی استفاده از اپراتور تقسیم رو هم به صورت مستقیم نداریم !!)
چه روشی به نظر شما خوبه ؟!
احتمالا تا الآن جوابتون رو پیدا کردین، نه؟
-----------------------------------------------------
من فرض می‌کنم هر دو عدد (هم مقسوم و هم مقسوم علیه) بیش از اندازه بزرگ هستند.
دو راه حل پیشنهاد می‌کنم:
روش اول) شیفت دادن:
ببینید، اولین نکته اینه که ما می‌تونیم در هر مبنایی عمل شیفت دادن رو خیلی سریع انجام بدیم. منظور از عمل شیفت دادن در مبنای n، ضرب عدد در توانی از nه. مثلا در مبنای ده، ضرب یک عدد در توانی از ده خیلی ساده‌ست؛ چون فقط کافیه یک یا چند صفر جلوی عدد قرار بدیم. (در سایر مبناها هم همینطوره)
از حالا به بعد بیاین فرض کنیم عدد را در مبنای ده ذخیره کردیم. و عمل شیفت را هم پیاده کرده‌ایم.
حالا اگه بخوایم عدد a را بر b تقسیم کنیم، می تونیم به این شیوه پیش بریم:
۱- b را شیفت می‌دیم (در ده ضرب می‌کنیم)، آنقدر که اگه یک مرحله دیگه پیش بریم، از a بزرگتر بشه. با کمی دقت می‌بینیم که تعداد شیفت مورد نیاز از روی تعداد ارقام دو عدد قابل محاسبه ست. خود عمل شیفت بدون هزینه است.
۲- عدد بدست آمده رو (یعنی b*10^k رو) چندبار با خودش جمع می‌زنیم و با a مقایسه می‌کنیم تا ببینیم آخرین رقم سمت چپ خارج قسمت چند است.
۳- مقدار a-b را حساب می کنیم و به جای a قرار می‌دیم. و دوباره از اول.
با این روش تعداد مراحل مورد نیاز برای رسیدن به جواب برابره با:
(تعداد ارقام خارج قسمت) * (عدد مبنا: مثلا ده) * (تعداد مراحلی که برای محاسبه جمع یا تفریق لازمه = تعداد ارقام مقسوم)
که یعنی:
(لگاریتم a/b در مبنای n) * (n) * (لگاریتم a در مبنای n)
بهبودی که می‌شه به این الگوریتم داد، اینه که در مرحله دوم به جای جستجوی خطی، از جستجوی دودویی استفاده کنیم:
(لگاریتم a/b در مبنای n) * (لگاریتم n در مبنای 2) * (لگاریتم a در مبنای n)
که یعنی:
(لگاریتم a/b در مبنای 2) * (لگاریتم a در مبنای n)
روش دوم) جستجوی دودویی:
۱- آنقدر b را با خودش جمع می‌زنیم (در واقع دو برابر می‌کنیم) تا زمانیکه اگر یکبار دیگر اینکار را انجام دهیم از a بزرگتر شود. (مثلا k بار) فرض کنید حاصل تمامی مراحل را در یک آرایه‌ی kتایی ذخیره کرده‌ایم.
۲- اکنون حساب کردن خارج قسمت ساده‌ست. کافیه که از بزرگترین عدد ذخیره شده شروع کنیم (یعنی درایه kام آرایه) و به عقب برگردیم. هر بار عدد حاصل از مرحله قبل را با عدد جدید جمع می‌زنیم، اگر بیشتر از a شد یعنی بیت kام خارج قسمت صفر است. وگرنه بیت مذبور یک است.
پیچیدگی این روش هم:
(تعداد مراحل محاسبه یعنی k) * (محاسبه جمع و تفریق)
یعنی:
(لگاریتم a/b در مبنای 2) * (لگاریتم a در مبنای n)
نتیجه) مقایسه دو روش:
جالبه که هر دو روش پیچیدگی زمانی یکسانی بدست می‌دهند. (تفاوت فقط در مقدار ثابت است). اما روش اول خارج قسمت را مستقیما در مبنای هدف محاسبه می کنه، در حالیکه روش دوم خارج قسمت را در مبنای دو حساب می‌کنه. همینطور از لحاظ پیچیدگی حافظه روش دوم نیاز به بهبود داره.
