Как возвести в степень в c

Реализация простого и быстрого возведения в степень на C/C++

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

Но прежде, чем начать, почему бы не реализовать обычное возведение? Правильно, нет причин себе в этом отказывать, поехали!

Функция возведения числа в степень

Методом «в лоб», пробежимся в цикле и перемножим число само на себя сколько нужно раз. Работает за O(deg) где deg степень.

//Возводит число num в степень deg простым циклом long power(long num, long deg) < long result = 1; for(long i = 0; i < deg; i++) < result *= num; >return result; >

Для возведения по модулю достаточно будет передать этот модуль в функцию и на каждой итерации брать результат по модулю.

Функция возведения числа в отрицательную степень

Небольшое улучшение, добавим возможность возводить число в отрицательную степень. Реализуется легко, изменяем возвращаемое значение и рассматриваем два случая: для положительной степени делаем все как обычно, а для отрицательной возвращаем 1 / result.

//Возводит число num в степень deg простым циклом(степень может быть отрицательной) double power(long num, long deg) < double result = 1; if(deg < 0) < deg = -deg; for(long i = 0; i < deg; i++) < result *= num; >return 1 / result; > else < for (long i = 0; i < deg; i++) < result *= num; >return result; > >

Функция быстрого возведения числа в степень

Ее еще называют бинарным возведением. Алгоритм построен на очевидной формуле

A n = (A n/2 ) 2 = A n/2 * A n/2

То есть для четного n можно получить результат выполнив всего log₂n перемножений, что уже дает логарифмическую сложность. А в случае, когда n нечетно, приведем его к четному виду с помощью еще одной очевидной формулы

Реализация выглядит следующим образом.

//Быстрое возведение числа num в степень deg long powerFast(long num, long deg) < long result = 1; while(deg) < if (deg % 2 == 0) < deg /= 2; num *= num; >else < deg--; result *= num; >> return result; >

Функция быстрого возведения в отрицательную степень

Можно реализовать воспользовавшись аналогичным приемом, как и в простом умножении — делим алгоритм на две ветки.

//Быстрое возведение числа num в степень deg(в том числе может быть отрицательной) double powerFast(long num, long deg) < double result = 1; if(deg < 0) < deg = -deg; while(deg) < if (deg % 2 == 0) < deg /= 2; num *= num; >else < deg--; result *= num; >> return 1 / result; > else < while(deg) < if (deg % 2 == 0) < deg /= 2; num *= num; >else < deg--; result *= num; >> return result; > >

Заключение

Таким образом мы научились возводить число в степень с логарифмической скоростью, что пригодится для реализации умножения и деления больших чисел(кстати, сложение и вычитание уже готовы). А на сегодня у меня все, спасибо за внимание!

Как возвести число в степень

((a + b + c)*pi)^2 Как возвести в степень это выражение на языке СИ?

Отслеживать

задан 22 мар 2020 в 15:15

23 3 3 бронзовых знака

Умножить на себя же. Вариант хуже — использовать функцию pow .

22 мар 2020 в 15:17

Чем же плоха функция pow?

22 мар 2020 в 15:17

По нынешним временам для float что умножение, что pow отправляются в сопроцессор с плавающей точкой. А вот что быстрее делается в сопроцессоре с плавающей точкой — умножение или pow это вопрос интересный.

22 мар 2020 в 15:25

Хотя бы потому что в общем случае это вызов функции. Вариант с целочисленной степенью в стандарте вроде бы отсутствует, так что опять же в общем случае это будет вычисление менее эффективное.