موضوع مقاله: الگوریتم تقسیم | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم تقسیم | مقدمه: الگوریتم تقسیم الگوریتمی است که با گرفتن دو عدد صحیح N و D، خارج‌قسمت یا باقی مانده آن‌ها را محاسبه می‌کند، که نتیجه تقسیم اقلیدسی است. | ## بخش 1: الگوریتم تقسیم | برخی از آن‌ها به صورت دستی استفاده می‌شوند، در حالی که برخی دیگر توسط طرح‌ها و نرم‌افزارهای مدارهای دیجیتال استفاده می‌شوند. الگوریتم‌های تقسیم به دو دسته اصلی تقسیم می‌شوند: تقسیم آهسته تقسیم سریع الگوریتم‌های تقسیم آهسته در هر تکرار یک رقم از خارج‌قسمت را تولید می‌کنند. روش‌های تقسیم سریع با تقریب نزدیک به خارج‌قسمت شروع می‌شود و دو برابر بیشتر رقم نهایی در هر تکرار تولید می‌کند. نشان می‌دهد که برای اعداد صحیح بزرگ، زمان کامپیوتر مورد نیاز برای تقسیم یکسان است، تا یک عامل ثابت، همانند زمان لازم برای انجام یک عمل ضرب به ازای هر الگوریتم استفاده شده. بحث به فرم اشاره می‌کند، که N = شمارنده (مقسوم) D = مخرج (مقسوم‌الیه) ورودی است، و Q = خارج‌قسمت R = باقیمانده خروجی است. تقسیم با تفریق مکرر ساده‌ترین الگوریتم تقسیم، که از لحاظ تاریخی در بزرگترین الگوریتم تقسیم کننده گنجانده شده‌است و در عناصر اقلیدس، کتاب VII، گزاره ۱ ارائه شده‌است، با گرفتن دو عدد صحیح مثبت فقط با استفاده از دو عمل تفریق و مقایسه، باقی‌مانده را محاسبه می‌کند. اگرچه بسیار ساده است، به اندازه (Ω (Q مرحله زمان می‌برد، و به همین ترتیب از الگوریتم‌های تقسیم آهسته مانند تقسیم طولانی کندتر است. اگر Q کوچک باشد (الگوریتم حساس‌به‌خروجی) مفید است و می‌تواند به عنوان یک ویژگی قابل اجرا استفاده شود. تقسیم طولانی تقسیم طولانی یک الگوریتم استاندارد است که برای تقسیم اعداد چند رقمی بیان شده در نماد اعشاری بر روی قلم و کاغذ استفاده می‌شود. این به تدریج از سمت چپ به انتهای راست مقسوم جابجا می‌شود و بزرگترین مضرب ممکن از مقسوم‌علیه را در هر مرحله تفریق می‌کند. مضروب‌ها سپس به رقم خارج‌قسمت تبدیل می‌شوند و نتیجه تفاضل نهایی در باقی مانده‌است. در صورت استفاده از ریشه دودویی، این روش اساس تقسیم عدد صحیح (بدون امضا) با الگوریتم باقیمانده زیر را تشکیل می‌دهد. [./ تقسیم کوتاه] یک شکل مختصر از تقسیم طولانی است که برای تقسیم کننده‌های تک رقمی مناسب است. Chunking - همچنین به عنوان روش اختصاصی جزئی یا روش جلاد شناخته می‌شود - نوعی تقسیم طولانی است که کمتر کارآمد است و درک آن ساده‌تر است. با اجازه دادن به چند برابر تعداد بیشتری از آنچه در حال حاضر در هر مرحله است، می‌توان یک نوع آزاد شکل بیشتری از تقسیم طولانی ایجاد کرد. روش‌های تقسیم آهسته روش‌های تقسیم آهسته همه بر اساس یک معادله بازگشتی استاندارد انجام می‌شوند. درحالی که: R j بخش j ام باقی‌مانده تقسیم است B ردیف است (معمولاً دوتا مبنا در داخل کامپیوترها و ماشین‌حساب‌ها هستند) (q n − (j + 1) عدد خارج قسمت در محل (n− (j + 1) است، درحالیکه محل رقم‌ها از کمترین اهمیت ۰ تا مهمترین آن‌ها n -1 شماره گذاری می‌شود. n تعداد رقم‌های خارج قسمت D تقسیم کننده است تقسیم بازگشتی بازیابی تقسیم بر روی اعداد کسری ثابت کار می‌کند و به این فرض بستگی دارد بر 0 <N> D. تقسیم بازگشتی غیراجرایی مانند تقسیم بازگشتی است، به جز اینکه مقدار 2R ذخیره شده‌است، بنابراین نیازی نیست D برای موارد R < 0 اضافه شود. تقسیم غیربازگشتی در تقسیم غیر بازگشتی از مجموعه ارقام {− 1، ۱} به‌جای {۰، ۱} برای خارج قسمت استفاده می‌کند. این الگوریتم پیچیده‌تر است، اما هنگامی که در سخت‌افزار اجرا می‌شود این مزیت را دارد که در هر بیت خارج قسمت فقط یک تصمیم و جمع / تفریق وجود دارد. پس از تفریق هیچ مرحلهٔ بازیابی وجود ندارد، که به‌طور بالقوه تعداد عملیات را تا نیمی از آن کاهش دهد و اجازه دهد سریعتر انجام شود. مثال: مقدار زیر را به مجموعه ارقام {۰٬۱} تبدیل کنید: شروع: ۱ شرط عبارت مثبت را تشکیل دهید: ۲ شرط عبارت منفی را پنهان کنید*: ۳ کم کنید: * (یادداشت باینری امضا شده با یک مکمل یکی بدون Two's Complement) اگر −۱ ارقامی از هستند که به صورت صفر (۰) ذخیره می‌شوند پس هست و محاسبه بدیهی است: انجام یک مکمل (مکمل بیت به بیت) روی اصلی. سرانجام، خارج‌قسمت‌های محاسبه‌شده توسط این الگوریتم همیشه فرد هستند و باقی‌مانده R در دامنه −D ≤ R < D. | ## بخش 2: الگوریتم تقسیم | تقسیم SRT مشابه تقسیم غیربازگشتی است، اما از یک جدول جستجو براساس مقسوم و مقسوم‌علیه برای تعیین هر رقم خارج‌قسمت استفاده می‌کند. مهم‌ترین تفاوت این است که یک نمایش اضافی برای خارج‌قسمت مورد استفاده قرار می‌گیرد. برای مثال، هنگام اجرای تقسیم SRT در مبنا ۴، هر رقم خارج‌قسمت از پنج امکان انتخاب می‌شود: {−۲، −۱، ۰، +۱، +۲ }. به این دلیل، انتخاب یک رقم خارج‌قسمت کافی نیست؛ ارقام بعدی می‌توانند خطاهای جزئی را اصلاح کنند. (به‌عنوان مثال، جفت‌های رقم خارج‌قسمت (۰، +۲) و (۱، −۲) معادل هستند، زیرا ۰ × ۴ + ۲ = ۱ × ۴ − ۲ است) این تحمل اجازه می‌دهد که ارقام خارج‌قسمت تنها با استفاده از چند بخش عمده از مقسوم و مقسوم‌علیه، بجای نیاز به یک کاهش با عرض کامل انتخاب شوند. این ساده‌سازی به‌نوبه خود اجازه می‌دهد تا یک مبنایی بالاتر از ۲ مورد استفاده قرار گیرد. مانند تقسیم غیربازگشتی، آخرین مراحل یک تفریق کامل نهایی برای حل آخرین بیت خارج‌قسمت، و تبدیل خارج‌قسمت به شکل دوگانه استاندارد هستند. روش‌های تقسیم سریع بخش نیوتن - رافسون نیوتن - رافسون از روش نیوتن برای پیدا کردن معکوس D استفاده می‌کند و آن را ضرب می‌کند که با N معکوس می‌شود تا خارج‌قسمت نهایی Q را پیدا کند. مراحل تقسیم نیوتن - رافسون عبارتند: یک تخمین برای معکوس از مقسوم‌علیه محاسبه کنید. به منظور استفاده از روش نیوتن برای یافتن معکوس برای یافتن یک تابع که دارای یک صفر در است، لازم است. تابع واضح این است که اما تکرار نیوتن - رافسون برای این، بی‌فایده است، چون نمی‌تواند بدون دانستن معکوس بودن آن محاسبه شود. (علاوه بر آن، برای محاسبه متقابل دقیق در یک مرحله به جای امکان بهبود تکراری تلاش می‌کند). که می‌توان از آن را فقط با استفاده از ضرب و تفریق، یا با استفاده از دو ترکیب ضرب - اضافه‌شده محاسبه کرد. از دیدگاه محاسباتی، عبارات و معادل نیستند برای به دست آوردن نتیجه با دقت 2 n بیت در حالی که از عبارت دوم استفاده می‌کنند، باید نتیجه را بین و محاسبه کند و با دقت مضاعف از (تعداد بیت) در مقابل، نتیجه بین و فقط باید با دقت n بیت محاسبه شود زیرا n بیت‌های اصلی (پس از نقطه دودویی) از صفر هستند. اگر این خطا به این‌صورت تعریف شود: ، سپس: این مربع خطا در هر گام تکرار - به اصطلاح هم‌گرایی درجه‌دوم روش نیوتن - رافسون - تأثیری دارد که تعداد ارقام صحیح در نتیجه تقریباً برای هر تکرار دوبرابر می‌شود. یک ویژگی که زمانی بسیار ارزشمند می‌شود که اعداد شامل بسیاری از ارقام باشند (به عنوان مثال در دامنه بزرگ عدد صحیح). اما به این معنی است که هم‌گرایی اولیه این روش می‌تواند نسبتاً کند باشد، به خصوص اگر تخمین اولیه انتخاب ضعیفی باشد. برای مسئله فرعی انتخاب یک تخمین اولیه ، می‌توان یک تغییر بیتی به مقسوم‌علیه مشترک را اعمال کرد تا آن را در مقیاس قرار دهید؛ با اعمال همان تغییر بیت بر روی عدد، اطمینان حاصل می‌شود که مقدار تغییر نمی‌کند. سپس می‌توان از تقریب خطی با این شکل استفاده کرد برای دادن مقدار اولیه نیوتن-رافسون. برای به حداقل رساندن حداکثر مقدار مطلق خطای این تخمین در فاصله ، باید استفاده کرد. ایجاد یک چندجمله‌ای با درجه بزرگ‌تر از ۱، محاسبه ضرایب با استفاده از الگوریتم Remez امکان‌پذیر است. نکته اصلی این است که حدس اولیه به چرخه‌های محاسباتی بیشتری نیاز دارد، اما امید به تبادل برای تکرارهای کمتری از نیوتن - رافسون. از آنجا که برای این روش همگرایی، دقیقاً درجه دوم است، به دنبال آن است که این مراحل برای محاسبه ارزش تا دو رقم دودویی کافی هستند. این به ۳ مورد برای IEEE تک دقت و ۴ برای هر دو با دقت دو برابر و دو فرمت توسعه یافته ارزیابی می‌شود. | ## بخش 3: الگوریتم تقسیم | تقسیم واریانت نیوتن - رافسون روش تقسیم نیوتن-رافسون می‌تواند کمی تغییر کند تا به شرح زیر باشد. پس از تغییر N و D به گونه ای که D در [۰٫۵ ، ۱٫۰] باشد، مقدار اولیه را با آن شروع کنید این بهترین تناسب درجه دوم برای 1 / D است و مقدار مطلق خطا را کمتر از یا برابر با ۱/۹۹ می‌دهد. اگر حلقه تا زمانی اجرا شود که X با ۱ / D در بیت‌های اصلی P موافقت کند، آنگاه تعداد تکرارها بیش از این نخواهد بود. استفاده از چند جمله‌ای‌های درجه بالاتر در هر کدام از مقداردهی اولیه یا تکرار، منجر به تجزیه عملکرد می‌شود زیرا ضرب اضافی مورد نیاز برای انجام تکرارهای بیشتر صرف خواهد شد. تقسیم گلدشمیت تقسیم گلدشمیت (پس از رابرت الیوت گلدشمیتد از یک فرایند تکراری برای ضرب مکرر هردو، مقسوم و مقسوم‌الیه مشترک با یک عامل مشترک F i استفاده می‌کند، این انتخاب به گونه‌ای است که مقسوم به ۱ برسد. این باعث می‌شود مقسوم به جستجوی خارج‌قسمت Q برسد: مراحل تقسیم گلدشمیت به شرح زیر است: تخمینی را برای فاکتور ضرب F i ایجاد کنید. اگر مقسوم‌الیه به اندازه کافی نزدیک به ۱ است، مقسوم را برگردانید، در غیر این‌صورت، حلقه را به مرحله ۱ بازگردانید. با فرض N / D، اندازه‌گیری شده‌است به‌طوری که ، هر F i بر اساس D است: ضرب مقسوم و مقسوم‌الیه براساس نتایج حاصله عبارتند از: بعد از تکرار تعداد کافی K . 2004, قضیه دو جمله ای در روش گلدشمیت می‌توان از عواملی استفاده کرد که اجازه می‌دهند تا به ساده‌سازی قضیه دو جمله‌ای کمک شود. که حداکثر در چه زمانی ، بنابراین حداقل دقت را در مورد رقم‌های ودویی ارائه می‌دهد. روش‌های عدد صحیح روش‌هایی که برای پیاده‌سازی سخت‌افزار طراحی شده‌اند معمولاً اعداد صحیح را با هزاران یا میلیون‌ها رقم اعشار نشان نمی‌دهند، به عنوان مثال در کاهش پیمانه‌ای در رمزنگاری رخ می‌دهند. نتیجه این است که پیچیدگی محاسباتی تقسیم به همان ترتیب (تا یک ثابت افزاینده)به عنوان ضرب ضرب است. نمونه‌هایی از کاهش ضرب و ضرب در روش نیوتن، همان‌طور که در بالا توضیح داده شد، [۱۳] و نیز کاهش اندکی سریع‌تر بارت و الگوریتم کاهش مونتگومری. [۱۴] [تأیید مورد نیاز] روش نیوتن به‌طور خاص در سناریوهایی مؤثر است که باید چندین بار در همان مقسوم‌علیه مشترک تقسیم شود، زیرا پس از وارونگی اولیه نیوتن تنها یک ضرب (کوتاه) برای هر بخش مورد نیاز است. از آنجا که مخرج ثابت است، متقابل آن نیز (1 / D) است؛ بنابراین می‌توان مقدار (1 / D) را یک بار در زمان کامپایل محاسبه کرد، و در زمان اجرا ضرب N و (1 / D) را به جای تقسیم N / D انجام داد. در نقطهٔ شناوریحسابی استفاده از (1 / D) مشکل کمی ایجاد می‌کند، اما درعدد صحیح حسابی، معکوس همیشه صفر (فرض | D |> 1) ارزیابی می‌شود. به عنوان مثال، برای تقسیم ۳ می‌توان از عوامل ۱/۳، ۲/۶، ۳/۹ یا ۱۹۴/۵۸۲ استفاده کرد. در نتیجه، اگر Y از قدرت دو مرحله تقسیم را داشته‌باشد، مرحله تقسیم به یک تغییر بیت سریع سریع کاهش می‌یابد. اما، مگر اینکه خود D دو قدرت داشته باشد، هیچ X و Y وجود ندارد که شرایط فوق را برآورده کند. خوشبختانه، N · X) / Y) دقیقاً همان نتیجه N / D در عدد صحیح حسابی را به دست می‌آورد حتی وقتی (X / Y) دقیقاً برابر با 1 / D نباشد، اما «به اندازه کافی نزدیک» است که خطایی که توسط تقریبی ایجاد شده‌است است. در واقعیت نمونه نقطه حسابی ثابت از اعداد صحیح بدون علامت ۳۲ بیتی، تقسیم‌شده توسط ۳ می‌تواند بوسیله یک ضرب با جایگزین شود. به همین ترتیب، تقسیم بر ۱۰ را می‌توان به صورت ضرب 3435973837 (0xCCCCCCCD) و به دنبال آن تقسیم 2 35 (یا ۳۵ تغییر بیت مناسب) بیان کرد. | ## جمع‌بندی | [۱۹] خطای دور می‌تواند به دلیل خطای گرد کردن خطای گرد کردن می‌تواند ناشی‌از محدودیت دقیق توسط عملیات تقسیم معرفی شود.