الگوریتم تقسیم اعداد — از صفر تا صد

الگوریتم تقسیم، براساس دو عدد صحیح مثل $$N$$ و $$D$$ عمل کرده و حاصل تقسیم این دو عدد یعنی مقدار خارج قسمت (Quotient) و باقی‌مانده (Reminder) را محاسبه می‌کند. در دوره‌های آموزشی دبستان با نحوه تقسیم اعداد آشنا شده‌اید ولی مشخص است که برای تقسیم اعداد بزرگ و اعشاری دیگر شیوه‌های معمول تقسیم کارا نخواهند بود. بنابراین در این نوشتار به بررسی چند الگوریتم تقسیم اعداد پرداخته‌ایم تا بدانیم که برنامه‌ها و سخت‌افزارهای رایانه‌ای چگونه و براساس چه اصولی، عمل تقسیم را انجام می‌دهند.

برای آشنایی بیشتر با نحوه تقسیم اعداد صحیح بهتر است مطلب تقسیم عدد صحیح — به زبان ساده را بخوانید. همچنین خواندن نوشتار اعداد اعشاری — به زبان ساده نیز خالی از لطف نیست.

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

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

فیلم آموزش محاسبات عددی با متمتیکا Mathematica – مقدماتی در فرادرس

کلیک کنید

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

• تقسیم آهسته (Slow Division): در گروه الگوریتم‌های تقسیم آهسته، با هر بار تکرار، یک رقم از خارج قسمت تولید می‌شود. نمونه‌هایی از الگوریتم‌های تقسیم آهسته عبارتند از تقسیم بازیابی دو عدد، تقسیم غیربازیابی و تقسیم SRT.
• تقسیم سریع (Fast Division): روش‌های تقسیم سریع با یک تقریب یا حدس اولیه که نزدیک به مقدار نهایی است، آغاز می‌شوند. الگوریتم‌های «نیوتن-رافسون» ( Newton-Raphson) و «گلدسمیت» (Goldschmidt) در این گروه قرار می‌گیرند.

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

در این نوشتار تقسیم را به صورت یک عمل‌گر در نظر می‌گیریم که با نماد $$N/D$$ نشان داده شده که در آن $$N$$‌ را مقسوم (Numerator-Dividend) و $$D$$ را مقسوم علیه (Denominator-Divisor) می‌نامیم. حاصل عمل تقسیم زوج مرتبی است به صورت $$(Q,R)$$ که $$Q$$ را خارج قسمت (Quotient) و $$R$$ را باقی‌مانده (Reminder) می‌نامیم. در ادامه الگوریتم‌ تقسیم اعداد یعنی الگوریتم تقسیم با تفریق‌های متوالی و همچنین الگوریتم‌های تقسیم آهسته را مورد بررسی قرار خواهیم داد. برای آشنایی با الگوریتم‌ تقسیم اعداد سریع به نوشتارهای بعدی این سری مطالب مراجعه کنید.

الگوریتم تقسیم با تفریق‌های متوالی

ساده‌ترین الگوریتم برای انجام عمل تقسیم، استفاده از تفریق‌های متوالی یا تکراری است. این الگوریتم در حالت پیشرفته‌تر، از روش پیدا کردن بزرگ‌ترین مقسوم علیه مشترک و قضیه اقلیدس استفاده می‌کند. این قضیه بیان می‌کند که اگر $$a, b, q, r$$ اعداد صحیحی باشند بطوریکه رابطه $$a=bq+r$$ بینشان برقرار باشد، آنگاه بزرگترین مقسوم علیه مشترک بین $$a$$ و $$b$$ با بزرگترین مقسوم علیه مشترک بین $$a$$ و $$r$$ برابر است.

$$\large a,b, q ,r \in Z; a=bq+r\rightarrow \operatorname{gcd}(a,b)=\operatorname{gcd}(a,r)$$

در اینجا منظور از $$\operatorname{gcd}$$ همان بزرگترین مقسوم علیه مشترک (Greatest Common Divisor) است.

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

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

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

مثال ۱

فرض کنید که باید تقسیم ۲۱ بر ۵ را محاسبه کنیم. هدف پیدا کردن خارج قسمت و باقی‌مانده این تقسیم است. طبق روالی که در الگوریتم گفته شده، محاسبات را انجام می‌دهیم.

