الگوریتم تقسیم

الگوریتم تقسیم الگوریتمی است که با گرفتن دو عدد صحیح N و D، خارج‌قسمت یا باقی مانده آن‌ها را محاسبه می‌کند، که نتیجه تقسیم اقلیدسی است. برخی از آن‌ها به صورت دستی استفاده می‌شوند، در حالی که برخی دیگر توسط طرح‌ها و نرم‌افزارهای مدارهای دیجیتال استفاده می‌شوند.

الگوریتم‌های تقسیم به دو دسته اصلی تقسیم می‌شوند:

تقسیم آهسته
تقسیم سریع

الگوریتم‌های تقسیم آهسته در هر تکرار یک رقم از خارج‌قسمت را تولید می‌کنند. نمونه‌هایی از تقسیم آهسته عبارت‌اند از بازیابی، بازیابی مجدد، عدم ترمیم و تقسیم SRT(Street and Racing Technology) یا همان فناوری خیابان و مسابقه. روش‌های تقسیم سریع با تقریب نزدیک به خارج‌قسمت شروع می‌شود و دو برابر بیشتر رقم نهایی در هر تکرار تولید می‌کند. الگوریتم‌های Newton-Raphson و Goldschmidt در این گروه قرار می‌گیرند.

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

بحث به فرم $N/D=(Q,R)$ اشاره می‌کند، که

N = شمارنده (مقسوم)
D = مخرج (مقسوم‌الیه)

ورودی است، و

Q = خارج‌قسمت
R = باقیمانده

خروجی است.

تقسیم با تفریق مکرر

ساده‌ترین الگوریتم تقسیم، که از لحاظ تاریخی در بزرگترین الگوریتم تقسیم کننده گنجانده شده‌است و در عناصر اقلیدس، کتاب VII، گزاره ۱ ارائه شده‌است، با گرفتن دو عدد صحیح مثبت فقط با استفاده از دو عمل تفریق و مقایسه، باقی‌مانده را محاسبه می‌کند.

while N ≥ D do
  N := N − D
end
return N

اثبات وجود و انحصار باقی مانده و خارج‌قسمت (که در تقسیم اقلیدسی شرح داده شده‌است) منجر به ایجاد یک الگوریتم تقسیم کامل با استفاده از جمع، تفریق و مقایسه می‌شود:

function divide(N, D)
  if D = 0 then error(DivisionByZero) end
  if D <0 then (Q, R) := divide(N, −D); return (−Q, R) end
  if N <0 then
    (Q,R) := divide(−N, D)
    if R = 0 then return (−Q, 0)
    else return (−Q − 1, D − R) end
  end
  -- At this point, N ≥ 0 and D> 0
  return divide_unsigned(N, D)
end
function divide_unsigned(N, D)
  Q := 0; R := N
  while R ≥ D do
    Q := Q + 1
    R := R − D
  end
  return (Q, R)
end

