Дай 10 !)

среда, 20 апреля 2011 г.

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

Рассмотрим задачу возведения числа в степень. Нам нужна процедура, которая, приняв в качестве аргумента основание b и положительное целое значение степени n, возвращает bn. Один из способов получить желаемое — через рекурсивное определение
которое прямо переводится в процедуру:
*-Нравится статья? Кликни по рекламе! :)



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) памяти.
Можно вычислять степени за меньшее число шагов, если использовать последовательное возведение в квадрат. Например, вместо того, чтобы вычислять b8 в виде:
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, растет логарифмически как по используемой памяти, так и по количеству шагов. Чтобы увидеть это, заметим, что вычисление b2n с помощью этого алгоритма требует всего на одно умножение больше, чем вычисление bn. Следовательно, размер степени, которую мы можем вычислять, возрастает примерно вдвое с каждым следующим умножением, которое нам разрешено делать. Таким образом, число умножений, требуемых для вычисления степени n, растет приблизительно так же быстро, как логарифм n по основанию 2. Процесс имеет степень роста θ(log(n)).

Точнее, количество требуемых умножений равно логарифму n по основанию 2 минус 1 и плюс количество единиц в двоичном представлении n. Это число всегда меньше, чем удвоенный логарифм n по основанию 2.
Произвольные константы k1 и k2 в определении порядка роста означают, что для логарифмического процесса основание, по которому берется логарифм, не имеет значения, так что все такие процессы описываются как θ(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

Результаты теста при вычислении 699 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/

9 комментариев:

  1. Качественный обзор!
    Не знаю насколько python любит рекурсию, поэтому возник вопрос нерекурсивная реализация даст заметной прибавки в производительности, если будет необходимо вычислять степень много раз?

    ОтветитьУдалить
    Ответы
    1. Если вычислять степень много раз, то можно дойти до максимальной глубины рекурсии и словить exception

      Удалить
  2. Спасибо :)
    Как я писал в "Линейные рекурсия и итерация. Чего не хватает Python" в Python не реализована хвостовая рекурсия, поэтому все как у всех - стек рекурсий.
    Добавил не рекурсивный алгоритм и сравнение. В самых первых статьях про вычисление факториала и чисел Фибоначчи, я уже показал, что рекурсивные алгоритмы проигрывают линейным. Там же описал почему.
    В статье "Динамическое программирование: размен денег" попытался показать применение рекурсии в программировании.

    ОтветитьУдалить
  3. Приведенная версия итеративного алгоритма не работает со степенями 0 и 1. В обоих случаях цикл while оказывается бесконечным.

    ОтветитьУдалить
  4. will wind up spending more good currency exchange rate. Good news about V-Bucks getting used to wash funds is anything but surprising, given that crooks are treating Fortnite to make money in a mind-boggling variety of methods. salsaroc.com How To Get V Bucks For Free

    ОтветитьУдалить
  5. вместо
    while n!=1:
    b*=b
    n/=2
    надо
    while n!=1:
    b*=b
    n//=2

    ОтветитьУдалить
  6. Нерекурсивный алгоритм работает не корректно.

    При возведении 2 в 13 степень выдает 512, если исправить n/=2 на n//=2, иначе циклится

    Вот пример рабочего нерекурсивного алгоритма:
    def exp(x,a):
    n=bin(a)[2:]
    x_n = 1
    for i in n:
    if int(i) == 0:
    x_n = x_n**2
    else:
    x_n = x*(x_n**2)
    return(x_n)
    источник: https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B1%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B3%D0%BE_%D0%B2%D0%BE%D0%B7%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D1%8F_%D0%B2_%D1%81%D1%82%D0%B5%D0%BF%D0%B5%D0%BD%D1%8C

    ОтветитьУдалить