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

Число 1.0730088 было подобрано вручную для достижения наибольшей точности вычислений.

Алгоритм: Бинарное возведение в степень

Увеличение скорости: в среднем в ~7.5 раз, преимущество сохраняется до возведения чисел в степень 134217728 в C++/C# и 4096 в Java.
Погрешность: нет, но стоит отметить, что операция умножения не ассоциативна для чисел с плавающей точкой, т.е. 1.21 * 1.21 не то же самое, что 1.1 * 1.1 * 1.1 * 1.1, однако при сравнении со стандартными функциями погрешности, как уже сказано ранее, не возникает.
Ограничения: степень должна быть целым числом не меньше 0

double BinaryPower(double b, unsigned long long e) < double v = 1.0; while(e != 0) < if((e & 1) != 0) < v *= b; >b *= b; e >>= 1; > return v; >

Реализация в C# и Java

// C# double BinaryPower(double b, UInt64 e) < double v = 1d; while(e != 0) < if((e & 1) != 0) < v *= b; >b *= b; e >>= 1; > return v; >

// Java double BinaryPower(double b, long e) < double v = 1d; while(e >0) < if((e & 1) != 0) < v *= b; >b *= b; e >>= 1; > return v; >

Широко известный алгоритм для возведения любого числа в целую степень с абсолютной точностью. Принцип действия прост: есть целая степень e, чтобы получить число b в этой степени нужно возвести это число во все степени 1, 2, 4, … 2 n (в коде этому соответствует b *= b), каждый раз сдвигая биты e вправо (e >>= 1) пока оно не равно 0 и тогда, когда последний бит e не равен нулю ((e & 1) != 0), домножать результат v на полученное b.
Пример: возвести 2 в степень 5.
v = 1, e = 5 = 101₂, b = 2
Шаги цикла:

1. e = 101₂ - последний 1 → v *= b → v = 2
   b *= b → b = 4
   e >>= 1 → e = 10₂ = 2
2. e = 10₂ - последний 0 → пропускаем
   b *= b → b = 16
   e >>= 1 → e = 1
3. e = 1₂ - последний 1 → v *= b → v = 32
   .
   e = 0 → выход из цикла

Результат: v = 32, что и есть 2 5 .

Алгоритм: "Делящая быстрая степень"

Увеличение скорости: в ~3.5 раз
Погрешность: ~13%
Примечание: в коде ниже присутствуют проверки для особых входных данных. Без них код работает всего на 10% быстрее, но погрешность возрастает в десятки раз (особенно при использовании отрицательных степеней).

double FastPowerDividing(double b, double e) < if(b == 1.0 || e == 0.0) < return 1.0; >double eAbs = fabs(e); double el = ceil(eAbs); double basePart = OldApproximatePower(b, eAbs / el); double result = BinaryPower(basePart, (unsigned long long)el); if(e < 0.0) < return 1.0 / result; >return result; >

Реализация в C# и Java

// C# double FastPowerDividing(double b, double e) < if(b == 1d || e == 0d) < return 1d; >var eAbs = Math.Abs(e); var el = Math.Ceiling(eAbs); var basePart = OldApproximatePower(b, eAbs / el); var result = BinaryPower(basePart, (UInt64)el); if(e < 0d) < return 1d / result; >return result; >

// Java double FastPowerDividing(double b, double e) < if(b == 1d || e == 0d) < return 1d; >var eAbs = Math.abs(e); var el = Math.ceil(eAbs); var basePart = OldApproximatePower(b, eAbs / el); var result = BinaryPower(basePart, (long)el); if(e < 0d) < return 1d / result; >return result; >

Узнав о методе аппроксимации чисел в степенях от -1 до 1 и о бинарном методе, мне захотелось объединить их для создания функции, которая могла бы быстро возводить число в любую степень. Для этого я придумал следующую формулу:

Мы разбиваем степень на две части: e / el, которая всегда меньше или равна 1, и el, которая является целым числом. Теперь для расчета x^(e / el) мы можем использовать “старую” аппроксимацию, а для x^el - бинарную степень.Таким образом, объединяя этих два узкоспециализированных метода, мы получили универсальный метод. Но эту идею можно реализовать по-другому.

