ভাগ — restoring আর non-restoring division

১ · ভাগ মানে কী — ভাজ্য, ভাজক, ভাগফল, ভাগশেষ আর হাতে binary ভাগ

পর্ব ২০-এ যোগ-বিয়োগ আর পর্ব ২১-এ গুণ দেখেছেন (Integer যোগ-বিয়োগ, গুণ)। চার মৌলিক গাণিতিক কাজের শেষটি হলো ভাগ — আর hardware-এর কাছে এটিই সবচেয়ে কঠিন। কেন কঠিন, সেটা বোঝাই এই পর্বের প্রথম লক্ষ্য। শুরু করা যাক চারটি নাম দিয়ে:

• ভাজ্য (dividend) — যাকে ভাগ করা হচ্ছে, যেমন ৭৪।
• ভাজক (divisor) — যা দিয়ে ভাগ করা হচ্ছে, যেমন ৮।
• ভাগফল (quotient) — কতবার ভাজক পুরোপুরি ঢোকে, এখানে ৯।
• ভাগশেষ (remainder) — যা বাকি থাকে, এখানে ২।

এই দুটি শর্ত মিলেই ভাগের সংজ্ঞা। একে বলে division-এর invariant (যে সম্পর্ক সবসময় সত্য থাকে):

ধনাত্মক সংখ্যায় এই দুই শর্ত মানে এমন ভাগফল আর ভাগশেষ একটিই আছে। ছোট্ট প্রমাণ: ধরুন a = d·q₁ + r₁ = d·q₂ + r₂, দুটি ভাগশেষই 0 থেকে d − 1-এর মধ্যে। বিয়োগ করলে d·(q₁ − q₂) = r₂ − r₁. ডান পাশের মান −(d − 1) থেকে d − 1-এর মধ্যে, অথচ বাঁ পাশ d-এর গুণিতক। d-এর একমাত্র গুণিতক যা এই সীমার ভেতরে পড়ে তা হলো 0. তাই q₁ = q₂ আর r₁ = r₂. ঋণাত্মক সংখ্যা এলে দ্বিতীয় শর্তটি নিয়ে মতভেদ শুরু হয় — সেটি অংশ ৪-এর গল্প।

দশমিকে আর binary-তে long division

স্কুলে শেখা long division (লম্বা ভাগ)-এর কথা মনে করুন। দশমিকে প্রতিটি ধাপে আপনাকে আন্দাজ করতে হয়, ভাজক কতবার ঢুকবে — ০ থেকে ৯-এর মধ্যে কোনটি। ভুল আন্দাজ করলে মুছে আবার করতে হয়। Binary-তে এই সমস্যা নেই: প্রতিটি ধাপে ভাগফলের অঙ্ক শুধু ০ অথবা ১. প্রশ্ন একটিই — “এখনকার আংশিক ভাগশেষ থেকে ভাজক বিয়োগ করা যায় কি না?” যায় তো ১ লিখে বিয়োগ করুন, না যায় তো ০ লিখে পরের বিট নামিয়ে আনুন।

প্রথম উদাহরণ সবচেয়ে ছোট: ৭ ÷ ২, binary-তে 111 ÷ 10.

        011        <- quotient (3)
      ------
  10 ) 111
       1           1 < 10  -> q bit 0
       11          11 >= 10 -> q bit 1, 11 - 10 = 1
       -10
        11         bring down 1: 11 >= 10 -> q bit 1
       -10
         1         <- remainder (1)        check: 10 x 11 + 1 = 111 (2 x 3 + 1 = 7)

দ্বিতীয় উদাহরণ একটু বড়: আমের হিসাব ৭৪ ÷ ৮, অর্থাৎ 1001010 ÷ 1000. নিচের stepper-এ প্রতিটি বিট নামিয়ে আনা আর তুলনা ধাপে ধাপে দেখুন। “পরে” চাপুন:

dividend  1 0 0 1 0 1 0
divisor   1000

take 1    : 1    < 1000 -> q = 0
take 10   : 10   < 1000 -> q = 00
take 100  : 100  < 1000 -> q = 000

take 1001 : 1001 >= 1000 -> q = 0001
            1001
          - 1000
          ------
               1   partial remainder

bring down 0 : 10   < 1000 -> q = 00010
bring down 1 : 101  < 1000 -> q = 000100

bring down 0 : 1010 >= 1000 -> q = 0001001
            1010
          - 1000
          ------
              10   remainder

quotient  = 0001001 = 9
remainder = 10      = 2

1000 x 1001 = 1001000      (8 x 9 = 72)
            +      10      (+ 2)
            = 1001010      (74)  OK
and 0 <= 10 < 1000          (0 <= 2 < 8)  OK

শেষ কথাটি গুরুত্বপূর্ণ, আর গুণের সাথে ভাগের বড় পার্থক্যও এখানেই। গুণে (পর্ব ২১) সবগুলো আংশিক গুণফল একে অপরের থেকে স্বাধীন — একসাথে বানিয়ে carry-save adder-এর গাছে যোগ করা যায়। ভাগে প্রতিটি ভাগফল-বিট জানতে আগের ধাপের ভাগশেষ লাগে। ধাপগুলো শিকলের মতো একটির পর একটি — এটাই ভাগ ধীর হওয়ার মূল কারণ।

২ · Restoring division — বিয়োগ করে দেখা, ঋণাত্মক হলে ফিরিয়ে আনা

Hardware-এ “তুলনা করে তারপর বিয়োগ” আলাদা দুটি কাজ না করে একটি কৌশল নেওয়া হয়: আগে বিয়োগ করে ফেলা, তারপর ফলের চিহ্ন দেখা। ফল ধনাত্মক বা শূন্য হলে বিয়োগ ঠিক ছিল — ভাগফল-বিট ১. ঋণাত্মক হলে বিয়োগ করা উচিত ছিল না — ভাজক আবার যোগ করে আগের মান ফিরিয়ে আনা (restore) আর ভাগফল-বিট ০. এই কারণে নাম restoring division.

Hardware-এ লাগে তিনটি register আর একটি adder-subtractor (পর্ব ১৩-এর ALU-ই যথেষ্ট):

