Algorithm

প্রাইম জেনারেটর (সিভ অফ এরাটোস্হেনেস)

প্রাইম জেনারেটর (সিভ অফ এরাটোস্হেনেস)

অামার সবচেয়ে পছন্দের অ্যালগোরিদম এটি। একটা নির্দিষ্ট রেঞ্জের মধ্যের সব প্রাইম নাম্বার(মৌলিক সংখ্যা) বের করার জন্য সবচেয়ে প্রাচীন এবং ইফিশিনেন্ট পদ্ধতি এটি। এই পোস্টে অামি কিভাবে অ্যালগোরিদম টা ইম্প্লিমেন্ট করতাম এই নিয়ে একটু লেখার চেষ্টা করব।

যাই হোক এটি অাবিষ্কার করেছিলেন তৎকালীন সময়ের স্যামওয়েল টার্লি 🙂 । তিনি ছিলেন প্রাচীন গ্রিক অামলের অালেকজান্দ্রিয়া লাইব্রেরির প্রধান লাইব্রেরিয়ান। তিনি ছিলেন একাধারে একজন বিজ্ঞানী,কবি,লাইব্রেরিয়ান,গণিতবিদ। তাঁর জন্ম খ্রিস্টপূর্ব ২৭৬ এ। এরাটোস্হেনেস নাম্বার থিওরীতে তাঁর এই ছাকনি অাবিস্কারের জন্য বিখ্যাত।

সিভ দেখার অাগে প্রাইম নাম্বার কি জিনিস সেটা অাগে দেখি। বলা হয় ১ এর চেয়ে বড় যে সকল সংখ্যার ১ এবং ঐ সংখ্যা ছাড়া কোন ধনাত্মক গুণনীয়ক(ডিভিসর) নেই তারা হচ্ছে প্রাইম যেমন: ৩,৫,৭,১১ ।

তো এই সংজ্ঞানুষারে প্রাইম নাম্বার বের করার জন্য অামরা কি করতে পারি। একটা সংখ্যা নেব তারপর ২ থেকে ঐ সংখ্যার অাগের সংখ্যা পর্যন্ত সব সংখ্যাগুলো দিয়ে ভাগ করে দেখবো ভাগ যায় কিনা। ভাগ করা না গেলে প্রাইম গেলে নন প্রাইম।

তো একটা নির্দিষ্ট রেঞ্জের মধ্যে এই প্রসেস চালাতে গেলে 0(n^2) টাইম কম্প্লেক্সিটির কারণে অামরা অনেক সময় ব্যয় করে ফেলব। অামাদের অারো ফাস্টার প্রসেসিং করা দরকার।

সিভ অফ এরাটোস্হেনেস যেটা প্রোপোস করে তা হলো : একটা রেঞ্জের মধ্যে প্রথম ধেকে শুরু করে যে কম্পজিট নাম্বার গুলো পাওয়া যাবে তাদের কেটে দিব। কম্পজিট নাম্বার হচ্ছে প্রাইম নাম্বারের গুণিতকগুলো। কাটাকাটি শেষ হলে যে নাম্বারগুলো পড়ে থাকবে তারাই হলো প্রাইম। উইকির এই ইমেজটা উদাহরণ দেবার জন্য অনেক চমৎকার:

sieve-workflow-animation
Sieve of Eratosthenes

 

এখানে যে কাজটা করা হয়েছে : প্রথম যে নাম্বারটা পাবো যা এখনো কাটাকাটি হয়নি তার সব গুণিতকগুলোকে কেটে দিব। এবং ঐ সংখ্যাটাকে প্রাইম হিসেবে স্টোর করবো।

তাহলে এখন কোডটা দেখি:

এখানে প্রথম লুপে অামরা সব জোড় সংখ্যাগুলোকে কেটে দিলাম। জোড় ইন্ডেক্স গুলা 1 বানালাম অার কি। 1হলে বলবো কাটা অার 0 হলে বলবো কাটা হয়নি।

