نمایش مبدأ برای توان‌رسانی دودویی

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

الگوریتم عادی توان‌رسانی برای محاسب <math>a^b</math> از مرتبهٔ زمانی <math>\Theta(b)</math> است که برای b های بزرگ الگوریتم [[کارایی الگوریتمی|ناکارآمدی]] است. یک مثال از ناکارآمدی این الگوریتم یافتن وارون ضربی اعداد در [[هم‌نهشتی (نظریه اعداد)|پیمانه]] اعداد بزرگ است.الگوریتم توان‌رسانی دودویی [[پیچیدگی زمانی|مرتبه زمانی]] اجرای تابع را از خطی به [[لگاریتم|لگاریتمی]] کاهش می‌دهد.

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

اگر <math>b</math> زوج باشد <math>a^b = (a^\frac{b}{2})^2</math>

اگر <math>b</math> فرد باشد <math>a^b = (a^{\left\lfloor\frac{b}{2}\right\rfloor})^2* a</math>

بنابراین می‌توان با ارائهٔ [[تابع]] <math>f(a,b)=a^b</math>دو تساوی بالا را به شکل یک [[رابطه بازگشتی]] درآورد.

<math>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}</math>

== کد الگوریتم ==
کد این الگوریتم به [[زبان برنامه‌نویسی پایتون]] به این صورت است:
<syntaxhighlight lang="python">def power(a,b):
    if b == 0:
        return 1
    c = power(a,b//2)
    c *= c
    if b % 2 == 1:
        c *= a
    return c</syntaxhighlight>
کد الگوریتم به زبان [[++C]] برای [[اعداد طبیعی]] اینگونه است. باید توجه داشت با توجه به محدودیت ظرفیت <code>int</code> و <code>long long</code> در[[++C]] و بزرگ بودن احتمالی خروجی تابع بهتر است یک پارامتر ورودی دیگری به عنوان <code>mod</code> به تابع داده شود تا باقی ماندهٔ <math>a^b</math>بر آن را به عنوان خروجی تابع تعریف کنیم:
<syntaxhighlight lang="cpp">int power(int a, int b, int mod)
{
    if (b == 0)
        return 1;

    long long c = power(a, b/2, mod);
    c = (c * c) % mod;

    if (b % 2 == 1)
        c = (c * a) % mod;

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

== تحلیل زمانی الگوریتم ==
در هر فراخوانی تابع یک بار تابع بازگشتی صدا زده می‌شود و نیز تعدادی عملیات ضرب و شرط که همگی از <math>O(1)</math> هستند انجام می‌شود؛ بنابراین پیچیدگی زمانی الگوریتم برابر تعداد کل دفعات فراخوانی توابع بازگشتی است.

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

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

== منابع ==
{{پانویس}}
* [[w:en: Exponentiation by squaring |ویکی‌پدیای انگلیسی]]

[[رده:نمایی‌ها]]
[[رده:الگوریتم‌های محاسباتی رایانه]]
[[رده:حساب رایانه‌ای]]