Integer যোগ-বিয়োগ — adder-subtractor, overflow আর status flag

১ · এক adder, দুই অর্থ — ISA-র সামনে প্রশ্নটা কী

মডিউল ২-এ hardware-এর দিকটা দেখা হয়ে গেছে। পর্ব ১১-এ (Adder) full adder জুড়ে ripple আর carry-lookahead adder, আর পর্ব ১৩-এ (ALU নকশা) সেই adder দিয়েই বিয়োগ: B-এর প্রতিটি বিটে একটি XOR আর প্রথম বিটের carry-in = 1, ফলে A − B = A + B′ + 1. এই যন্ত্রটির নাম adder-subtractor. এই পর্বে B′ মানে B-এর সব বিট উল্টানো (কোডে ~B), আর ⊕ মানে XOR. এক ছবিতে পুরো circuit:

          B (n bits)
            │
   sub ──►[ XOR each bit ]──► B or B'
   │                          │
   │      A ─────────────►[ n-bit adder ]──► S (n bits)
   └──────────► carry-in ──►      │
                              carry-out (C),  V = c(n) xor c(n-1)

এখানে একটি কথা মনে রাখলে বাকি পর্ব সহজ হয়ে যাবে: adder জানে না সংখ্যাগুলো signed না unsigned. পর্ব ০৫-এ (two's complement) দেখেছেন, two's complement-এর সবচেয়ে বড় সুবিধা এটাই — একই বিট-প্যাটার্নের যোগ দুই অর্থেই ঠিক, যদি ফল সীমার ভেতরে থাকে। সীমা ছাড়ালে দুই অর্থে দুই রকম বিপদ: unsigned-এ MSB থেকে carry বেরোয়, আর signed-এ overflow হয় (V = 1). কোন বিপদটি গুরুত্বপূর্ণ, তা জানে শুধু প্রোগ্রাম।

তাই ISA নকশাকারের সামনে প্রশ্ন: carry আর overflow-এর খবর কোথায় রাখবেন? একটি বিশেষ register-এ (flag)? নাকি overflow হলে প্রোগ্রাম থামিয়ে দেবেন (trap)? নাকি কিছুই রাখবেন না, software-কে নিজে বের করে নিতে বলবেন? তিনটি পথই বাস্তবে আছে। আর এই সিদ্ধান্ত থেকেই ঠিক হয় বড় সংখ্যার যোগ, তুলনা আর শাখা কতগুলো instruction-এ হবে।

২ · ISA কীভাবে carry আর overflow জানায় — flag, trap, নাকি কিছুই না

পথ ১: flag — x86 আর ARM

x86-এর প্রায় প্রতিটি গাণিতিক instruction ফলের সাথে status flag লেখে: CF (unsigned carry), OF (signed overflow), ZF, SF. ARM-এর নাম C, V, Z, N; তবে ARM-এ সাধারণ add flag ছোঁয় না — শেষে S লাগানো adds/subs লেখে। Flag-গুলো কীভাবে তৈরি হয় আর বিয়োগের পর x86-এর CF আর ARM-এর C কেন উল্টো অর্থ বহন করে, তা পর্ব ১৩-এর অংশ ৬-এ বিস্তারিত আছে; এখানে আমরা শুধু ব্যবহারটা দেখব। Overflow হলে লাফ দিতে চাইলে একটি instruction-ই যথেষ্ট:

# উদাহরণ — a + b overflow করলে handler-এ লাফ (৩২-বিট int, হাতে লেখা; x86 অংশ Intel syntax-এ)
# x86-64                  # ARM64
add   edi, esi            adds  w0, w0, w1
jo    overflow   # OF=1   b.vs  overflow     # V=1 (signed)
# unsigned হলে:
add   edi, esi            adds  w0, w0, w1
jc    overflow   # CF=1   b.cs  overflow     # C=1 (carry)

পুরোনো x86-এ into (interrupt on overflow) নামে একটি instruction-ও ছিল, যা OF = 1 হলে সরাসরি exception তুলত; ৬৪-বিট মোডে এটি আর বৈধ নয় — কম ব্যবহৃত আরও কয়েকটি instruction-এর সাথে AMD64 নকশায় এটি বাদ পড়ে।

পথ ২: trap — MIPS-এর add বনাম addu

MIPS অন্য পথ নিয়েছিল। এর add, addi আর sub signed overflow হলে নিজে থেকেই একটি overflow trap (exception) তোলে — ফল register-এ লেখাই হয় না, CPU সরাসরি operating system-এর exception handler-এ চলে যায়। আর addu, addiu, subu কখনো trap করে না, শুধু wrap করে। নামের “u” দেখে অনেকে ভাবেন এগুলো unsigned যোগ — আসলে নয়। যোগফলের বিট দুটিতে হুবহু এক; পার্থক্য শুধু trap-এ। এমনকি addiu তার immediate-কে sign-extend করে, অর্থাৎ ঋণাত্মক ধ্রুবকও যোগ করা যায়।

পথ ৩: কিছুই না — RISC-V

RISC-V-এর base ISA-তে (RV32I, RV64I) কোনো flag register নেই, আর কোনো integer instruction overflow-এ trap-ও করে না। add শুধু mod 2³² যোগফল লেখে — ব্যস। Overflow জানতে চাইলে প্রোগ্রাম নিজে এক থেকে তিনটি বাড়তি instruction দিয়ে বের করে নেয় (পরের অংশ)। এমনকি M extension-এর ভাগ instruction-ও শূন্য দিয়ে ভাগে trap করে না, একটি নির্দিষ্ট ফল দেয় (অংশ ৮)।

RISC-V কেন এমন করল? Flag একটি লুকোনো, সবার ভাগের register: প্রায় প্রতিটি instruction সেটি লেখে, তাই pipeline আর out-of-order CPU-কে flag-এর জন্যও নির্ভরতা খুঁজতে আর rename করতে হয় (পর্ব ৩৬, ৪০)। আর trap মানে প্রতিটি যোগকে “হয়তো exception তুলবে” ধরে নিয়ে নিখুঁত (precise) exception-এর ব্যবস্থা রাখা (পর্ব ৩৮)। RISC-V-র নকশাকারদের যুক্তি ছিল, বেশিরভাগ যোগে overflow যাচাই লাগেই না; যেখানে লাগে, সেখানে শাখা-instruction দিয়ে সস্তায় করা যায়। এর দামটা কোথায়, তা অংশ ৪-এ দেখবেন।

৩ · RISC-V-তে overflow ধরা — sltu আর slt-এর কৌশল

RISC-V-এর unprivileged spec-এর integer computational instruction অংশে একটি ব্যাখ্যামূলক টীকা আছে, যেখানে নকশাকাররা নিজেরাই overflow ধরার কয়েকটি sequence দেখিয়েছেন। নিচে সেগুলো প্রায় সেই রূপেই দেওয়া হলো (register-এর নাম ও মন্তব্য আমাদের; spec-এর সাম্প্রতিক সংস্করণে লেখার ধরন একটু ভিন্ন হতে পারে)। সবগুলোর ভিত্তি দুটি তুলনা-instruction: sltu আর slt — set-on-less-than-এর unsigned ও signed রূপ (hardware-এর দিক পর্ব ১৩-এর অংশ ৪-এ)।

# উদাহরণ — RV32I, t0 = t1 + t2

# (ক) unsigned যোগে carry: একটি বাড়তি শাখা
add   t0, t1, t2
bltu  t0, t1, overflow      # sum <u t1  <=>  carry out
#     (carry মান হিসেবে চাইলে: sltu t3, t0, t1)

# (খ) signed যোগ, একটি operand-এর চিহ্ন জানা (যেমন ধনাত্মক immediate)
addi  t0, t1, +imm
blt   t0, t1, overflow      # positive imm, yet sum got smaller

# (গ) সাধারণ signed যোগ: তিনটি বাড়তি instruction
add   t0, t1, t2
slti  t3, t2, 0             # t3 = (t2 < 0)
slt   t4, t0, t1            # t4 = (sum < t1)
bne   t3, t4, overflow      # these two must agree when there is no overflow

কেন sltu-তে carry ধরা পড়ে — প্রমাণ

ধরুন a আর b দুটি ৩২-বিট unsigned সংখ্যা, আর s = (a + b) mod 2³². দুই ক্ষেত্র:

• Carry নেই: s = a + b, আর b ≥ 0, তাই s ≥ a. অর্থাৎ s < a মিথ্যা।
• Carry আছে: s = a + b − 2³². যেহেতু b < 2³², তাই b − 2³² < 0, ফলে s < a সত্য।

সুতরাং carry ⇔ s <_u a (একইভাবে s <_u b). একটি sltu দিয়েই x86-এর CF পাওয়া গেল।

কেন (গ)-এর sequence signed overflow ধরে — প্রমাণ

এখন a, b, s-কে signed ধরুন। Overflow না হলে s = a + b হুবহু, তাই s < a ঠিক তখনই, যখন b < 0 — দুটি তুলনা একমত। Overflow হলে দুটি উপক্ষেত্র: b ≥ 0 হলে (ধনাত্মক overflow, a-ও তখন ধনাত্মক) s = a + b − 2³² < a, অথচ b < 0 মিথ্যা; আর b < 0 হলে (ঋণাত্মক overflow) s = a + b + 2³² > a, অথচ b < 0 সত্য। দুই উপক্ষেত্রেই তুলনা দুটি দ্বিমত। অতএব overflow ⇔ (b < 0) ≠ (s < a) — ঠিক যা slti, slt আর bne পরীক্ষা করে।

আরেকটি প্রচলিত কৌশল সরাসরি পর্ব ০৫-এর চিহ্নের নিয়ম থেকে আসে: “দুটি operand-এর চিহ্ন এক, অথচ ফলের চিহ্ন আলাদা”। বিটের ভাষায়, (s ⊕ a) আর (s ⊕ b) দুটিরই MSB ১ হলে overflow:

# উদাহরণ — XOR কৌশল (signed add overflow), RV32I
add   t0, t1, t2
xor   t3, t0, t1            # sign of sum differs from t1 ?
xor   t4, t0, t2            # sign of sum differs from t2 ?
and   t3, t3, t4
bltz  t3, overflow          # MSB = 1  ->  overflow   (bltz = blt t3, x0)

# বিয়োগ t0 = t1 - t2-এর জন্য spec-ধাঁচের যাচাই (একই যুক্তি, তুলনা উল্টো):
sub   t0, t1, t2
slti  t3, t2, 0
slt   t4, t1, t0            # no overflow: (t1 < t0) exactly when t2 < 0
bne   t3, t4, overflow

নিচের stepper-এ দুটি সীমানার উদাহরণে (ক) আর (গ) একসাথে চলছে — একটিতে শুধু signed overflow, অন্যটিতে শুধু unsigned carry. “পরে” চাপুন:

t1 = 0x7FFFFFFF   (signed  2147483647 = INT_MAX)
t2 = 0x00000001   (signed  1)
add t0, t1, t2
t0 = 0x80000000   (signed -2147483648, unsigned 2147483648)

t0 <u t1 ?   2147483648 < 2147483647 ?  no
t3 = 0   -> no carry
check: 2147483647 + 1 = 2147483648 < 2^32   (fits as unsigned)

slti t3, t2, 0   : 1 < 0 ?            t3 = 0
slt  t4, t0, t1  : -2147483648 < 2147483647 ?  t4 = 1

t3 = 0, t4 = 1  ->  not equal  ->  branch taken: signed overflow
check: 2147483647 + 1 = 2147483648 > INT_MAX

t1 = t2 = 0xFFFFFFFF   (signed -1, unsigned 4294967295)
add  t0, t1, t2   : t0 = 0xFFFFFFFE
sltu t3, t0, t1   : 4294967294 < 4294967295 ?  t3 = 1  -> carry
check: 4294967295 + 4294967295 = 8589934590 >= 2^32

slti t3, t2, 0   : -1 < 0 ?    t3 = 1
slt  t4, t0, t1  : -2 < -1 ?    t4 = 1
bne  t3, t4      : equal  ->  not taken: no signed overflow   (-1 + -1 = -2)

দুটি উদাহরণ দিয়ে নিয়ম প্রমাণ হয় না। নিচের simulator RV32-এর add, sub, slt, sltu, xor, and-কে ৩২-বিট প্যাটার্নে নকল করে (>>> 0 দিয়ে unsigned, | 0 দিয়ে signed চোখ), চারটি কৌশল চালায়, আর ফলকে JavaScript-এর BigInt দিয়ে করা নির্ভুল গণিতের সাথে মেলায় — সীমানার সাতটি জোড়ায় এবং ২,০০,০০০টি এলোমেলো জোড়ায়। Run চাপুন:

// RV32 registers hold 32-bit patterns. u() = unsigned view, s() = signed view.
const u = x => x >>> 0, s = x => x | 0;
const add = (a, b) => u(a + b), sub = (a, b) => u(a - b);
const sltu = (a, b) => +(u(a) < u(b)), slt = (a, b) => +(s(a) < s(b));
const xor = (a, b) => u(a ^ b), and = (a, b) => u(a & b), srli = (a, k) => a >>> k;
function check(t1, t2) {
  const t0 = add(t1, t2);
  const carry = sltu(t0, t1);                          // add; sltu t3, t0, t1
  const ovfSpec = +(slt(t2, 0) !== slt(t0, t1));       // slti t3,t2,0; slt t4,t0,t1; bne
  const ovfXor = srli(and(xor(t0, t1), xor(t0, t2)), 31); // sign of (s^a)&(s^b)
  const d = sub(t1, t2);                               // sub t0, t1, t2
  const subOvf = +(slt(t2, 0) !== slt(t1, d));         // slti; slt t4, t1, t0; bne
  const A = BigInt(s(t1)), B = BigInt(s(t2)), lim = 2n ** 31n;
  const truth = { carry: +(BigInt(u(t1)) + BigInt(u(t2)) >= 2n ** 32n),
    ovf: +(A + B >= lim || A + B < -lim), subOvf: +(A - B >= lim || A - B < -lim) };
  return { t0, carry, ovfSpec, ovfXor, subOvf, truth };
}
const hx = v => "0x" + u(v).toString(16).toUpperCase().padStart(8, "0");
const cases = [[0x7FFFFFFF, 1], [0xFFFFFFFF, 0xFFFFFFFF], [0x80000000, 0x80000000],
  [0x7FFFFFFF, 0x7FFFFFFF], [0x80000000, 0x7FFFFFFF], [0xFFFFFFF0, 0x20], [0, 0x80000000]];
console.log("t1         t2         sum        carry ovf(spec) ovf(xor) subOvf  truth c/o/s");
for (const [a, b] of cases) {
  const r = check(a, b), t = r.truth;
  console.log(`${hx(a)} ${hx(b)} ${hx(r.t0)}   ${r.carry}      ${r.ovfSpec}        ${r.ovfXor}       ${r.subOvf}     ${t.carry}/${t.ovf}/${t.subOvf}`);
}
let seed = 12345, bad = 0, n = 200000;                 // deterministic LCG sweep
const rnd = () => (seed = u(Math.imul(seed, 1664525) + 1013904223));
for (let i = 0; i < n; i++) {
  const r = check(rnd(), rnd()), t = r.truth;
  if (r.carry !== t.carry || r.ovfSpec !== t.ovf || r.ovfXor !== t.ovf || r.subOvf !== t.subOvf) bad++;
}
console.log(`random pairs: ${n}, mismatches with exact BigInt math: ${bad}`);

t1         t2         sum        carry ovf(spec) ovf(xor) subOvf  truth c/o/s
0x7FFFFFFF 0x00000001 0x80000000   0      1        1       0     0/1/0
0xFFFFFFFF 0xFFFFFFFF 0xFFFFFFFE   1      0        0       0     1/0/0
0x80000000 0x80000000 0x00000000   1      1        1       0     1/1/0
0x7FFFFFFF 0x7FFFFFFF 0xFFFFFFFE   0      1        1       0     0/1/0
0x80000000 0x7FFFFFFF 0xFFFFFFFF   0      0        0       1     0/0/1
0xFFFFFFF0 0x00000020 0x00000010   1      0        0       0     1/0/0
0x00000000 0x80000000 0x80000000   0      0        0       1     0/0/1
random pairs: 200000, mismatches with exact BigInt math: 0

৪ · বহু-শব্দের যোগ — ৩২-বিট যন্ত্রে ৬৪ আর ১২৮ বিট

প্রাথমিক বিদ্যালয়ে যেভাবে যোগ শিখেছিলেন — এককের ঘর, তারপর হাতে থাকা ১ নিয়ে দশকের ঘর — বড় সংখ্যার যোগ CPU-তেও ঠিক তা-ই। পার্থক্য শুধু, এক-একটি “ঘর” এখানে একটি পুরো register: ৩২-বিট যন্ত্রে ৩২ বিট, অর্থাৎ ভিত্তি 2³²-এর একটি “অঙ্ক”। এই অঙ্কগুলোকে বলে limb, আর এভাবে register-এর চেয়ে চওড়া সংখ্যার হিসাবকে বলে multi-precision arithmetic. ৩২-বিট CPU-তে C-র uint64_t যোগ, বা ৬৪-বিট CPU-তে ১২৮-বিট যোগ — দুটিই এভাবে হয়।

x86 আর ARM-এ এর জন্য বিশেষ instruction আছে: add with carry. প্রথম limb-এ সাধারণ যোগ, যা carry flag-এ carry রাখে; পরের limb-এ adc, যা দুটি operand-এর সাথে আগের carry-ও যোগ করে আর নতুন carry রেখে যায়। RISC-V-তে carry flag নেই, তাই sltu দিয়ে carry বের করে আলাদা add-এ যোগ করতে হয়:

# উদাহরণ — ৩২-বিট যন্ত্রে uint64_t যোগ (a = hi:lo, b = hi:lo), হাতে লেখা; x86 অংশ Intel syntax-এ
# x86 (32-bit)          # ARM (AArch32)        # RISC-V RV32I (a1:a0 += a3:a2)
add  eax, ecx           adds r0, r0, r2        add   a0, a0, a2    # low halves
adc  edx, ebx           adc  r1, r1, r3        sltu  t0, a0, a2    # carry = new low <u a2
                                               add   a1, a1, a3    # high halves
                                               add   a1, a1, t0    # + carry

লক্ষ করুন, RISC-V-তে sltu তুলনা করে a2-এর সাথে, a0-এর সাথে নয় — কারণ a0 ততক্ষণে নতুন যোগফল দিয়ে মুছে গেছে। অংশ ৩-এর প্রমাণ বলে, s <_u a বা s <_u b — যেকোনোটি দিয়েই carry ধরা যায়। Compiler (যেমন RV32-এর জন্য gcc -O2) uint64_t যোগে প্রায় এই চারটি instruction-ই বানায়, register-এর ক্রম একটু ভিন্ন হতে পারে। এবার একটি সংখ্যা দিয়ে ধাপে ধাপে:

A = 0x00000002_FFFFFFF0  (12884901872)   a1 = 0x00000002   a0 = 0xFFFFFFF0
B = 0x00000001_00000020  ( 4294967328)   a3 = 0x00000001   a2 = 0x00000020

  0xFFFFFFF0
+ 0x00000020
= 0x1_00000010   (33 bits!)
a0 = 0x00000010    (only 32 bits are kept)

a0 <u a2 ?   0x00000010 < 0x00000020 ?  yes
t0 = 1     (the lost 33rd bit, recovered)

a1 = 0x00000002 + 0x00000001 = 0x00000003

a1 = 0x00000003 + 1 = 0x00000004
result a1:a0 = 0x00000004_00000010 = 17179869200
check 12884901872 + 4294967328 = 17179869200   ok

x86 :  add eax, ecx    ; CF = 1
       adc edx, ebx    ; 2 + 1 + CF = 4
ARM :  adds r0, r0, r2 ; C = 1
       adc  r1, r1, r3
RISC-V: 4 instructions, x86/ARM: 2

মাঝের limb-এ দুটি carry হতে পারে

তিন বা তার বেশি limb হলে মাঝের প্রতিটি limb-এ যোগ হয় তিনটি জিনিস: a_i + b_i + আগের carry. RISC-V-তে তখন দুই ধাপে যোগ আর দুবার sltu লাগে: প্রথমে s = a + b (carry c1 = s <_u a), তারপর r = s + c_in (carry c2 = r <_u s), আর নতুন carry = c1 OR c2. দুটি একসাথে ১ হতে পারে না (s-এ wrap হলে s ≤ 2³² − 2, তাই +1-এ আর wrap হয় না), তাই OR-এর বদলে যোগ করলেও চলে। প্রতি মাঝের limb-এ মোট পাঁচটি instruction, x86-এ একটি adc.

হাতে একটি ১২৮-বিট যোগ, চারটি ৩২-বিট limb-এ (limb ০ সবচেয়ে কম গুরুত্বের):

ফল (উপরের limb আগে): 10325477 7A9CBEE0 7EDCBA99 06543210. নিচের C প্রোগ্রাম ঠিক এই যোগটি করে — limb-গুলো uint32_t-এ, carry RISC-V-এর মতো তুলনা দিয়ে — তারপর ফল gcc-র unsigned __int128 (একটি GCC/Clang extension, ৬৪-বিট লক্ষ্যে পাওয়া যায়) দিয়ে করা যোগের সাথে মেলায়। দ্বিতীয় অংশে signed overflow ধরা হয় দুইভাবে: gcc-র __builtin_add_overflow আর অংশ ৩-এর XOR নিয়ম — সব হিসাব unsigned-এ, তাই কোথাও undefined behaviour নেই:

#include <stdio.h>
#include <stdint.h>
#include <limits.h>
typedef unsigned __int128 u128;                     /* gcc extension */
/* r = a + b on 4 x 32-bit limbs (limb 0 = least significant); returns carry */
static uint32_t add128(uint32_t r[4], const uint32_t a[4], const uint32_t b[4]) {
    uint32_t carry = 0;
    for (int i = 0; i < 4; i++) {
        uint32_t s = a[i] + b[i], c1 = s < a[i];     /* wrap, then carry like sltu */
        r[i] = s + carry;
        carry = c1 | (r[i] < s);                     /* second possible carry */
    }
    return carry;
}
static u128 join(const uint32_t x[4]) {
    return ((u128)x[3] << 96) | ((u128)x[2] << 64) | ((u128)x[1] << 32) | x[0];
}
/* sign rule on raw bits: operands agree in sign, the sum does not */
static int xor_rule(uint32_t a, uint32_t b) { uint32_t s = a + b; return (int)(((a ^ s) & (b ^ s)) >> 31); }
int main(void) {
    uint32_t a[4] = {0x76543210, 0xFEDCBA98, 0x89ABCDEF, 0x01234567};
    uint32_t b[4] = {0x90000000, 0x80000000, 0xF0F0F0F0, 0x0F0F0F0F};
    uint32_t m[4] = {~0u, ~0u, ~0u, ~0u}, one[4] = {1, 0, 0, 0}, r[4];
    uint32_t c = add128(r, a, b);
    printf("limbs : %08X %08X %08X %08X  carry %u\n", r[3], r[2], r[1], r[0], c);
    printf("match __int128: %s\n", join(r) == join(a) + join(b) ? "yes" : "no");
    c = add128(r, m, one);
    printf("max+1 : %08X %08X %08X %08X  carry %u\n", r[3], r[2], r[1], r[0], c);
    int t[][2] = {{INT_MAX, 1}, {-1, -1}, {INT_MIN, -1}, {INT_MIN, INT_MIN}, {100, -200}};
    for (int i = 0; i < 5; i++) {
        int s, f = __builtin_add_overflow(t[i][0], t[i][1], &s);
        printf("%11d + %11d: builtin %d, xor rule %d, wrapped %d\n",
               t[i][0], t[i][1], f, xor_rule(t[i][0], t[i][1]), s);
    }
}

limbs : 10325477 7A9CBEE0 7EDCBA99 06543210  carry 0
match __int128: yes
max+1 : 00000000 00000000 00000000 00000000  carry 1
 2147483647 +           1: builtin 1, xor rule 1, wrapped -2147483648
         -1 +          -1: builtin 0, xor rule 0, wrapped -2
-2147483648 +          -1: builtin 1, xor rule 1, wrapped 2147483647
-2147483648 + -2147483648: builtin 1, xor rule 1, wrapped 0
        100 +        -200: builtin 0, xor rule 0, wrapped -100

Bignum — সীমাহীন integer কীভাবে হয়

Python-এ 2**1000 লিখলে ৩০২ অঙ্কের সঠিক সংখ্যা আসে; কোনো overflow নেই। এর রহস্য এই limb-এর হিসাবই। Python-এর int, Java-র BigInteger, আর C-র জন্য বিখ্যাত library GMP — সবাই একটি সংখ্যাকে limb-এর array হিসেবে রাখে, সাথে চিহ্ন আর দৈর্ঘ্য। এমন সংখ্যাকে বলে bignum বা arbitrary-precision integer. দুটি বৈশিষ্ট্য মনে রাখার মতো:

• Limb-এর মাপ: GMP সাধারণত যন্ত্রের পুরো word ব্যবহার করে (৬৪-বিট CPU-তে ৬৪ বিটের limb), আর গতির জন্য যোগ-গুণের ভেতরের লুপ প্রতিটি CPU-র জন্য হাতে লেখা assembly-তে, যেখানে x86-এ adc-এর শিকল চলে। CPython (প্রচলিত Python) সাধারণত ৩০ বিটের “digit” রাখে, প্রতিটি একটি ৩২-বিট শব্দে — ওপরের বাড়তি বিট carry রাখার জায়গা দেয়, আর বহনযোগ্য C কোডে দুটি digit-এর গুণফল ৬৪ বিটে ধরে যায়।
• খরচ বাড়ে দৈর্ঘ্যের সাথে: n-limb যোগে n ধাপ — O(n). তাই Python-এ বিশাল int-এর হিসাব ছোট int-এর চেয়ে অনেক ধীর, আর অসীম নয়: মেমরি শেষ হলে থামে। গুণের দ্রুত পদ্ধতিগুলো (Karatsuba ইত্যাদি) পর্ব ২১-এর আলোচনার সাথে মিলিয়ে পড়তে পারেন।

৫ · Saturating arithmetic — wrap-এর বদলে সীমায় আটকে রাখা

একটি সাদা-কালো ছবির প্রতিটি pixel ০ (কালো) থেকে ২৫৫ (সাদা) — একটি uint8_t. ছবি উজ্জ্বল করতে প্রতিটি pixel-এ ৬০ যোগ করলেন। ২৫০ মানের প্রায়-সাদা pixel-এ 250 + 60 = 310, mod 256-এ 54 — হঠাৎ গাঢ় ধূসর! ছবিতে উজ্জ্বল জায়গায় কালো ছোপ পড়বে। এখানে wrap সম্পূর্ণ ভুল আচরণ; ঠিক আচরণ হলো ২৫৫-এ আটকে যাওয়া। একে বলে saturating arithmetic: ফল সীমা ছাড়ালে সর্বোচ্চ মান, নিচে নামলে সর্বনিম্ন মান।

নিয়ম দুই রকম: unsigned ৮ বিটে সীমা [0, 255], signed ৮ বিটে [−128, 127]. সীমা চেনার উপায় আগের অংশগুলো থেকেই আসে — unsigned যোগে carry হলে ২৫৫, unsigned বিয়োগে borrow হলে ০; signed-এ V = 1 হলে operand-এর চিহ্ন দেখে ১২৭ বা −১২৮. নিচের simulator ৮ বিটের যোগ-বিয়োগ wrap আর saturate দুইভাবে করে, তারপর একটি সারির pixel উজ্জ্বল করে:

// 8-bit wrapping vs saturating arithmetic (signed: -128..127, unsigned: 0..255)
const wrapU = x => ((x % 256) + 256) % 256;
const wrapS = x => { const w = wrapU(x); return w > 127 ? w - 256 : w; };
const clamp = (x, lo, hi) => Math.min(hi, Math.max(lo, x));
const rows = [                     // [kind, a, op, b]
  ["signed", 120, "+", 10], ["signed", -120, "-", 10], ["signed", -100, "+", -50],
  ["signed", 100, "+", 27], ["unsigned", 250, "+", 10], ["unsigned", 5, "-", 10],
  ["unsigned", 200, "-", 50],
];
console.log("kind      expr          exact   wrap    saturate");
for (const [kind, a, op, b] of rows) {
  const exact = op === "+" ? a + b : a - b;
  const w = kind === "signed" ? wrapS(exact) : wrapU(exact);
  const sat = kind === "signed" ? clamp(exact, -128, 127) : clamp(exact, 0, 255);
  console.log(`${kind.padEnd(9)} ${`${a} ${op} ${b}`.padEnd(13)} ${String(exact).padStart(5)}` +
              ` ${String(w).padStart(6)} ${String(sat).padStart(8)}`);
}
// brightness +60 on a row of 8-bit grey pixels (0 = black, 255 = white)
const px = [10, 90, 180, 200, 230, 250];
const fmt = a => a.map(v => String(v).padStart(4)).join("");
console.log("\npixels       :" + fmt(px));
console.log("+60 wrapping :" + fmt(px.map(v => wrapU(v + 60))));
console.log("+60 saturate :" + fmt(px.map(v => clamp(v + 60, 0, 255))));
// associativity is lost: (a + b) - b is no longer a
const a = 120, b = 10;
console.log(`\nsigned (${a} + ${b}) - ${b}: wrap = ${wrapS(wrapS(a + b) - b)}, ` +
            `saturate = ${clamp(clamp(a + b, -128, 127) - b, -128, 127)}`);

kind      expr          exact   wrap    saturate
signed    120 + 10        130   -126      127
signed    -120 - 10      -130    126     -128
signed    -100 + -50     -150    106     -128
signed    100 + 27        127    127      127
unsigned  250 + 10        260      4      255
unsigned  5 - 10           -5    251        0
unsigned  200 - 50        150    150      150

pixels       :  10  90 180 200 230 250
+60 wrapping :  70 150 240   4  34  54
+60 saturate :  70 150 240 255 255 255

signed (120 + 10) - 10: wrap = 120, saturate = 117

কোথায় ব্যবহার হয়? শব্দ (audio) প্রক্রিয়ায় — wrap হলে বিকট “ক্লিক” শোনা যায়, saturation-এ শুধু হালকা clipping; ছবি আর ভিডিওতে; আর DSP chip-এ, যেখানে saturating যোগ বহু দশক ধরে একটি মৌলিক instruction. এর সবচেয়ে বড় ব্যবহার SIMD-এ: x86-এর SSE2-তে paddusb (unsigned saturate) আর paddsb (signed saturate) একসাথে ১৬টি byte যোগ করে; ARM-এর NEON-এ uqadd/sqadd; RISC-V Vector extension-এ vsaddu/vsadd. ARM-এর ৩২-বিট DSP extension-এ scalar qadd-ও আছে। RISC-V-এর base ISA-তে scalar saturating instruction নেই — software-এ তুলনা আর শাখা দিয়ে করতে হয়। SIMD-এর পুরো গল্প পর্ব ৪২-এ (SIMD আর vector).

৬ · Signed বনাম unsigned তুলনা — blt বনাম bltu আর −1-এর ফাঁদ

পর্ব ১৩-এর অংশ ৭-এ দেখেছেন, একই বিয়োগ থেকে signed তুলনা পড়ে N ⊕ V, আর unsigned তুলনা পড়ে borrow; RISC-V-তে এরা আলাদা instruction: blt/bge (signed) আর bltu/bgeu (unsigned). কোনটি বসবে, তা ঠিক করে compiler — C-র type দেখে। আর এখানেই একটি পুরোনো, বিপজ্জনক বাগের জন্ম।

/* উদাহরণ — একটি পরিচিত বাগ */
int i = -1;
size_t n = 10;                  /* sizeof, strlen() ইত্যাদির type */
if (i < n) puts("in range");    /* ছাপে না! */
else       puts("out of range");

C-র usual arithmetic conversions (পর্ব ০৫-এর অংশ ৮) অনুযায়ী signed আর unsigned (সমান বা বড় মাপের) তুলনায় signed-টি unsigned-এ রূপান্তরিত হয়। −1 হয়ে যায় 0xFFFFFFFF… — অর্থাৎ সবচেয়ে বড় সংখ্যা। Compiler তাই বিয়োগ বা signed তুলনা নয়, unsigned তুলনা বসায়:

# উদাহরণ — RV32 (size_t = 32 বিট unsigned), i in a0, n in a1
bltu  a0, a1, in_range       # 0xFFFFFFFF <u 10 ?  false
# signed হলে হতো:  blt a0, a1, in_range   # -1 < 10 ?  true

Hardware কোনো ভুল করেনি; ভুল হয়েছে type-এ। gcc -Wall -Wextra এমন তুলনায় -Wsign-compare warning দেয় — এজন্যই এই কোর্সের প্রতিটি C কোড warning চালু রেখে চালানো হয়। বিপজ্জনক দিকটি উল্টো ক্ষেত্রে: একটি signed দৈর্ঘ্য len যদি “len > MAX হলে বাতিল” পরীক্ষা পেরিয়ে যায় (−1 তো MAX-এর চেয়ে ছোট!), তারপর memcpy(buf, src, len)-এ গিয়ে size_t হয়ে প্রায় ৪৩০ কোটি byte-এর (৩২-বিট size_t-এ; ৬৪-বিটে আরও অনেক বেশি) কপি চায় — buffer overflow. নিরাপদ নিয়ম: দৈর্ঘ্য আর index-এর জন্য শুরু থেকেই size_t, আর বাইরে থেকে আসা signed মানে আগে len < 0 যাচাই।

৭ · Shift দিয়ে গুণ-ভাগ — sra-র floor আর C-র truncation

পর্ব ১৩-এর অংশ ৮-এ barrel shifter-এর circuit দেখেছেন। এবার shift-কে গণিত হিসেবে দেখা যাক, কারণ compiler গুণ-ভাগের বদলে প্রায়ই shift বসায় — গুণ কয়েক cycle নেয়, ভাগ আরও অনেক বেশি, আর shift সাধারণত এক cycle. ব্যয়বহুল কাজকে সস্তা কাজে বদলানোর এই কৌশলকে compiler-এর ভাষায় বলে strength reduction.

• sll k = ×2^k: signed আর unsigned দুটিতেই, mod 2³²-এ। বাঁয়ের বিট বেরিয়ে গেলে ফল wrap করে — গুণের overflow-এর মতোই। (C-তে ঋণাত্মক signed সংখ্যাকে << করা আবার undefined behaviour; unsigned-এ করাই নিরাপদ।)
• srl k = unsigned ÷ 2^k: ভাগফল নিচের দিকে গোল — unsigned-এ যা C-র /-এর সাথে হুবহু এক।
• sra k = floor(x ÷ 2^k): arithmetic shift সবসময় −∞-এর দিকে গোল করে। ধনাত্মক x-এ এটি C-র ভাগের সাথে এক, কিন্তু ঋণাত্মক x-এ নয়: −7 sra 2 = −2, অথচ C-তে −7 / 4 = −1.

কারণ C (C99 থেকে নির্দিষ্টভাবে) ভাগফলকে শূন্যের দিকে গোল করে — একে বলে truncating division. −1.75 শূন্যের দিকে গোল করলে −1, −∞-এর দিকে করলে −2. ঋণাত্মক সংখ্যায় শূন্যের দিকে গোল করা মানে ওপরের দিকে গোল করা (ceiling). তাই compiler-কে sra-র আগে একটি সংশোধন বসাতে হয়:

x >> 31 (arithmetic) ঋণাত্মক x-এ সব বিট ১ (−1), অঋণাত্মকে ০. তার সাথে & (2k − 1) দিলে bias = ঋণাত্মক x-এ 2^k − 1, নাহলে ০. প্রমাণ: m = 2^k আর x = qm + r (0 ≤ r < m) লিখুন। r = 0 হলে (x + m − 1) ÷ m-এর floor = q + floor((m − 1)/m) = q. আর r > 0 হলে = q + 1 + floor((r − 1)/m) = q + 1. দুই ক্ষেত্রেই এটি ceiling(x/m) — ঋণাত্মক x-এর জন্য ঠিক যা truncation চায়। ধনাত্মক x-এ bias ০, তাই সাধারণ floor-ই থাকে।

x = -7 = 0xFFFFFFF9 = 1111 ... 1111 1001
-7 / 4 = -1.75
C wants  -1   (truncate toward zero)
floor is -2

1111 ... 1111 1001   >> 2 (sign bits enter)
1111 ... 1111 1110 = 0xFFFFFFFE = -2
= floor(-1.75)   -> WRONG for C

srai t0, a0, 31 : t0 = 0xFFFFFFFF   (x < 0, all sign bits)
srli t0, t0, 30 : t0 = 0x00000003 = 3 = 2^2 - 1

a0 = -7 + 3 = -4 = 0xFFFFFFFC = 1111 ... 1111 1100

1111 ... 1111 1100 >> 2
1111 ... 1111 1111 = 0xFFFFFFFF = -1   = C's -7 / 4   ok

srai t0, a0, 31 : t0 = 0
srli t0, t0, 30 : bias = 0
7 + 0 = 7,  7 >> 2 = 1 = 7 / 4   ok  (fix-up changes nothing)

বাস্তব compiler কী বানায়? int f(int x) { return x / 4; }-এর জন্য RV32-এ gcc -O2 সাধারণত ঠিক stepper-এর চারটি instruction দেয়, আর x86-64-এ gcc সাধারণত একটি lea দিয়ে x + 3 বানিয়ে cmovns দিয়ে বেছে নেয় (version ও flag-ভেদে সামান্য ভিন্ন হতে পারে; Compiler Explorer-এ নিজে দেখে নিতে পারেন):

# উদাহরণ — int x / 4, gcc -O2 (প্রচলিত রূপ; x86-64 অংশ Intel syntax-এ)
# RISC-V RV32               # x86-64
srai  a5, a0, 31            lea    eax, [rdi+3]     # x + 3
srli  a5, a5, 30            test   edi, edi
add   a0, a5, a0            cmovns eax, edi         # x >= 0 ? x : x + 3
srai  a0, a0, 2             sar    eax, 2
ret                         ret
# unsigned x / 4 হলে দুটিতেই শুধু একটি srli / shr.

নিচের C প্রোগ্রাম কয়েকটি মানে /, >> আর bias কৌশল পাশাপাশি দেখায়, তারপর −১,০০,০০০ থেকে +১,০০,০০০ পর্যন্ত প্রতিটি x-এ k = 1…4-এর জন্য মিলিয়ে গোনে কতবার অমিল হয়। (C-তে ঋণাত্মক signed সংখ্যার >> implementation-defined; gcc নথিভুক্তভাবে একে arithmetic shift হিসেবে করে।)

#include <stdio.h>
#include <stdint.h>
/* gcc defines >> on a negative int as an arithmetic shift (sra/sar) */
static int32_t sra(int32_t x, int k)  { return x >> k; }
static int32_t biased(int32_t x, int k) {           /* what compilers emit */
    int32_t bias = (x >> 31) & ((1 << k) - 1);       /* 2^k - 1 if x < 0, else 0 */
    return (x + bias) >> k;
}
int main(void) {
    int32_t xs[] = {7, -7, -8, -9, -1, -2147483647 - 1};
    printf("          x        x/4       x>>2     biased  x%%4\n");
    for (int i = 0; i < 6; i++) {
        int32_t x = xs[i];
        printf("%11d %10d %10d %10d %5d\n", x, x / 4, sra(x, 2), biased(x, 2), x % 4);
    }
    for (int k = 1; k <= 4; k++) {
        long bad_sra = 0, bad_bias = 0, d = 1L << k;
        for (int32_t x = -100000; x <= 100000; x++) {
            if (sra(x, k) != x / d) bad_sra++;
            if (biased(x, k) != x / d) bad_bias++;
        }
        printf("k=%d (divide by %2ld): x>>k wrong %6ld times, biased wrong %ld\n",
               k, d, bad_sra, bad_bias);
    }
    return 0;
}

          x        x/4       x>>2     biased  x%4
          7          1          1          1     3
         -7         -1         -2         -1    -3
         -8         -2         -2         -2     0
         -9         -2         -3         -2    -1
         -1          0         -1          0    -1
-2147483648 -536870912 -536870912 -536870912     0
k=1 (divide by  2): x>>k wrong  50000 times, biased wrong 0
k=2 (divide by  4): x>>k wrong  75000 times, biased wrong 0
k=3 (divide by  8): x>>k wrong  87500 times, biased wrong 0
k=4 (divide by 16): x>>k wrong  93750 times, biased wrong 0

৮ · ভাগের নিয়ম এক নজরে — C, Python আর hardware

ভাগের circuit (restoring, non-restoring) পর্ব ২২-এ (ভাগ)। এখানে শুধু “ফল কী হওয়া উচিত” — কারণ ভাষাভেদে উত্তর ভিন্ন, আর এক ভাষা থেকে আরেক ভাষায় কোড আনার সময় এখানেই বাগ ঢোকে। সব নিয়মে একটি অভেদ সত্য থাকে: a = (a / b) × b + (a % b). ভাগফল কোন দিকে গোল হয়, তা থেকেই ভাগশেষের চিহ্ন ঠিক হয়।

Python-এর পদ্ধতিকে বলে floor division, আর এতে একটি সুবিধা আছে: x % n সবসময় 0 থেকে n − 1 (n ধনাত্মক হলে) — ঘড়ি, সপ্তাহের দিন বা circular buffer-এর index-এর জন্য ঠিক যা দরকার। C-তে (-1) % 7 হয় −1, তাই “গতকাল কোন বার” হিসাবে ((d - 1) % 7 + 7) % 7 লিখতে হয়। Python-এ (d - 1) % 7-ই যথেষ্ট। লক্ষ করুন, C-তে signed ভাগের shift কৌশলের মতো %-এর জন্যও compiler bias বসায়; Python-এর // সরাসরি sra-র সাথে মেলে।

দুটি বিশেষ ক্ষেত্র, যেখানে ISA-গুলোও আলাদা আচরণ করে:

• শূন্য দিয়ে ভাগ: x86-এর div/idiv একটি divide-error exception তোলে (Linux-এ প্রোগ্রাম সাধারণত SIGFPE পেয়ে বন্ধ হয়)। RISC-V কোনো trap করে না: ভাগফলের সব বিট ১ আর ভাগশেষ = ভাজ্য — শাখা দিয়ে যাচাই software-এর কাজ। ARM64-এ ফল ০, trap নেই। C-তে এটি undefined behaviour.
• INT_MIN / −1: আসল উত্তর +2³¹, যা ৩২ বিটে ধরে না — ভাগেও overflow হয়! x86-এ আবার divide-error; RISC-V-তে ভাগফল INT_MIN (ভাজ্য নিজেই) আর ভাগশেষ ০, কোনো trap নেই। C-তে undefined behaviour.

৯ · বাস্তবে overflow ঠেকানো — checked arithmetic, ভাষার সুবিধা আর লুপের সীমা

Overflow-এর বিখ্যাত দুর্ঘটনাগুলো — Ariane 5 রকেট, YouTube-এর view counter, Year 2038 — পর্ব ০৫-এর অংশ ৯-এ আছে। এখানে প্রশ্ন: আজকের প্রোগ্রামার কী করেন? উত্তর তিন স্তরে।

১. Checked arithmetic — হিসাবের সাথে overflow-এর খবর

যে যোগে overflow হলে ক্ষতি (টাকার অঙ্ক, buffer-এর মাপ, malloc-এর আকার), সেখানে checked arithmetic ব্যবহার করুন — হিসাব আর “overflow হলো কি না” একসাথে।

২. Compiler আর sanitizer দিয়ে পাহারা

C-তে signed overflow undefined behaviour, আর optimizer সেই ধারণায় overflow-যাচাই মুছে দিতে পারে (পর্ব ০৫-এর অংশ ৮-এ উদাহরণ)। পরীক্ষার সময় কাজে লাগে UBSan: -fsanitize=signed-integer-overflow (বা পুরো -fsanitize=undefined) দিয়ে compile করলে চলার সময় overflow ঘটলেই কোন লাইনে, তা জানায়। GCC-র পুরোনো -ftrapv signed যোগ-বিয়োগ-গুণে overflow হলে প্রোগ্রাম থামানোর কথা, কিন্তু বিভিন্ন version-এ এটি অসম্পূর্ণ বা অনির্ভরযোগ্য বলে পরিচিত; আজকাল সাধারণত sanitizer-কেই (দরকারে -fsanitize-trap-সহ) বেশি ভরসাযোগ্য ধরা হয়। আর -fwrapv উল্টো কাজ করে — signed overflow-কে নিয়মমতো wrap বানিয়ে দেয়, ফলে UB আর থাকে না (কিন্তু ভুল ফল ঠিকও হয় না)।

৩. লুপ আর সীমার পরিচিত ফাঁদ

• Unsigned উল্টো গণনা: for (unsigned i = n - 1; i >= 0; i--) কখনো থামে না — unsigned i কখনো ঋণাত্মক হয় না; 0-এর পর 4294967295. নিরাপদ রূপ: for (size_t i = n; i-- > 0; ).
• n − 1 যখন n = 0: for (size_t i = 0; i < n - 1; i++)-এ n = 0 হলে n − 1 হয়ে যায় সবচেয়ে বড় size_t — লুপ কার্যত অসীম, array-র বাইরে পড়া। লিখুন i + 1 < n.
• মাঝের index: binary search-এ mid = (lo + hi) / 2-এ lo + hi signed সীমা ছাড়াতে পারে। ২০০৬ সালে Joshua Bloch একটি বহুল-পঠিত লেখায় দেখান, Java-র standard library-র binary search-সহ বহু বাস্তবায়নে ঠিক এই বাগ বহু বছর লুকিয়ে ছিল — দেখা দেয় শুধু প্রায় ১০৭ কোটির (2³⁰) বেশি উপাদানের array-তে। সমাধান: lo + (hi - lo) / 2.
• গুণে আকার: malloc(count * size)-এ গুণফল wrap করলে ছোট buffer বরাদ্দ হয়, পরে বড় লেখা — নিরাপত্তা-ত্রুটির পরিচিত উৎস। calloc(count, size) বা __builtin_mul_overflow ব্যবহার করুন।

দশমিক হিসাব — BCD আর x86-এর DAA

টাকা-পয়সার হিসাবে binary-র বদলে দশমিক অঙ্কেই হিসাব রাখার একটি পুরোনো ধারা আছে: BCD, যেখানে প্রতিটি দশমিক অঙ্ক ৪ বিটে (পর্ব ০৪-এর অংশ ৯), আর যোগফল ৯ ছাড়ালে +6 সংশোধন (পর্ব ১১-এর BCD adder). 8080 আর 8086 যুগের CPU এই সংশোধন একটি instruction-এ করত: x86-এর DAA (Decimal Adjust after Addition) সাধারণ binary add-এর পর AL register-এর দুটি packed BCD অঙ্ক ঠিক করে দেয়, auxiliary carry flag (AF — নিচের nibble থেকে carry) দেখে। যেমন BCD 0x38 + 0x45: binary যোগফল 0x7D, নিচের nibble D > 9, তাই +6 → 0x83 — অর্থাৎ 38 + 45 = 83. এই পরিবারের (DAA, DAS, AAA, AAS, AAM, AAD) instruction ৬৪-বিট মোডে আর বৈধ নয়। দশমিক hardware অবশ্য হারিয়ে যায়নি: IBM-এর mainframe-এ packed decimal instruction আজও ব্যাংক আর বিমার হিসাবে চলে, আর কিছু IBM POWER প্রসেসরে decimal floating-point unit আছে।

১০ · AI-এর যুগে integer হিসাব

AI টুল overflow-এর সংজ্ঞা ভালো বলে, কিন্তু ISA-র খুঁটিনাটিতে আর সীমানার মানে প্রায়ই হোঁচট খায়। প্রচলিত ভুলগুলো:

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

• ISA স্পষ্ট: x86/ARM-এর flag, MIPS-এর trap আর RISC-V-এর নিয়ম গুলিয়ে ফেলা হয়নি
• সীমানার মান দিয়ে নিজে চালিয়েছি: 0, −1, INT_MAX, INT_MIN, 0x80000000 + 0x80000000
• Carry আর overflow আলাদা করে যাচাই করেছি — একটি থাকলে অন্যটি থাকবেই, এমন ধরে নিইনি
• Shift দিয়ে ভাগে অন্তত একটি ঋণাত্মক, 2^k-এর গুণিতক নয় এমন মান (যেমন −7) চালিয়েছি
• C কোড -Wall -Wextra আর -fsanitize=undefined দিয়ে চালিয়েছি; signed-unsigned তুলনার warning শূন্য
• Compiler কী বানায় তা Compiler Explorer-এ বা gcc -O2 -S দিয়ে নিজে দেখেছি