Основы программирования

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


Второй важнейший алгоритм элементарной теории чисел - это алгоритм быстрого возведения в степень. Наряду с алгоритмом Евклида, он встречается буквально на каждом шагу, когда речь идет о применении теории чисел в программировании, - например, в теории кодирования.

Пусть требуется возвести элемент a в целую неотрицательную степень n. В качестве a может фигурировать целое или вещественное число, квадратная матрица, элемент кольца вычетов по модулю m и т.п. - требуется только, чтобы элемент a принадлежал алгебраической структуре, в которой определена ассоциативная операция умножения (т.е. в общем случае, a - элемент полугруппы).

Идея алгоритма состоит в том, чтобы возвести a в произвольную степень, применяя элементарные операции возведения в квадрат и умножения.

В качестве фазового пространства X этой задачи рассмотрим множество троек

X = {(b,k,p)}.

Здесь b выступает в роли текущего основания степени, k - в роли текущего показателя степени, p - это уже вычисленная часть степени. Ключевым моментом всегда является формулировка инварианта цикла:

I(b,k,p): bk*p = an = const,

т.е. величина bk*p постоянна и равна an. Легко подобрать начальные значения так, чтобы инвариант выполнялся:

b0 = a; k0 = n; p0 = 1. I(b0,k0,p0) = I(a,n,1): an*1 = an

Условие завершения совместно с выполнением инварианта должно обеспечить легкое решение требуемой задачи, т.е. вычисление an. Действительно, если k = 0, то из инварианта следует, что

b0*p = p = an,

т.е. искомая величина содержится в переменной p. Итак, условие завершения состоит в равенстве нулю числа k:

Q(b,k,p): k = 0

Осталось написать преобразование T точки x = (b,k,p), которое сохраняет инвариант и одновременно уменьшает k. Определим преобразование T следующим образом:

T(b,k,p) = (b*b, k/2, p), если k четное T(b,k,p) = (b, k-1, p*b), если k нечетное

Легко видеть, что инвариант сохраняется и k монотонно убывает. Итак, выпишем алгоритм быстрого возведения в степень для случая вещественного основания:

вещ алг. быстрое возведение в степень(вх: вещ a, цел n) | дано: основание a и показатель степени n >= 0 | надо: вычислить a в степени n начало алгоритма | вещ b, p; цел k; | | // инициализация | b := a; p := 1.0; k := n; | утверждение: b^k * p == a^n; | | цикл пока k > 0 | | инвариант: b^k * p == a^n; | | если k четное | | | то | | | k := k / 2; | | | b := b * b; | | | иначе | | | k := k - 1; | | | p := p * b; | | конец если | конец цикла | | утверждение: k == 0 и b^k * p == a^n; | ответ := p; конец алгоритма



Содержание раздела