বাইনারি এক্সপোনেনশিয়েশন#

বাইনারি এক্সপোনেনশিয়েশন (যা স্কোয়ারিং-এর মাধ্যমে এক্সপোনেনশিয়েশন নামেও পরিচিত) একটি কৌশল যা $a^n$ গণনা করতে মাত্র $O(\log n)$ টি গুণ ব্যবহার করে (সাধারণ পদ্ধতিতে প্রয়োজনীয় $O(n)$ টি গুণের পরিবর্তে)।

পাটিগণিতের বাইরেও এর গুরুত্বপূর্ণ অ্যাপ্লিকেশন রয়েছে, কারণ এটি সংযোজনীয়তা (associativity) বৈশিষ্ট্যযুক্ত যেকোনো অপারেশনে ব্যবহার করা যায়:

$$(X \cdot Y) \cdot Z = X \cdot (Y \cdot Z)$$

সবচেয়ে স্পষ্ট উদাহরণ হলো মডুলার গুণ, ম্যাট্রিক্স গুণ এবং অন্যান্য সমস্যা যা আমরা নিচে আলোচনা করব।

অ্যালগরিদম#

$a$-কে $n$ ঘাতে উন্নীত করা সাধারণভাবে $a$ দিয়ে $n - 1$ বার গুণ হিসেবে প্রকাশ করা হয়: $a^{n} = a \cdot a \cdot \ldots \cdot a$। তবে, বড় $a$ বা $n$-এর জন্য এই পদ্ধতি ব্যবহারিক নয়।

$a^{b+c} = a^b \cdot a^c$ এবং $a^{2b} = a^b \cdot a^b = (a^b)^2$।

বাইনারি এক্সপোনেনশিয়েশনের মূল ধারণা হলো, আমরা সূচকের (exponent) বাইনারি উপস্থাপনা ব্যবহার করে কাজকে ভাগ করি।

$n$-কে বেস ২-তে লেখা যাক, উদাহরণস্বরূপ:

$$3^{13} = 3^{1101_2} = 3^8 \cdot 3^4 \cdot 3^1$$

যেহেতু $n$ সংখ্যাটির বেস ২-তে ঠিক $\lfloor \log_2 n \rfloor + 1$ টি ডিজিট আছে, তাই আমাদের মাত্র $O(\log n)$ টি গুণ করতে হবে, যদি আমরা $a^1, a^2, a^4, a^8, \dots, a^{2^{\lfloor \log_2 n \rfloor}}$ ঘাতগুলো জানি।

সুতরাং আমাদের শুধু এগুলো দ্রুত গণনা করার একটি উপায় জানতে হবে। সৌভাগ্যক্রমে এটি খুবই সহজ, কারণ ধারার প্রতিটি পদ আগের পদের বর্গ।

$$\begin{align} 3^1 &= 3 \\ 3^2 &= \left(3^1\right)^2 = 3^2 = 9 \\ 3^4 &= \left(3^2\right)^2 = 9^2 = 81 \\ 3^8 &= \left(3^4\right)^2 = 81^2 = 6561 \end{align}$$

সুতরাং $3^{13}$-এর চূড়ান্ত উত্তর পেতে, আমাদের এদের মধ্যে শুধু তিনটি গুণ করতে হবে ($3^2$ বাদ দিয়ে, কারণ $n$-এ সংশ্লিষ্ট বিটটি সেট নেই): $3^{13} = 6561 \cdot 81 \cdot 3 = 1594323$

এই অ্যালগরিদমের চূড়ান্ত কমপ্লেক্সিটি $O(\log n)$: আমাদের $a$-এর $\log n$ টি ঘাত গণনা করতে হবে এবং চূড়ান্ত উত্তর পেতে সর্বাধিক $\log n$ টি গুণ করতে হবে।

নিম্নলিখিত রিকার্সিভ পদ্ধতি একই ধারণা প্রকাশ করে:

$$a^n = \begin{cases} 1 &\text{if } n == 0 \\ \left(a^{\frac{n}{2}}\right)^2 &\text{if } n > 0 \text{ and } n \text{ even}\\ \left(a^{\frac{n - 1}{2}}\right)^2 \cdot a &\text{if } n > 0 \text{ and } n \text{ odd}\\ \end{cases}$$

