RAM মডেল অফ কম্পিউটেশন

The RAM model of computation

৭ মিনিট পড়া সহজ · Beginner Python কোডসহ সম্পূর্ণ বাংলায়

এক নজরে · TL;DR

RAM (Random Access Machine) মডেল হলো একটি সরলীকৃত গণনা মডেল যেখানে ধরে নেওয়া হয় প্রতিটি "মৌলিক" অপারেশন (যোগ, তুলনা, অ্যাসাইনমেন্ট, মেমরি অ্যাক্সেস) নির্দিষ্ট সময়ে ($O(1)$) সম্পন্ন হয় — অপারেন্ডের প্রকৃত আকার নির্বিশেষে।
এই অনুমানের কারণেই আমরা একটি অ্যালগরিদমের গতি "সেকেন্ডে" পরিমাপ না করে "কতগুলো মৌলিক অপারেশন সম্পন্ন হলো" তা গুনে বিশ্লেষণ করতে পারি — এটাই M2-এর অ্যাসিম্পটোটিক অ্যানালাইসিসের ভিত্তি।
বাস্তব হার্ডওয়্যারে এই অনুমান সম্পূর্ণ নিখুঁত নয় — cache hierarchy-এর কারণে মেমরি অ্যাক্সেসের সময় ভিন্ন ভিন্ন হতে পারে, আর Python-এর arbitrary-precision ইন্টিজারে খুব বড় সংখ্যার গুণন প্রকৃতপক্ষে operand-এর আকারের উপর নির্ভর করে ধীর হয়ে যায়।
নিচের কোড সেলে সত্যিকারের সময় মেপে দেখানো হয়েছে — ছোট অপারেন্ডে মৌলিক অপারেশনগুলো একই মাত্রার (comparable) সময় নেয়, কিন্তু অপারেন্ডের আকার অনেক বাড়লে (বড় ইন্টিজার গুণন) এই "O(1)" ধারণা ভেঙে পড়ে।

এই পাঠে যা শিখবেন

RAM মডেল অফ কম্পিউটেশন কী এবং কেন এটি অ্যালগরিদম অ্যানালাইসিসের ভিত্তি
কোন কোন অপারেশনকে "মৌলিক" ($O(1)$) ধরে গণনা করা হয়
বাস্তব হার্ডওয়্যারের সাথে RAM মডেলের অনুমানের পার্থক্য — cache hierarchy ও big-integer arithmetic
একটি সত্যিকারের টাইমিং এক্সপেরিমেন্ট দিয়ে ধারণাটি হাতে-কলমে যাচাই

১ · RAM মডেল কী

M1/L01-এ আমরা দেখেছি অ্যালগরিদম অ্যানালাইসিসের কাজ হলো একটি অ্যালগরিদম ইনপুট বড় হলে কতটা "ধীর" হবে তা গাণিতিকভাবে নির্ণয় করা। কিন্তু এই বিশ্লেষণ করতে হলে প্রথমে ঠিক করতে হবে — আমরা কী গুনছি? একটি নির্দিষ্ট কম্পিউটারে সেকেন্ডে পরিমাপ করলে তা প্রসেসরের গতি, প্রোগ্রামিং ভাষা, কম্পাইলার — সবকিছুর উপর নির্ভর করবে, যা অ্যালগরিদমের নিজস্ব বৈশিষ্ট্য নয়। এই সমস্যা সমাধানের জন্য ব্যবহৃত হয় RAM মডেলRandom Access Machine modelএকটি আদর্শায়িত (idealized) গণনা মডেল যেখানে মেমরির যেকোনো অবস্থানে সমান সময়ে অ্যাক্সেস করা যায়, এবং প্রতিটি মৌলিক অপারেশন ধ্রুব সময়ে সম্পন্ন হয় বলে ধরে নেওয়া হয়।।

RAM মডেলে নিচের অপারেশনগুলোকে "মৌলিক" (basic) ধরা হয়, প্রতিটির খরচ $O(1)$:

গাণিতিক অপারেশন
যোগ, বিয়োগ, গুণ, ভাগ — নির্দিষ্ট আকারের (word-size) সংখ্যার উপর।