• گام ۱: محاسبه $$21-5=16$$
• گام ۲: محاسبه $$16-5=11$$
• گام ۳: محاسبه $$11-5=6$$
• گام ۴: محاسبه $$6-5=1$$
• گام ۵: از آنجایی که $$1$$ به عنوان مقسوم جدید، کوچکتر از مقسوم علیه است، عملیات متوقف شده و چون تعداد گام‌ها برابر با ۴ است،‌ پس خارج قسمت برابر است با $$4$$ و باقی‌مانده نیز $$1$$ خواهد بود. پس داریم:

$$\large 21=5 \times 4+1$$

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

مثال ۲

فرض کنید این بار قرار است تقسیم 21- را بر ۵ بدست آوریم. از آنجایی که مقسوم منفی است، مقسوم علیه را قرینه می‌کنیم تا بتوانیم از الگوریتم گفته شده کمک بگیریم. توجه داریم که پاسخ تقسیم یعنی خارج قسمت در این حالت باید قرینه شود.

• گام ۱: محاسبه $$-21-(-5)=-16$$
• گام ۲: محاسبه $$-16-(-5)=-11$$
• گام ۳: محاسبه $$-11-(-5)=-6$$
• گام ۴: محاسبه $$-6-(-5)=-1$$
• گام ۵: محاسبه $$-1-(-5)=4$$

چون باقی‌مانده (نتیجه حاصل از گام پنجم) بعد از ۵ گام، از مقسوم علیه کوچکتر شده است، عملیات تقسیم پایان می‌یابد و با توجه به پنج گام طی شده، خارج قسمت برابر با $$-5$$ و باقی‌مانده نیز $$4$$ خواهد بود. به این ترتیب خواهیم داشت:

$$\large -21=5\times (-5)+4$$

نکته: توجه دارید به علت استفاده از قرینه مقسوم علیه، باید خارج قسمت هم قرینه شود. به همین علت مقدار آن را $$-5$$‌ در نظر گرفتیم.

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

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

متاسفانه گام‌های این الگوریتم بسیار کند بوده و از مرتبه $$\Omega(Q)$$ است.

الگوریتم تقسیم اعداد به روش طولانی (Long Division)

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

فیلم آموزش محاسبات سریع ریاضی در فرادرس

کلیک کنید

فرض کنید هر عدد طبیعی مثل $$N$$ را بتوان به صورت عددی برمبنا یا پایه $$b>1$$ به صورت دنباله‌ای از ارقام $$n=a_0a_1a_2\cdots,a_k$$ نوشت که در آن‌ها $$ {\displaystyle 0\leq \alpha _{i}<b}$$ است. از طرفی مقدار $$i$$ را یک عدد طبیعی از ۰ تا $$k$$ در نظر می‌گیریم، یعنی $${\displaystyle 0\leq i\leq k}$$. به این ترتیب می‌توان عدد $$N$$‌ را به صورت ‌زیر نمایش داد.

$$\large {\displaystyle N=\sum _{i=0}^{k}\alpha _{i}b^{k-i}}$$

فرض کنید قرار است عدد $$N$$ مقسوم و $$D$$ مقسوم علیه باشد. هدف پیدا کردن خارج قسمت یا $$Q$$ و باقی‌مانده $$R$$ تقسیم عدد $$N$$ بر عدد $$D$$‌ است.  همچنین تعداد ارقام عدد $$D$$ را برابر با $$l$$ در نظر می‌گیریم.

برای انجام این تقسیم به روش طولانی، گام‌ها به صورت زیر خواهند بود.

• گام ۱: اگر $$k< l$$ باشد آنگاه $$Q=0$$ و $$R=N$$،‌ در غیر اینصورت گام‌های بعدی تا زمانی که $$ {\displaystyle 0\leq i\leq k-1}$$ باشد ادامه پیدا می‌کند.
• گام ۲: در هر بار تکرار با شمارنده $$i$$، مقدار $$q_i$$ را خارج قسمت حاصل از تکرار  $$i$$‌ام و $$d_i$$‌ را هم مقسوم در نظر می‌گیریم. به این ترتیب $$r_i$$ باقی‌مانده و $$\alpha_i$$‌ نیز رقم بعدی عدد مقسوم اولیه است. از طرفی $$\beta_i$$ را هم رقم بعدی مقسوم علیه محسوب می‌کنیم. با توجه به تعریف اعداد برمبنای $$b$$،‌ خواهیم داشت، $${\displaystyle 0\leq \beta _{i}<b}$$.