Алгоритм: "Дробная быстрая степень"

Увеличение скорости: в ~4.4 раза
Погрешность: ~0.7%

double FastPowerFractional(double b, double e) < if(b == 1.0 || e == 0.0) < return 1.0; >double absExp = fabs(e); unsigned long long eIntPart = (long long)absExp; double eFractPart = absExp - eIntPart; double result = OldApproximatePower(b, eFractPart) * BinaryPower(b, eIntPart); if(e < 0.0) < return 1.0 / result; >return result; >

Реализация в C# и Java

// C# double FastPowerFractional(double b, double e) < if(b == 1d || e == 0d) < return 1d; >double absExp = Math.Abs(e); UInt64 eIntPart = (UInt64)absExp; double eFractPart = absExp - eIntPart; double result = OldApproximatePower(b, eFractPart) * BinaryPower(b, eIntPart); if(e < 0d) < return 1d / result; >return result; >

// Java double FastPowerFractional(double b, double e) < if(b == 1d || e == 0d) < return 1d; >double absExp = Math.abs(e); long eIntPart = (long)absExp; double eFractPart = absExp - eIntPart; double result = OldApproximatePower(b, eFractPart) * BinaryPower(b, eIntPart); if(e < 0d) < return 1d / result; >return result; >

По сути, любое число состоит из суммы двух частей: целой и дробной. Целую можно использовать для возведения основания в степень при помощи бинарного возведения, а дробную - при помощи “старой” аппроксимации.

В результате получаем следующую формулу:

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

Алгоритм: "Другая аппроксимация"

Увеличение скорости: в ~9 раз
Погрешность: Ограничения: точность стремительно падает при повышении абсолютного значения степени и остается приемлемой в промежутке [-10, 10]

double AnotherApproximatePower(double a, double b) < union < double d; int x[2]; >u = < a >; u.x[1] = (int)(b * (u.x[1] - 1072632447) + 1072632447); u.x[0] = 0; return u.d; >

Реализация в C# и Java