তুলনা
দুটি মানের সমতা বা ক্রম পরীক্ষা (==, >, ইত্যাদি)।

অ্যাসাইনমেন্ট
একটি মান কোনো ভ্যারিয়েবলে সংরক্ষণ করা।

মেমরি/অ্যারে অ্যাক্সেস
A[i]-এর মতো ইনডেক্সিং — অ্যারের যেকোনো অবস্থানে সরাসরি, ধ্রুব সময়ে পৌঁছানো যায় (এই কারণেই একে "Random Access" মেশিন বলা হয়)।

RAM মডেল না থাকলে "ধাপ গণনা" করার কোনো সুস্পষ্ট অর্থই থাকত না — এটিই অ্যাসিম্পটোটিক অ্যানালাইসিসের গোপন ভিত্তি।

RAM মডেলে আরও একটি সূক্ষ্ম শর্ত থাকে: প্রতিটি সংখ্যা একটি word-এ ধরে (সাধারণত ইনপুট আকার $n$-এর সাপেক্ষে $O(\log n)$ বিট) — অর্থাৎ ইনপুটের একটি ইনডেক্স বা গণনা রাখার জন্য যথেষ্ট, কিন্তু অসীম বড় সংখ্যা নয়। এই শর্তটিই নিচে ব্যাখ্যা করা big-integer ব্যতিক্রমের মূল কারণ।

২ · কেন এই সরলীকরণ দরকার

RAM মডেলের সবচেয়ে বড় সুবিধা হলো — এটি অ্যালগরিদম অ্যানালাইসিসকে হার্ডওয়্যার-নিরপেক্ষ করে তোলে। একটি অ্যালগরিদম $O(n^2)$ ধাপ নেয় কি না, তা প্রমাণ করার জন্য কোনো নির্দিষ্ট প্রসেসরের ক্লক স্পিড জানার প্রয়োজন নেই — শুধু জানতে হবে অ্যালগরিদমটি কতগুলো মৌলিক অপারেশন সম্পন্ন করে, ইনপুট আকার $n$-এর ফাংশন হিসেবে। এই বিমূর্ততা (abstraction) ছাড়া M2 থেকে শুরু করে এই কোর্সের প্রতিটি অ্যাসিম্পটোটিক দাবিই অর্থহীন হয়ে যেত — কারণ "দ্রুত" বা "ধীর" শব্দগুলো তখন শুধু একটি নির্দিষ্ট মেশিনের জন্যই সত্য হতো, সাধারণভাবে নয়।

৩ · বাস্তব হার্ডওয়্যারের ব্যতিক্রম

RAM মডেল একটি দরকারি সরলীকরণ — একটি নিখুঁত বর্ণনা নয়। বাস্তব হার্ডওয়্যারে দুটি উল্লেখযোগ্য ব্যতিক্রম আছে:

ক্যাভিয়েট ১ · Cache hierarchy

RAM মডেলে ধরে নেওয়া হয় মেমরির যেকোনো অবস্থানে অ্যাক্সেস করতে একই সময় লাগে। বাস্তবে আধুনিক প্রসেসরে একাধিক স্তরের ক্যাশ (L1, L2, L3) থাকে — সম্প্রতি ব্যবহৃত বা কাছাকাছি মেমরি অবস্থানে অ্যাক্সেস (cache hit) দূরের বা অব্যবহৃত অবস্থানে অ্যাক্সেসের (cache miss) চেয়ে বহুগুণ দ্রুত হতে পারে। এই কারণেই দুটো অ্যালগরিদম একই $O(n)$ হলেও, মেমরি অ্যাক্সেস প্যাটার্নের (locality) পার্থক্যের জন্য বাস্তবে একটি অন্যটির চেয়ে লক্ষণীয়ভাবে দ্রুত চলতে পারে — এই কোর্স এই বিষয়ে গভীরে যাবে না, কিন্তু এটি জানা থাকা জরুরি।

ক্যাভিয়েট ২ · Big-integer arithmetic

