پرش به محتویات

توان‌رسانی دودویی

توان‌رسانی دودویی (که به عنوان توان‌رسانی با مربع‌سازی نیز شناخته می‌شود) ترفندی است که اجازه می‌دهد $a^n$ را تنها با استفاده از $O(\log n)$ ضرب (به جای $O(n)$ ضرب مورد نیاز در رویکرد ساده) محاسبه کنیم.

این روش همچنین کاربردهای مهمی در بسیاری از مسائل غیرمرتبط با حساب دارد، زیرا می‌توان آن را با هر عملیاتی که خاصیت شرکت‌پذیری دارد، استفاده کرد:

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

واضح‌ترین کاربردهای آن در ضرب پیمانه‌ای، ضرب ماتریس‌ها و مسائل دیگری است که در ادامه به آنها خواهیم پرداخت.

الگوریتم

به توان $n$ رساندن $a$ به صورت ساده به عنوان ضرب $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$ را در مبنای ۲ بنویسیم، برای مثال:

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

از آنجایی که عدد $n$ در مبنای ۲ دقیقاً $\lfloor \log_2 n \rfloor + 1$ رقم دارد، اگر توان‌های $a^1, a^2, a^4, a^8, \dots, a^{2^{\lfloor \log n \rfloor}}$ را بدانیم، تنها به $O(\log n)$ ضرب نیاز داریم.

بنابراین فقط به یک راه سریع برای محاسبه آن‌ها نیاز داریم. خوشبختانه این کار بسیار آسان است، زیرا هر عنصر در دنباله، مربع عنصر قبلی است.

$$\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)$ است: ما باید $\log n$ توان از $a$ را محاسبه کنیم و سپس حداکثر $\log n$ ضرب برای به دست آوردن پاسخ نهایی از آن‌ها انجام دهیم.

رویکرد بازگشتی زیر همین ایده را بیان می‌کند:

$$a^n = \begin{cases} 1 &\text{اگر } n == 0 \\ \left(a^{\frac{n}{2}}\right)^2 &\text{اگر } n > 0 \text{ و } n \text{ زوج باشد}\\ \left(a^{\frac{n - 1}{2}}\right)^2 \cdot a &\text{اگر } n > 0 \text{ و } n \text{ فرد باشد}\\ \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$ های بزرگ ($b >> m$) سریع‌تر کرد. اگر $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$ تبدیل می‌کند. بنابراین، می‌توانیم این ماتریس تبدیل را به توان $n$ برسانیم تا $F_n$ را در پیچیدگی زمانی $O(\log n)$ پیدا کنیم.

اعمال یک جایگشت به تعداد $k$ بار

مسئله: به شما یک دنباله به طول $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$ تعداد کل تبدیل‌هایی است که باید اعمال شوند (پس از باز کردن عملیات "حلقه").

راه حل: بیایید ببینیم انواع مختلف تبدیل‌ها چگونه مختصات را تغییر می‌دهند:

  • عملیات انتقال: یک ثابت متفاوت به هر یک از مختصات اضافه می‌کند.
  • عملیات مقیاس‌دهی: هر یک از مختصات را در یک ثابت متفاوت ضرب می‌کند.
  • عملیات دوران: تبدیل پیچیده‌تر است (در اینجا به جزئیات نمی‌پردازیم)، اما هر یک از مختصات جدید همچنان می‌تواند به عنوان یک ترکیب خطی از مختصات قدیمی نمایش داده شود.

همانطور که می‌بینید، هر یک از تبدیل‌ها را می‌توان به عنوان یک عملیات خطی بر روی مختصات نشان داد. بنابراین، یک تبدیل را می‌توان به صورت یک ماتریس $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}$$

(شاید بپرسید چرا یک مختصات چهارم ساختگی معرفی کردیم؟ این زیبایی مختصات همگن است که کاربرد زیادی در گرافیک کامپیوتری دارد. بدون آن، پیاده‌سازی عملیات افاین مانند عملیات انتقال به عنوان یک ضرب ماتریسی واحد ممکن نبود، زیرا به ما نیاز دارد که یک ثابت به مختصات اضافه کنیم. تبدیل افاین در بعد بالاتر به یک تبدیل خطی تبدیل می‌شود!)

