প্রাইম নাম্বার - বিট-ওয়াইজ সিভ (Prime Number - Bitwise Sieve)

Aug 6, 2013

আগের পর্বঃ প্রাইম নাম্বার - সিভ অফ এরাটস্থেনিজ

আগের পর্বে আমরা প্রাইম নাম্বার জেনারেট করার একটি এফিসিয়েন্ট এলগোরিদম ‘সিভ অফ এরাটস্থেনিজ’ নিয়ে আলোচনা করেছিলাম। তবে এলগোরিদমটিতে আমরা দেখেছি যে অনেক মেমরি অপচয় হয়, যেই মেমরিকে ব্যবহার করে আমরা আরও বেশি রেঞ্জের প্রাইম নাম্বার জেনারেট করতে পারি। এই পর্বে আমরা সেই মেমরির প্রতিটি বিট ব্যবহার করে অপচয় রোধ করার পদ্ধতিটাই দেখবো।

এই পর্বের আলোচনা বোঝার জন্য আগে প্রাইম নাম্বার সম্পর্কিত বেসিক কনসেপ্টগুলো এবং এই এলগোরিদমের মূল রূপটি জানতে হবে। এছাড়াও বিট-ওয়াইজ অপারেটর সমূহের ব্যবহার সম্পর্কে পরিষ্কার ধারণা থাকতে হবে। এইসব বিষয়ের উপর লেখাগুলো হলঃ

১। প্রাইম নাম্বার - বেসিক
২। প্রাইম নাম্বার - সিভ অফ এরাটস্থেনিজ
৩। বিট-ওয়াইজ অপারেটর

আমরা যখন সিভ অফ এরাটস্থেনিজের মাধ্যমে প্রাইম নাম্বার জেনারেট করেছি তখন একটি অ্যারে নিয়েছি যেটির ইন্ডেক্স দিয়ে আমরা নাম্বারটিকে প্রকাশ করেছি এবং সেই ইন্ডেক্সের এলিমেন্টে 0 বা 1 রেখে তা দিয়ে কম্পোজিট বা প্রাইম নির্দেশ করেছি। এই কাজটি করতে আমাদের একটি এলিমেন্টের কেবল একটি মাত্র বিট প্রয়োজন হয়েছে। বাকি সবগুলো বিট শুধু শুধু নষ্ট হয়েছে। এখন আমরা সেই বিটগুলোকেও কাজে লাগাবো।

ধরা যাক আমরা n পর্যন্ত সবগুলো প্রাইম নাম্বার জেনারেট করতে চাই। এর জন্য আমরা int টাইপের একটা অ্যারে নিলাম। অ্যারের সাইজ হতে হবে n+1 । কারণ n সাইজের অ্যারেতে n-1 পর্যন্ত ইন্ডেক্স থাকে। এটা অ্যারের বেসিক কনসেপ্ট। int হল ৩২ বিট মেমরির ডাটা টাইপ। n এর মান যদি 5 হয়, তাহলে 0 থেকে 5 পর্যন্ত প্রাইম জেনারেট করলে অ্যারেটি দেখতে কেমন হবে দেখা যাক।

position                                ...8 7654 3210
prime[0] = 1 = 0000 0000 0000 0000 0000 0000 0000 0001
prime[1] = 1 = 0000 0000 0000 0000 0000 0000 0000 0001
prime[2] = 0 = 0000 0000 0000 0000 0000 0000 0000 0000
prime[3] = 0 = 0000 0000 0000 0000 0000 0000 0000 0000
prime[4] = 1 = 0000 0000 0000 0000 0000 0000 0000 0001
prime[5] = 0 = 0000 0000 0000 0000 0000 0000 0000 0000

এই যে প্রতিটা অ্যারে এলিমেন্টের মধ্যে ৩১টি করে বিট অব্যবহৃত রয়ে যাচ্ছে সেগুলোর প্রতিটিকে আমরা একেকটি প্রাইম নাম্বারের ফ্ল্যাগ (নির্দেশক) হিসেবে ব্যবহার করব। ফলে একটি অ্যারে এলিমেন্টের মাধ্যমে আমরা ৩২টি নাম্বারকে প্রকাশ করতে পারব। অর্থাৎ একই সাইজের অ্যারেতে আমরা আগের রেঞ্জের ৩২ গুণ বেশি পর্যন্ত রেঞ্জের মধ্যে প্রাইম নির্ণয় করতে পারব।

এই কাজটির জন্য আমরা কোন একটি এলিমেন্টের একেবারে ডানের বা প্রথম বিটটিকে ০তম বিট এবং একেবারে বামের বিটকে ৩১তম বিট বলব। প্রথম এলিমেন্ট বা prime[0] তে 0 থেকে 31 পর্যন্ত নাম্বারগুলোর ফ্ল্যাগ থাকবে। দ্বিতীয় এলিমেন্ট বা prime[1] এ 32 থেকে 63 পর্যন্ত নাম্বারগুলোর ফ্ল্যাগ থাকবে এবং এভাবে চলতে থাকবে। এখন তাহলে দেখা যাক n এর মান 5 হলে কিরকম হবে।

