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

Standard

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

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

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

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

আমরা যখন সিভ অফ এরাটস্থেনিজের মাধ্যমে প্রাইম নাম্বার জেনারেট করেছি তখন একটি অ্যারে নিয়েছি যেটির ইন্ডেক্স দিয়ে আমরা নাম্বারটিকে প্রকাশ করেছি এবং সেই ইন্ডেক্সের এলিমেন্টে 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 নাম্বার বিটটি চেক করব। এভাবে করে আমরা যেকোন নাম্বারের জন্য কাজটি করতে পারি।

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

[code language=”cpp”]
// 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 );
}
[/code]

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

[code language=”cpp”]
#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;
}
[/code]

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

[code language=”cpp”]
#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;
}
[/code]

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

  • অনিন্দ্য একটা ভুল মনে হয় লক্ষ্য করনি।
    for( int i = 4; i > 5 ] = setBit( prime[ i >> 5 ], i & 31 );
    এটা না হয়ে এই code টা হবে।
    for( int i = 4; i > 5 ] = setBit( prime[ i >> 5 ], i & 31 );

  • for( int i = 4; i > 5 ] = setBit( prime[ i >> 5 ], i & 31 );
    এর পরিবর্তে হবে,
    for( int i = 4; i > 5 ] = setBit( prime[ i >> 5 ], i & 31 );

    • দুঃখিত আপনার কমেন্টটি পরিষ্কার বোঝা যাচ্ছে না। তবে আমার কোডে একটা ভুল ছিল সেটি ঠিক করে দিয়েছি। আপনি সেটিই বুঝিয়ে থাকলে তার জন্য ধন্যবাদ। 🙂

  • int prime[MAX];
    এখানে MAX কত?
    পাল ভাইয়া, আমি যদি n limit পর্যন্ত প্রাইম চেক করতে চাই, তাহলে আমার n/32+1 টা array লাগবে। কিন্তু , কেন আমি MAX নেবো? যদিও আমি ওই ভাবে চেষ্টা করে সঠিক সংখ্যক প্রাইম নাম্বার পাই নাই। আসা করি , আমাকে ক্লিয়ার করবেন…।। আপনাকে অনেক ধন্যবাদ ভাইয়া। অনেক ভালো করে লিখছেন…।। অনেক অনেক শুভ কামনা…

    • আমি বুঝতে পারছি না যে, যে খানে আমার মেমোরি কম লাগার কথা সেখানে তো মেমোরি কমতেছে না…।।

      • MAX এর তো কোন নির্দিষ্ট মান নেই! তোমার যত পর্যন্ত প্রাইম বের করা দরকার তার জন্য MAX এর মান যত লাগবে তুমি তত ঠিক করে নিবে। তোমার যদি n পর্যন্ত প্রাইম বের করতে হয় তাহলে (n/32)+1 টা এলিমেন্টের অ্যারে লাগবে। তখন তুমি MAX এর মান ধরবে (n/32)+1। আমি কোড রান করে দেখলাম সঠিক সংখ্যক প্রাইম পেয়েছে। তুমি হয়তো অন্য কোথাও ভুল করেছ।

  • Habib

    MAX=(n+1)/32

    n=11;

    ei ta diye apni n porjonto prime print korle dekhben missing thake….

    • এখানে MAX = (n/32)+1 হবে।

      আর n = 11 দিলে তো আমি কোন প্রাইম বাদ দেখছি না। 2, 3, 5, 7 এবং 11 সবগুলোই এসেছে।

      তুমি অন্য কোথাও ভুল করেছ।

      • Habib

        Give your code please.

  • দাদা এই সিভ কে কি segmented seieve বলা যায় ??

    • না এটা সেগমেন্টেড সিভ না। সেগমেন্টেড সিভ হচ্ছে কোন একটা রেঞ্জের মধ্যে সবগুলা সিভ বের করা। যেমন [১০০০, ২০০০] রেঞ্জের মধ্যে যদি সব প্রাইম বের করতে হয় সেটা হবে সেগমেন্টেড সিভ।

  • Riaz uddin

    please give a post about segmented seive.

  • kiamot

    খুব ভালো লাগল , তবে আমার বুজতে কষ্ট হছে । বিশেষ করে Number Theory ~!

    • শুধু একটা লেখা পরে বুঝতে কষ্ট হবে। এই ধরনের অনেকের লেখা পড়তে হবে। বই পড়তে হবে। একেক জায়গায় একেক ভাষায় লেখা থাকবে। একেকভাবে বোঝানো থাকবে। সবকিছু মিলিয়ে কনসেপ্ট ক্লিয়ার হবে।

  • 2 power 32 পর্যন্ত প্রাইম কি এটা দিয়ে বের করা যাবে??

    • 2^31 পর্যন্ত যাবে।