نکته: به یاد دارید که باید باقی‌مانده تقسیم مثبت باشد در نتیجه در تکرار $$i$$ام باقی‌مانده $$r_i$$ باید بزرگتر یا مساوی با صفر بوده و از $$D$$ نیز کوچکتر باشد. یعنی:

$$ {\displaystyle 0\leq r_{i}<D}$$

مراحل تکرار با مقدار دهی اولیه به صورت زیر آغاز می‌شود.

$$ \large {\displaystyle q_{-1}=0}\\ \large {\displaystyle r_{-1}=\sum _{i=0}^{l-1}\alpha _{i}b^{k-i}}$$

در هر بار تکرار الگوریتم، محاسبات زیر برای تکرار $$i$$ام در ادامه قابل مشاهده است.

$$ \large d_{i}=br_{i-1}+\alpha _{i+l-1}\\ \large r_{i}=d_{i}-D\beta _{i}=br_{i-1}+\alpha _{i+l-1}-D\beta _{i}\\ \large q_{i}=bq_{i-1}+\beta _{i}$$

واضح است که مقدار $$\beta_i$$ به ازاء $$0\leq r_i <D$$، منحصر به فرد است.

آخرین مقدار برای $$Q=q_{k-l}$$، خارج قسمت تقسیم اصلی بوده و باقی‌مانده نیز برابر است با $$R=r_{k-l}$$.

مثال ۳

فرض کنید قرار است عدد $$N=1260257$$ را بر $$D=37$$ تقسیم کنیم. توجه داشته باشید که مبنای ده برای هر دو این اعداد در نظر گرفته شده است. همانطور که گفته شد، مقدارهای اولیه $$q_{-1}=0$$ و $$r_{-1}=1$$ خواهند بود. جدول زیر مراحل تکراری و نتیجه محاسبات مربوط به الگوریتم تقسیم طولانی را نشان می‌دهد.

از کنار هم قرار دادن مقادیر $$\beta_i$$ از بالا به پایین، مقدار خارج قسمت حاصل می‌شود. از طرفی در آخرین سطر نیز مقدار $$q_{5}=34061$$ است که همان خارج قسمت را نشان می‌دهد. به این ترتیب خارج قسمت نیز در ستون $$r_i$$ و در سطر آخری مشخص شده است که برابر با صفر خواهد بود.

الگوریتم تقسیم اعداد دو دویی به روش طولانی (Long Division)

از آنجایی که در نحوه نمایش اعداد برمبنای ۲، فقط از دو رقم $$0$$ و $$1$$ استفاده می‌شود، نحوه انجام مراحل تقسیم ساده‌تر است. از طرفی ضرب دو عدد یا صفر است یا ۱. به این ترتیب نحوه محاسبه تقسیم در این حالت برای رایانه‌های دیجیتال بسیار مناسب است. از آنجایی که ضرب یک عدد در $$2$$ به معنی جابجا کردن یک بیت (bit) به سمت چپ خواهد بود، همینطور پیدا کردن مقدار $$\beta_i$$ نیز محدود به یک عملگر مقایسه‌ای $$d_i\geq D$$ خواهد شد که در صورت صحیح بودن این شرط، مقدار $$\beta_i$$ برابر با ۱ و در غیر اینصورت برابر با صفر می‌شود. در هر یک از مراحل اجرای این الگوریتم باید داشته باشیم $${\displaystyle 0\leq i\leq k-1}$$.

مراحل انجام محاسبات برای اعداد دو دویی به صورت زیر است.