তাহলে দ্বিতীয় লুপ টাতে এবং ইনার লুপে অামরা বিজোড় সংখ্যাগুলো নিচ্ছি অার তার গুণিতকগুলোকে কেটে দিচ্ছি। সবশেষে অামরা চেক করে দেখবো অ্যারের কোন ইন্ডেক্সগুলোতে 0 অাছে। 0 ভাল্যুুওয়ালা ইন্ডেক্সগুলোই প্রাইম।এটা 0(n^2) থেকে অনেক ফাস্টার।

এখন একটা একটা প্রবলেম সল্ভ করি: অামাদের বলা হলো একটা সংখ্যাকে সমান দুটো সংখ্যার গুনফল অাকারে লেখতে হবে  দুটো সংখ্যা কি হবে? উত্তরটা হলো ঐ সংখ্যার বর্গমূল। মানে  a=√a* √a

এখন যদি বলি এইদুটো সংখ্যার যেকোন একটাকে একটু বাড়ায় দেবো তাহলে অবশ্যই অন্যটাকে একটু কমায় দিতে হবে।ব্যাপারটা দাঁড়ালো একটা সংখ্যার গুননীয়ক গুলোর মধ্যে অন্তত একটা অবশ্যই ঐ সংখ্যার বর্গমূলের সমান বা ছোট হবে। হাইস্কুল বা প্রাইমারীতে এই প্রমাণটা  ছিল। এটা কাজে লাগাবো এখন। এখানে অামরা 500 এর নিচের সংখ্যাগুলোর গুননীয়ক চেক করছি তাহলে অামাদের দ্বিতীয় লুপটা √500≈25 পর্যন্ত চালালেই হবে। অলরেডি অনেক ফাস্ট হলো অ্যালগোটা

এখন অাসি ইনারলুপ টাতে এখানে অামরা  a এর প্রথম গুণিতক অর্থাৎ a*2 থেকে শুরু করেছি। কিন্তু অামরা তো 2 এর সব গুনিতক অামদের প্রথম লুপে কেটে এসেছি । মূলত অামদের শুরু করতে হবে a*a থেকে (more fast)। তাহলে a যদি 3 হয় অামদের ইনার লুপ কাটাকাটি করবে 9,12,15,18,21, . . . . .

দেখা যাচ্ছে অাবার অামরা জোড় ইন্ডেক্স এক্সেস করছি(12,18, . . .) কোন দরকার নেই b+=a করার কারণ বিজোড় এর সাথে বিজোড় যোগ করার কারণে জোড় ইন্ডেক্স এক্সেস হচ্ছে। তাহলে কি করবো? বিজোড় এর সাথে a এর প্রথম জোড় গুণিতক ( a*2) যোগ করবো। অারো ফাস্ট হলো ইনার লুপ।

অারো কি একটু ফাস্ট করা যায়? হুমমম যায় ভাই। কম্পিউটার জেনারেল অপারেশন এর চেয়ে বিটওয়াইজ অপারেশনগুলো একটু ফাস্ট করতে পারে । তাই উপরের ফরলুপে a*2 এর জায়গায় অামরা  a<<1 করে a এর ভ্যালু ডাবল করবো।  লেফ্ট শিফ্ট  অপারেশন করলে সংখ্যার ডানে একটা এক্সট্রা 0 এ্যাড হয়। দশমিক নাম্বার সিস্টেমে যেমন সংখ্যার শেষে 0 দিলে সংখ্যা 10 গুণ হয় বাইনারীতে হয় 2 গুণ।

তাহলে অামাদের সুপার ফাস্ট অ্যালগো দাঁড়ালো এমন:

অারো কি একটু ফাস্ট করা যায়? থাক অামাদের কারোরই পড়ার বা লেখার ধৈর্য অাশা করি অবশিষ্ট নেই। শুনছি সিভ অফ অ্যাটকিন্স 0(n) এ কাজ করে ।যাই হোক এটার কম্প্লেক্সিটি  O(n log log n)

এতদূর পর্যন্ত পড়ে থাকলে অনেক অনেক ধন্যবাদ 🙂 ।

Share this post
Be the First to comment.

Leave a Comment

Your email address will not be published. Required fields are marked *