RAM মডেলে ধরে নেওয়া হয় সংখ্যাগুলো একটি নির্দিষ্ট, সীমিত word-এ ধরে (যেমন ৬৪-বিট)। কিন্তু Python-এর ইন্টিজার arbitrary-precision — যত বড় সংখ্যাই হোক, তা মেমরিতে ধরে রাখা যায়। যখন সংখ্যাগুলো এত বড় হয়ে যায় যে একটি word-এ আর ধরে না (যেমন শত শত ডিজিটের সংখ্যা), তখন গুণন-ভাগের প্রকৃত সময় সংখ্যার digit সংখ্যার উপর নির্ভর করে বাড়তে থাকে — RAM মডেলের "প্রতিটি গাণিতিক অপারেশন $O(1)$" অনুমানটি তখন আর সত্যি থাকে না। নিচের কোড সেলে এটি সত্যিকারের সময় মেপে দেখানো হয়েছে।

৪ · একটি সত্যিকারের টাইমিং এক্সপেরিমেন্ট

নিচের কোডে time.perf_counter() দিয়ে তিনটি "মৌলিক" অপারেশন (যোগ, তুলনা, লিস্ট-ইনডেক্সিং) — প্রতিটি বহুবার পুনরাবৃত্তি করে — কতটা সময় নেয় তা মাপা হয়েছে, তারপর ছোট বনাম অনেক বড় ইন্টিজারের গুণনের সময় তুলনা করা হয়েছে:

Python

import time

def time_repeated(fn, repeats):
    start = time.perf_counter()
    for _ in range(repeats):
        fn()
    return time.perf_counter() - start

REPEATS = 200_000
x, y = 17, 29
arr = list(range(1000))

t_add     = time_repeated(lambda: x + y, REPEATS)
t_compare = time_repeated(lambda: x > y, REPEATS)
t_index   = time_repeated(lambda: arr[500], REPEATS)

print("== ছোট, নির্দিষ্ট আকারের অপারেন্ডে মৌলিক অপারেশন ==")
print(f"{REPEATS:,} বার যোগ:            {t_add:.4f} সে.")
print(f"{REPEATS:,} বার তুলনা:          {t_compare:.4f} সে.")
print(f"{REPEATS:,} বার list ইনডেক্সিং: {t_index:.4f} সে.")
print("তিনটিই একই মাত্রার (order of magnitude) সময় নিচ্ছে -- RAM মডেলের ধারণার সাথে সঙ্গতিপূর্ণ, প্রতিটিই আচরণে O(1)।")

# --- এবার অপারেন্ডের আকার (digit সংখ্যা) অনেক বাড়িয়ে দেখা যাক ---
REPEATS_BIG = 100
small_a, small_b = 10**50, 10**50 + 7
big_a, big_b = 10**20000, 10**20000 + 7

t_mult_small = time_repeated(lambda: small_a * small_b, REPEATS_BIG)
t_mult_big   = time_repeated(lambda: big_a * big_b, REPEATS_BIG)

print("\n== বড় ইন্টিজার গুণন (real-hardware ক্যাভিয়েট) ==")
print(f"৫০-ডিজিট সংখ্যার গুণন ({REPEATS_BIG} বার):      {t_mult_small:.4f} সে.")
print(f"২০,০০০-ডিজিট সংখ্যার গুণন ({REPEATS_BIG} বার):  {t_mult_big:.4f} সে.")
print(f"অনুপাত (বড় / ছোট): {t_mult_big / t_mult_small:.1f}x ধীর")
print("digit সংখ্যা বাড়লে গুণন বাস্তবে আর O(1) থাকে না -- RAM মডেলের 'সব গাণিতিক অপারেশন O(1)' অনুমানটি operand-এর আকার যথেষ্ট বড় হলে ভেঙে পড়ে।")

