Быстрое возведение в степень

Быстрое возведение в степень – это алгоритм, который позволяет возвести любое число в натуральную степень за сокращенное количество умножений.

Описание алгоритма

Для любого числа 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;
}

Смотрите также: