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

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

শুধু পাটিগণিত না, এটা যেকোনো অ্যাসোসিয়েটিভ (associative) অপারেশনে কাজ করে:

$$(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$।

বাইনারি এক্সপোনেনশিয়েশনের মূল আইডিয়া হলো — এক্সপোনেন্টের বাইনারি রিপ্রেজেন্টেশন ব্যবহার করে কাজটাকে ভাগ করা।

$n$ কে বেস 2-তে লিখি, যেমন:

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

$n$ এর বেস 2-তে $\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$ টা ট্রান্সফর্মেশন অ্যাপ্লাই কর। প্রতিটা ট্রান্সফর্মেশন হতে পারে একটা শিফট, একটা স্কেলিং অথবা কোনো নির্দিষ্ট অক্ষের চারপাশে নির্দিষ্ট কোণে রোটেশন। একটা “লুপ” অপারেশনও আছে যেটা একটা দেওয়া ট্রান্সফর্মেশন লিস্ট $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}$$

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

$$\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$ বিল্ট-ইন ডাটা টাইপে ধরে, কিন্তু এদের গুণফল 64-বিট ইন্টিজারে ধরে না। বিগনাম অ্যারিথমেটিক্স ব্যবহার না করে $a \cdot b \pmod m$ বের করতে হবে।

সমাধান: আমরা উপরের বাইনারি এক্সপোনেনশিয়েশন অ্যালগরিদমই অ্যাপ্লাই করি, শুধু গুণের বদলে যোগ করি। সোজা কথায়, আমরা দুইটা সংখ্যার গুণকে $O (\log m)$ টা যোগ আর 2 দিয়ে গুণের (যেটা আসলে একটা যোগ) অপারেশনে ভাঙি।

$$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$ দিয়ে মডুলো নাও। শুনতে অবিশ্বাস্য লাগতে পারে, কিন্তু এটা অনেক দ্রুত আর ইমপ্লিমেন্ট করাও সহজ। আরো জানতে এখানে দেখ।