আরবিট্রারি-প্রিসিশন অ্যারিথমেটিক#
আরবিট্রারি-প্রিসিশন অ্যারিথমেটিক, যা “bignum” বা সহজভাবে “লং অ্যারিথমেটিক” নামেও পরিচিত, ডেটা স্ট্রাকচার এবং অ্যালগরিদমের একটি সেট যা স্ট্যান্ডার্ড ডেটা টাইপে ধারণ করা সম্ভব এমন সংখ্যার চেয়ে অনেক বড় সংখ্যা প্রসেস করতে দেয়। এখানে আরবিট্রারি-প্রিসিশন অ্যারিথমেটিকের কয়েকটি ধরন আলোচনা করা হলো।
ক্লাসিক্যাল ইন্টিজার লং অ্যারিথমেটিক#
মূল ধারণাটি হলো সংখ্যাটি কোনো ভিত্তিতে এর “ডিজিট”-এর একটি অ্যারে হিসেবে সংরক্ষিত থাকে। সবচেয়ে বেশি ব্যবহৃত কয়েকটি ভিত্তি হলো দশমিক, দশমিকের ঘাত ($10^4$ বা $10^9$) এবং বাইনারি।
এই ফর্মে সংখ্যার উপর অপারেশনগুলো কলাম যোগ, বিয়োগ, গুণ এবং ভাগের “স্কুল” অ্যালগরিদম ব্যবহার করে সম্পাদিত হয়। দ্রুত গুণ অ্যালগরিদমও ব্যবহার করা সম্ভব: ফাস্ট ফুরিয়ে ট্রান্সফর্ম এবং কারাৎসুবা অ্যালগরিদম।
এখানে আমরা শুধুমাত্র অ-ঋণাত্মক পূর্ণসংখ্যার জন্য লং অ্যারিথমেটিক বর্ণনা করি। ঋণাত্মক পূর্ণসংখ্যা সামলানোর জন্য অ্যালগরিদমগুলো সম্প্রসারিত করতে একটি অতিরিক্ত “ঋণাত্মক সংখ্যা” ফ্ল্যাগ প্রবর্তন ও রক্ষণাবেক্ষণ করতে হবে অথবা টু’জ কম্প্লিমেন্ট ইন্টিজার রিপ্রেজেন্টেশন ব্যবহার করতে হবে।
ডেটা স্ট্রাকচার#
আমরা সংখ্যাগুলো vector<int> হিসেবে সংরক্ষণ করব, যেখানে প্রতিটি এলিমেন্ট সংখ্যার একটি একক “ডিজিট”।
typedef vector<int> lnum;পারফর্মেন্স উন্নত করতে আমরা $10^9$ ভিত্তি হিসেবে ব্যবহার করব, যাতে লং সংখ্যার প্রতিটি “ডিজিট”-এ একসাথে ৯টি দশমিক ডিজিট থাকে।
const int base = 1000*1000*1000;ডিজিটগুলো সর্বনিম্ন থেকে সর্বোচ্চ তাৎপর্যপূর্ণ ক্রমে সংরক্ষিত থাকবে। সকল অপারেশন এমনভাবে ইমপ্লিমেন্ট করা হবে যাতে প্রতিটির পরে ফলাফলে কোনো লিডিং জিরো থাকে না, যতক্ষণ অপারেন্ডগুলোতে কোনো লিডিং জিরো না থাকে। সকল অপারেশন যেগুলোর ফলে লিডিং জিরোসহ সংখ্যা আসতে পারে, তার পরে সেগুলো সরানোর কোড থাকা উচিত। লক্ষ্য করুন যে এই রিপ্রেজেন্টেশনে শূন্য সংখ্যার জন্য দুটি বৈধ নোটেশন আছে: একটি খালি ভেক্টর, এবং একটি একক শূন্য ডিজিটসহ ভেক্টর।
আউটপুট#
লং ইন্টিজার প্রিন্ট করা সবচেয়ে সহজ অপারেশন। প্রথমে আমরা ভেক্টরের শেষ এলিমেন্ট প্রিন্ট করি (ভেক্টর খালি হলে 0), তারপর বাকি এলিমেন্টগুলো প্রয়োজনে লিডিং জিরো দিয়ে প্যাড করে প্রিন্ট করি যাতে সেগুলো ঠিক ৯ ডিজিট দীর্ঘ হয়।
printf ("%d", a.empty() ? 0 : a.back());
for (int i=(int)a.size()-2; i>=0; --i)
printf ("%09d", a[i]);লক্ষ্য করুন যে আমরা a.size() কে ইন্টিজারে কাস্ট করি আনসাইনড ইন্টিজার আন্ডারফ্লো এড়াতে, যদি ভেক্টরে ২টির কম এলিমেন্ট থাকে।
ইনপুট#
একটি লং ইন্টিজার পড়তে, এর নোটেশন একটি string-এ পড়ুন এবং তারপর “ডিজিট”-এ রূপান্তর করুন:
for (int i=(int)s.length(); i>0; i-=9)
if (i < 9)
a.push_back (atoi (s.substr (0, i).c_str()));
else
a.push_back (atoi (s.substr (i-9, 9).c_str()));string-এর পরিবর্তে char-এর অ্যারে ব্যবহার করলে, কোড আরও সংক্ষিপ্ত হবে:
for (int i=(int)strlen(s); i>0; i-=9) {
s[i] = 0;
a.push_back (atoi (i>=9 ? s+i-9 : s));
}ইনপুটে লিডিং জিরো থাকলে, সেগুলো নিম্নরূপে সরানো যায়:
while (a.size() > 1 && a.back() == 0)
a.pop_back();যোগ#
লং ইন্টিজার $a$-কে $b$ দ্বারা বৃদ্ধি করুন এবং ফলাফল $a$-তে সংরক্ষণ করুন:
int carry = 0;
for (size_t i=0; i<max(a.size(),b.size()) || carry; ++i) {
if (i == a.size())
a.push_back (0);
a[i] += carry + (i < b.size() ? b[i] : 0);
carry = a[i] >= base;
if (carry) a[i] -= base;
}বিয়োগ#
লং ইন্টিজার $a$ থেকে $b$ বিয়োগ করুন ($a \ge b$) এবং ফলাফল $a$-তে সংরক্ষণ করুন:
int carry = 0;
for (size_t i=0; i<b.size() || carry; ++i) {
a[i] -= carry + (i < b.size() ? b[i] : 0);
carry = a[i] < 0;
if (carry) a[i] += base;
}
while (a.size() > 1 && a.back() == 0)
a.pop_back();লক্ষ্য করুন যে বিয়োগ সম্পাদনের পর আমরা লিডিং জিরো সরিয়ে ফেলি, যাতে আমাদের প্রেমিসটি বজায় থাকে যে আমাদের লং ইন্টিজারে লিডিং জিরো থাকে না।
শর্ট ইন্টিজার দ্বারা গুণ#
লং ইন্টিজার $a$-কে শর্ট ইন্টিজার $b$ ($b < base$) দ্বারা গুণ করুন এবং ফলাফল $a$-তে সংরক্ষণ করুন:
int carry = 0;
for (size_t i=0; i<a.size() || carry; ++i) {
if (i == a.size())
a.push_back (0);
long long cur = carry + a[i] * 1ll * b;
a[i] = int (cur % base);
carry = int (cur / base);
}
while (a.size() > 1 && a.back() == 0)
a.pop_back();অতিরিক্ত অপটিমাইজেশন: যদি রানটাইম অত্যন্ত গুরুত্বপূর্ণ হয়, তাহলে আপনি দুটি ভাগকে একটি দিয়ে প্রতিস্থাপন করার চেষ্টা করতে পারেন - শুধুমাত্র ভাগের ইন্টিজার ফলাফল (ভেরিয়েবল carry) খুঁজে বের করে এবং তারপর গুণ ব্যবহার করে মডুলো খুঁজে বের করে। এটি সাধারণত কোডকে দ্রুত করে, যদিও নাটকীয়ভাবে নয়।
লং ইন্টিজার দ্বারা গুণ#
লং ইন্টিজার $a$ এবং $b$ গুণ করুন এবং ফলাফল $c$-তে সংরক্ষণ করুন:
lnum c (a.size()+b.size());
for (size_t i=0; i<a.size(); ++i)
for (int j=0, carry=0; j<(int)b.size() || carry; ++j) {
long long cur = c[i+j] + a[i] * 1ll * (j < (int)b.size() ? b[j] : 0) + carry;
c[i+j] = int (cur % base);
carry = int (cur / base);
}
while (c.size() > 1 && c.back() == 0)
c.pop_back();শর্ট ইন্টিজার দ্বারা ভাগ#
লং ইন্টিজার $a$-কে শর্ট ইন্টিজার $b$ ($b < base$) দ্বারা ভাগ করুন, ইন্টিজার ফলাফল $a$-তে এবং ভাগশেষ carry-তে সংরক্ষণ করুন:
int carry = 0;
for (int i=(int)a.size()-1; i>=0; --i) {
long long cur = a[i] + carry * 1ll * base;
a[i] = int (cur / b);
carry = int (cur % b);
}
while (a.size() > 1 && a.back() == 0)
a.pop_back();ফ্যাক্টরাইজেশন রিপ্রেজেন্টেশনের জন্য লং ইন্টিজার অ্যারিথমেটিক#
ধারণাটি হলো পূর্ণসংখ্যাকে এর ফ্যাক্টরাইজেশন হিসেবে, অর্থাৎ এটিকে ভাগ করে এমন মৌলিক সংখ্যাগুলোর ঘাত হিসেবে সংরক্ষণ করা।
এই পদ্ধতিটি ইমপ্লিমেন্ট করা খুব সহজ, এবং গুণ ও ভাগ সহজে (ক্লাসিক্যাল পদ্ধতির চেয়ে অ্যাসিম্পটোটিক্যালি দ্রুত) করতে দেয়, কিন্তু যোগ বা বিয়োগ নয়। ক্লাসিক্যাল পদ্ধতির তুলনায় এটি মেমোরি-এফিশিয়েন্টও।
এই পদ্ধতিটি প্রায়ই অ-মৌলিক সংখ্যা M মডুলোতে গণনার জন্য ব্যবহৃত হয়; এই ক্ষেত্রে একটি সংখ্যা M-এর ভাজকগুলোর ঘাত হিসেবে সংরক্ষিত থাকে যেগুলো সংখ্যাটিকে ভাগ করে, এবং সাথে M মডুলোতে ভাগশেষ।
মৌলিক মডুলোতে লং ইন্টিজার অ্যারিথমেটিক (গার্নার অ্যালগরিদম)#
ধারণাটি হলো মৌলিক সংখ্যার একটি সেট নির্বাচন করা (সাধারণত এগুলো যথেষ্ট ছোট হয় যাতে স্ট্যান্ডার্ড ইন্টিজার ডেটা টাইপে ধারণ করা যায়) এবং একটি পূর্ণসংখ্যাকে সেই প্রতিটি মৌলিক সংখ্যা দ্বারা ভাগের ভাগশেষের ভেক্টর হিসেবে সংরক্ষণ করা।
চায়নিজ রিমেইন্ডার থিওরেম বলে যে এই রিপ্রেজেন্টেশন ০ থেকে এই মৌলিক সংখ্যাগুলোর গুণফল বিয়োগ এক পর্যন্ত যেকোনো সংখ্যা স্বতন্ত্রভাবে পুনরুদ্ধার করতে যথেষ্ট। গার্নার অ্যালগরিদম এই রিপ্রেজেন্টেশন থেকে সংখ্যাটি স্বাভাবিক ইন্টিজারে পুনরুদ্ধার করতে দেয়।
এই পদ্ধতি ক্লাসিক্যাল পদ্ধতির তুলনায় মেমোরি সাশ্রয় করতে দেয় (যদিও সাশ্রয় ফ্যাক্টরাইজেশন রিপ্রেজেন্টেশনের মতো নাটকীয় নয়)। এছাড়াও, এটি মডুলো হিসেবে ব্যবহৃত মৌলিক সংখ্যার সংখ্যার সমানুপাতিক সময়ে দ্রুত যোগ, বিয়োগ এবং গুণ করতে দেয় (ইমপ্লিমেন্টেশনের জন্য চায়নিজ রিমেইন্ডার থিওরেম আর্টিকেল দেখুন)।
ট্রেডঅফ হলো পূর্ণসংখ্যাকে আবার স্বাভাবিক ফর্মে রূপান্তর করা বেশ কষ্টসাধ্য এবং গুণসহ ক্লাসিক্যাল আরবিট্রারি-প্রিসিশন অ্যারিথমেটিক ইমপ্লিমেন্ট করা প্রয়োজন। এছাড়াও, এই পদ্ধতি ভাগ সাপোর্ট করে না।
ভগ্নাংশ আরবিট্রারি-প্রিসিশন অ্যারিথমেটিক#
প্রোগ্রামিং প্রতিযোগিতায় পূর্ণসংখ্যার তুলনায় ভগ্নাংশ কম ঘন ঘন দেখা যায়, এবং ভগ্নাংশের জন্য লং অ্যারিথমেটিক ইমপ্লিমেন্ট করা অনেক বেশি জটিল, তাই প্রোগ্রামিং প্রতিযোগিতায় ভগ্নাংশ লং অ্যারিথমেটিকের শুধুমাত্র একটি ছোট সাবসেট দেখা যায়।
অনূহ্য ভগ্নাংশে অ্যারিথমেটিক#
একটি সংখ্যাকে অনূহ্য ভগ্নাংশ $\frac{a}{b}$ হিসেবে উপস্থাপন করা হয়, যেখানে $a$ এবং $b$ পূর্ণসংখ্যা। ভগ্নাংশের উপর সকল অপারেশন এই ভগ্নাংশগুলোর ইন্টিজার লব এবং হরের উপর অপারেশন হিসেবে উপস্থাপন করা যায়। সাধারণত এর জন্য লব এবং হর সংরক্ষণের জন্য ক্লাসিক্যাল আরবিট্রারি-প্রিসিশন অ্যারিথমেটিক ব্যবহার করা প্রয়োজন, তবে কখনো কখনো বিল্ট-ইন ৬৪-বিট ইন্টিজার ডেটা টাইপ যথেষ্ট হয়।
ফ্লোটিং পয়েন্ট পজিশন আলাদা টাইপ হিসেবে সংরক্ষণ#
কখনো কখনো একটি সমস্যায় ওভারফ্লো বা আন্ডারফ্লোর অনুমতি না দিয়ে অত্যন্ত ছোট বা অত্যন্ত বড় সংখ্যা হ্যান্ডেল করা প্রয়োজন। বিল্ট-ইন double ডেটা টাইপ ৮-১০ বাইট ব্যবহার করে এবং $[-308; 308]$ রেঞ্জে এক্সপোনেন্টের মান অনুমোদন করে, যা কখনো কখনো অপর্যাপ্ত হতে পারে।
পদ্ধতিটি খুব সরল: একটি আলাদা ইন্টিজার ভেরিয়েবল এক্সপোনেন্টের মান সংরক্ষণ করতে ব্যবহৃত হয়, এবং প্রতিটি অপারেশনের পর ফ্লোটিং-পয়েন্ট সংখ্যাটি নরমালাইজ করা হয়, অর্থাৎ এক্সপোনেন্ট সামঞ্জস্য করে $[0.1; 1)$ ব্যবধানে ফিরিয়ে আনা হয়।
দুটি এই ধরনের সংখ্যা গুণ বা ভাগ করার সময়, তাদের এক্সপোনেন্ট যথাক্রমে যোগ বা বিয়োগ করতে হয়। সংখ্যাগুলো যোগ বা বিয়োগ করার সময়, প্রথমে এক্সপোনেন্ট মানের পার্থক্যের সমান ঘাতে ১০ দ্বারা গুণ করে তাদের সাধারণ এক্সপোনেন্টে আনতে হয়।
একটি শেষ কথা, এক্সপোনেন্ট ভিত্তি ১০ হতে হবে না। ফ্লোটিং-পয়েন্ট সংখ্যার অভ্যন্তরীণ রিপ্রেজেন্টেশনের উপর ভিত্তি করে, এক্সপোনেন্ট ভিত্তি হিসেবে ২ ব্যবহার করা সবচেয়ে যুক্তিসঙ্গত।