আসসালামু আলাইকুম! অনেক অনেক দিন পর গুহা থেকে বেরোলাম আমি সাদমান সাকিব। গুহা থেকে বের হওয়ার একটা ছবি দেখে আসিঃ
গুহা থেকে বেরিয়ে আজ আমি আমার অন্যতম প্রিয় বিষয়বস্তু কম্পিউটার প্রোগ্রামিং নিয়ে লিখা শুরু করে দিবো। টপিকটা হচ্ছে, একটা সংখ্যাকে এর n-তম ঘাতে তুলে ফেলা! খুবই সহজ কাজ! আমরা এই সহজ কাজটাকে প্রথমে আমাদের জন্য সহজ করে লিখবো,তারপর কম্পিউটারের জন্যে সহজ করে লিখবো।
১) আমাদের জন্য সহজ করেঃ
তোমার কাছে একটি সংখ্যা দেয়া আছে মনে করো “a”। তোমাকে ” a^n ” বের করতে হবে। সবচেয়ে সহজ উপায় কি হতে পারে?
উত্তরঃmath.h এ যে pow() ফাংশন আছে,তার ব্যবহার!
pow(a,n) লিখে ফেললেই কাজ শেষ। সমস্যা বাঁধে গিয়ে “Actual” মানের সাথে এই pow() ফাংশন থেকে জেনারেটেড রেজাল্ট এর Error নিয়ে। ধরো,তুমি 5^2 এই ফাংশনের সাহায্যে বের করলে। তুমি যদি এখন রেজাল্টটাকে কয়েক দশমিক ঘর পর্যন্ত প্রিন্ট করে দেখো,তাহলে মেশিনভেদে আউটপুট পাবে অনেকটা এমনঃ
25.000000000…..000001
যারা জানো না,pow() ফাংশনের রিটার্ন টাইপ কিন্তু ফ্লোট ( float ) !
তাই আমরা নিজেদের মত করে একটা ফাংশন বানিয়ে নিবো,যার রিটার্ন টাইপ হবে ইন্টিজার ( integer ).
ফাংশনটার প্রোটোটাইপঃ
১) ইনপুট হিসেবে নিবে a এবং n
২) a কে n বার নিজেদের মধ্যে একটা লুপ ঘুড়িয়ে গুণ করে দিবে।
৩) গুণফলটাকে রিটার্ন করে দিবে।
টাইম কমপ্লেক্সিটিঃ
যেহেতু লুপটা 1 থেকে n পর্যন্ত ঘুরছে,আর প্রতিটা গুণ ধরে নেয়া যায় কন্সট্যান্ট টাইমে হচ্ছে,তাই এই গুণ করার লুপটা O(n) সময় নিবে।
ফাংশন কোড (সি++) ঃ
|
1 2 3 4 5 6 7 8 9 |
int power(int a,int n) { int res=1; while(n--) { res=res*a; } return res; } |
খুব সহজ কোড। চমৎকার ভাবে কাজও করবে।
২) কম্পিউটারের জন্য সহজ করেঃ
আমরা উপরের অংশে দেখলাম,আমাদের জন্য লিখতে সহজ একটা পাওয়ার ফাংশন,যার কার্যকারিতা যেমনই হোক না কেন,লিখাটা বেশ সোজা! তবে “লিখতে সোজা” কোড দিয়ে কি আর অপেক্ষাকৃত কঠিন বা সময়সাপেক্ষ কাজ করাটা বুদ্ধিমানের কাজ? অবশ্যই না! তাই আমরা এখন আমাদের জন্য “কিছুটা” কঠিন,কিন্তু Execute করতে কম্পিউটারের জন্য বেশ সহজ,সময় সাশ্রয়ী একটি পদ্ধতি দেখে আসবো,যার নাম এক্সপনেনসিয়েশন!
ধরে নাও,তোমাকে আমি 5^20 বের করতে বললাম। উপরের ফাংশনে 2০টা লুপ ঘুরে রেজাল্ট জেনারেট করে দিবে। কিন্তু 2০টা লুপ আমার কনটেস্টের জন্য অনেক কস্টলি(!)। কিভাবে এটাকে আরো দ্রুততম সময়ে করা যায়?
একটা ছোট্ট গ্রাফ/রিকারশন দেখে আসিঃ
ব্যাপারটা আসলে কঠিন কিছু না। আমাকে যদি বলা হয় 5^100 = ? আমি বলবো 5^100 = 5^50 * 5^50
আমাকে যদি বলা হয় “5^50 এর মান তো x , তাহলে 5^100 এর মান কত?”
আমি বলবো,”আরে,এ তো সোজা! x * x ই হচ্ছে 5^100 “
তার মানে দেখো,তুমি যদি 5^50 এর মান আগে থেকেই জানো,তোমার কি আর বেশি কিছু দরকার হচ্ছে? তুমি কি তোমার জানা মানটাই নিজেদের মাঝে একবার গুণ করে উত্তর বলে দিতে পারছো না?
এবার 5^50 = ?
সোজা, 5^50 = 5^25 * 5^25
5^25 = ?
5^25 = 5 * (5^24) ( কেননা,তুমি ২৫ কে সমান দুইভাগে ভাগ করতে পারবে না )
এভাবে যেতে যেতে একদম 5^1 পর্যন্ত চলে যাও,যার মান 5।
5^20 এর জন্যে আমাদের এই এলগরিদমটা কিভাবে রেজাল্ট জেনারেট করে,তা দেখে আসিঃ
খেয়াল করে দেখো,এখানে হিসাবটা আগের চাইতে অনেক অনেক কমে গিয়েছে! একেবারে নিচে দেখো,5^1 হচ্ছে তোমার বেইজ কেইস! ওখান থেকে একবার বের করলে 5^2,সেখান থেকে একবার ক্যালকুলেট করা হলো 5^4 । সেখান থেকে 5^5 ক্যালকুলেট করা হলো একবার , সেখান থেকে 5^10 ক্যালকুলেট করা হলো একবার । সেখান থেকে,5^20 ক্যালকুলেট করা হলো, একবার।
দেখো তো, “একবার” লিখাটা কয়বার আছে? ঠিকঠাকমত গুণে দেখলে উত্তরটা আসবে ” ৫ বার ”
আগের ফাংশনে এই কাজটা করতে কাজ করতে হত ২০ বার,আর এখানে ৫ বার। ২ ভিত্তিক log(20) = 4.32 বা প্রায় ৫
Fast enough,isn’t it?
ফাংশনটার প্রোটোটাইপঃ
১) ইনপুট নিবে a এবং n
২) n যদি জোড় হয়,তাহলে a^(n/2) ক্যালকুলেট করে,সেটাকে একটা ভ্যারিয়বলে স্টোর করবে। তারপর রিটার্ন করবে ভ্যারিয়বল*ভ্যারিয়বল।
৩) বিজোড় হলে রিটার্ন করবে a*a^(n-1)
৪) n==1 হলে , রিটার্ন করবে a.
টাইম কমপ্লেক্সিটিঃ
যেহেতু প্রতিটা ফাংশন থেকে দু’টো করে কাজ তৈরি হয়,কিন্তু এক্সিকিউট করতে হয় কেবল “একটা” , তাই প্রতি দু’টো কাজ থেকে একটি কাজ বাদ পরে যাচ্ছে। তাই টাইম কমপ্লেক্সিটি দাঁড়াচ্ছে O(log(n)). [এখানে লগের ভিত্তি ২]
ফাংশন কোড (সি++) ঃ
|
1 2 3 4 5 6 7 8 9 10 11 |
int power(int a,int n) { if(n==1) return a; if(n%2==1) return a*power(a,n-1); int temp; temp=power(a,n/2); return temp*temp; } |
৩) কনটেস্ট্যান্টদের জন্য ( ফাস্ট এক্সপনেনসিয়েশন ):
রিকার্শন এক অদ্ভূত যাদুর নাম। কিভাবে কিভাবে যেন একটা ফাংশন লিখে ফেললে , ভিতর থেকে ঘুরিয়ে পেঁচিয়ে কাজ-টাজ করে আউটপুট দিয়ে দেয়! তবে এর একটা ড্র-ব্যাক হচ্ছে,এটা স্লো। হ্যা,লুপের চাইতে রিকার্শন বেশ স্লো। কারণ এটি কম্পিউটারের মেমরি থেকে একটা অংশ নিয়ে স্ট্যাক বানায়,সেটার ভেতর একটা একটা করে ফাংশন কল স্টোর করে বেইজ কেস পর্যন্ত এগিয়ে যায়,তারপর নিচ থেকে ফাংশনগুলো এক্সিকিউট করতে করতে উপরে উঠে আসে। এই যে অতিরিক্ত মেমরী টা লেগে যাচ্ছে,আমরা এই অংশে সেটাকে বাদ দিয়ে বোটম-আপ এপ্রোচে লুপ ঘুড়িয়ে a^n বের করবো। টাইম কমপ্লেক্সিটি থিওরিটিক্যালি সেইম,কিন্তু প্র্যাকটিক্যালি ডিফরেন্ট। মেমরী কমপ্লেক্সিটি সম্পর্কে আর নতুন করে বলে লাভ নেই!
দেখো, 5^20 কে আমরা আরেকটু অন্যভাবে চাইলেই লিখতে পারতামঃ
এখানে পার্থক্য আগেরটা থেকে একটাই যে,৫ এর উপর ঘাতগুলো সব দুই এর ঘাত।
২০ কে বাইনারী তে লিখলে হয়ঃ ১০১০০ (১৬+৪)
প্রথমে আমি ধরে নিই,আমাকে ৫ দেয়া আছে। এবং সাথে দেয়া আছে ঘাত হিসেবে ২০। আমাকে 5^20 বের করতে হবে। ২০ কে আবার বাইনারীতেও রূপান্তর করে ফেললাম।
Execution:
বাইনারী সংখ্যাটার বাম দিক থেকে প্রথম অংকটা ১ , তাহলে আমরা বের করবো (5^0)(5^0)=1 এবং এর সাথে গুণ করে দিবো 5। তাহলে আমরা এই স্টেপে পাচ্ছি = 5^1 [ ধরে নিচ্ছি,5^0 আমরা শুরু থেকে কোথাও স্টোর করে রেখেছি]
বাইনারী সংখ্যাটার বাম দিক থেকে দ্বিতীয় অংকটা ০, তাহলে আমরা বের করবো (5^1)(5^1)= 5^2
বাইনারী সংখ্যাটার বাম দিক থেকে তৃতীয় অংকটা ১, তাহলে আমরা বের করবো (5^2)*(5^2)=5^4 এবং এর সাথে গুণ করে দিবো 5। তাহলে আমরা এই স্টেপে পাচ্ছি = 5^5
বাইনারী সংখ্যাটার বাম দিক থেকে চতুর্থ অংকটা ০, তাহলে আমরা বের করবো (5^5)*(5^5)= 5^10
বাইনারী সংখ্যাটার বাম দিক থেকে পঞ্চম অংকটা ০, তাহলে আমরা বের করবো (5^10)*(5^10)= 5^20
কাজ শেষ!
মূল সুবিধাটা এখানেই,অতিরিক্ত কোনো মেমরী খরচ হচ্ছেনা। একটি log(n) সাইজের লুপ দিয়েই কাজটা করে ফেলা যাচ্ছে। কনটেস্টে এটা বেশ কাজে দেয়,যখন বেশ বড় ভ্যালুর জন্য তোমাকে a^n বের করতে হয়। তুমি mod করে করে এগিয়ে গিয়েও হয়তো সবসময় পার পাবেনা,মেমরী কমপ্লেক্সিটির প্যাচে ফেলে তোমার নিশ্চিত Accepted কোডটিকেও Memory Limit Exceeded এ পরিণত করে দিতে পারে।
ফাংশন কোডঃ
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
int power(int a,int n) { string bin=""; int temp; while(n>0) { temp=n%2; if(temp==0) bin+="0"; else bin+="1"; n/=2; } reverse(bin.begin(),bin.end()); // bin নামক স্ট্রিং এ এখন আমাদের n এর বাইনারী ফর্ম টি সেইভড! int res=1; // এই সেই 5^0,যা আমি উদাহরণে ব্যবহার করেছিলাম for(int i=0; i<bin.size(); i++) { res=res*res; if(bin[i]=='1') res=a*res; } return res; } |
শুধুমাত্র পদ্ধতি ৩ অবলম্বন করে আমি একটা প্রব্লেমে 0.020 সেকেন্ড রানটাইম থেকে,0.000 সেকেন্ডে নামিয়ে নিয়ে এসেছিলাম। তাই এর গুরুত্ব নেহায়েত কম নয়!
তো,জানাবে কেমন লাগলো। সবশেষে ধন্যবাদ জানাতে চাই আমার ডিপার্টমেন্ট এর শ্রদ্ধেয় লেকচারার আন্না ফারিহা ম্যাডামকে। উনার একটি লিখা পড়েই আমি অনুপ্রাণিত হয়ে এই পোস্টটি লিখেছি। লিখায় ভুল থাকলে কিংবা বুঝতে অসুবিধা হলে,কমেন্ট বক্সে জানাতে ভুলো না/ভুলবেন না। আজকের মতো এটুকুই।
আগামী পর্বে থাকছে অ্যারে মাল্টিপ্লিকেশন উইদ মডুলার এক্সপনেন্সিয়েশন,রিকারেন্স ইকুয়েশন সল্ভ ইন O(log(n)) টাইম!
Sadman Sakib
Latest posts by Sadman Sakib (see all)
- Randomized Algorithm – Competitive Programming – Part 2 - February 10, 2020
- Randomized Algorithm – Competitive Programming – Part 1 - December 24, 2019
- গ.সা.গু. এবং ল.সা.গু. – Mind Blown - December 28, 2017
Thanks, vaia! Helpful one. Ummm, Big Mod niye likhben, please. 🙂
চলে আসবে। 🙂
wow 😀
chomotkar hoece vai.. modular inverse nie likle upokri2 hotam.
wow vai onkkisu easily sikha gelo
nice
ei site e aro onkkk topic paben, onk easy + efficient vabe bujaise..
generic viagra in the usa https://buszcentrum.com/
buy careprost in the usa https://carepro1st.com/
dapoxetine before and after https://salemeds24.wixsite.com/dapoxetine
acyclovir without doctor prescription reviews https://www.herpessymptomsinmen.org/productacyclovir/
average age men need viagra http://droga5.net/
vidalista 20mg online https://vidalista.mlsmalta.com/
generic priligy in united states https://ddapoxetine.com/
buy chloroquine and hydroxychloroquine https://hydroxychloroquinee.com/
ivermectin tablets for humans http://ivermmectin.com/
shoppers drug mart prescription refills https://medpills.bee-rich.com/
ed meds prescribed online https://tadalafili.com/
cialis singapore pharmacy https://www.lm360.us/
Very nice post. I just stumbled upon your blog and wanted to say that I have
truly enjoyed browsing your blog posts. In any
case I will be subscribing to your rss feed
and I hope you write again very soon! https://hydroxychloroquineb.bee-rich.com/
oan ivermectin https://ivermectin1st.com/
I’m truly enjoying the design and layout of your website.
It’s a very easy on the eyes which makes it much more enjoyable for me to come here and visit more often. Did you hire out a developer
to create your theme? Fantastic work! http://antiibioticsland.com/Cipro.htm
prednisone 10mg cost https://bvsinfotech.com/
Is this the iterative code of bigmode? Here we do the same thing
If n is odd then result=result*number
Else result er sqaure.
Then n/=2;
Why we need string?
I mean if we write the code without mod
I like it when individuals come together and
share ideas. Great website, continue the good work! http://herreramedical.org/tadalafil
Hello! Do you know if they make any plugins to protect against hackers?
I’m kinda paranoid about losing everything I’ve worked hard on. Any
suggestions? https://hydroxychloroquinec.cleckleyfloors.com/
amoxil dosage recommendations http://amoxycillin1st.com/
purchase cialis online no prescription https://cialis.adicbc.com/
Hi, I think your site might be having browser compatibility issues.
When I look at your website in Safari, it looks fine but when opening in Internet Explorer, it
has some overlapping. I just wanted to give you a quick heads up!
Other then that, fantastic blog! http://www.deinformedvoters.org/dapoxetine-60mg
buy hydroxychloroquine online https://hydroxychloroquinex.com/
Good day! Would you be angry if I share your post with my google group? There’s a lot of folks that I think would surely enjoy your work here. Please let me know. Thanks mercurycards.com/activate
You possess a specialized craft. Your publishing capabilities are without a doubt superior. Kudos for sending material over the internet and training your followers. paturnpiketollbyplate.com login
Im not sure where you are getting your info, but great topic. I needs to spend some time learning more or understanding more. Thanks for magnificent info I was looking for this information for my mission.
I dont even know how I ended up here, but I thought this post was great. I do not know who you are but definitely you’re going to a famous blogger if you aren’t already 😉 Cheers!
I relish seeing your blogging site. You are simply astute and also create so adequately. Thanks a bunches when it comes to striving on this specific blog site. maxfli straightfli
Good day! Do you know if they make any plugins to safeguard against hackers? I’m kinda paranoid about losing everything I’ve worked hard on. Any tips?
Do you mind if I quote a few of your articles as long as I provide credit and sources back to your site? My website is in the exact same area of interest as yours and my visitors would truly benefit from a lot of the information you present here. Please let me know if this ok with you. Cheers!
I am always looking online for ideas that can assist me. Thx!
Hi there! This is my first visit to your blog! We are a team of volunteers and starting a new initiative in a community in the same niche. Your blog provided us useful information to work on. You have done a marvellous job!
Currently it appears like Movable Type is the preferred blogging platform out there right now. (from what I’ve read) Is that what you’re using on your blog?
Hi there! Do you know if they make any plugins to safeguard against hackers? I’m kinda paranoid about losing everything I’ve worked hard on. Any suggestions?