ফাস্ট পাওয়ার বা দ্রুত ঘাত (Fast Power)

আপনি ২^৬৪ (2⁶⁴) কীভাবে হিসেব করবেন? সবচেয়ে সাধারণ উপায় হলো: ২-কে নিজের সাথে ৬৪ বার গুণ করা। এতে আপনাকে ৬৩ বার গুণ করতে হবে।

এটিকে করার আরও একটি স্মার্ট পদ্ধতি আছে। ২ থেকে শুরু করুন। এটিকে স্কয়ার বা বর্গ করুন → ৪। ৪-কে স্কয়ার করুন → ১৬। ১৬-কে স্কয়ার করুন → ২৫৬। এভাবে মাত্র ৬ বার স্কয়ার করলেই আপনি ২^৬৪ পেয়ে যাবেন। যেখানে আপনার ৬৩ বার গুণের প্রয়োজন ছিল, সেখানে এখন লাগছে মাত্র ৬ বার গুণ। আর ঘাত বা পাওয়ার যত বাড়বে, এই পার্থক্যের পার্থক্যও তত বড় হবে: ২^{১,০০০,০০০} হিসেব করতে লিনিয়ার পদ্ধতিতে যেখানে ১০ লক্ষ ধাপ লাগত, সেখানে এই পদ্ধতিতে মাত্র ২০ বার স্কয়ার করলেই কাজ হয়ে যাবে।

এই ট্রিকটি — অর্থাৎ রিপিটেড স্কয়ারিং (repeated squaring) বা বারবার বর্গ করা — হলো ফাস্ট পাওয়ার (একে এক্সপোনেনশিয়েশন বাই স্কয়ারিংও বলা হয়) এর মূল ভিত্তি।

মূল ধারণা

যদি n জোড় (even) হয়: xⁿ = (x^n/2)²। একবার x^n/2 হিসেব করুন, তারপর সেটিকে বর্গ করে দিন। একটি রিকার্সিভ কল এবং একটি গুণফল।

যদি n বেজোড় (odd) হয়: xⁿ = x · xⁿ⁻¹। এখানে ১টি বাড়তি গুণের মাধ্যমে সমস্যাটিকে জোড় বা ইভেন কেসে পরিণত করা হয়।

প্রতিটি ধাপে n এর মান অর্ধেক হয়ে যায়, তাই মাত্র \(\log_2(n)\) ধাপের পরেই n এর মান ০-তে পৌঁছায় — যা হলো আমাদের বেস কেস (যেকোনো কিছুর পাওয়ার ০ হলে তার মান ১)। সর্বমোট: \(O(\log n)\) সংখ্যক গুণফল।

ইটারেটিভ ভার্সন বা পুনরাবৃত্তিমূলক সংস্করণ

n সংখ্যাটিকে বাইনারিতে চিন্তা করুন। প্রতিটি বিট আপনাকে বলে দিচ্ছে যে আপনার ফলাফলে x-এর একটি নির্দিষ্ট পাওয়ার বা ঘাত অন্তর্ভুক্ত করতে হবে কি না। ইটারেটিভ পদ্ধতিতে এলএসবি (LSB) থেকে এমএসবি (MSB) পর্যন্ত বিটগুলো স্ক্যান করা হয়: একটি রানিং রেজাল্ট এবং একটি কারেন্ট বেস (বর্তমান ভিত্তি) সংরক্ষণ করুন। যদি বর্তমান বিটটি ১ হয়, তবে রেজাল্টকে বর্তমান বেস দিয়ে গুণ করুন। সবসময় বেসকে বর্গ করুন এবং n-কে ১ ধাপ ডানে শিফট (shift right) করুন। এতে কোনো রিকার্সনের প্রয়োজন হয় internal — যা মাত্র \(O(1)\) স্পেস বা জায়গা নেয়।

পূর্ণসংখ্যার বাইরে: ম্যাট্রিক্স ফাস্ট পাওয়ার

একই ট্রিক যেকোনো অ্যাসোসিয়েটিভ অপারেশনের জন্য কাজ করে — এমনকি ম্যাট্রিক্স মাল্টিপ্লিকেশনের ক্ষেত্রেও। ম্যাট্রিক্স [[১,১],[১,০]]ⁿ হিসেব করলে তা n-তম ফিবোনাচি (Fibonacci) সংখ্যা প্রদান করে। ফাস্ট পাওয়ার ব্যবহার করে এই ম্যাট্রিক্সটিকে n-তম ঘাতে উন্নীত করুন, এবং আপনি ফিবোনাচি(n) হিসেব করতে পারবেন মাত্র \(O(\log n)\) ম্যাট্রিক্স মাল্টিপ্লিকেশনের মাধ্যমে যেখানে \(O(n)\) সময় লাগত। এটি তখন খুব গুরুত্বপূর্ণ হয়ে দাঁড়ায় যখন n এর মান ১০^১৮-এর মতো বিশাল হয়।