ইমপ্লিমেন্টেশন#

প্রথমে রিকার্সিভ পদ্ধতি, যা রিকার্সিভ সূত্রের সরাসরি রূপান্তর:

long long binpow(long long a, long long b) {
    if (b == 0)
        return 1;
    long long res = binpow(a, b / 2);
    if (b % 2)
        return res * res * a;
    else
        return res * res;
}

দ্বিতীয় পদ্ধতি রিকার্সন ছাড়াই একই কাজ সম্পন্ন করে। এটি একটি লুপে সকল ঘাত গণনা করে এবং $n$-এ সংশ্লিষ্ট সেট বিটযুক্ত ঘাতগুলো গুণ করে। যদিও উভয় পদ্ধতির কমপ্লেক্সিটি অভিন্ন, এই পদ্ধতি বাস্তবে দ্রুততর হবে কারণ রিকার্সিভ কলের ওভারহেড নেই।

long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

অ্যাপ্লিকেশনসমূহ#

একটি সংখ্যা দ্বারা মডুলোতে বড় ঘাতের কার্যকর গণনা#

সমস্যা: $x^n \bmod m$ গণনা করুন। এটি একটি অত্যন্ত সাধারণ অপারেশন। উদাহরণস্বরূপ, মডুলার গুণগত বিপরীত গণনায় এটি ব্যবহৃত হয়।

সমাধান: যেহেতু আমরা জানি মডুলো অপারেটর গুণে হস্তক্ষেপ করে না ($a \cdot b \equiv (a \bmod m) \cdot (b \bmod m) \pmod m$), তাই আমরা সরাসরি একই কোড ব্যবহার করতে পারি, শুধু প্রতিটি গুণকে মডুলার গুণ দিয়ে প্রতিস্থাপন করলেই হবে:

long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

লক্ষ্য করুন: বড় $b >> m$-এর জন্য এই অ্যালগরিদম দ্রুততর করা সম্ভব। যদি $m$ একটি ধনাত্মক সংখ্যা হয় এবং $\gcd(x, m) = 1$ হয়, তাহলে মৌলিক $m$-এর জন্য $x^n \equiv x^{n \bmod (m-1)} \pmod{m}$ এবং যৌগিক $m$-এর জন্য $x^n \equiv x^{n \bmod{\phi(m)}} \pmod{m}$। এটি সরাসরি ফার্মার ক্ষুদ্র উপপাদ্য এবং অয়লারের উপপাদ্য থেকে প্রাপ্ত, বিস্তারিত জানতে মডুলার ইনভার্স নিবন্ধটি দেখুন।

ফিবোনাচ্চি সংখ্যার কার্যকর গণনা#

সমস্যা: $n$-তম ফিবোনাচ্চি সংখ্যা $F_n$ গণনা করুন।

সমাধান: বিস্তারিত জানতে ফিবোনাচ্চি সংখ্যা নিবন্ধ দেখুন। আমরা এখানে শুধু অ্যালগরিদমের একটি সংক্ষিপ্ত বিবরণ দেব। পরবর্তী ফিবোনাচ্চি সংখ্যা গণনা করতে শুধু আগের দুটি সংখ্যা প্রয়োজন, কারণ $F_n = F_{n-1} + F_{n-2}$। আমরা একটি $2 \times 2$ ম্যাট্রিক্স তৈরি করতে পারি যা এই রূপান্তর বর্ণনা করে: $F_i$ এবং $F_{i+1}$ থেকে $F_{i+1}$ এবং $F_{i+2}$-তে রূপান্তর। উদাহরণস্বরূপ, $F_0$ এবং $F_1$ জোড়ায় এই রূপান্তর প্রয়োগ করলে এটি $F_1$ এবং $F_2$-তে পরিবর্তিত হবে। অতএব, $O(\log n)$ টাইম কমপ্লেক্সিটিতে $F_n$ বের করতে আমরা এই রূপান্তর ম্যাট্রিক্সকে $n$-তম ঘাতে উন্নীত করতে পারি।

একটি পারমুটেশন $k$ বার প্রয়োগ { data-toc-label=‘Applying a permutation $k$ times’ }#

সমস্যা: আপনাকে $n$ দৈর্ঘ্যের একটি ক্রম দেওয়া হয়েছে। এতে একটি প্রদত্ত পারমুটেশন $k$ বার প্রয়োগ করুন।

