বিটওয়াইজ সিভ(Bitwise Sieve)

আমরা যদি int টাইপের একটি 0 নেই তাহলে এতে থাকবে 32 টি শূন্য। যেহেতু int চার বাইট এবং এক বাইট সমান আঁট বিট, তাহলে 4 X 8 = 32 বিট। 

এখন, 32 টি বিট থেকে যদি প্রথম বিট কে 1 করে দেই তাহলে হবে 1। এরপর দ্বিতীয় বিট কেও 1 করে দিলাম তাহলে হবে 3। নিচে একটু ভালো করে দেখে নেই।

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 = 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 = 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 = 3

কোন এক বিচিত্র কারণে আমার মন বললো তৃতীয় এবং চতুর্থ বিট 0 ই থাকুক কিন্তু পঞ্চম বিট কে 1 করে দিব। তাহলে এখন,

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 = 19
আবার ষষ্ঠ বিট 0 রেখে সপ্তম বিট 1 করে দিলে,
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 = 83
আবার অষ্টম বিট কে 0 রেখে নবম বিট কে 1 করে দিলে,
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 1 = 339

এবার আমরা প্রথম নয়টি বিট থেকে সেই বিটের পজিশন গুলো নিয়ে আলাদা করব যারা 0। তবে পজিশনের নাম্বার দেওয়া শুরু করব শূন্য থেকে। তাহলে 0 ও 1 পজিশনের বিটে যেহেতু 1 আছে তাই এই দুটি নিব না কিন্তু 2 ও 3 তম পজিশনে যেহেতু 1 নেই তাই এই দুটি আলাদা করে নিলাম। এবার 4 তম বিটে 1 আছে তাই নিব না তবে 5 তম বিটে 0 আছে তাই এটি নিব। এখন পজিশন গুলো হবে 2 3 5। আবার 6 তম বিটে 1 আছে কিন্তু 7 তম বিটে 1 নেই তাই এখন পজিশন গুলো হবে 2 3 5 7। 8 তম বিটে 1 আছে তাই নিব না আর যেহেতু বলেছিলাম প্রথম 9 টি বিট থেকে নিব। যেহেতু 0 থেকে 8 পর্যন্ত 9 টি বিট তাই আমাদের কাজ শেষ। কিন্তু, আমরা যে পজিশন গুলো পেলাম সেগুলো ভালো করে দেখলে দেখা যাবে আসলে এগুলো প্রাইম নাম্বার। 339 কে বাইনারি তে প্রকাশ করে আমরা প্রথম চারটি প্রাইম পেতে পারি।

উপরের বিষয় টি যদি আপনি ধরতে পারেন তাহলে আপনি বিটওয়াইজ সিভ প্রায় শিখে ফেলেছেন। এখন, সামনে যা দেখব তার জন্য দুটি বিষয় জেনে রাখা আবশ্যক, বিটওয়াইজ অপারেটর ও ইরাটোস থেনিসের সিভ(Sieve of Eratosthenes)।

এখন আসি আসল বিষয়ে। আমরা সাধারণ সিভ অ্যালগরিদমে মার্ক করার জন্য int বা bool টাইপের ডাটা নিয়ে কাজ করি। একটি নাম্বার প্রাইম কিনা তা জানার জন্য আমরা আসলে 32 টি বিট বা 8 টি বিট ব্যবহার করতেছি। কিন্তু উপরে আমরা দেখেছি 1 টি বিট দিয়েই আসলে একটি নাম্বার প্রাইম কিনা তা বলে দিতে পারি। সুতরাং একটি নাম্বারের জন্য একটি int নিয়ে 32 টি বিটের মাঝে বাকি 31 টি বিটের কোন ব্যবহার করতেছি না বা, bool টাইপ নিলে 8 টি বিটের মাঝে বাকি 7 টি বিটের কোন ব্যবহার করতেছি না। 

সুতরাং আমরা যদি একটি int এর 32 টি বিটকেই কাজে লাগাতে পারি তাহলে, একটি int দিয়ে 32 টি নাম্বার চেক করতে পারি প্রাইম কিনা। আবার দুইটি int দিয়ে 64 টি নাম্বার দেখতে পারি প্রাইম কিনা। একই ভাবে আমরা n টি নাম্বার চেক করার জন্য n/32 টি int নিয়েই কাজ চালিয়ে নিতে পারি। মানে মেমোরি কম লাগবে 32 ভাগের 31 ভাগ। 