$$\large a_{i+l-1}=n\;\&\;(1<<\;(k+1-i-l)\\ \large d_i=r_{i-1} <<1+\alpha_{i+l-1} \\  \large  \beta_i = !(d_i<D) \\ \large r_i=d_i-D\; \&\; \beta_i\\ \large q_i=q_{i-1} <<1+\beta_i$$

مثال ۴

فرض کنید $$N=10111001$$ و $$D=1101$$ اعدادی بر مبنای ۲ هستند. هدف پیدا کردن تقسیم عدد $$N$$ بر $$D$$ و بدست آوردن مقادیر $$Q$$ و $$R$$‌ به عنوان خارج قسمت و باقی‌مانده تقسیم است.

مقدار دهی اولیه برای چنین مسئله‌ای به صورت زیر است.

$$\large {\displaystyle q_{-1}=0},\;\; {\displaystyle r_{-1}=101}$$

نکته: در جدول محاسبات بالا منظور از >>$$1$$، جابجایی یک بیت به سمت چپ (bit shift to the left) است. همچنین علامت $$!$$‌ نیز به معنی نقیض یا (Not) بوده و $$\&$$ نیز بیانگر عملگر عطف (AND) است.

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

به این ترتیب مشخص می‌شود که خارج قسمت $$Q=1110$$ و باقی‌مانده $$R=11$$ است.

در قطعه شبه کد زیر، تقسیم دو عدد صحیح (بدون علامت) برمبنای ۲ نمایش داده شده است.

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_2$$ بر $$D=100_2$$ نشان داد.

نکته: مقدار $$1100_2$$ همان عدد ۱۲ برمبنای ۱۰ و $$100_2$$ نیز مقدار ۴ برمبنای ۱۰ است پس در حقیقت عمل تقسیم ۱۲ بر ۴ صورت خواهد گرفت که می‌دانیم خارج قسمت برابر با ۳ و باقی‌مانده هم صفر خواهد بود.

Step 1: Set R=0 and Q=0
Step 2: Take i=3 (one less than the number of bits in N)
Step 3: R=00 (left shifted by 1)
Step 4: R=01 (setting R(0) to N(i))
Step 5: R<D, so skip statement

Step 2: Set i=2
Step 3: R=010
Step 4: R=011
Step 5: R<D, statement skipped

Step 2: Set i=1
Step 3: R=0110
Step 4: R=0110
Step 5: R>=D, statement entered
Step 5b: R=10 (R−D)
Step 5c: Q=10 (setting Q(i) to 1)

Step 2: Set i=0
Step 3: R=100
Step 4: R=100
Step 5: R>=D, statement entered
Step 5b: R=0 (R−D)
Step 5c: Q=11 (setting Q(i) to 1)

end
Q=112 (310) and R=0.

همانطور که دیده می‌شود، خارج قسمت این تقسیم برابر با $$Q=112$$ برمبنای ۲ است که همان مقدار ۳ برمبنای ۱۰ بوده و باقی‌مانده نیز با توجه به خروجی برنامه صفر خواهد بود.

الگوریتم تقسیم اعداد به روش آهسته

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

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

جمله‌های این عبارت در ادامه معرفی شده‌اند:

• $$R_j$$ جزء $$j$$ام از باقی‌مانده تقسیم است.
• $$B$$ مبنا اعداد است که در تقسیم دو دویی برابر با ۲ است. چنین کاری برای آشنایی با الگوریتم‌ تقسیم اعداد در رایانه‌ها مورد بررسی قرار می‌گیرد.
• $$n$$ نیز تعداد ارقام خارج قسمت است.
• $$q_{n-(j+1)}$$ نیز رقم خارج قسمت در مکان $$n-(j+1)$$ است.
• $$D$$، مقسوم علیه است.

الگوریتم تقسیم اعداد بازیابی (Restoring Division)

یکی از انواع روش‌های تقسیم آهسته، الگوریتم «تقسیم بازیابی» (Restoring Division) است. در ادامه به کمک مولفه‌هایی که در بالا به آن اشاره کردیم، عملکرد این الگوریتم را مورد بررسی قرار خواهیم داد.

فیلم آموزش چرتکه در فرادرس

کلیک کنید

باید توجه داشت که این تقسیم براساس شرط $$0<D<N$$ عمل می‌کند. ارقام تشکیل دهنده خارج قسمت در هر مرحله از مجموعه $$\{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

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

الگوریتم تقسیم اعداد غیربازیابی (Non-restoring Division)

اگر به جای ارقام $$\{0,1\}$$ از مجموعه $$\{-1,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
  if R >= 0 then
    q[i] := +1
    R := 2 * R − D
  else
    q[i] := −1
    R := 2 * R + D
  end if
end
 
-- Note: N=Numerator, D=Denominator, n=#bits, R=Partial remainder, q(i)=bit #i of quotient.

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

1. فرض کنید $$Q=111\overline{1} 1\overline{1} 1\overline{1}$$. البته توجه داشته باشید که در اینجا منظور از $$\overline{1}$$‌ همان $$-1$$ است.
2. ارقام $$1$$‌ مثبت را جدا می‌کنیم. $$P=11101010$$.
3. ارقام $$-1$$ را جدا (Mask) می‌کنیم و با رقم $$1$$ نمایش می‌دهیم. $$M=00010101$$.
4. تفاصل $$P$$ را از $$M$$ محاسبه می‌کنیم. این مقدار همان خارج قسمت است. $$Q=11010101$$.

نکته: بطور معمول در رایانه‌های دیجیتالی برای انجام عمل تقسیم به این صورت، برای ذخیره‌سازی $$-1$$ از $$0$$ استفاده می‌شود. به این ترتیب مقدار $$P$$ همان $$Q$$ است و محاسبه $$M$$ در گام چهارم به سادگی صورت می‌گیرد. کافی است که متمم مولفه‌ای هر رقم از $$Q$$ اولیه را محاسبه کنیم.

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

خارج قسمت در این الگوریتم همیشه فرد است و باقی‌مانده نیز در بازه $$[-D,D]$$ تغییر می‌کند. برای مثال اگر بخواهیم عدد $$5$$ را بر $$2$$ تقسیم کنیم، خارج قسمت برابر با $$3$$ و باقی‌مانده نیز $$-1$$ خواهد بود.

برای تبدیل باقی‌مانده به مقدار مثبت (بطوریکه قرارداد اولیه تقسیم فرض شده است) احتیاج به یک گام بازیابی (Restoring) بعد از محاسبه $$Q$$ داریم تا آن را از حالت غیر استاندارد به استاندارد تبدیل کنیم. شبه کدی که در ادامه قابل مشاهده است به این منظور نوشته شده است.

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

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

الگوریتم تقسیم اعداد SRT

یکی از روش‌های معمول و محبوب در الگوریتم تقسیم اعداد روش SRT است که نامش برگرفته از اسامی کسانی است که آن را ایجاد کرده‌اند. «سوینی» (Sweeney)، «رابرتسون»‌ (Robertson) و «توچر» (Tocher) این روش تقسیم اعداد را برای پردازشگر‌ها ابداع کرده‌اند.

فیلم آموزش ریاضی صنف هفتم – ویژه دانش آموزان افغانستانی در فرادرس

کلیک کنید

الگوریتم تقسیم اعداد SRT مشابه الگوریتم تقسیم بدون بازیابی عمل می‌کند ولی از یک جدول جستجو براساس مقسوم و مقسوم علیه بهره می‌برد تا ارقام خارج قسمت را تشخیص دهد. تفاوت اصلی در این بین، استفاده از بیان تکراری خارج قسمت است. برای مثال زمانی که یک عدد برمبنای ۴ را تقسیم می‌کنیم، هر رقم  خارج قسمت، از بین ۵ مقدار ممکن یعنی $$-2$$، $$-1$$، $$0$$, $$1$$ و $$2$$ انتخاب می‌شود. از آنجایی که ممکن است رقم انتخابی صحیح نباشد، بعدا ارقام خارج قسمت براساس یک روش تصحیح خطا، اصلاح می‌شود. برای مثال در ارقام خارج قسمت زوج‌های $$(0,+2)$$ و $$(1,-2)$$ یکسان هستند. زیرا $$0\times 4+2=1\times 4-2$$.

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

نکته: خطای ممیز شناور (Floating Point Bug) در پردازشگر‌های پنتیوم که باعث اشکال در انجام عمل تقسیم شده بود، به علت خطا در جدول جستجو این الگوریتم بوده است.

خلاصه و جمع‌بندی

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

در صورتی که به مباحث مرتبط در زمینه ریاضیات پایه علاقه‌مند هستید، آموز‌ش‌های زیر به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌های ریاضیات
• مجموعه آموزش‌های ریاضی و فیزیک
• آموزش جامع ریاضی دبیرستان – علوم تجربی
• اعداد حقیقی — به زبان ساده
• اعداد گویا — به زبان ساده
• اعداد مختلط – به زبان ساده

^^