Возведение в степень

Необходимо возвести число в натуральную степень

Реализация алгоритма рассмотрена на классе binteger длинной арифметики.

На примере покажу суть алгоритма:
x¹²=x⁴ * x⁸
Для вычисления n-ной степени можно идти по битам числа n и, если текущий бит 1, умножать результат на множитель, который с каждым шагом возводится в квадрат.
Сложность O(n² * log p) или O(M * log p), где O(M) - сложность операции умножения.

Листинг C++
binteger power (binteger x, int n)
{
    binteger res = binteger (1);
    binteger s = binteger (x);
    for ( ; n > 0; n >>= 1)
    {
        if (n & 1)
            res = res * s;
        s = s * s;
    }
    return res;
}

18:29
12.07.2010

По всем вопросам обращаться: rumterg@gmail.com