A আর Q পাশাপাশি জোড়া লাগানো একটি ২n-বিটের shift register হিসেবে কাজ করে (A:Q). প্রতিবার বাঁয়ে সরালে Q-এর সবচেয়ে বাঁয়ের বিট A-তে ঢোকে — ঠিক long division-এ “পরের বিট নামিয়ে আনা”-র মতো — আর Q-এর ডান দিকে একটি খালি ঘর তৈরি হয়, যেখানে নতুন ভাগফল-বিট বসবে। ভাজ্যের বিটগুলো এক এক করে বেরিয়ে যায়, আর তাদের জায়গা ভাগফলের বিট দখল করে। A-তে একটি বাড়তি বিট রাখা হয় চিহ্ন দেখার জন্য, কারণ বিয়োগের ফল ঋণাত্মক হতে পারে (পর্ব ০৫-এর two's complement-এ)। অ্যালগরিদম:

A = 0;  Q = dividend;  M = divisor
repeat n times:
    shift A:Q left by one bit          # next dividend bit enters A
    A = A - M                          # trial subtraction
    if A < 0:  q0 = 0;  A = A + M      # restore
    else:      q0 = 1
quotient = Q;  remainder = A

এবার পরীক্ষার সবচেয়ে প্রিয় উদাহরণ: ৪-বিটে 0111 ÷ 0010 (7 ÷ 2). A-কে ৫ বিটে দেখানো হয়েছে। প্রতিটি ধাপে কোন লাইন চলছে আর register-এ কী আছে, মিলিয়ে দেখুন:

1A = 0; Q = dividend; M = divisor2repeat n times:3  shift A:Q left by 14  A = A - M5  if A < 0: q0 = 0; A = A + M6  else:     q0 = 17quotient = Q; remainder = A

এই অ্যালগরিদম কেন সবসময় ঠিক উত্তর দেয়? প্রতিটি iteration-এর শুরুতে একটি invariant সত্য থাকে: 0 ≤ A < M, আর A হলো এ পর্যন্ত নামানো ভাজ্য-বিটগুলোর ভাগশেষ। Shift করলে A হয় 2A + (পরের বিট), যা 2M − 1-এর চেয়ে বড় হতে পারে না। তাই M বড়জোর একবার ঢোকে, আর বিয়োগ (প্রয়োজনে restore) করলে আবার 0 ≤ A < M. n বার পরে সব বিট নামানো শেষ, তাই A পুরো ভাজ্যের ভাগশেষ আর Q পুরো ভাগফল। এই একই যুক্তি দেখায়, কেন A-তে n + 1 বিট লাগে: 2A + 1 সর্বোচ্চ 2M − 1, যা n বিটে না-ও ধরতে পারে (M-এর MSB ১ হলে)।

৮-বিটের একটি উদাহরণ: 1001 0110 ÷ 0000 1011 (150 ÷ 11)

পরীক্ষায় প্রায়ই ৮-বিটের একটি টেবিল চাওয়া হয়। নিয়ম একই, শুধু ৮টি iteration. প্রতিটি iteration-এর শেষে A আর Q কী দাঁড়াল, তা নিচে (A ৯ বিট):

ফল: ভাগফল 0000 1101 = ১৩, ভাগশেষ ৭. যাচাই: 11 × 13 + 7 = 143 + 7 = 150 ✓. এখানে ৮টি বিয়োগ আর ৫টি restore — মোট ১৩টি যোগ-বিয়োগ। লক্ষ করুন, ভাগফলের যতগুলো বিট ০, ঠিক ততগুলো restore. সবচেয়ে খারাপ ক্ষেত্রে (ভাগফল ০) n বিয়োগ + n restore = 2n; গড়ে মোটামুটি 1.5n.

৩ · Non-restoring division — ফিরিয়ে না এনে পরের ধাপে যোগ

Restoring-এর অপচয়টি স্পষ্ট: ঋণাত্মক হলে একটি যোগ করে আগের মান ফেরানো, তারপর পরের ধাপে shift করে আবার বিয়োগ। দুটি কাজকে একটিতে নামানো যায় কি? ছোট্ট একটি বীজগণিত দেখুন। ধরুন বিয়োগের পর A ঋণাত্মক হলো। Restoring পরের ধাপে যা করে:

অর্থাৎ restore না করে সরাসরি shift করে M যোগ করলেই একই মান আসে! এটাই non-restoring division-এর মূল চিন্তা। নিয়ম:

A = 0;  Q = dividend;  M = divisor
repeat n times:
    if A >= 0:  shift A:Q left;  A = A - M
    else:       shift A:Q left;  A = A + M
    q0 = 1 if A >= 0 else 0
if A < 0:  A = A + M          # final correction of the remainder
quotient = Q;  remainder = A

প্রতি iteration-এ ঠিক একটি যোগ বা বিয়োগ, তাই মোট n টি, আর শেষে A ঋণাত্মক থাকলে একটি সংশোধন — সর্বোচ্চ n + 1. ভাগফল-বিটের নিয়ম বদলায়নি: নতুন A ধনাত্মক হলে ১, ঋণাত্মক হলে ০. শেষের সংশোধন কেন লাগে? শেষ ধাপে A ঋণাত্মক থাকলে পরের কোনো ধাপ নেই যেখানে “যোগ” দিয়ে তা পুষিয়ে নেওয়া যাবে, তাই restoring-এর মতো একবার M যোগ করে আসল ভাগশেষ ফেরাতে হয়। ভাগফল তখনো ঠিক থাকে, কারণ ঋণাত্মক A-তে q0 = 0 ইতিমধ্যে বসানো আছে।

নিচের stepper-এ একই 7 ÷ 2-এর দ্বিতীয় iteration দেখুন — যেখানে আগের ধাপের ফল ঋণাত্মক, আর restoring হলে কী হতো তার সাথে তুলনা:

A:Q = 00000 0111   M = 00010
shift      -> A = 00000, Q = 111_
A = A - M  -> A = 11110 (-2)   negative
q0 = 0     -> Q = 1110
no restore!  A stays -2

A:Q = 11110 1110
shift      -> A = 11101 (-3), Q = 110_
A = A + M  -> A = 11111 (-1)   still negative
q0 = 0     -> Q = 1100
operations so far: 2

restoring:  restore  11110 + 00010 = 00000  (0)
            shift    00000 -> 00001          (1)
            subtract 00001 - 00010 = 11111 (-1)
non-rest.:  shift 11110 -> 11101 (-3), add -> 11111 (-1)

same A, same q0 -- restoring used 3 ops, non-restoring 2

A = -2, M = 2, next dividend bit = 1
restoring    : 2(A + M) - M + 1 = 2(0) - 2 + 1 = -1
non-restoring: 2A + M + 1       = -4 + 2 + 1    = -1
(+1 = the dividend bit that entered A during the shift)

iter 3: A = -1 < 0  -> shift A = 11111 (-1), A + M = 00001 (1), q0 = 1
iter 4: A =  1 >= 0 -> shift A = 00011 (3),  A - M = 00001 (1), q0 = 1
A >= 0 at the end   -> no correction needed

Q = 0011 (3), R = 00001 (1)
add/sub: non-restoring 4   vs   restoring 6

নিচের simulator দুটি অ্যালগরিদমকেই একই ইনপুটে চালায় — ৪-বিটের 7 ÷ 2 আর ৮-বিটের 150 ÷ 11 — আর পরীক্ষার টেবিলের মতো কলাম ছাপে: iteration, ধাপ, quotient (Q), divisor (M) আর remainder (A). Run চাপুন, তারপর নিজের সংখ্যা বসিয়ে দেখুন:

// Restoring vs non-restoring division, n-bit unsigned. A has n+1 bits (sign).
const b = (v, w) => (v >>> 0).toString(2).padStart(32, "0").slice(-w);
function divide(N, M, n, restoring) {
  let A = 0, Q = N, ops = 0;
  const row = (it, step) => console.log(String(it).padEnd(5) + step.padEnd(18) +
    b(Q, n).padEnd(10) + b(M, n + 1).padEnd(11) + b(A, n + 1) + ` (${A})`);
  console.log((restoring ? "RESTORING" : "NON-RESTORING") +
    "\niter step              quotient  divisor    remainder A");
  row(0, "initial");
  for (let i = 1; i <= n; i++) {
    const wasNeg = A < 0;
    A = (A << 1) | ((Q >> (n - 1)) & 1);           // shift A:Q left by one
    Q = (Q << 1) & ((1 << n) - 1);
    if (restoring || !wasNeg) { A -= M; ops++; row(i, "shl, A = A - M"); }
    else { A += M; ops++; row(i, "shl, A = A + M"); }
    if (A >= 0) { Q |= 1; row(i, "A>=0: q0 = 1"); }
    else if (restoring) { A += M; ops++; row(i, "A<0: restore"); }
    else row(i, "A<0: q0 = 0");
  }
  if (!restoring && A < 0) { A += M; ops++; row("end", "fix: A = A + M"); }
  console.log(`=> Q = ${Q}, R = ${A}, add/sub operations = ${ops}\n`);
}
for (const [N, M, n] of [[7, 2, 4], [150, 11, 8]]) {
  console.log(`=== ${N} / ${M} as ${n}-bit: ${b(N, n)} / ${b(M, n)} ===`);
  divide(N, M, n, true);
  divide(N, M, n, false);
}

=== 7 / 2 as 4-bit: 0111 / 0010 ===
RESTORING
iter step              quotient  divisor    remainder A
0    initial           0111      00010      00000 (0)
1    shl, A = A - M    1110      00010      11110 (-2)
1    A<0: restore      1110      00010      00000 (0)
2    shl, A = A - M    1100      00010      11111 (-1)
2    A<0: restore      1100      00010      00001 (1)
3    shl, A = A - M    1000      00010      00001 (1)
3    A>=0: q0 = 1      1001      00010      00001 (1)
4    shl, A = A - M    0010      00010      00001 (1)
4    A>=0: q0 = 1      0011      00010      00001 (1)
=> Q = 3, R = 1, add/sub operations = 6

NON-RESTORING
iter step              quotient  divisor    remainder A
0    initial           0111      00010      00000 (0)
1    shl, A = A - M    1110      00010      11110 (-2)
1    A<0: q0 = 0       1110      00010      11110 (-2)
2    shl, A = A + M    1100      00010      11111 (-1)
2    A<0: q0 = 0       1100      00010      11111 (-1)
3    shl, A = A + M    1000      00010      00001 (1)
3    A>=0: q0 = 1      1001      00010      00001 (1)
4    shl, A = A - M    0010      00010      00001 (1)
4    A>=0: q0 = 1      0011      00010      00001 (1)
=> Q = 3, R = 1, add/sub operations = 4

=== 150 / 11 as 8-bit: 10010110 / 00001011 ===
RESTORING
iter step              quotient  divisor    remainder A
0    initial           10010110  000001011  000000000 (0)
1    shl, A = A - M    00101100  000001011  111110110 (-10)
1    A<0: restore      00101100  000001011  000000001 (1)
2    shl, A = A - M    01011000  000001011  111110111 (-9)
2    A<0: restore      01011000  000001011  000000010 (2)
3    shl, A = A - M    10110000  000001011  111111001 (-7)
3    A<0: restore      10110000  000001011  000000100 (4)
4    shl, A = A - M    01100000  000001011  111111110 (-2)
4    A<0: restore      01100000  000001011  000001001 (9)
5    shl, A = A - M    11000000  000001011  000000111 (7)
5    A>=0: q0 = 1      11000001  000001011  000000111 (7)
6    shl, A = A - M    10000010  000001011  000000100 (4)
6    A>=0: q0 = 1      10000011  000001011  000000100 (4)
7    shl, A = A - M    00000110  000001011  111111110 (-2)
7    A<0: restore      00000110  000001011  000001001 (9)
8    shl, A = A - M    00001100  000001011  000000111 (7)
8    A>=0: q0 = 1      00001101  000001011  000000111 (7)
=> Q = 13, R = 7, add/sub operations = 13

NON-RESTORING
iter step              quotient  divisor    remainder A
0    initial           10010110  000001011  000000000 (0)
1    shl, A = A - M    00101100  000001011  111110110 (-10)
1    A<0: q0 = 0       00101100  000001011  111110110 (-10)
2    shl, A = A + M    01011000  000001011  111110111 (-9)
2    A<0: q0 = 0       01011000  000001011  111110111 (-9)
3    shl, A = A + M    10110000  000001011  111111001 (-7)
3    A<0: q0 = 0       10110000  000001011  111111001 (-7)
4    shl, A = A + M    01100000  000001011  111111110 (-2)
4    A<0: q0 = 0       01100000  000001011  111111110 (-2)
5    shl, A = A + M    11000000  000001011  000000111 (7)
5    A>=0: q0 = 1      11000001  000001011  000000111 (7)
6    shl, A = A - M    10000010  000001011  000000100 (4)
6    A>=0: q0 = 1      10000011  000001011  000000100 (4)
7    shl, A = A - M    00000110  000001011  111111110 (-2)
7    A<0: q0 = 0       00000110  000001011  111111110 (-2)
8    shl, A = A + M    00001100  000001011  000000111 (7)
8    A>=0: q0 = 1      00001101  000001011  000000111 (7)
=> Q = 13, R = 7, add/sub operations = 8

৪ · Signed ভাগ — চিহ্ন আলাদা, আর ভাগশেষের তিন নিয়ম

ওপরের দুটি অ্যালগরিদম unsigned সংখ্যার জন্য। ঋণাত্মক সংখ্যা ভাগ করার সবচেয়ে সরল (আর বহু hardware-এ ব্যবহৃত) পদ্ধতি হলো চিহ্ন আলাদা করে রাখা:

1. দুটি সংখ্যার মান (magnitude) নিয়ে unsigned ভাগ করা: |a| ÷ |d| = q′, ভাগশেষ r′.
2. ভাগফলের চিহ্ন = দুটি চিহ্ন-বিটের XOR: চিহ্ন আলাদা হলে ভাগফল ঋণাত্মক।
3. ভাগশেষের চিহ্ন = ভাজ্যের চিহ্ন (এই নিয়মে, যা C আর RISC-V মানে)।

যেমন −7 ÷ 2: 7 ÷ 2 = 3, ভাগশেষ 1. চিহ্ন আলাদা, তাই ভাগফল −3; ভাজ্য ঋণাত্মক, তাই ভাগশেষ −1. যাচাই: 2 × (−3) + (−1) = −7 ✓. একটি খুঁটিনাটি: ৩২-বিটে |INT_MIN| = 2³¹, যা signed-এ ধরে না কিন্তু ৩২-বিট unsigned-এ ধরে — তাই magnitude-কে unsigned হিসেবে রাখলে সমস্যা নেই। (Two's complement-এ সরাসরি ভাগের non-restoring রূপও আছে, কিন্তু ধারণা বোঝার জন্য এই পথটিই সহজ।)

ভাগশেষের চিহ্ন — তিনটি প্রচলিত নিয়ম

ঋণাত্মক সংখ্যায় অংশ ১-এর invariant-এর প্রথম অংশ (a = d·q + r) সবাই মানে, কিন্তু “ভাগশেষ কোন সীমায় থাকবে” নিয়ে তিনটি প্রচলিত নিয়ম আছে। প্রতিটি নিয়ম ভাগফলকে কোন দিকে গোল (round) করে, সেটাই পার্থক্য:

±7 ÷ ±2-এর চারটি জোড়ায় তিন নিয়ম পাশাপাশি (প্রতিটি সারিতে d × q + r = a যাচাই করা):

লক্ষ করুন: দুটি সংখ্যাই ধনাত্মক হলে তিন নিয়মই এক। ভাজক ধনাত্মক হলে floored আর Euclidean এক। আর তিন নিয়মেই |r| < |d| — পার্থক্য শুধু r-এর চিহ্নে, আর সেই অনুযায়ী q এক কম-বেশি। একটি দরকারি সম্পর্ক: truncated-এর ভাগশেষ r ≠ 0 হলে আর r-এর চিহ্ন d-এর উল্টো হলে, floored পেতে q থেকে 1 বাদ দিন আর r-এর সাথে d যোগ করুন। −7 ÷ 2: (−3, −1) থেকে (−4, 1).

নিচের প্রোগ্রাম তিন নিয়মকেই কয়েকটি ± জোড়ায় চালায় আর প্রতিটির জন্য invariant যাচাই করে। সাথে RISC-V-এর দুটি বিশেষ ক্ষেত্র — শূন্য দিয়ে ভাগ আর INT_MIN ÷ −1 — spec-এর টেবিলের নিয়ম হুবহু কোডে লিখে (এগুলো অংশ ৫-এর বিষয়):

// Three conventions for signed integer division. Each must give a = d*q + r.
const trunc = (a, d) => { const q = Math.trunc(a / d) || 0; return [q, a - d * q]; }; // C, Java, RISC-V
const floor = (a, d) => { const q = Math.floor(a / d); return [q, a - d * q]; };      // Python // and %
const eucl = (a, d) => {                                                              // r is never negative
  const m = Math.abs(d), r = ((a % m) + m) % m; return [(a - r) / d, r];
};
const cell = ([q, r]) => `q=${q} r=${r}`.padEnd(11);
console.log("  a   d | truncated  | floored    | Euclidean  | a = d*q + r, |r| < |d| ?");
for (const [a, d] of [[7, 2], [-7, 2], [7, -2], [-7, -2], [-7, 3], [6, -3]]) {
  const res = [trunc(a, d), floor(a, d), eucl(a, d)];
  const ok = res.every(([q, r]) => d * q + r === a && Math.abs(r) < Math.abs(d));
  console.log(`${String(a).padStart(3)} ${String(d).padStart(3)} | ${res.map(cell).join("| ")}| ${ok}`);
}
// RISC-V "M" extension, RV32: the spec's table for the special cases (no trap!)
const INT_MIN = -2147483648;
function rvDiv(a, d) {                 // div / rem (signed)
  if (d === 0) return [-1, a];         // quotient: all bits set; remainder: the dividend
  if (a === INT_MIN && d === -1) return [INT_MIN, 0];   // overflow case
  return trunc(a, d);
}
const rvDivu = (a, d) => (d === 0 ? [0xFFFFFFFF, a] : [Math.floor(a / d), a % d]);
const hex = v => "0x" + (v >>> 0).toString(16).toUpperCase().padStart(8, "0");
console.log("\nRISC-V rule (from the spec table)   quotient              remainder");
for (const [a, d] of [[7, 0], [-7, 0], [INT_MIN, -1], [-7, 2]]) {
  const [q, r] = rvDiv(a, d);
  console.log(`div/rem   ${String(a).padStart(11)} / ${String(d).padStart(2)}  ${String(q).padStart(11)} (${hex(q)})  ${r}`);
}
const [uq, ur] = rvDivu(7, 0);
console.log(`divu/remu           7 /  0  ${String(uq).padStart(11)} (${hex(uq)})  ${ur}`);

  a   d | truncated  | floored    | Euclidean  | a = d*q + r, |r| < |d| ?
  7   2 | q=3 r=1    | q=3 r=1    | q=3 r=1    | true
 -7   2 | q=-3 r=-1  | q=-4 r=1   | q=-4 r=1   | true
  7  -2 | q=-3 r=1   | q=-4 r=-1  | q=-3 r=1   | true
 -7  -2 | q=3 r=-1   | q=3 r=-1   | q=4 r=1    | true
 -7   3 | q=-2 r=-1  | q=-3 r=2   | q=-3 r=2   | true
  6  -3 | q=-2 r=0   | q=-2 r=0   | q=-2 r=0   | true

RISC-V rule (from the spec table)   quotient              remainder
div/rem             7 /  0           -1 (0xFFFFFFFF)  7
div/rem            -7 /  0           -1 (0xFFFFFFFF)  -7
div/rem   -2147483648 / -1  -2147483648 (0x80000000)  0
div/rem            -7 /  2           -3 (0xFFFFFFFD)  -1
divu/remu           7 /  0   4294967295 (0xFFFFFFFF)  7

৫ · শূন্য দিয়ে ভাগ আর INT_MIN ÷ −1 — কোন CPU কী করে

দুটি ভাগের কোনো “ঠিক” উত্তর n-বিট integer-এ নেই। প্রথমটি শূন্য দিয়ে ভাগ — গণিতেই সংজ্ঞাহীন। দ্বিতীয়টি signed overflow: ৩২-বিটে INT_MIN = −2,147,483,648, আর INT_MIN ÷ −1 = +2,147,483,648, যা ৩২-বিট signed-এর সর্বোচ্চ (2,147,483,647)-এর চেয়ে এক বেশি। (এটি ভাগের একমাত্র overflow — অন্য সব ক্ষেত্রে |ভাগফল| ≤ |ভাজ্য|।) ভিন্ন ISA এদের ভিন্নভাবে সামলায়:

RISC-V-এর সারিটি spec-এর (unprivileged ISA manual-এর M extension অধ্যায়) একটি টেবিল থেকে নেওয়া, আর এটি ISA-র অংশ — যেকোনো সঠিক RISC-V core এই মানই দেবে। ARM-এর সারিটি AArch64-এর জন্য; পুরোনো ৩২-বিট ARM-এর অনেক core-এ ভাগের instruction-ই ছিল না, আর কিছু Cortex-R/M core-এ শূন্য দিয়ে ভাগে trap চালু করার একটি নিয়ন্ত্রণ-বিট আছে বলে জানা যায় — নির্দিষ্ট chip-এর manual দেখে নিন। Linux-এ x86-এর #DE ধরা পড়লে kernel প্রোগ্রামকে SIGFPE signal পাঠায়, আর terminal-এ লেখা আসে “Floating point exception” — integer ভাগ হলেও! নামটি ঐতিহাসিক, বিভ্রান্তিকর।

RISC-V কেন trap রাখেনি

RISC-V spec নিজেই এর যুক্তি লিখে রেখেছে (ভাবার্থ): trap রাখলে এটি হতো standard ISA-র একমাত্র গাণিতিক trap — floating-point-এর ভুলও trap করে না, শুধু flag বসিয়ে একটি নির্ধারিত মান লেখে। ভাষার মানদণ্ড যদি শূন্য দিয়ে ভাগে exception চায় (যেমন Java), compiler ভাগের পাশে একটি শাখা (beqz) বসিয়ে দিলেই হয়; সেই শাখা প্রায় কখনো নেওয়া হয় না, তাই branch predictor সহজে ঠিক অনুমান করে আর খরচ খুব কম। আর “সব বিট ১” মানটি বেছে নেওয়া হয়েছে কারণ ভাজক ০ হলে অংশ ২-এর অ্যালগরিদম প্রতিটি বিয়োগে সফল হয় (A − 0 ≥ 0), ফলে প্রতিটি ভাগফল-বিট আপনা থেকেই ১ আর A-তে ভাজ্য রয়ে যায় — divider-এর circuit-এ বাড়তি কিছু লাগে না। নিজে যাচাই করে দেখুন: অ্যালগরিদমে M = 0 বসান।

৬ · দ্রুত ভাগ — SRT, Newton–Raphson আর Goldschmidt

Restoring বা non-restoring প্রতি ধাপে ভাগফলের ১টি বিট দেয়। ৬৪-বিট ভাগে তাহলে ৬৪টি ধাপ, প্রতিটিতে একটি পূর্ণ ৬৪-বিট যোগ-বিয়োগ, যার carry পুরো প্রস্থ পেরোয়। দ্রুত করার দুটি বড় পথ আছে: প্রতি ধাপে বেশি বিট বের করা (digit recurrence, যেমন SRT), অথবা ভাগকে গুণে রূপান্তর করা (Newton–Raphson, Goldschmidt).

SRT division — redundant অঙ্ক আর lookup table

SRT division-এর নাম তিন গবেষকের নামের আদ্যক্ষর থেকে — Sweeney, Robertson আর Tocher, যারা ১৯৫০-এর দশকের শেষ দিকে প্রায় একই সময়ে আলাদাভাবে এই ধারণায় পৌঁছান বলে জানা যায়। মূল কৌশল দুটি:

• Redundant ভাগফল-অঙ্ক: radix-2 SRT-এ প্রতিটি অঙ্ক {−1, 0, 1}, radix-4-এ {−2, −1, 0, 1, 2}. একই সংখ্যা একাধিক উপায়ে লেখা যায় — radix-4-এ দুই অঙ্কের (1, −2) আর (0, 2) দুটিই 2 বোঝায়, কারণ 1 × 4 − 2 = 0 × 4 + 2. তাই একটি ধাপে অঙ্ক একটু বড় বা ছোট বাছলেও পরের ধাপের অঙ্ক তা পুষিয়ে দিতে পারে। ফলে প্রতি ধাপে পুরো প্রস্থের তুলনা লাগে না — আংশিক ভাগশেষের প্রথম কয়েকটি বিট আর ভাজকের প্রথম কয়েকটি বিট দেখে আন্দাজ করলেই চলে। Non-restoring আসলে radix-2-এর একটি বিশেষ রূপ, যেখানে অঙ্ক {−1, +1}.
• Lookup table আর carry-save: অঙ্ক বাছাইয়ের সেই আন্দাজ আসে একটি ছোট lookup table (PLA বা ROM) থেকে। আংশিক ভাগশেষ রাখা হয় carry-save রূপে, তাই প্রতি ধাপে carry ছড়ানোর অপেক্ষাও নেই। Radix-4 প্রতি ধাপে ২টি বিট, radix-16 ৪টি বিট দেয়।

দামটি হলো জটিলতা, আর সেই জটিলতার বিখ্যাত শিকার Intel-এর প্রথম Pentium — ঘটনাটি Pentium FDIV bug নামে পরিচিত। ১৯৯৪ সালে গণিতবিদ Thomas Nicely লক্ষ করেন, কিছু বিরল ভাজক-ভাজ্যের জোড়ায় Pentium-এর floating-point ভাগ ভুল উত্তর দেয়। পরে জানা যায়, radix-4 SRT divider-এর lookup table-এর কয়েকটি ঘর (সাধারণত বলা হয় ৫টি) ভুলবশত ফাঁকা ছিল। Intel শেষ পর্যন্ত chip বদলে দেওয়ার প্রস্তাব দেয়, আর এর জন্য প্রায় ৪৭৫ মিলিয়ন ডলারের একটি খরচ (charge) দেখায় বলে প্রতিবেদনে আসে। টেবিলের ভুল ঠিক কীভাবে ভুল ফল দিত, তা নিচের ভাবনার প্রশ্ন ২-এ; floating-point ভাগের বাকি ধাপ (exponent বিয়োগ, normalise আর rounding) পর্ব ২৪-এ (Floating point-এর হিসাব)।

Newton–Raphson — গুণ দিয়ে 1/d

দ্বিতীয় পথ ভিন্ন: a ÷ d = a × (1/d). আর 1/d-কে শুধু গুণ আর বিয়োগ দিয়ে বের করা যায় Newton–Raphson পদ্ধতিতে। ফাংশন f(x) = 1/x − d-এর শূন্য হলো x = 1/d. Newton-এর সূত্র x_k+1 = x_k − f(x_k)/f′(x_k), আর f′(x) = −1/x². বসালে:

সুন্দর ব্যাপার হলো, এতে কোনো ভাগ নেই — দুটি গুণ আর একটি বিয়োগ। কত দ্রুত মেলে? ভুলকে e_k = 1 − d·x_k ধরলে:

অর্থাৎ প্রতিটি ধাপে ভুল বর্গ হয় — ভুল 10⁻² থেকে 10⁻⁴, তারপর 10⁻⁸. সঠিক অঙ্কের সংখ্যা প্রতি ধাপে দ্বিগুণ — একে বলে quadratic convergence. শর্ত একটি: শুরুর ভুল |e₀| < 1 হতে হবে। নিচের stepper-এ 1/3 দেখুন, শুরুর অনুমান x₀ = 0.3:

d  = 3,  target 1/3 = 0.3333333333333333
x0 = 0.3
e0 = 1 - 3 x 0.3 = 0.1        (1 correct digit)

d*x0 = 0.9,  2 - 0.9 = 1.1
x1 = 0.3 x 1.1 = 0.33
e1 = 1 - 0.99 = 0.01  = e0^2    (2 digits)

d*x1 = 0.99,  2 - 0.99 = 1.01
x2 = 0.33 x 1.01 = 0.3333
e2 = 1 - 0.9999 = 0.0001 = e1^2  (4 digits)

x3 = 0.33333333
e3 = 1e-8 = e2^2                (8 digits)

x4 = 0.3333333333333333
e4 = 2.22e-16  (about 1e-16 = e3^2; double has ~16 digits)
4 iterations: 1 -> 2 -> 4 -> 8 -> 16 digits

Goldschmidt division একই গণিতের আরেক রূপ। a/d-এর ওপরে-নিচে একই গুণক F = 2 − D দিয়ে বারবার গুণ করা হয়: N ← N·F, D ← D·F. D = 1 − ε হলে নতুন D = (1 − ε)(1 + ε) = 1 − ε² — এখানেও ভুল বর্গ হয়। D যখন ১-এ পৌঁছায়, N হয়ে যায় a/d. সুবিধা: প্রতি ধাপের দুটি গুণ একে অপরের ওপর নির্ভর করে না, তাই pipelined multiplier-এ পাশাপাশি চলে। অসুবিধা: Newton–Raphson “নিজেকে শুধরে নেয়” (প্রতি ধাপে আসল d ব্যবহার হয়, তাই আগের ধাপের rounding ভুল মুছে যায়), Goldschmidt-এ rounding ভুল জমতে থাকে, তাই শেষে বাড়তি সংশোধন লাগে। IBM System/360 Model 91 (১৯৬০-এর দশক) এই পদ্ধতির প্রথম দিকের ব্যবহারকারী হিসেবে উল্লেখিত, আর পরেও কিছু AMD প্রসেসরের floating-point ভাগে এ ধরনের গুণ-ভিত্তিক পদ্ধতি ব্যবহারের কথা প্রকাশিত হয়েছে।

নিচের প্রোগ্রাম দুটি পদ্ধতিই চালায়: 1/3 (x₀ = 0.3) আর 1/0.75 — দ্বিতীয়টিতে ভাজককে floating-point mantissa-র মতো [0.5, 1) সীমায় রেখে বহুল ব্যবহৃত সরলরেখা-অনুমান x₀ = 48/17 − (32/17)·d দিয়ে শুরু:

// Newton-Raphson for 1/d: x(k+1) = x(k) * (2 - d*x(k)). The error e = 1 - d*x squares each step.
function newton(d, x0, steps) {
  console.log(`1/${d} = ${1 / d}   (start x0 = ${x0.toFixed(6)})`);
  console.log("k   x(k)                 e = 1 - d*x(k)   correct digits");
  let x = x0;
  for (let k = 0; k <= steps; k++) {
    const e = 1 - d * x;
    const digits = e === 0 ? "all (double)" : (-Math.log10(Math.abs(e))).toFixed(1);
    console.log(`${k}   ${x.toPrecision(16).padEnd(21)}${e.toExponential(2).padEnd(17)}${digits}`);
    x = x * (2 - d * x);               // one multiply-subtract-multiply step
  }
  console.log("");
}
newton(3, 0.3, 4);
const d = 0.75;                        // divisor scaled into [0.5, 1), like a mantissa
newton(d, 48 / 17 - (32 / 17) * d, 4); // classic straight-line first guess

// Goldschmidt: multiply N and D by F = 2 - D; D -> 1 and N -> N/D.
let N = 1, D = d;
console.log("Goldschmidt for 1/0.75\nk   F                   N                    D");
for (let k = 1; k <= 4; k++) {
  const F = 2 - D;
  N *= F; D *= F;                      // the two multiplies are independent
  console.log(`${k}   ${String(F).padEnd(20)}${N.toPrecision(16).padEnd(21)}${D.toPrecision(16)}`);
}

1/3 = 0.3333333333333333   (start x0 = 0.300000)
k   x(k)                 e = 1 - d*x(k)   correct digits
0   0.3000000000000000   1.00e-1          1.0
1   0.3300000000000000   1.00e-2          2.0
2   0.3333000000000000   1.00e-4          4.0
3   0.3333333300000000   1.00e-8          8.0
4   0.3333333333333333   2.22e-16         15.7

1/0.75 = 1.3333333333333333   (start x0 = 1.411765)
k   x(k)                 e = 1 - d*x(k)   correct digits
0   1.411764705882353    -5.88e-2         1.2
1   1.328719723183391    3.46e-3          2.5
2   1.333317369284372    1.20e-5          4.9
3   1.333333333142195    1.43e-10         9.8
4   1.333333333333333    0.00e+0          all (double)

Goldschmidt for 1/0.75
k   F                   N                    D
1   1.25                1.250000000000000    0.9375000000000000
2   1.0625              1.328125000000000    0.9960937500000000
3   1.00390625          1.333312988281250    0.9999847412109375
4   1.0000152587890625  1.333333333022892    0.9999999997671694

ভাগ কেন এখনো ধীর — latency আর pipelining

এত কৌশলের পরও আধুনিক CPU-তে ভাগ গুণের চেয়ে অনেক ধীর। সাধারণ চিত্র (মাইক্রো-আর্কিটেকচার আর operand-এর আকারভেদে অনেক বদলায় — Agner Fog-এর instruction টেবিলের মতো উৎস থেকে নির্দিষ্ট CPU-র সংখ্যা দেখে নিন):

ভাগ পুরোপুরি pipelined নয় কেন? গুণে প্রতিটি আংশিক গুণফল স্বাধীন, তাই Wallace tree-র মতো একটি বড় combinational গাছ বানিয়ে তাকে stage-এ কেটে ফেলা যায় — প্রতি cycle-এ নতুন গুণ ঢোকে। ভাগে প্রতিটি অঙ্ক আগের ভাগশেষের ওপর নির্ভর করে, তাই divider সাধারণত একটি ছোট circuit যা নিজেকেই বারবার ব্যবহার করে (iterative). একটি ভাগ চলার সময় পরেরটি অপেক্ষা করে। অনেক আধুনিক divider আরও একটি কৌশল নেয়: ভাজ্যের শুরুর শূন্যগুলো গুনে আগেভাগে থেমে যাওয়া (early termination), তাই ছোট সংখ্যার ভাগ দ্রুত শেষ হয় — latency তখন ডেটার ওপর নির্ভর করে।

৭ · Compiler ভাগ এড়িয়ে চলে — magic number, AND আর hash table

ভাগ এত দামি বলে compiler সুযোগ পেলেই একে সস্তা কাজে বদলে দেয় — একে বলে strength reduction. সবচেয়ে সাধারণ ক্ষেত্র তিনটি।

১. ২-এর ঘাত দিয়ে ভাগ: shift

Unsigned x / 2^k = x >> k (logical shift). Signed-এ সাবধান: arithmetic shift নিচের দিকে (floor) গোল করে, অথচ C-র ভাগ শূন্যের দিকে কাটে। −7 >> 1 = −4, কিন্তু −7 / 2 = −3. তাই compiler ঋণাত্মক x-এ আগে 2^k − 1 যোগ করে (bias), তারপর shift করে। এর বিস্তারিত আর প্রমাণ পর্ব ২০-এ (Integer যোগ-বিয়োগ)।

২. ধ্রুবক দিয়ে ভাগ: magic number দিয়ে গুণ

ভাজক যদি compile-এর সময়েই জানা থাকে (যেমন x / 3, x / 10), তাহলে ভাগকে একটি গুণ আর একটি shift-এ বদলানো যায়; সেই বিশেষ গুণকটিকে বলে magic number. এর ব্যাপক ব্যবহারের ভিত্তি Torbjörn Granlund আর Peter Montgomery-র ১৯৯৪ সালের গবেষণাপত্র “Division by Invariant Integers using Multiplication”. ধারণাটি দশমিকের মতোই সহজ: x / 3 = x × (1/3), আর 1/3-কে একটি binary ভগ্নাংশ M / 2^s দিয়ে যথেষ্ট কাছাকাছি লিখলেই হয়। ৩২-বিট unsigned-এর জন্য:

কেন সব x-এ ঠিক (প্রমাণ): M = (2³³ + 1)/3 বসালে x·M / 2³³ = x/3 + x/(3·2³³). শেষ পদটি — ভুলের পরিমাণ — x < 2³² হওয়ায় 2³²/(3·2³³) = 1/6-এর চেয়ে ছোট। এখন x/3 = q + r/3, যেখানে r ∈ {0, 1, 2}, তাই ভগ্নাংশ অংশ সর্বোচ্চ 2/3. মোট ভগ্নাংশ অংশ < 2/3 + 1/6 = 5/6 < 1, তাই floor নিলে ঠিক q আসে — কখনো পরের পূর্ণসংখ্যায় পৌঁছায় না। একই হিসাবে x / 10 = (x × 0xCCCCCCCD) >> 35: 0xCCCCCCCD × 10 = 2³⁵ + 2, ভুল < 2³²/(5·2³⁵) = 1/40, আর 9/10 + 1/40 < 1. লক্ষ করুন, গুণফল ৬৪ বিটের — x আর M দুটিই ৩২-বিট, তাই গুণফল 2⁶⁴-এর নিচে, উপচে পড়ে না।

সাম্প্রতিক gcc -O2 x86-64-এর জন্য unsigned f(unsigned x) { return x / 3; }-কে মোটামুটি এভাবে লেখে (সংস্করণভেদে সামান্য আলাদা হতে পারে):

# x86-64, Intel syntax (System V: x in edi, result in eax)
div3:
    mov     eax, edi
    mov     edx, 2863311531      # 0xAAAAAAAB
    imul    rax, rdx             # 64-bit product
    shr     rax, 33
    ret

# RV32IM (x in a0): mulhu gives the upper 32 bits = product >> 32
div3:
    li      a5, -1431655765      # 0xAAAAAAAB as a signed immediate
    mulhu   a0, a0, a5
    srli    a0, a0, 1            # total shift 32 + 1 = 33
    ret

কোনো div instruction নেই! নিচের C প্রোগ্রাম এই দাবিটি যাচাই করে: সব ছোট সংখ্যা, একটি নির্ধারিত নিয়মে ছড়ানো ৪০ লাখের বেশি সংখ্যা আর সীমার কাছের মানগুলোতে magic-গুণ বনাম আসল /. সাথে একটি ভুল “magic” (0x55555555 >> 32, যা দেখতে 1/3-এর মতোই) আর ২-এর ঘাত দিয়ে ভাগশেষের AND-কৌশল:

#include <stdio.h>
#include <stdint.h>

/* Division by a constant without a divide instruction (unsigned 32-bit) */
static uint32_t div3(uint32_t x)  { return (uint32_t)(((uint64_t)x * 0xAAAAAAABu) >> 33); }
static uint32_t div10(uint32_t x) { return (uint32_t)(((uint64_t)x * 0xCCCCCCCDu) >> 35); }
static uint32_t naive3(uint32_t x) { return (uint32_t)(((uint64_t)x * 0x55555555u) >> 32); }

static unsigned long tested, bad3, bad10, badnaive;
static void check(uint32_t x) {
    tested++;
    if (div3(x) != x / 3u) bad3++;
    if (div10(x) != x / 10u) bad10++;
    if (naive3(x) != x / 3u) badnaive++;
}

int main(void) {
    const uint32_t edge[] = {0u, 1u, 2u, 3u, 9u, 10u, 11u, 0x7FFFFFFFu,
                             0x80000000u, 0xFFFFFFFDu, 0xFFFFFFFEu, 0xFFFFFFFFu};
    for (unsigned i = 0; i < sizeof edge / sizeof edge[0]; i++) check(edge[i]);
    for (uint32_t i = 0; i < (1u << 22); i++) {
        check(i);                          /* all small numbers 0 .. 4194303 */
        check(i * 2654435761u);            /* odd multiplier: spread over 32 bits */
        check(0xFFFFFFFFu - i);            /* the top end */
    }
    printf("tested %lu values\n", tested);
    printf("x*0xAAAAAAAB >> 33 vs x/3 : %lu mismatches\n", bad3);
    printf("x*0xCCCCCCCD >> 35 vs x/10: %lu mismatches\n", bad10);
    printf("x*0x55555555 >> 32 vs x/3 : %lu mismatches (e.g. 3 -> %u)\n",
           badnaive, (unsigned)naive3(3u));
    printf("1000003 %% 8 = %u, 1000003 & 7 = %u (unsigned)\n", 1000003u % 8u, 1000003u & 7u);
    printf("-7 %% 8 = %d, -7 & 7 = %d (signed int: not the same!)\n", -7 % 8, -7 & 7);
    return 0;
}

tested 12582924 values
x*0xAAAAAAAB >> 33 vs x/3 : 0 mismatches
x*0xCCCCCCCD >> 35 vs x/10: 0 mismatches
x*0x55555555 >> 32 vs x/3 : 4194302 mismatches (e.g. 3 -> 0)
1000003 % 8 = 3, 1000003 & 7 = 3 (unsigned)
-7 % 8 = -7, -7 & 7 = 1 (signed int: not the same!)

৩. ২-এর ঘাত দিয়ে ভাগশেষ: AND

Unsigned x % 2^k = x & (2^k − 1) — শুধু নিচের k বিট রাখা, একটি bitmask দিয়ে। x % 8 = x & 7, এক cycle-এর কাজ। Signed int-এ এটি মেলে না (−7 % 8 = −7, কিন্তু −7 & 7 = 1), তাই signed %-এ compiler বাড়তি কয়েকটি instruction দিয়ে চিহ্ন সামলায়। পারফরম্যান্সের দিক থেকে ব্যবহারিক কয়েকটি পরামর্শ:

• যে সংখ্যা কখনো ঋণাত্মক হয় না, তা unsigned রাখলে / আর % সস্তা হয় (চিহ্ন-সংশোধন লাগে না)।
• লুপের ভেতরে একই চলক ভাজক দিয়ে বারবার ভাগ হলে (যেমন i % n), সম্ভব হলে বাইরে একবার হিসাব করুন, বা গোনার কৌশল নিন (if (++j == n) j = 0;).
• Runtime-এ জানা কিন্তু বারবার ব্যবহৃত ভাজকের জন্যও magic number একবার হিসাব করে রাখা যায় — libdivide-এর মতো library এই কাজ করে।
• অনুমানে নয়, মেপে সিদ্ধান্ত নিন: compiler ধ্রুবক ভাগ নিজেই বদলায়, হাতে “optimize” করে কোড জটিল করার দরকার নেই।

Hash table-এ এই কৌশলের সবচেয়ে চেনা ব্যবহার। Table-এর আকার ২-এর ঘাত (যেমন 1024) রাখলে bucket-এর সূচক h & (size − 1) — ভাগের বদলে একটি AND. Java-র HashMap এই কারণে আকার ২-এর ঘাত রাখে, আর hash-এর ওপরের বিটগুলো নিচে মিশিয়ে নেয় (কারণ AND শুধু নিচের বিট দেখে, আর দুর্বল hash-এ নিচের বিটগুলো একঘেয়ে হতে পারে)। মৌলিক সংখ্যার (prime) আকারের table-এ বণ্টন ভালো হয় কিন্তু % লাগে। Hash table-এর নকশা দেখুন DSA কোর্সের hash table পর্বে।

৮ · AI-এর যুগে ভাগের হিসাব

AI টুল restoring division-এর ব্যাখ্যা গুছিয়ে লিখতে পারে, কিন্তু টেবিলের সারি, চিহ্নের নিয়ম আর ISA-র বিশেষ ক্ষেত্রে প্রায়ই আত্মবিশ্বাসের সাথে ভুল করে। প্রচলিত কয়েকটি ভুল:

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• প্রতিটি উত্তরে ভাজ্য = ভাজক × ভাগফল + ভাগশেষ মিলিয়ে দেখেছি, আর ভাগশেষ কোন সীমায় তা পরীক্ষা করেছি
• টেবিলের অন্তত দুটি সারি নিজে হাতে করেছি — shift-এ কোন বিট A-তে ঢুকল, বিয়োগে চিহ্ন কী
• চিহ্নের নিয়ম কোন ভাষা বা ISA-র, তা স্পষ্ট; C আর Python মিশে যায়নি
• বিশেষ ক্ষেত্র চালিয়েছি: ভাজক 0, INT_MIN ÷ −1, ভাজ্য < ভাজক, ভাজক 1
• RISC-V বা x86-এর আচরণ নিয়ে দাবি থাকলে manual-এর লাইনটি নিজে পড়েছি
• Magic number-এর দাবি exhaustive বা বড় নমুনায় script দিয়ে পরীক্ষা করেছি