در اینجا چند مثال از نحوه نمایش تبدیل‌ها در قالب ماتریس آورده شده است:

  • عملیات انتقال: انتقال مختصات $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}$$
  • عملیات دوران: دوران به اندازه $\theta$ درجه حول محور $x$ طبق قانون دست راست (جهت پادساعتگرد).
$$\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})$ محاسبه می‌شود و سپس در $O(n)$ به هر یک از $n$ نقطه اعمال می‌شود، که پیچیدگی کل آن $O(n + m \log{k})$ است.

تعداد مسیرهای به طول $k$ در یک گراف

مسئله: با داشتن یک گراف جهت‌دار بدون وزن با $n$ رأس، تعداد مسیرهای به طول $k$ از هر رأس $u$ به هر رأس دیگر $v$ را بیابید.

راه حل: این مسئله با جزئیات بیشتر در یک مقاله جداگانه بررسی شده است. الگوریتم شامل به توان $k$ رساندن ماتریس مجاورت $M$ گراف است (ماتریسی که در آن $m_{ij} = 1$ اگر یالی از $i$ به $j$ وجود داشته باشد، و در غیر این صورت $0$ است). اکنون $m_{ij}$ تعداد مسیرهای به طول $k$ از $i$ به $j$ خواهد بود. پیچیدگی زمانی این راه حل $O(n^3 \log k)$ است.

نکته: در همان مقاله، نوع دیگری از این مسئله در نظر گرفته شده است: زمانی که یال‌ها وزن‌دار هستند و لازم است مسیر با کمترین وزن که دقیقاً شامل $k$ یال است، پیدا شود. همانطور که در آن مقاله نشان داده شده است، این مسئله نیز با توان‌رسانی ماتریس مجاورت حل می‌شود. ماتریس شامل وزن یال از $i$ به $j$ یا $\infty$ اگر چنین یالی وجود نداشته باشد، خواهد بود. به جای عملیات معمول ضرب دو ماتریس، باید از یک عملیات اصلاح شده استفاده شود: به جای ضرب، هر دو مقدار با هم جمع می‌شوند و به جای جمع‌بندی، کمینه گرفته می‌شود. یعنی: $result_{ij} = \min\limits_{1\ \leq\ k\ \leq\ n}(a_{ik} + b_{kj})$.

نوعی از توان‌رسانی دودویی: ضرب دو عدد به پیمانه $m$

مسئله: دو عدد $a$ و $b$ را به پیمانه $m$ ضرب کنید. $a$ و $b$ در انواع داده داخلی جا می‌شوند، اما حاصلضرب آنها برای جا شدن در یک عدد صحیح ۶۴ بیتی بسیار بزرگ است. ایده این است که $a \cdot b \pmod m$ را بدون استفاده از حساب اعداد بزرگ (bignum) محاسبه کنیم.

راه حل: ما به سادگی الگوریتم ساخت دودویی را که در بالا توضیح داده شد، اعمال می‌کنیم، فقط به جای ضرب، جمع انجام می‌دهیم. به عبارت دیگر، ما ضرب دو عدد را به $O (\log m)$ عملیات جمع و ضرب در دو (که در اصل، یک جمع است) "بسط" داده‌ایم.

$$a \cdot b = \begin{cases} 0 &\text{اگر }a = 0 \\ 2 \cdot \frac{a}{2} \cdot b &\text{اگر }a > 0 \text{ و }a \text{ زوج باشد} \\ 2 \cdot \frac{a-1}{2} \cdot b + b &\text{اگر }a > 0 \text{ و }a \text{ فرد باشد} \end{cases}$$

نکته: می‌توانید این مسئله را به روش دیگری با استفاده از عملیات ممیز شناور حل کنید. ابتدا عبارت $\frac{a \cdot b}{m}$ را با استفاده از اعداد ممیز شناور محاسبه کرده و آن را به یک عدد صحیح بدون علامت $q$ تبدیل کنید. $q \cdot m$ را با استفاده از حساب اعداد صحیح بدون علامت از $a \cdot b$ کم کرده و آن را به پیمانه $m$ بگیرید تا پاسخ را پیدا کنید. این راه حل نسبتاً غیرقابل اعتماد به نظر می‌رسد، اما بسیار سریع و پیاده‌سازی آن بسیار آسان است. برای اطلاعات بیشتر به اینجا مراجعه کنید.

مسائل تمرینی