সঠিক সেকেন্ডের মান হার্ডওয়্যার ও ব্রাউজার-নির্ভর — তাই একটি নির্দিষ্ট মিলিসেকেন্ড সংখ্যাকে সার্বজনীন সত্য হিসেবে ধরা ভুল হবে (এই বিষয়ে CLAUDE.md-এর নীতি অনুসরণ করা হয়েছে)। এর বদলে প্রবণতাটি (trend) লক্ষ্য করুন: প্রথম অংশে যোগ, তুলনা ও ইনডেক্সিং — তিনটিই কাছাকাছি, একই মাত্রার সময় নেয় (কোনোটিই অন্যটির চেয়ে হাজার গুণ ধীর নয়) — এটাই RAM মডেলের "সব মৌলিক অপারেশন O(1)" ধারণার বাস্তব সমর্থন। কিন্তু দ্বিতীয় অংশে, operand-এর digit সংখ্যা ৫০ থেকে ২০,০০০-এ (৪০০ গুণ) বাড়ানোর পর গুণনের সময় উল্লেখযোগ্যভাবে বেড়ে যায় — সাধারণত বহুগুণ ধীর, রান-টু-রান অনুপাত সামান্য ভিন্ন হতে পারে, কিন্তু প্রবণতা সবসময় স্পষ্ট থাকে: বড় অপারেন্ড মানেই ধীর গতি, যা RAM মডেলের আদর্শায়িত অনুমান থেকে একটি বাস্তব বিচ্যুতি।

মূল কথা · Key takeaway

RAM মডেল একটি ইচ্ছাকৃত সরলীকরণ — এটি নিখুঁতভাবে বাস্তব হার্ডওয়্যারকে বর্ণনা করে না, কিন্তু এটি অ্যালগরিদম অ্যানালাইসিসকে ব্যবহারযোগ্য, হার্ডওয়্যার-নিরপেক্ষ ও গাণিতিকভাবে রিগোরাস করে তোলে। এই কোর্সের বাকি সব পাঠে (বিশেষভাবে M2-এর অ্যাসিম্পটোটিক নোটেশন থেকে শুরু করে) আমরা নীরবে এই মডেলটি ধরে নেব — সাধারণ ইনপুট আকারের (যেখানে সংখ্যাগুলো একটি word-এ ধরে) জন্য এটি একটি চমৎকার আনুমানিক বাস্তবতা, যদিও ক্রিপ্টোগ্রাফির মতো বিশেষায়িত ক্ষেত্রে (যেখানে ইচ্ছাকৃতভাবেই অতিকায় সংখ্যা ব্যবহৃত হয়) এই অনুমানটি সরাসরি ভেঙে পড়ে।

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।

প্র ০১ যদি RAM মডেল বাস্তবে ১০০% নিখুঁত না হয় (cache, big-integer ব্যতিক্রম আছে), তাহলে আমরা কেন এখনও এটি ব্যবহার করি?

কারণ এটি প্রায় সব সাধারণ ব্যবহারিক পরিস্থিতিতে (যেখানে সংখ্যাগুলো একটি word-এ ধরে) একটি চমৎকার আনুমানিক বাস্তবতা দেয়, এবং বিনিময়ে অ্যালগরিদম অ্যানালাইসিসকে সরল, হার্ডওয়্যার-নিরপেক্ষ ও গাণিতিকভাবে ট্র্যাক্টেবল করে তোলে। প্রতিটি মডেলই একটি সরলীকরণ — গুরুত্বপূর্ণ হলো মডেলটি কখন ভাঙতে পারে তা জানা (যেমন ক্রিপ্টোগ্রাফি বা cache-sensitive পারফরম্যান্স ইঞ্জিনিয়ারিং-এ), যাতে প্রয়োজনে আরও সূক্ষ্ম মডেল ব্যবহার করা যায়।

প্র ০২ উপরের কোডে REPEATS_BIG-এর মান REPEATS-এর চেয়ে অনেক ছোট (১০০ বনাম ২,০০,০০০) রাখা হয়েছে কেন?

কারণ বড় ইন্টিজারের (২০,০০০ ডিজিট) গুণন প্রতিটি ছোট-অপারেন্ড অপারেশনের চেয়ে ইতিমধ্যেই অনেক ধীর — যদি একই ২,০০,০০০ বার পুনরাবৃত্তি করা হতো, পুরো এক্সপেরিমেন্ট চালাতে অস্বাভাবিক বেশি সময় লাগত। যেহেতু আমরা শুধু অনুপাত (ছোট বনাম বড়) দেখতে চাই, কম পুনরাবৃত্তিতেই সেই প্রবণতা স্পষ্ট বোঝা যায়।