double AnotherApproxPower(double a, double b) < int tmp = (int)(BitConverter.DoubleToInt64Bits(a) >> 32); int tmp2 = (int)(b * (tmp - 1072632447) + 1072632447); return BitConverter.Int64BitsToDouble(((long)tmp2)

double AnotherApproxPower(double a, double b) < int tmp = (int)(Double.doubleToLongBits(a) >> 32); int tmp2 = (int)(b * (tmp - 1072632447) + 1072632447); return Double.longBitsToDouble(((long)tmp2)

Про историю этого алгоритма я ничего не знаю, я просто нашёл его тут: Optimized pow() approximation for Java, C / C++, and C#. Возможно, если использовать его в “делящей–” и “дробной быстрых степенях" вместо “старой” аппроксимации, можно достигнуть лучшей точности ценой немного меньшей скорости.

Сравнение производительности

Сравнение производительности производилось следующим образом: генерируем 500000 чисел-оснований в промежутке от 0.0 до 99999.0 и 500000 чисел-степеней в промежутке от A до B. Запоминаем текущее время, запускаем цикл на 500000 итераций, вычисляем значение основания в степени через функцию f и результат суммируем в calculationResult. По окончанию цикла снова замеряем время, разница во времени и есть время выполнения. Данная процедура повторяется 20 раз, конечный результат - усредненный за все 20 тестов.

Псевдокод сравнения производительности в C++:

(long long iterationsCount = 500000, double* bases, double* exps) double calculationResult = 0.0; double* base = bases; double* exp = exps; double* baseEnd = base + iterationsCount; auto start = std::chrono::high_resolution_clock::now(); while(base < baseEnd) < calculationResult += f(*base++, *exp++); >auto finish = std::chrono::high_resolution_clock::now(); auto time = std::chrono::duration_cast(finish - start).count();

Аналогично измерялась скорость в C# и Java. В репозитории проекта можно посмотреть на реальный код для сравнения производительности в C++, C# и Java.

Тесты производились в каждом языке для степеней в промежутках [-10.5, 0], [0, 2], [0, 10.5], [0, 25.75], [0, 55.5]. Прирост скорости каждого метода по сравнению со стандартным в каждом языке для каждого сета степеней изображен на графиках ниже:

Рассмотреть подробнее результаты тестов можно посмотреть в этой таблице.

Тесты проводились на i5-10300H, 19.8 DDR4 GB usable RAM, 64-битная платформа.
C++: MSVC + /O2 + /Oi + /Ot
C#: optimize code

Сравнение точности

Для рассчитывания точности я возводил очередное число в определенную степень стандартным и одним из нестандартных способами, потом делил большее из полученных чисел на меньшее, складывал все эти отношения вместе, а в конце делил их на количество сравнений. Так и получалось значение погрешности.
Основания и степени генерировались также, как и в алгоритме сравнения производительности.
Для более гибкого и удобного тестирования я создал Blazor страницу, на которой можно построить графики реальных и полученных одним из методов значений чисел, лежащих в заданном промежутке и возведенных в указанную степень:

Ниже на этой же странице можно самим провести сравнение точности каждого метода для всех степеней, лежащих в заданном промежутке:

Вывод

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

Код всего проекта доступен на гитхабе. Там вы найдете и реализации всех алгоритмов в трех языках, и программы для сравнения точности для каждого языка, и код сайта.

Спасибо за внимание. Надеюсь эта статья поможет сделать ваш код немного быстрее.

• ускорение кода
• приближëнные алгоритмы
• приближённые вычисления
• приближенное решение
• алгоритмы
• оптимизация кода
• оптимизация программ

Возведение в степень на C#: 3 способа

В программировании на C# возведение в степень – это обычная задача, которую можно решать разными способами. В этой статье мы рассмотрим основные методы возведения числа в степень, начиная с основ и заканчивая более продвинутыми техниками. Мы также познакомимся с некоторыми математическими аспектами и лучшими практиками программирования.

Что такое возведение в степень?

Прежде всего, разберёмся, что такое возведение в степень. Возведение в степень — это математическая операция, в которой число (основание) умножается само на себя определённое количество раз (показатель степени). Например, (2^3) означает (2 \times 2 \times 2 = 8).

Основной метод: Math.Pow

Самый простой и распространённый способ возвести число в степень в C# — использовать метод Math.Pow . Этот метод принимает два аргумента: основание и показатель степени. Оба аргумента должны быть типа double .

Пример использования Math.Pow

double baseNumber = 2; double exponent = 3; double result = Math.Pow(baseNumber, exponent); Console.WriteLine(result); // Вывод: 8 

Преимущества и недостатки Math.Pow

Преимущества:

1. Простота использования.
2. Высокая точность.

Недостатки:

1. Основание и показатель степени должны быть double , что может привести к необходимости преобразования типов.
2. В некоторых случаях может быть медленнее специализированных алгоритмов.

Возведение в степень с помощью цикла

Если вы хотите использовать целые числа без преобразования типов, можно возвести число в степень с помощью цикла.

Пример с циклом

int baseNumber = 2; int exponent = 3; int result = 1; for (int i = 0; i < exponent; i++) < result *= baseNumber; > Console.WriteLine(result); // Вывод: 8 

Плюсы и минусы

Плюсы:

1. Работает с целыми числами.
2. Легко понять и реализовать.

Читайте так же Нахождение Факториала в C#: Простое Руководство

Минусы:

1. Может быть неэффективным при больших показателях степени.

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

Бинарное возведение в степень — это более эффективный способ вычисления больших степеней. Оно разбивает степень на степени двойки, что уменьшает количество необходимых умножений.

Пример бинарного возведения в степень

long BinaryPow(long baseNumber, long exponent) < long result = 1; while (exponent > 0) < if ((exponent & 1) == 1) result *= baseNumber; baseNumber *= baseNumber; exponent >>= 1; > return result; > Console.WriteLine(BinaryPow(2, 3)); // Вывод: 8 

Преимущества:

1. Эффективность при больших показателях степени.
2. Полезно в алгоритмах, где требуются быстрые вычисления степени.

Недостатки:

1. Сложнее для понимания и реализации.

Заключение

В этой статье мы рассмотрели разные способы возведения числа в степень в C#. Метод Math.Pow идеален для простых задач и когда необходима высокая точность. Циклы хороши для целых чисел и простых операций. Бинарное возведение в степень подходит для эффективных расчётов в более сложных и высокопроизводительных алгоритмах.

Используйте подходящий способ в зависимости от ваших нужд и контекста задачи. Помните, что выбор правильного метода — это важная часть оптимизации и качества вашего кода.

Степень в C, C++ и С#: как возвести число в любую степень, побитовые операции

Функция pow является частью библиотеки cmath, и поэтому её заголовок обязательно должен быть подключен в секции #include, как это сделано в примере. Также cout и cin являются частью библиотеки iostream и она у нас тоже подключена.

Давайте рассмотрим еще несколько примеров:

Пример, в котором степень и число задается пользователем:

#include #include using namespace std; int main()< setlocale(0, ""); double a, b; cout > a; cout > b; cout int pow2(int n)

Пояснение: возведение "2" в степень "n" реализуется с помощью сдвига, в общем случае:

• сдвиг влево (в сторону старших разрядов) реализует умножение на два,
• сдвиг вправо (в сторону младших разрядов) реализует деление на два.

Число n должно быть целочисленным.

Пример, в котором не используется функция pow()

#include using namespace std; int main()< int n, a; cin>>n>>a; int tmp = n; if (a == 0) < coutfor(int i = 1; i < a; i++) < n*=tmp; >cout

В этом примере пользователь вводит числа n и a . Где n - число, которое возводится в степень, a - степень числа. В цикле for, мы умножаем число n на само себя a раз и в результате получаем степень.

Напишем свою функцию для возведение числа в степень:

double raiseToPow(double x, int power) < double result; int i; result =1.0; for (i=1, i<=power;i++) < result = result*x; >return(result); >

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

Свежие записи

• SQL UPDATE: примеры обновления строк в таблице
• PHP: substr и мощные альтернативы, чтобы вырезать часть строки
• Степень в C, C++ и С#: как возвести число в любую степень, побитовые операции
• Скачать ShowKeyPlus: ссылка на последнюю официальную версию, скачивание, установка
• Как создать файл в Linux: 12 способов
• SQL INSERT INTO: примеры вставки строк в таблицу БД MySQL
• PHP: str_replace - замена или удаление подстроки в строке
• Функция date() в php: распространенные форматы, примеры, советы
• cURL в PHP: примеры POST, GET запросов с headers, cookie, JSON и многопоточностью
• JSON в PHP: примеры json_encode, json_decode, работа с кириллицей и utf-8
• Файл gitignore - примеры и документация
• Сортировка массивов в php: ksort, asort и прочие sort'ы
• jQuery onclick: как выполнить код при клике на кнопку
• 500 Internal Server Error - в чем причина?
• SMTP от Yandex: как отправить письма из PHP - пример настроек
• No such file or directory - в чем причина?
• Как получить первый элемент массива в php
• Cтроку в массив по разделителю в PHP: explode, str_split, strtok - что выбрать?
• 301 редирект на https с www через htaccess
• Как в php добавить к массиву другой массив?
• 301 редирект на https без www с помощью htaccess
• Регулярные выражения в PHP
• PHP json_decode — как декодировать результат в массив?
• Yii2 ActiveRecord шпаргалка по составлению запросов
• Поиск подстроки в строке с помощью PHP
• Отправка почты на php
• Как подключить php код в html
• Конвертировать массив в строку при помощи PHP
• Подключение одного php файла в другой
• Подборка ссылок для веб-разработчика
• Проблема с кириллицей в PHPWord

Реализация простого и быстрого возведения в степень на 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; > >

Заключение

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