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

Рассмотрим задачу возведения числа в степень. Нам нужна процедура, которая, приняв в качестве аргумента основание b и положительное целое значение степени n, возвращает bⁿ. Один из способов получить желаемое — через рекурсивное определение

которое прямо переводится в процедуру:
*-Нравится статья? Кликни по рекламе! :)

def expt(b, n):
    if n==0:
        return 1
    return b*expt(b, n-1)

Это линейно рекурсивный процесс, требующий θ(n) шагов и θ(n) памяти. Подобно факториалу, мы можем немедленно сформулировать эквивалентную линейную итерацию:

def expt(b, n):
    def exptIter(counter, product):
        if counter==0:
            return product
        return exptIter(counter-1, b*product)
    return exptIter(n,1)

Эта версия требует θ(n) шагов и θ(1) памяти.
Можно вычислять степени за меньшее число шагов, если использовать последовательное возведение в квадрат. Например, вместо того, чтобы вычислять b⁸ в виде:

b · (b · (b · (b · (b · (b · (b · b))))))

мы можем вычислить его за три умножения:

 Этот метод хорошо работает для степеней, которые сами являются степенями двойки. В общем случае при вычислении степеней мы можем получить преимущество от последовательного возведения в квадрат, если воспользуемся правилом:

 Этот метод можно выразить в виде процедуры:

def fastExp(b, n):
    def even(n):#проверка четности
        if n%2==0:
            return 1
        return 0
    if n==0:
        return 1
    if even(n):
        return fastExp(b, n/2)**2
    return b*fastExp(b, n-1)

Процесс, вычисляющий fastExpt, растет логарифмически как по используемой памяти, так и по количеству шагов. Чтобы увидеть это, заметим, что вычисление b²ⁿ с помощью этого алгоритма требует всего на одно умножение больше, чем вычисление bⁿ. Следовательно, размер степени, которую мы можем вычислять, возрастает примерно вдвое с каждым следующим умножением, которое нам разрешено делать. Таким образом, число умножений, требуемых для вычисления степени n, растет приблизительно так же быстро, как логарифм n по основанию 2. Процесс имеет степень роста θ(log(n)).

Точнее, количество требуемых умножений равно логарифму n по основанию 2 минус 1 и плюс количество единиц в двоичном представлении n. Это число всегда меньше, чем удвоенный логарифм n по основанию 2.
Произвольные константы k₁ и k₂ в определении порядка роста означают, что для логарифмического процесса основание, по которому берется логарифм, не имеет значения, так что все такие процессы описываются как θ(log(n)).

Если n велико, разница между порядком роста θ(log(n)) и θ(n) оказывается очень заметной. Например, fastExpt при n = 1000 требует всего 14 умножений. С помощью идеи последовательного возведения в квадрат можно построить также итеративный алгоритм, который вычисляет степени за логарифмическое число шагов, хотя, как это часто бывает с итеративными алгоритмами, его нельзя записать так же просто, как рекурсивный алгоритм.

UPD. Не рекурсивный алгоритм

def fastExp(b,n):
    def even(n):#проверка четности
        if n%2==0:
            return 1
        return 0
    a=1
    if not even(n):
        a=b
        n-=1
    while n!=1:
        b*=b
        n/=2
    b*=a
    return b

Результаты теста при вычислении 6⁹⁹ 100000 раз:

• Рекурсивный 2100004 function calls (1100004 primitive calls) in 15.029 CPU seconds
• Линейный 200004 function calls in 1.644 CPU seconds
• Встроенная функция pow в модуль math 100005 function calls in 0.600 CPU seconds

Так что используйте встроенную функцию, она написана на C!)

Используемая литература:

1. http://mitpress.mit.edu/sicp/