প্র ০৩ M1/L02-এ আমরা দেখেছি সিউডোকোডে ভ্যারিয়েবলের টাইপ ডিক্লেয়ারেশন লেখা হয় না। RAM মডেলের প্রেক্ষাপটে এটি কি কখনো একটি সমস্যা তৈরি করতে পারে?

হ্যাঁ, সূক্ষ্মভাবে। সিউডোকোডে x ← x + 1-এর মতো একটি লাইনকে সবসময় $O(1)$ ধরে নেওয়া হয় — এই কোর্সের প্রায় সব বিশ্লেষণেই এই ধারণা যথেষ্ট নির্ভরযোগ্য, কারণ বেশিরভাগ অ্যালগরিদমে সংখ্যাগুলো ইনপুট আকার $n$-এর তুলনায় ছোট থাকে (word-এ ধরে)। কিন্তু যদি কোনো অ্যালগরিদম ইচ্ছাকৃতভাবে অতিকায় সংখ্যা নিয়ে কাজ করে (যেমন ক্রিপ্টোগ্রাফিক অ্যালগরিদম, যেখানে সংখ্যাগুলো শত শত বিটের), তাহলে "প্রতিটি গাণিতিক অপারেশন O(1)" অনুমানটি বাস্তবসম্মত থাকে না — তখন operand-এর bit-length-কেও বিশ্লেষণে হিসাবে আনতে হয়।

অনুশীলন

চিন্তা করুন: RAM মডেলে A[i]-এর মতো একটি অ্যারে ইনডেক্সিংকে $O(1)$ ধরা হয়। কিন্তু একটি লিংকড লিস্টের $i$-তম এলিমেন্টে পৌঁছাতে কি একই যুক্তি খাটে? কেন বা কেন নয়?

না — লিংকড লিস্টে $i$-তম এলিমেন্টে পৌঁছাতে হলে শুরু থেকে একে একে $i$টি নোড অতিক্রম করতে হয় (কোনো সরাসরি "ঠিকানা গণনা" নেই), তাই এই অপারেশনের খরচ $O(i)$ — ইনপুট-নির্ভর, ধ্রুব নয়। এটাই দেখায় RAM মডেলে "মৌলিক অপারেশন O(1)" ধরে নেওয়াটা ডেটা স্ট্রাকচারের উপরও নির্ভরশীল — অ্যারের র‍্যান্ডম অ্যাক্সেস বৈশিষ্ট্যই একে $O(1)$ করে তোলে, প্রতিটি ডেটা স্ট্রাকচারের এই সুবিধা থাকে না।
পরীক্ষা করুন: উপরের কোড সেলে big_a, big_b-এর ডিজিট সংখ্যা 20000 থেকে বাড়িয়ে 40000 করে (অর্থাৎ 10**40000) Run চাপুন। অনুপাত (t_mult_big / t_mult_small) কেমন বদলাবে বলে আপনার ধারণা?

ডিজিট সংখ্যা দ্বিগুণ করলে অনুপাতটি আরও বাড়বে (আরও বেশি ধীর দেখাবে) — কারণ বড় ইন্টিজার গুণনের সময় digit সংখ্যার সাথে সুপার-লিনিয়ারভাবে বাড়ে (আধুনিক Python বাস্তবায়নে সাধারণত Karatsuba-জাতীয় অ্যালগরিদম ব্যবহৃত হয়, যার জটিলতা প্রায় $O(d^{1.585})$, যেখানে $d$ = digit সংখ্যা — এই সাব-কোয়াড্রাটিক গুণন অ্যালগরিদমগুলো নিয়ে বিস্তারিত এই কোর্সের পরিধির বাইরে)। সঠিক সাংখ্যিক অনুপাত হার্ডওয়্যার-নির্ভর, কিন্তু প্রবণতা — digit বাড়লে সময়ও বাড়ে — সবসময় স্পষ্ট থাকবে।