position                            ...8 7654 3210
prime[0] = 0000 0000 0000 0000 0000 0000 0001 0011

এখানে আমরা যে কাজটি করব তা হল, সিভ অফ এরাটস্থেনিজে যখন লুপের মধ্যে কোন একটি প্রাইম নাম্বার আসবে তখন সেই নাম্বারটিকে 32 দিয়ে ভাগ করব। ভাগফল যত হবে তত নাম্বার ইন্ডেক্সে নাম্বারটির ফ্ল্যাগ আছে। এখন কোন বিটটি ফ্ল্যাগ হবে সেটির জন্য আমরা নাম্বারটিকে 32 দিয়ে mod করব। ভাগশেষ যেটি হবে সেটিই হল নাম্বারটির ফ্ল্যাগের পজিশন। উদাহরণ দিয়ে দেখা যাক।

আমরা যদি 4 এর ফ্ল্যাগ সেট করতে চাই অথবা দেখতে চাই ফ্ল্যাগটি 1 নাকি 0 তাহলে prime অ্যারের 4/32 = 0 ইন্ডেক্সের এলিমেন্টে যাব এবং 4%32 = 4 নাম্বার বিটটি সেট করব বা চেক করব। একইভাবে যদি 32 এর জন্য করি তাহলে 32/32 = 1 ইন্ডেক্সের এলিমেন্টে যাব এবং 32%32 = 0 নাম্বার বিটটি চেক করব। এভাবে করে আমরা যেকোন নাম্বারের জন্য কাজটি করতে পারি।

কোন একটি নাম্বারের ফ্ল্যাগ সেট করা এবং পরবর্তিতে নাম্বারটি প্রাইম কি প্রাইম না তা জানার জন্য ফ্ল্যাগটি চেক করার জন্য আমরা দুটি ফাংশন ব্যবহার করব। ফাংশন দুটি হলঃ

// n এর position-তম বিটকে 1 সেট করার জন্য
int setBit( int n, int position )
{
    n = n | ( 1 << position );
    return n;
}
// n এর position-তম বিট চেক করার জন্য
bool checkBit( int n, int position )
{
    return n & ( 1 << position );
}

ফাংশনদুটিতে কেবল বিট-ওয়াইজ অপারেটরের কাজ। ফাংশনদুটির কাজ না বুঝলে বিট-ওয়াইজ অপারেটরগুলোর কাজ ভালোমত বুঝতে হবে। এখন কোডের বাকি অংশ খুবই সহজ। সিভ অফ এরাটস্থেনিজে যেখানে আমরা কোন একটা ফ্ল্যাগকে 1 করেছিলাম সেখানে setBit() ব্যবহার করব আর যেখানে ফ্ল্যাগের মান চেক করেছিলাম সেখানে checkBit() ব্যবহার করব!

#define MAX 10001
int prime[MAX];
void primeGenerator( int n ) // n পর্যন্ত প্রাইম বের করব
{
    int x = sqrt( n );
    prime[0] = setBit( prime[0], 0 );
    prime[0] = setBit( prime[0], 1 );
    for( int i = 4; i <= n; i += 2 )
        prime[i/32] = setBit( prime[i/32], i%32 );
    for( int i = 3; i <= x; i += 2 ) {
        if( !checkBit( prime[i/32], i%32 ) {
            for( int j = i+i; j <= n; j += i )
                prime[j/32] = setBit( prime[j/32], j%32 );
        }
    }
    return;
}

এছাড়াও ‘বিট-ওয়াইজ নিয়ে খেলা!’ লেখাটি পড়ে থাকলে জানা যাবে যে আমরা ( i / 32 ) কে লিখতে পারি ( i » 5 ) এবং ( i % 32 ) কে আমরা লিখতে পারি ( i & 31 ), উভয়ক্ষেত্রেই কারণ হল 32 নাম্বারটিকে আমরা 2 এর পাওয়ার হিসেবে লিখতে পারি। 32 = 2^5 । ফলে কোডটিতে ভাগ এবং mod এর অপারেশনগুলো উঠিয়ে দিয়ে এই বিট-ওয়াইজ অপারেশনগুলো ব্যবহার করে আমরা একে আরও এফিসিয়েন্ট করতে পারি।

#define MAX 10001
int prime[MAX];
void primeGenerator( int n ) // n পর্যন্ত প্রাইম বের করব
{
    int x = sqrt( n );
    prime[0] = setBit( prime[0], 0 );
    prime[0] = setBit( prime[0], 1 );
    for( int i = 4; i <= n; i += 2 )
       prime[ i >> 5 ] = setBit( prime[ i >> 5 ], i & 31 );
    for( int i = 3; i <= x; i += 2 ) {
       if( !checkBit( prime[ i >> 5 ], i & 31 ) {
          for( int j = i+i; j <= n; j += i )
             prime[ j >> 5 ] = setBit( prime[ j >> 5 ], j & 31 );
        }
    }
    return;
}

এভাবে আমরা সিভ অফ এরাটস্থেনিজকে আরও অনেকখানি এফিসিয়েন্ট করে তুলতে পারি, মেমরি এবং টাইম উভয়ের দিক থেকে।