این روش همیشه R ≥ ۰ تولید می‌کند. اگرچه بسیار ساده است، به اندازه (Ω (Q مرحله زمان می‌برد، و به همین ترتیب از الگوریتم‌های تقسیم آهسته مانند تقسیم طولانی کندتر است. اگر Q کوچک باشد (الگوریتم حساس‌به‌خروجی) مفید است و می‌تواند به عنوان یک ویژگی قابل اجرا استفاده شود.

تقسیم طولانی

تقسیم طولانی یک الگوریتم استاندارد است که برای تقسیم اعداد چند رقمی بیان شده در نماد اعشاری بر روی قلم و کاغذ استفاده می‌شود. این به تدریج از سمت چپ به انتهای راست مقسوم جابجا می‌شود و بزرگترین مضرب ممکن از مقسوم‌علیه را در هر مرحله تفریق می‌کند. مضروب‌ها سپس به رقم خارج‌قسمت تبدیل می‌شوند و نتیجه تفاضل نهایی در باقی مانده‌است.

در صورت استفاده از ریشه دودویی، این روش اساس تقسیم عدد صحیح (بدون امضا) با الگوریتم باقیمانده زیر را تشکیل می‌دهد. [./https://en.wikipedia.org/wiki/Short%20division تقسیم کوتاه] یک شکل مختصر از تقسیم طولانی است که برای تقسیم کننده‌های تک رقمی مناسب است. Chunking - همچنین به عنوان روش اختصاصی جزئی یا روش جلاد شناخته می‌شود - نوعی تقسیم طولانی است که کمتر کارآمد است و درک آن ساده‌تر است. با اجازه دادن به چند برابر تعداد بیشتری از آنچه در حال حاضر در هر مرحله است، می‌توان یک نوع آزاد شکل بیشتری از تقسیم طولانی ایجاد کرد.

تقسیم بهره (بدون امضا) با باقی مانده

if D = 0 then error(DivisionByZeroException) end
Q := 0                  -- Initialize quotient and remainder to zero
R := 0
for i := n − 1 .. 0 do  -- Where n is number of bits in N
  R := R <<1           -- Left-shift R by 1 bit
  R(0) := N(i)          -- Set the least-significant bit of R equal to bit i of the numerator
  if R ≥ D then
    R := R − D
    Q(i) := 1
  end
end

مثال

اگر N = 1100 ₂ (12 ₁₀) و D = 100 ₂ (4 ₁₀) بگیریم

مرحله اول: R = ۰ و Q = ۰ را تنظیم کنید مرحله دوم: i = ۳ را بگیرید (یکی کمتر از تعداد بیت‌های N) مرحله سوم: R = ۰۰ (سمت چپ توسط ۱) مرحله چهارم: R = ۰۱ (تنظیم (R(0 تا (N(i) مرحله پنجم: R <D، بنابراین بیانیه را رد کنید

مرحله دوم: تنظیم i = ۲ مرحله سوم: R = ۰۱۰ مرحله چهارم: R = ۰۱۱ مرحله پنجم: R <D، بیانیه رد شد

مرحله دوم: تنظیم i = ۱ مرحله سوم: R = ۰۱۱۰ مرحله چهارم: R = ۰۱۱۰ مرحله پنجم: R> = D، عبارت وارد شده‌است مرحله پنج بی: 5b: R = 10 (R − D) مرحله پنج سی: 5c: Q = ۱۰ (تنظیم Q (i) تا ۱)

مرحله دوم: تنظیم i = ۰ مرحله سوم: R = ۱۰۰ مرحله چهارم: R = ۱۰۰ مرحله پنجم: R> = D، عبارت وارد شده‌است مرحله پنج‌بی: R = 0 (R − D) مرحله پنج‌سی: Q = ۱۱ (تنظیم Q (i) تا ۱)

پایان

(Q = 11 ₂ (3 ₁₀ و R = ۰.

روش‌های تقسیم آهسته

روش‌های تقسیم آهسته همه بر اساس یک معادله بازگشتی استاندارد انجام می‌شوند.

R_{j+1}=B\times R_{j}-q_{n-(j+1)}\times D\,

درحالی که:

R _j بخش j ام باقی‌مانده تقسیم است
B ردیف است (معمولاً دوتا مبنا در داخل کامپیوترها و ماشین‌حساب‌ها هستند)
(q _{n − (j + 1)} عدد خارج قسمت در محل (n− (j + 1) است، درحالیکه محل رقم‌ها از کمترین اهمیت ۰ تا مهمترین آن‌ها n -1 شماره گذاری می‌شود.
n تعداد رقم‌های خارج قسمت
D تقسیم کننده است

تقسیم بازگشتی

بازیابی تقسیم بر روی اعداد کسری ثابت کار می‌کند و به این فرض بستگی دارد بر 0 <N> D.^{^{[نیازمند منبع]}}

اعداد خارج قسمت q از مجموعه ارقام {۰, ۱} تشکیل شده‌است.

الگوریتم پایه برای بازیابی تقسیم باینری (در مبنا ۲) عبارت است از:

R := N
D := D <<n            -- R and D need twice the word width of N and Q
for i := n − 1 .. 0 do  -- For example 31..0 for 32 bits
  R := 2 * R − D          -- Trial subtraction from shifted value (multiplication by 2 is a shift in binary representation)
  if R ≥ 0 then
    q(i) := 1          -- Result-bit 1
  else
    q(i) := 0          -- Result-bit 0
    R := R + D         -- New partial remainder is (restored) shifted value
  end
end

-- Where: N = Numerator, D = Denominator, n = #bits, R = Partial remainder, q(i) = bit #i of quotient

الگوریتم تقسیم بازگشتی در بالا با حفظ مقدار تغییرداده شدهٔ 2R قبل از تفریق به‌جای ثابت فرعی T

(به عنوان مثال، T = R <<1) و کپی کردن ثابت T به‌جای R هنگامی‌که نتیجهٔ تفریق 2R - D منفی باشد، می‌تواند از مرحله بازیابی صرف‌نظر کند.

تقسیم بازگشتی غیراجرایی مانند تقسیم بازگشتی است، به جز اینکه مقدار 2R ذخیره شده‌است، بنابراین نیازی نیست D برای موارد R < 0 اضافه شود.

تقسیم غیربازگشتی

در تقسیم غیر بازگشتی از مجموعه ارقام {− 1، ۱} به‌جای {۰، ۱} برای خارج قسمت استفاده می‌کند. این الگوریتم پیچیده‌تر است، اما هنگامی که در سخت‌افزار اجرا می‌شود این مزیت را دارد که در هر بیت خارج قسمت فقط یک تصمیم و جمع / تفریق وجود دارد. پس از تفریق هیچ مرحلهٔ بازیابی وجود ندارد، که به‌طور بالقوه تعداد عملیات را تا نیمی از آن کاهش دهد و اجازه دهد سریعتر انجام شود.^[۱] الگوریتم پایه برای دودویی (مبنای ۲) تقسیم غیر بازگشتی اعداد غیر منفی است:

R := N
D := D <<n            -- R and D need twice the word width of N and Q
for i := n − 1 .. 0 do  -- For example 31..0 for 32 bits
  R := 2 * R − D          -- Trial subtraction from shifted value (multiplication by 2 is a shift in binary representation)
  if R ≥ 0 then
    q(i) := 1          -- Result-bit 1
  else
    q(i) := 0          -- Result-bit 0
    R := R + D         -- New partial remainder is (restored) shifted value
  end
end

-- Where: N = Numerator, D = Denominator, n = #bits, R = Partial remainder, q(i) = bit #i of quotient

به دنبال این الگوریتم، خارج قسمت به شکلی غیر استاندارد متشکل از ارقام − 1 و ۱ است. این روش نیازمند تبدیل روش دودویی به روش خارج قسمت می‌باشد. مثال:

مقدار زیر را به مجموعه ارقام {۰٬۱} تبدیل کنید:
شروع:	$Q=111{\bar {1}}1{\bar {1}}1{\bar {1}}$
۱ شرط عبارت مثبت را تشکیل دهید:	$P=11101010\,$
۲ شرط عبارت منفی را پنهان کنید*:	$M=00010101\,$
۳ کم کنید: $P-M$	$Q=11010101\,$
* (یادداشت باینری امضا شده با یک مکمل یکی بدون Two's Complement)

اگر −۱ ارقامی از $Q$ هستند که به صورت صفر (۰) ذخیره می‌شوند پس $P$ هست $Q$ و محاسبه $M$ بدیهی است: انجام یک مکمل (مکمل بیت به بیت) روی $Q$ اصلی.

Q := Q − bit.bnot(Q)      * Appropriate if −1 Digits in Q are Represented as zeros as is common.

سرانجام، خارج‌قسمت‌های محاسبه‌شده توسط این الگوریتم همیشه فرد هستند و باقی‌مانده R در دامنه −D ≤ R < D. به‌عنوان مثال، ۵/۲ = 3 R-۱ است. برای تبدیل شدن به یک باقی‌ماندهٔ مثبت، بعد از تبدیل Q از فرم غیراستاندارد به فرم استاندارد، تنها یک گام بازگشتی را انجام دهید:

if R <0 then
   Q := Q − 1
   R := R + D  -- Needed only if the Remainder is of interest.
end if

باقی‌مانده واقعی R>> n است. (مانند تقسیم بازگشتی، بیت‌های سطح پایین R به‌همان میزان که به‌عنوان بیت‌های خارج‌قسمت Q تولید می‌شوند، استفاده می‌شوند و استفاده از یک نماد واحد برای تغییر هر دو متداول است)

بخش SRT

دلیل نام‌گذاری این روش از روی اسامی به‌وجودآورندگان روش می‌باشد (Sweeney , Robertson و Tocher)، تقسیم SRT یک روش معروف برای تقسیم در بسیاری از پیاده‌سازی‌های ریزپردازنده است. تقسیم SRT مشابه تقسیم غیربازگشتی است، اما از یک جدول جستجو براساس مقسوم و مقسوم‌علیه برای تعیین هر رقم خارج‌قسمت استفاده می‌کند.

مهم‌ترین تفاوت این است که یک نمایش اضافی برای خارج‌قسمت مورد استفاده قرار می‌گیرد. برای مثال، هنگام اجرای تقسیم SRT در مبنا ۴، هر رقم خارج‌قسمت از پنج امکان انتخاب می‌شود: {−۲، −۱، ۰، +۱، +۲ }. به این دلیل، انتخاب یک رقم خارج‌قسمت کافی نیست؛ ارقام بعدی می‌توانند خطاهای جزئی را اصلاح کنند. (به‌عنوان مثال، جفت‌های رقم خارج‌قسمت (۰، +۲) و (۱، −۲) معادل هستند، زیرا ۰ × ۴ + ۲ = ۱ × ۴ − ۲ است) این تحمل اجازه می‌دهد که ارقام خارج‌قسمت تنها با استفاده از چند بخش عمده از مقسوم و مقسوم‌علیه، بجای نیاز به یک کاهش با عرض کامل انتخاب شوند. این ساده‌سازی به‌نوبه خود اجازه می‌دهد تا یک مبنایی بالاتر از ۲ مورد استفاده قرار گیرد.

مانند تقسیم غیربازگشتی، آخرین مراحل یک تفریق کامل نهایی برای حل آخرین بیت خارج‌قسمت، و تبدیل خارج‌قسمت به شکل دوگانه استاندارد هستند.

اشکال نقطه‌ی‌عطف تقسیم پردازنده Intel Pentium که ناشی از یک جدول جستجو با کد گذاری نادرست است. پنج مورد از ۱۰۶۶ ورودی به اشتباه حذف شده‌بودند.

روش‌های تقسیم سریع

بخش نیوتن - رافسون

نیوتن - رافسون از روش نیوتن برای پیدا کردن معکوس D استفاده می‌کند و آن را ضرب می‌کند که با N معکوس می‌شود تا خارج‌قسمت نهایی Q را پیدا کند.

مراحل تقسیم نیوتن - رافسون عبارتند:

یک تخمین $X_{0}$ برای معکوس $1/D$ از مقسوم‌علیه $D$ محاسبه کنید.
محاسبه تخمین‌های دوطرفه پی‌درپی دقیق‌تر $X_{1},X_{2},\ldots ,X_{S}$ . این‌جایی است که فرد از روش نیوتن-رافسون به این‌ترتیب استفاده می‌کند.
خارج‌قسمت را با ضرب مقسوم در مقسوم‌الیه دوطرفه محاسبه کنید $Q=NX_{S}$ .

به منظور استفاده از روش نیوتن برای یافتن معکوس $D$ برای یافتن یک تابع $f(x)$ که دارای یک صفر در $x=1/D$ است، لازم است. تابع واضح این است که $f(x)=DX-1$ اما تکرار نیوتن - رافسون برای این، بی‌فایده است، چون نمی‌تواند بدون دانستن معکوس بودن آن محاسبه شود.

$D$ (علاوه بر آن، برای محاسبه متقابل دقیق در یک مرحله به جای امکان بهبود تکراری تلاش می‌کند). تابعی که کار می‌کند $f(X)=(1/X)-D$ است، که در آن تکرار نیوتن - رافسون، را می‌دهد.

X_{i+1}=X_{i}-{f(X_{i}) \over f'(X_{i})}=X_{i}-{1/X_{i}-D \over -1/X_{i}^{2}}=X_{i}+X_{i}(1-DX_{i})=X_{i}(2-DX_{i}),

که می‌توان از آن $X_{i}$ را فقط با استفاده از ضرب و تفریق، یا با استفاده از دو ترکیب ضرب - اضافه‌شده محاسبه کرد.

از دیدگاه محاسباتی، عبارات $X_{i+1}=X_{i}+X_{i}(1-DX_{i})$ و $X_{i+1}=X_{i}(2-DX_{i})$ معادل نیستند برای به دست آوردن نتیجه با دقت 2 n بیت در حالی که از عبارت دوم استفاده می‌کنند، باید نتیجه را بین $X_{i}$ و $(2-DX_{i})$ محاسبه کند و با دقت مضاعف از $X_{i}$ (تعداد بیت) ^{^{[نیازمند منبع]}} در مقابل، نتیجه بین $X_{i}$ و $(1-DX_{i})$ فقط باید با دقت n بیت محاسبه شود زیرا n بیت‌های اصلی (پس از نقطه دودویی) از $(1-DX_{i})$ صفر هستند.

اگر این خطا به این‌صورت تعریف شود: $\varepsilon _{i}=1-DX_{i}$ ، سپس:

{\begin{aligned}\varepsilon _{i+1}&=1-DX_{i+1}\\&=1-D(X_{i}(2-DX_{i}))\\&=1-2DX_{i}+D^{2}X_{i}^{2}\\&=(1-DX_{i})^{2}\\&={\varepsilon _{i}}^{2}.\\\end{aligned}}

این مربع خطا در هر گام تکرار - به اصطلاح هم‌گرایی درجه‌دوم روش نیوتن - رافسون - تأثیری دارد که تعداد ارقام صحیح در نتیجه تقریباً برای هر تکرار دوبرابر می‌شود. یک ویژگی که زمانی بسیار ارزشمند می‌شود که اعداد شامل بسیاری از ارقام باشند (به عنوان مثال در دامنه بزرگ عدد صحیح). اما به این معنی است که هم‌گرایی اولیه این روش می‌تواند نسبتاً کند باشد، به خصوص اگر تخمین اولیه $X_{0}$ انتخاب ضعیفی باشد.

برای مسئله فرعی انتخاب یک تخمین اولیه $X_{0}$ ، می‌توان یک تغییر بیتی به مقسوم‌علیه مشترک $D$ را اعمال کرد تا آن را در مقیاس $0.5\leqslant D\leqslant 1$ قرار دهید؛ با اعمال همان تغییر بیت بر روی عدد $N$ ، اطمینان حاصل می‌شود که مقدار تغییر نمی‌کند. سپس می‌توان از تقریب خطی با این شکل استفاده کرد

X_{0}=T_{1}+T_{2}D\approx {\frac {1}{D}}\,

برای دادن مقدار اولیه نیوتن-رافسون. برای شروع به کار انداختن نیوتن - رافسون. برای به حداقل رساندن حداکثر مقدار مطلق خطای این تخمین در فاصله $[0.5,1]$ ، باید استفاده کرد.

X_{0}={48 \over 17}-{32 \over 17}D.\,

ضرایب تخمین خطی به شرح زیر تعیین می‌شود. مقدار مطلق خطا است $|\varepsilon _{0}|=|1-D(T_{1}+T_{2}D)|$ . حداقل مقدار حداکثر مطلق خطا به وسیله قضیه Chebyshev equioscillation تعیین می‌شود $F(D)=1-D(T_{1}+T_{2}D)$ . مکان حداقلی که $F(D)$ رخ می‌دهد $F'(D)=0$ ، که راه حل دارد $D=-T_{1}/(2T_{2})$ . تابعی که در آن حداقل باید به عنوان تابع در نقاط نهایی باشد، یعنی $F(1/2)=F(1)=-F(-T_{1}/(2T_{2}))$ . دو معادله در دو مجهولی که راه حل منحصر به فردی دارد $T_{1}=48/17$ و $T_{2}=-32/17$ ، و حداکثر خطا است $F(1)=1/17$ . با استفاده از این تخمین، مقدار مطلق خطا کم‌تر از مقدار اولیه است.

\vert \varepsilon _{0}\vert \leq {1 \over 17}\approx 0.059.\,

ایجاد یک چندجمله‌ای با درجه بزرگ‌تر از ۱، محاسبه ضرایب با استفاده از الگوریتم Remez امکان‌پذیر است. نکته اصلی این است که حدس اولیه به چرخه‌های محاسباتی بیشتری نیاز دارد، اما امید به تبادل برای تکرارهای کمتری از نیوتن - رافسون.

از آنجا که برای این روش همگرایی، دقیقاً درجه دوم است، به دنبال آن است که

S=\left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,

این مراحل برای محاسبه ارزش تا دو رقم دودویی کافی هستند. این به ۳ مورد برای IEEE تک دقت و ۴ برای هر دو با دقت دو برابر و دو فرمت توسعه یافته ارزیابی می‌شود.

Pseudocode

در ادامه خارج‌قسمت N و D با دقت نقاط دوتایی P محاسبه می‌شود:

Express D as M × 2^e where 1 ≤ M <2 (standard floating point representation)
D' := D / 2^e+1 // scale between 0.5 and 1, can be performed with bit shift / exponent subtraction
N' := N / 2^e+1
X := ۴۸/۱۷ − ۳۲/۱۷ × D' // precompute constants with same precision as D
repeat  $\left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,$  times // can be precomputed based on fixed P
 X := X + X × (1 - D' × X)
end
return N' × X

به عنوان مثال، برای یک تقسیم نقطه شناور با دقت دو برابر، در این روش از ۱۰ ضرب، ۹ جمع و ۲ تغییر استفاده می‌شود.

تقسیم واریانت نیوتن - رافسون

روش تقسیم نیوتن-رافسون می‌تواند کمی تغییر کند تا به شرح زیر باشد. پس از تغییر N و D به گونه ای که D در [۰٫۵ ، ۱٫۰] باشد، مقدار اولیه را با آن شروع کنید

X:={\frac {140}{33}}+D\cdot \left({\frac {-64}{11}}+D\cdot {\frac {256}{99}}\right).

این بهترین تناسب درجه دوم برای 1 / D است و مقدار مطلق خطا را کمتر از یا برابر با ۱/۹۹ می‌دهد. انتخاب شده‌است تا خطا برابر با چند جملهای دوباره مرتبه سوم تغییر یافته Chebyshev از نوع اول باشد. ضرایب باید از پیش محاسبه شده و کدگذاری شوند.

سپس در حلقه، از یک تکرار استفاده کنید که خطا را به توان ۳ می‌رساند.

E:=1-D\cdot X

Y:=X\cdot E

X:=X+Y+Y\cdot E.

اصطلاح Y · E جدید است.

اگر حلقه تا زمانی اجرا شود که X با ۱ / D در بیت‌های اصلی P موافقت کند، آنگاه تعداد تکرارها بیش از این نخواهد بود.

\left\lceil \log _{3}\left({\frac {P+1}{\log _{2}99}}\right)\right\rceil

که این تعداد دفعات ۹۹ باید توان ۳ باشد تا به $2^{P+1}$ ^برسد. سپس

Q:=N\cdot X

خارج‌قسمت بیت‌های P است.

استفاده از چند جمله‌ای‌های درجه بالاتر در هر کدام از مقداردهی اولیه یا تکرار، منجر به تجزیه عملکرد می‌شود زیرا ضرب اضافی مورد نیاز برای انجام تکرارهای بیشتر صرف خواهد شد.

تقسیم گلدشمیت

تقسیم گلدشمیت (پس از رابرت الیوت گلدشمیتد^[۲])

از یک فرایند تکراری برای ضرب مکرر هردو، مقسوم و مقسوم‌الیه مشترک با یک عامل مشترک F _i استفاده می‌کند، این انتخاب به گونه‌ای است که مقسوم به ۱ برسد. این باعث می‌شود مقسوم به جستجوی خارج‌قسمت Q برسد:

Q={\frac {N}{D}}{\frac {F_{1}}{F_{1}}}{\frac {F_{2}}{F_{2}}}{\frac {F_{\ldots }}{F_{\ldots }}}.

مراحل تقسیم گلدشمیت به شرح زیر است:

تخمینی را برای فاکتور ضرب F _{i ایجاد کنید}.
مقسوم و مقسوم‌الیه را توسط F _i ضرب کنید.
اگر مقسوم‌الیه به اندازه کافی نزدیک به ۱ است، مقسوم را برگردانید، در غیر این‌صورت، حلقه را به مرحله ۱ بازگردانید.

با فرض N / D، اندازه‌گیری شده‌است به‌طوری که $0<D<1$ ، هر F _i بر اساس D است:

F_{i+1}=2-D_{i}.

ضرب مقسوم و مقسوم‌الیه براساس نتایج حاصله عبارتند از:

{\frac {N_{i+1}}{D_{i+1}}}={\frac {N_{i}}{D_{i}}}{\frac {F_{i+1}}{F_{i+1}}}.

بعد از تکرار تعداد کافی K $Q=N_{k}$ .

روش گلدشمیت در پردازنده‌های AMD Athlon AMD و مدلهای بعدی استفاده می‌شود.^[۳]^[۴] همچنین به الگوریتم Anderson Earle Goldschmidt Powers (AEGP) معروف است و توسط پردازنده‌های مختلف IBM پیاده‌سازی می‌شود.^[۵]^[۶]

قضیه دو جمله ای

در روش گلدشمیت می‌توان از عواملی استفاده کرد که اجازه می‌دهند تا به ساده‌سازی قضیه دو جمله‌ای کمک شود. فرض کنید

N / D توسط یک قدرت از این دو مقیاس بندی شده‌است. با قضیه Binom ساده شود. فرض کنید N / D به توان دو رسانده شده‌است $D\in ({\tfrac {1}{2}},1]$ . ما انتخاب می‌کنیم $D=1-x$ و $F_{i}=1+x^{2^{i}}$ . این نتیجه حاصل می‌شود:

{\frac {N}{1-x}}={\frac {N\cdot (1+x)}{1-x^{2}}}={\frac {N\cdot (1+x)\cdot (1+x^{2})}{1-x^{4}}}=\cdots =Q'={\frac {N'=N\cdot (1+x)\cdot (1+x^{2})\cdot \cdot \cdot (1+x^{2^{(n-1)}})}{D'=1-x^{2^{n}}\approx 1}}

.

بعد از $n$ مرحله $(x\in [0,{\tfrac {1}{2}}))$ ، مخرج $1-x^{2^{n}}$ می‌تواند با یک خطای نسبی به ۱ برسد.

\varepsilon _{n}={\frac {Q'-N'}{Q'}}=x^{2^{n}}

که حداکثر در $2^{-2^{n}}$ چه زمانی $x={1 \over 2}$ ، بنابراین حداقل دقت را در مورد $2^{n}$ رقم‌های ودویی ارائه می‌دهد.

روش‌های عدد صحیح

روش‌هایی که برای پیاده‌سازی سخت‌افزار طراحی شده‌اند معمولاً اعداد صحیح را با هزاران یا میلیون‌ها رقم اعشار نشان نمی‌دهند، به عنوان مثال در کاهش پیمانه‌ای در رمزنگاری رخ می‌دهند.

برای این اعداد صحیح بزرگ، الگوریتم تقسیم کارآمدتر مشکل را با استفاده کردن از تعداد کمی ضرب تبدیل می‌کند، که می‌تواند با استفاده از یک الگوریتم ضرب مؤثر مجانبی مانند الگوریتم Karatsuba، ضرب Toom–Cook یا الگوریتم Schonhage - Strassen انجام شود.

نتیجه این است که پیچیدگی محاسباتی تقسیم به همان ترتیب (تا یک ثابت افزاینده)به عنوان ضرب ضرب است. نمونه‌هایی از کاهش ضرب و ضرب در روش نیوتن، همان‌طور که در بالا توضیح داده شد، [۱۳] و نیز کاهش اندکی سریع‌تر بارت و الگوریتم کاهش مونتگومری. [۱۴] [تأیید مورد نیاز] روش نیوتن به‌طور خاص در سناریوهایی مؤثر است که باید چندین بار در همان مقسوم‌علیه مشترک تقسیم شود، زیرا پس از وارونگی اولیه نیوتن تنها یک ضرب (کوتاه) برای هر بخش مورد نیاز است.

تقسیم بر یک ثابت

تقسیم توسط یک ثابت D معادل ضرب معکوس آن است. از آنجا که مخرج ثابت است، متقابل آن نیز (1 / D) است؛ بنابراین می‌توان مقدار (1 / D) را یک بار در زمان کامپایل محاسبه کرد، و در زمان اجرا ضرب N و (1 / D) را به جای تقسیم N / D انجام داد. در نقطهٔ شناوریحسابی استفاده از (1 / D) مشکل کمی ایجاد می‌کند، اما درعدد صحیح حسابی، معکوس همیشه صفر (فرض | D |> 1) ارزیابی می‌شود.

استفاده از آن به‌طور خاص (1 / D) لازم نیست. از هر مقدار (X / Y) که به (1 / D) کاهش می‌یابد استفاده می‌شود. به عنوان مثال، برای تقسیم ۳ می‌توان از عوامل ۱/۳، ۲/۶، ۳/۹ یا ۱۹۴/۵۸۲ استفاده کرد. در نتیجه، اگر Y از قدرت دو مرحله تقسیم را داشته‌باشد، مرحله تقسیم به یک تغییر بیت سریع سریع کاهش می‌یابد. اثر محاسبه N / D به عنوان (N · (X / Y جانشین تقسیم با یک ضرب و یک تغییر است. توجه داشته باشید که پرانتز مهم است، زیرا(N · (X / Y را صفر ارزیابی می‌کند.

اما، مگر اینکه خود D دو قدرت داشته باشد، هیچ X و Y وجود ندارد که شرایط فوق را برآورده کند. خوشبختانه، N · X) / Y) دقیقاً همان نتیجه N / D در عدد صحیح حسابی را به دست می‌آورد حتی وقتی (X / Y) دقیقاً برابر با 1 / D نباشد، اما «به اندازه کافی نزدیک» است که خطایی که توسط تقریبی ایجاد شده‌است است. در بیت‌هایی که با عملیات تغییر کنار گذاشته می‌شوند.^[۷]^[۸]^[۹]

در واقعیت نمونه نقطه حسابی ثابت از اعداد صحیح بدون علامت ۳۲ بیتی، تقسیم‌شده توسط ۳ می‌تواند بوسیله یک ضرب با2863311531/2³³ جایگزین شود. یک ضرب با ۲۸۶۳۳۱۱۵۳۱ (هگزادسیمال 0xAAAAAAAB) با یک تغییر ۳۳ بیت راست بیان‌می‌شود. ارزش ۲۸۶۳۳۱۱۵۳۱ به عنوان 2³³/3 محاسبه شده‌است، پس از آن گرد می‌شود.

به همین ترتیب، تقسیم بر ۱۰ را می‌توان به صورت ضرب 3435973837 (0xCCCCCCCD) و به دنبال آن تقسیم 2 ³⁵ (یا ۳۵ تغییر بیت مناسب) بیان کرد.

در بعضی موارد، تقسیم بر یک ثابت می‌تواند در زمان کمتری با تبدیل «ضرب توسط ثابت» با یک سری تغییرات

انجام شود و جمع یا تفریق کند.^[۱۰] در برخی موارد تقسیم بر ۱۰ است که در صورت نیاز، خارج‌قسمت دقیق بدست می‌آید. [۱۹]

خطای دور می‌تواند به دلیل

خطای گرد کردن

خطای گرد کردن می‌تواند ناشی‌از محدودیت دقیق توسط عملیات تقسیم معرفی شود.

اطلاعات بیشتر: نقطه شناوری

جستارهای وابسته

بخش گالی
الگوریتم ضرب
اشکال Pentium FDIV

منابع

↑ Flynn. "Stanford EE486 (Advanced Computer Arithmetic Division) – Chapter 5 Handout (Division)" (PDF). Stanford University. Archived from the original (PDF) on 18 April 2022. Retrieved 24 January 2020.
↑ https://web.archive.org/web/20180718114413/https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5392026
↑ Oberman, Stuart F. (1999). "Floating Point Division and Square Root Algorithms and Implementation in the AMD-K7 Microprocessor" (PDF). Proceedings of the IEEE Symposium on Computer Arithmetic: 106–115.
↑ Soderquist, Peter; Leeser, Miriam (July–August 1997). "Division and Square Root: Choosing the Right Implementation". IEEE Micro. 17 (4): 56–66. doi:10.1109/40.612224.
↑ S. F. Anderson, J. G. Earle, R. E. Goldschmidt, D. M. Powers. The IBM 360/370 model 91: floating-point execution unit, IBM Journal of Research and Development, January 1997
↑ Guy Even, Peter-M. Seidel, Warren E. Ferguson. A parametric error analysis of Goldschmidt’s division algorithm. 2004,
↑ Granlund, Torbjörn; Montgomery, Peter L. (June 1994). "Division by Invariant Integers using Multiplication" (PDF). SIGPLAN Notices. 29 (6): 61–72. CiteSeerX 10.1.1.1.2556. doi:10.1145/773473.178249.
↑ Möller, Niels; Granlund, Torbjörn (February 2011). "Improved Division by Invariant Integers" (PDF). IEEE Transactions on Computers. 60 (2): 165–175. doi:10.1109/TC.2010.143.
↑ ridiculous_fish. "Labor of Division (Episode III): Faster Unsigned Division by Constants". 2011.
↑ LaBudde, Robert A. ; Golovchenko, Nikolai; Newton, James; and Parker, David; Massmind: "Binary Division by a Constant"

خواندن بیشتر

Warren Jr., Henry S. (2013). Hacker's Delight (2 ed.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8.
Savard, John J. G. (2018) [2006]. "Advanced Arithmetic Techniques". quadibloc. Archived from the original on 2018-07-03. Retrieved 2018-07-16.

پیوند به بیرون

الگوریتم‌های حساب ریاضی کامپیوتر JavaScript Simulator - شامل شبیه‌ساز بسیاری از الگوریتم‌های تقسیم بندی متفاوت است
Doras, Cory (19 October 2011). "Labor of Division (Episode III): Faster Unsigned Division by Constants" (PDF). ridiculous_fish. Doras, Cory (19 October 2011). "Labor of Division (Episode III): Faster Unsigned Division by Constants" (PDF). ridiculous_fish. (تقسیم بر ثابتها را گسترش می‌دهد)
https://web.archive.org/web/20170112215236/http://www.dauniv.ac.in/downloads/CArch_PPTs/CompArchCh03L07IntegerDivision.pdf
https://web.archive.org/web/20180403141218/http://www.seas.ucla.edu/~ingrid/ee213a/lectures/division_presentV2.pdf
http://www.m1c4a1.wz.cz/docs/goldschmidt.pdf بایگانی‌شده در ۱۳ ژوئیه ۲۰۱۹ توسط Wayback Machine

[1] Flynn. "Stanford EE486 (Advanced Computer Arithmetic Division) – Chapter 5 Handout (Division)" (PDF). Stanford University. Archived from the original (PDF) on 18 April 2022. Retrieved 24 January 2020.

[2] ttps://web.archive.org/web/20180718114413/https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5392026

[3] Oberman, Stuart F. (1999). "Floating Point Division and Square Root Algorithms and Implementation in the AMD-K7 Microprocessor" (PDF). Proceedings of the IEEE Symposium on Computer Arithmetic: 106–115.

[4] Soderquist, Peter; Leeser, Miriam (July–August 1997). "Division and Square Root: Choosing the Right Implementation". IEEE Micro. 17 (4): 56–66. doi:10.1109/40.612224.

[5] S. F. Anderson, J. G. Earle, R. E. Goldschmidt, D. M. Powers. The IBM 360/370 model 91: floating-point execution unit, IBM Journal of Research and Development, January 1997

[6] Guy Even, Peter-M. Seidel, Warren E. Ferguson. A parametric error analysis of Goldschmidt’s division algorithm. 2004,

[7] Granlund, Torbjörn; Montgomery, Peter L. (June 1994). "Division by Invariant Integers using Multiplication" (PDF). SIGPLAN Notices. 29 (6): 61–72. CiteSeerX 10.1.1.1.2556. doi:10.1145/773473.178249.

[8] Möller, Niels; Granlund, Torbjörn (February 2011). "Improved Division by Invariant Integers" (PDF). IEEE Transactions on Computers. 60 (2): 165–175. doi:10.1109/TC.2010.143.

[9] ridiculous_fish. "Labor of Division (Episode III): Faster Unsigned Division by Constants". 2011.

[10] LaBudde, Robert A. ; Golovchenko, Nikolai; Newton, James; and Parker, David; Massmind: "Binary Division by a Constant"

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]

[۹]

[۱۰]