সমাধান: বাইনারি এক্সপোনেনশিয়েশন ব্যবহার করে পারমুটেশনকে $k$-তম ঘাতে উন্নীত করুন, তারপর ক্রমে প্রয়োগ করুন। এতে টাইম কমপ্লেক্সিটি হবে $O(n \log k)$।

vector<int> applyPermutation(vector<int> sequence, vector<int> permutation) {
    vector<int> newSequence(sequence.size());
    for(int i = 0; i < sequence.size(); i++) {
        newSequence[i] = sequence[permutation[i]];
    }
    return newSequence;
}

vector<int> permute(vector<int> sequence, vector<int> permutation, long long k) {
    while (k > 0) {
        if (k & 1) {
            sequence = applyPermutation(sequence, permutation);
        }
        permutation = applyPermutation(permutation, permutation);
        k >>= 1;
    }
    return sequence;
}

লক্ষ্য করুন: এই সমস্যাটি পারমুটেশন গ্রাফ তৈরি করে এবং প্রতিটি চক্র স্বাধীনভাবে বিবেচনা করে লিনিয়ার সময়ে আরও দক্ষতার সাথে সমাধান করা যায়। তখন আপনি চক্রের আকার দ্বারা $k$-এর মডুলো গণনা করতে পারেন এবং এই চক্রের অন্তর্ভুক্ত প্রতিটি সংখ্যার চূড়ান্ত অবস্থান নির্ণয় করতে পারেন।

বিন্দুসমূহে জ্যামিতিক অপারেশনের দ্রুত প্রয়োগ#

সমস্যা: $n$ টি বিন্দু $p_i$ দেওয়া আছে, প্রতিটি বিন্দুতে $m$ টি রূপান্তর প্রয়োগ করুন। প্রতিটি রূপান্তর হতে পারে একটি সরণ (shift), একটি স্কেলিং অথবা একটি নির্দিষ্ট অক্ষের চারপাশে নির্দিষ্ট কোণে ঘূর্ণন। একটি “লুপ” অপারেশনও আছে যা একটি প্রদত্ত রূপান্তর তালিকা $k$ বার প্রয়োগ করে (“লুপ” অপারেশন নেস্টেড হতে পারে)। সমস্ত রূপান্তর $O(n \cdot length)$-এর চেয়ে দ্রুত প্রয়োগ করতে হবে, যেখানে $length$ হলো প্রয়োগযোগ্য মোট রূপান্তরের সংখ্যা (“লুপ” অপারেশন উন্মোচনের পরে)।

সমাধান: দেখা যাক বিভিন্ন ধরনের রূপান্তর কীভাবে স্থানাঙ্ক পরিবর্তন করে:

সরণ (Shift) অপারেশন: প্রতিটি স্থানাঙ্কে ভিন্ন ধ্রুবক যোগ করে।
স্কেলিং অপারেশন: প্রতিটি স্থানাঙ্ককে ভিন্ন ধ্রুবক দিয়ে গুণ করে।
ঘূর্ণন অপারেশন: রূপান্তরটি আরও জটিল (আমরা এখানে বিস্তারিত যাব না), তবে প্রতিটি নতুন স্থানাঙ্ক পুরানোগুলোর একটি রৈখিক সংযোজন হিসেবে উপস্থাপন করা যায়।

যেমন দেখা যাচ্ছে, প্রতিটি রূপান্তর স্থানাঙ্কের উপর একটি রৈখিক অপারেশন হিসেবে উপস্থাপন করা যায়। সুতরাং, একটি রূপান্তরকে নিম্নরূপ $4 \times 4$ ম্যাট্রিক্স আকারে লেখা যায়:

$$\begin{pmatrix} a_{11} & a_ {12} & a_ {13} & a_ {14} \\ a_{21} & a_ {22} & a_ {23} & a_ {24} \\ a_{31} & a_ {32} & a_ {33} & a_ {34} \\ a_{41} & a_ {42} & a_ {43} & a_ {44} \end{pmatrix}$$

যেটি পুরানো স্থানাঙ্ক এবং একটি একক সম্বলিত ভেক্টরের সাথে গুণ করলে নতুন স্থানাঙ্ক এবং একটি একক সম্বলিত নতুন ভেক্টর দেয়:

$$\begin{pmatrix} x & y & z & 1 \end{pmatrix} \cdot \begin{pmatrix} a_{11} & a_ {12} & a_ {13} & a_ {14} \\ a_{21} & a_ {22} & a_ {23} & a_ {24} \\ a_{31} & a_ {32} & a_ {33} & a_ {34} \\ a_{41} & a_ {42} & a_ {43} & a_ {44} \end{pmatrix} = \begin{pmatrix} x' & y' & z' & 1 \end{pmatrix}$$

(কাল্পনিক চতুর্থ স্থানাঙ্ক কেন প্রবর্তন করা হলো, জিজ্ঞেস করছেন? এটাই হলো সমাঙ্গ স্থানাঙ্কের (homogeneous coordinates) সৌন্দর্য, যা কম্পিউটার গ্রাফিক্সে দারুণ ব্যবহার পায়। এটি ছাড়া সরণের মতো অ্যাফাইন অপারেশনকে একটি মাত্র ম্যাট্রিক্স গুণ হিসেবে রূপায়ণ করা সম্ভব হতো না, কারণ এতে স্থানাঙ্কে ধ্রুবক যোগ করতে হয়। উচ্চতর মাত্রায় অ্যাফাইন রূপান্তর একটি রৈখিক রূপান্তরে পরিণত হয়!)

নিচে কিছু উদাহরণ দেওয়া হলো কীভাবে রূপান্তরগুলো ম্যাট্রিক্স আকারে উপস্থাপিত হয়:

সরণ অপারেশন: $x$ স্থানাঙ্ক $5$, $y$ স্থানাঙ্ক $7$ এবং $z$ স্থানাঙ্ক $9$ দ্বারা সরানো।

$$\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 5 & 7 & 9 & 1 \end{pmatrix}$$

স্কেলিং অপারেশন: $x$ স্থানাঙ্ককে $10$ দিয়ে এবং বাকি দুটিকে $5$ দিয়ে স্কেল করা।

$$\begin{pmatrix} 10 & 0 & 0 & 0 \\ 0 & 5 & 0 & 0 \\ 0 & 0 & 5 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}$$

ঘূর্ণন অপারেশন: ডান-হাত নিয়ম অনুসরণ করে (ঘড়ির কাঁটার বিপরীত দিকে) $x$ অক্ষের চারপাশে $\theta$ ডিগ্রি ঘোরানো।

$$\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & \cos \theta & -\sin \theta & 0 \\ 0 & \sin \theta & \cos \theta & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}$$

এখন, প্রতিটি রূপান্তর ম্যাট্রিক্স হিসেবে বর্ণিত হলে, রূপান্তরের ক্রমকে এই ম্যাট্রিক্সগুলোর গুণফল হিসেবে এবং $k$ পুনরাবৃত্তির “লুপ"কে ম্যাট্রিক্সের $k$-তম ঘাত হিসেবে বর্ণনা করা যায় (যা বাইনারি এক্সপোনেনশিয়েশন ব্যবহার করে $O(\log{k})$-তে গণনা করা যায়)। এভাবে, সমস্ত রূপান্তর উপস্থাপনকারী ম্যাট্রিক্সটি প্রথমে $O(m \log{k})$-তে গণনা করা যায়, তারপর এটি $n$ টি বিন্দুর প্রতিটিতে $O(n)$-এ প্রয়োগ করা যায়, সর্বমোট কমপ্লেক্সিটি $O(n + m \log{k})$।

একটি গ্রাফে $k$ দৈর্ঘ্যের পথের সংখ্যা { data-toc-label=‘Number of paths of length $k$ in a graph’ }#

সমস্যা: $n$ টি ভার্টেক্সবিশিষ্ট একটি নির্দেশিত ওজনহীন গ্রাফ দেওয়া আছে, যেকোনো ভার্টেক্স $u$ থেকে অন্য যেকোনো ভার্টেক্স $v$-তে $k$ দৈর্ঘ্যের পথের সংখ্যা বের করুন।

