Реализация простого и быстрого возведения в степень на C/C++
Привет всем. Продолжаю потихоньку публиковать свои реализации известных всем и очень популярных алгоритмов, например, уже успел реализовать супер сложную быструю сортировку. На этот раз отклонюсь чуть ближе к математике и рассмотрю алгоритм быстрого возведения в степень, который часто(или даже скорее всегда) используется в стандартных библиотечных функциях возведениях.
Но прежде, чем начать, почему бы не реализовать обычное возведение? Правильно, нет причин себе в этом отказывать, поехали!
Функция возведения числа в степень
Методом «в лоб», пробежимся в цикле и перемножим число само на себя сколько нужно раз. Работает за O(deg) где deg степень.
Для возведения по модулю достаточно будет передать этот модуль в функцию и на каждой итерации брать результат по модулю.
Функция возведения числа в отрицательную степень
Небольшое улучшение, добавим возможность возводить число в отрицательную степень. Реализуется легко, изменяем возвращаемое значение и рассматриваем два случая: для положительной степени делаем все как обычно, а для отрицательной возвращаем 1 / result.
Функция быстрого возведения числа в степень
Ее еще называют бинарным возведением. Алгоритм построен на очевидной формуле
A n = (A n/2 ) 2 = A n/2 * A n/2
То есть для четного n можно получить результат выполнив всего log2n перемножений, что уже дает логарифмическую сложность. А в случае, когда n нечетно, приведем его к четному виду с помощью еще одной очевидной формулы
Реализация выглядит следующим образом.
Функция быстрого возведения в отрицательную степень
Можно реализовать воспользовавшись аналогичным приемом, как и в простом умножении — делим алгоритм на две ветки.
Заключение
Таким образом мы научились возводить число в степень с логарифмической скоростью, что пригодится для реализации умножения и деления больших чисел(кстати, сложение и вычитание уже готовы). А на сегодня у меня все, спасибо за внимание!
Как возвести 2 в степень i без pow [закрыт]
Хотите улучшить этот вопрос? Добавьте больше подробностей и уточните проблему, отредактировав это сообщение.
Закрыт 2 года назад .
Как возвести 2 в степень i. Запрещено использовать pow
Думаю, если автор вопроса имел в виду целое число i , притом не слишком большое, то обычно это делается одной операцией
Однако здесь нужно сделать много всяких проверок, зависящих от конкретной задачи. Например, если ожидаемый результат больше, чем позволяет разрядность типичных типов данных языка программирования. Если речь идет о больших i , то нужно применять длинную арифметику.
Если же i — дробное, то традиционно для этого используют несколько приёмов: редукция аргумента и последующий за ней метод Ньютона. Есть и другие варианты, но мне кажется, автору вопроса не это нужно.
С++ вычисляет степень числа без использования pow или цикла
Я начинающий пользователь C++, и мне дали задание написать функцию, которая вычисляет степень числа, но нам не разрешено использовать функцию pow или цикл.
Пользователь функции должен ввести основание и показатель степени в командном окне.
pow(x, y) можно записать как exp(y * log(x)) . Насколько я могу судить, это удовлетворяет ограничениям вопроса.
С реальными x и y , любая альтернатива тому сложна. Конечно, есть глупые альтернативы, использующие рекурсию для интеграла, y но использование рекурсии для линейных задач никогда не будет особенно хорошим подходом.
Затем вы пишете:
Затем вы улучшаете:
Последний алгоритм известен как двоичное возведение в степень.
И, наконец, вы изучаете шаблоны:
Редактировать. Оптимизация хвостовой рекурсии. Давайте посмотрим на ассемблерный код, сгенерированный для первой версии pow() без оптимизаций ( -O0 ):
Мы видим рекурсию call pow(double, unsigned int) .
Теперь давайте добавим некоторые оптимизации ( -O2 -ffast-math ):
Где рекурсивный вызов? Его больше нет! Компилятор использует оптимизацию хвостового вызова и преобразует рекурсивный вызов в простой цикл. Этот ассемблерный код эквивалентен этому C++:
Эта оптимизация невозможна без -ffast-math опции из-за неассоциативности умножения с плавающей запятой.