এখন তাহলে কোড দেখার পালা। তার আগে আমি আশা করছি নিজেই একবার চেষ্টা করে দেখবেন কোড দেখার আগে। বিটওয়াইজ অপারেটর থেকে দেখেছি একটি বিট কীভাবে 0 থাকলে 1 করতে হয়। আরেকটি কাজ হচ্ছে যদি id তম পজিশনে থাকি তাহলে mark অ্যারের id/32 তম পজিশনের ভ্যালুর 32 টি বিট কে ব্যবহার করব আর ভ্যালুটির কত তম পজিশনে আছি তা জানব id%32 দিয়ে। id = 35 যদি হয় তাহলে id/32=1 মানে দ্বিতীয় int এ আছি এবং id%32=3 মানে চতুর্থ পজিশনের বিট কে দেখব।

const int N = 1e3; int mark[N/32 + 1]; bool check(int x, int p) {   /// here x as mark[i/32] and check p-th position is 1 or 0 in x   return x & (1<<p); } int ON(int x, int p) {   /// here x as mark[i/32] and make 0 into 1 in p-th position in x   return x | (1<<p); } void bit_sieve() {   /// marked 0 and 1 as not prime   mark[0] = 3;   /// marked multiple of 2 as not prime   for (int i = 4;i <= N;i += 2) {     mark[i/32] = ON(mark[i/32], i%32);   }   int lim = sqrt(N);   for (int i = 3;i <= lim;i += 2) {     if (check(mark[i/32], i%32) == false) {       // marked multiple of i as not prime       for (int j = i*i;j <= N;j += i+i){         mark[j/32] = ON(mark[j/32], j%32);       }     }   } } int main() {   bit_sieve();   for (int i = 0;i <= N;i++) {     if (check(mark[i/32], i%32)==false) {       cout << i << '\n';     }   }   return 0; }

check(); ফাংশন টি তে দেখতেছি mark অ্যারের id/32 পজিশনের ভ্যালুর id%32 পজিশনের বিট 0 নাকি 1। ON(); ফাংশন mark অ্যারের id/32 তম ভ্যালুর id%32 তম পজিশনের বিট কে 1 করে দিবে। bit_sieve(); ফাংশনের প্রথমেই mark[0] তে 3 বসানোর কারণ হয়ত বুঝে গেছেন। 0 আর 1 ত প্রাইম নয় আর এই দুটিকে লুপের ভিতরেও কিছু করছি না তাই প্রথম int এর প্রথম দুইটি বিটে 1 1 বসিয়ে আগেই মার্ক করে রাখলাম এই দুটি প্রাইম নয়। বাকি কাজ গুলো সাধারণ সিভের মতই প্রায়। 

যেহেতু, id/32 আর id>>5 একই এবং id%32 আর id&31 একই তাই আমরা / এবং % ব্যবহার না করে >> এবং & এই বিটওয়াইজ অপারেটরগুলোই ব্যবহার করতে পারি। কারণ, আমরা জেনেছি বিটওয়াইজ অপারেটর গুলো অ্যারিথমেটিক অপারেটর গুলোর থেকে দ্রুত কাজ করতে পারে।

const int N = 1e3; int mark[(N>>5) + 1]; bool check(int x, int p) {   return x & (1<<p); } int ON(int x, int p) {   return x | (1<<p); } void bit_sieve() {   mark[0] = 3;   for (int i = 4;i <= N;i += 2) {     mark[(i>>5)] = ON(mark[(i>>5)], i&31);   }   int lim = sqrt(N);   for (int i = 3;i <= lim;i += 2) {     if (check(mark[(i>>5)], i&31) == false) {       for (int j = i*i;j <= N;j += i+i){         mark[(j>>5)] = ON(mark[(j>>5)], i&31);       }     }   } } int main() {   bit_sieve();   for (int i = 0;i <= N;i++) {     if (check(mark[(i>>5)], i&31)==false) {       cout << i << '\n';     }   }   return 0; }

বিটওয়াইজ সিভ দিয়ে আপনি প্রায় 100000000 পর্যন্ত প্রাইম নাম্বার বের করে ফেলতে পারবেন। আর এটি সাধারণ সিভের থেকে সময় ও মেমোরি কিছু কম নিবে। যদি কোন বিষয় বুঝতে সমস্যা হয় তাহলে নির্দ্বিধায় কমেন্ট করতে পারেন।

এই বিষয়ে আরো টিউটোরিয়াল।
টিউটোরিয়াল ১
টিউটোরিয়াল ২