Швидке піднесення до степеня

Швидке піднесення до степеня – це алгоритм, який дозволяє піднести до натурального степеня будь яке число, за скорочену кількість множень.

Опис алгоритму

Для будь-якого числа x та парного степеня n виконується рівність:

xn = (xn/2)2 = xn/2 ⋅ xn/2

Це і є основою алгоритму швидкого піднесення до степеню. Оскільки таке розбиття дозволяє за одну операцію множення зменшити степінь в два рази.

Для випадку непарної степені, достатньо зменшити її на одиницю:

xn = xn - 1 ⋅ x, при цьому (n - 1) парне число.

Рекурсивна реалізація швидкого піднесення до степеню

static long Power(long x, int n)
{
    if (n == 0)
    {
        return 1;
    }

    if (n % 2 == 0)
    {
        var p = Power(x, n / 2);
        return p * p;
    }
    else
    {
        return x * Power(x, n - 1);
    }
}

Для оптимізації можна замінити перевірку на парність та ділення на 2 бітовими операціями:

static long Power(long x, int n)
{
    if (n == 0)
    {
        return 1;
    }
    
    //у парного числа останній біт рівний нулю
    if ((n & 1) == 0) 
    {
        //зміщення на один біт вправо рівнозначно діленню на два
        var p = Power(x, n >> 1);
        return p * p;
    }
    else
    {
        return x * Power(x, n - 1);
    }
}

Ітераційна реалізація

В цьому методі, швидкого піднесення до степеню, також використаємо оптимізацію перевірки парності та ділення на два:

static long Power(long x, int n)
{
    var result = 1L;
    while (n > 0)
    {
        if ((n & 1) == 0)
        {
            x *= x;
            n >>= 1;
        }
        else
        {
            result *= x;
            --n;
        }
    }

    return result;
}

Дивіться також: