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

توان‌رسانی دودویی الگوریتمی سریع برای محاسبهٔ توان‌های بزرگ اعداد است.

الگوریتم عادی توان‌رسانی برای محاسب ${\displaystyle a^{b}}$ از مرتبهٔ زمانی ${\displaystyle \Theta (b)}$ است که برای b های بزرگ الگوریتم ناکارآمدی است. یک مثال از ناکارآمدی این الگوریتم یافتن وارون ضربی اعداد در پیمانه اعداد بزرگ است.الگوریتم توان‌رسانی دودویی مرتبه زمانی اجرای تابع را از خطی به لگاریتمی کاهش می‌دهد.

الگوریتم اصلی

این الگوریتم بر پایهٔ این دو تساوی ساده بنا شده است:

اگر ${\displaystyle b}$ زوج باشد ${\displaystyle a^{b}=(a^{\frac {b}{2}})^{2}}$

اگر ${\displaystyle b}$ فرد باشد ${\displaystyle a^{b}=(a^{\left\lfloor {\frac {b}{2}}\right\rfloor })^{2}*a}$

بنابراین می‌توان با ارائهٔ تابع ${\displaystyle f(a,b)=a^{b}}$دو تساوی بالا را به شکل یک رابطه بازگشتی درآورد.

${\displaystyle f(a,b)={\begin{cases}b{\mbox{ mod }}2=0:f(a,a\lfloor {\frac {b}{2}}\rfloor )^{2}\\b{\mbox{ mod }}2=1:a*f(a,a\lfloor {\frac {b}{2}}\rfloor )^{2}\end{cases}}}$

کد الگوریتم

کد این الگوریتم به زبان برنامه‌نویسی پایتون به این صورت است:

def power(a,b):
    if b == 0:
        return 1
    c = power(a,b//2)
    c *= c
    if b % 2 == 1:
        c *= a
    return c

کد الگوریتم به زبان ++C برای اعداد طبیعی اینگونه است. باید توجه داشت با توجه به محدودیت ظرفیت int و long long در++C و بزرگ بودن احتمالی خروجی تابع بهتر است یک پارامتر ورودی دیگری به عنوان mod به تابع داده شود تا باقی ماندهٔ ${\displaystyle a^{b}}$بر آن را به عنوان خروجی تابع تعریف کنیم:

int power(int a, int b, int mod){
    if (b == 0)
        return 1;
    long long c = power(a,b/2);
    c = (c * c)%mod;
    if (b % 2 == 1)
        c = (c * a)%mod
    return c;
}

باید دقت شود که متغیر داخلی c را باید حتماً از نوع long long تعریف کرد حتی اگر تمامی ورودی‌ها و خروجی‌ها int باشند؛ زیرا ضرب دو یا چند متغیر int ممکن است از محدودهٔ int بیرون بزند و جواب غیرقابل قبولی تولید شود.

تحلیل زمانی الگوریتم

در هر فراخوانی تابع یک بار تابع بازگشتی صدا زده می‌شود و نیز تعدادی عملیات ضرب و شرط که همگی از ${\displaystyle O(1)}$ هستند انجام می‌شود؛ بنابراین پیچیدگی زمانی الگوریتم برابر تعداد کل دفعات فراخوانی توابع بازگشتی است.

با توجه به اینکه در هر مرحله قراخوانی تابع بازگشتی مقدار عدد ${\displaystyle b}$ نصف می‌شود و شرط پایان برنامه وقتی است که ${\displaystyle b=0}$ این الگوریتم از ${\displaystyle O(\log(b))}$ است.

کاربردها

این الگوریتم از الگوریتم‌های بسیار پرکاربرد در حوزه نظریه اعداد است؛ برای مثال برای یافتن وارون ضربی در پیاده‌سازی تابع ترکیب برای مقادیر ورودی بزرگ کاربرد دارد. برای مثال فرض کنید می‌خواهیم ${\displaystyle {\binom {n}{k}}}$ را به پیمانهٔ ${\displaystyle m}$ حساب کنیم از آنجا که ${\displaystyle {\binom {n}{k}}={\frac {n!}{k!\times (n-k)!}}}$ لازم است ${\displaystyle {\frac {1}{n!}}}$ و ${\displaystyle {\frac {1}{(n-k)!}}}$ را به پیمانهٔ ${\displaystyle m}$ محاسبه کنیم که طبق تابع فی اویلر درصورتی که ${\displaystyle n!}$ و ${\displaystyle (n-k)!}$ نسبت به ${\displaystyle m}$ متباین باشند به ترتیب برابر با ${\displaystyle ({\frac {1}{n!}})^{\phi (m)}{\bmod {m}}}$ و ${\displaystyle ({\frac {1}{(n-k)!}})^{\phi (m)}{\bmod {m}}}$ می‌باشند. درصورتی که عدد ${\displaystyle m}$ بزرگ باشد این الگوریتم بسیار سریع‌تر از الگوریتم سرراست کار می‌کند.

منابع

• ویکی‌پدیای انگلیسی