সমাধান: এই সমস্যাটি একটি পৃথক নিবন্ধে বিস্তারিত আলোচনা করা হয়েছে। অ্যালগরিদমটি হলো গ্রাফের অ্যাডজেসেন্সি ম্যাট্রিক্স $M$ ($i$ থেকে $j$-তে এজ থাকলে $m_{ij} = 1$, অন্যথায় $0$) কে $k$-তম ঘাতে উন্নীত করা। এখন $m_{ij}$ হবে $i$ থেকে $j$-তে $k$ দৈর্ঘ্যের পথের সংখ্যা। এই সমাধানের টাইম কমপ্লেক্সিটি $O(n^3 \log k)$।

লক্ষ্য করুন: ঐ একই নিবন্ধে এই সমস্যার আরেকটি রূপ বিবেচনা করা হয়েছে: যখন এজগুলোতে ওজন আছে এবং ঠিক $k$ টি এজ সম্বলিত ন্যূনতম ওজনের পথ বের করতে হবে। যেমনটি ঐ নিবন্ধে দেখানো হয়েছে, এই সমস্যাটিও অ্যাডজেসেন্সি ম্যাট্রিক্সের এক্সপোনেনশিয়েশন দ্বারা সমাধান করা হয়। ম্যাট্রিক্সে $i$ থেকে $j$-তে এজের ওজন থাকবে, অথবা এমন কোনো এজ না থাকলে $\infty$। সাধারণ ম্যাট্রিক্স গুণের পরিবর্তে একটি পরিবর্তিত অপারেশন ব্যবহার করতে হবে: গুণের পরিবর্তে দুটি মান যোগ করা হয় এবং যোগফলের পরিবর্তে সর্বনিম্ন মান নেওয়া হয়। অর্থাৎ: $result_{ij} = \min\limits_{1\ \leq\ k\ \leq\ n}(a_{ik} + b_{kj})$।

বাইনারি এক্সপোনেনশিয়েশনের বৈচিত্র: $m$ মডুলোতে দুটি সংখ্যার গুণ { data-toc-label=‘Variation of binary exponentiation: multiplying two numbers modulo $m$ ’ }#

সমস্যা: দুটি সংখ্যা $a$ এবং $b$-কে $m$ মডুলোতে গুণ করুন। $a$ এবং $b$ বিল্ট-ইন ডেটা টাইপে মাপসই হয়, কিন্তু তাদের গুণফল ৬৪-বিট ইন্টিজারে ধারণ করা যায় না। ধারণাটি হলো বিগনাম অ্যারিথমেটিক্স ব্যবহার না করে $a \cdot b \pmod m$ গণনা করা।

সমাধান: আমরা কেবল উপরে বর্ণিত বাইনারি গঠন অ্যালগরিদম প্রয়োগ করি, শুধু গুণের পরিবর্তে যোগ করি। অন্য কথায়, আমরা দুটি সংখ্যার গুণকে $O (\log m)$ টি যোগ ও ২ দিয়ে গুণের (যা মূলত একটি যোগ) অপারেশনে “সম্প্রসারিত” করেছি।

$$a \cdot b = \begin{cases} 0 &\text{if }a = 0 \\ 2 \cdot \frac{a}{2} \cdot b &\text{if }a > 0 \text{ and }a \text{ even} \\ 2 \cdot \frac{a-1}{2} \cdot b + b &\text{if }a > 0 \text{ and }a \text{ odd} \end{cases}$$

লক্ষ্য করুন: আপনি ফ্লোটিং-পয়েন্ট অপারেশন ব্যবহার করে ভিন্নভাবেও এই সমস্যাটি সমাধান করতে পারেন। প্রথমে ফ্লোটিং-পয়েন্ট সংখ্যা ব্যবহার করে $\frac{a \cdot b}{m}$ রাশিটি গণনা করুন এবং এটিকে একটি আনসাইনড ইন্টিজার $q$-তে রূপান্তর করুন। আনসাইনড ইন্টিজার অ্যারিথমেটিক্স ব্যবহার করে $a \cdot b$ থেকে $q \cdot m$ বিয়োগ করুন এবং উত্তর পেতে $m$ দিয়ে মডুলো নিন। এই সমাধানটি দেখতে অবিশ্বাস্য মনে হতে পারে, কিন্তু এটি অত্যন্ত দ্রুত এবং ইমপ্লিমেন্ট করা খুব সহজ। আরও তথ্যের জন্য এখানে দেখুন।