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

Ускоряем pow

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

Сравнить точность алгоритмов можно прямо сейчас на этой странице.

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

1%, а иногда и вовсе без неё.

Содержание

Алгоритмы (5 штук)

На повестке дня у нас есть 5 алгоритмов: «Старая аппроксимация», «Бинарная степень», «Делящая быстрая степень», «Дробная” быстрая степень» и «Другая” аппроксимация».
Названия алгоритмам я придумал сам (за исключением бинарной степени), так как нигде не нашёл официальных версий, но вы можете называть их иначе.

Для расчета прироста скорости и погрешности будем сравнивать эти методы со стандартными функциями pow, Math.Pow и Math.pow в C++, C# и Java соответственно. О том, как производилось сравнение, будет сказано в частях “Сравнение производительности” и “Сравнение точности”.

Алгоритм: «Старая аппроксимация»

Увеличение скорости: в

11 раз
Погрешность: <2%
Ограничения: приемлемая точность только для степеней от -1 до 1

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

Этот метод основан на алгоритме, использованном в игре Quake III Arena 2005 года. Он возводил число x в степень -0.5, т.е. находил значение:

Разработчики для этого написали такую функцию

Узнал я об этом методе из статьи «Магическая константа» 0x5f3759df. В ней подробно объясняется как работает этот код и как его можно улучшить для работы с любой степенью и double’ми вместо float’ов. В моих кодах также есть магическая константа 4606853616395542500L. Нашёл я её по следующей формуле (она описана в статье выше):

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

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

Увеличение скорости: в среднем в

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

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

Широко известный алгоритм для возведения любого числа в целую степень с абсолютной точностью. Принцип действия прост: есть целая степень 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
Шаги цикла:

e = 101₂ — последний 1 → v *= b → v = 2
b *= b → b = 4
e >>= 1 → e = 10₂ = 2

e = 10₂ — последний 0 → пропускаем
b *= b → b = 16
e >>= 1 → e = 1

e = 1₂ — последний 1 → v *= b → v = 32
.
e = 0 → выход из цикла

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

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

Увеличение скорости: в

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

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

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

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

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

Увеличение скорости: в

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

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

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

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

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

Увеличение скорости: в

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

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

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

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

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

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

Аналогично измерялась скорость в 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 страницу, на которой можно построить графики реальных и полученных одним из методов значений чисел, лежащих в заданном промежутке и возведенных в указанную степень:

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

Вывод

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

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

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

Долой калькулятор: 12 простых трюков, которые помогут вам быстро считать

Как бы мы ни хотели это признавать, учителя были правы: математика нужна каждому из нас. Но далеко не всем дается ловкое жонглирование числами. Тогда на помощь приходят легко запоминающиеся математические приемы – настоящее спасение, когда под рукой, как назло, нет калькулятора.

Ниже вы найдете 12 способов быстрых вычислений для всех, кто далек от точных наук.

1. Быстрое вычисление 20%

Представим, что границы вновь открыли и первым делом вы отправились в США. А там принято оставлять на чай. Обычно размер чаевых составляет 15-20% от суммы вашего заказа.

По словам Кейт Сноу, автора серии книг The Math Facts That Stick, чтобы быстро вычислить 20% от суммы, вам нужно просто разделить число в чеке на 5.

Например, вы поели на 85 долларов. Разделите 85 на 5, и у вас получится 17 долларов – чаевые, которые вы должны оставить официанту.

2. Умножение двузначных чисел на 11

Умножить число на 11 очень легко с помощью хитрого трюка от math.hmc.edu. Просто сложите две цифры и поместите полученную сумму в середину числа.

Например, вы умножаете 25 на 11. Если сложить 2 и 5, получится 7. Теперь расположите 7 между 2 и 5, чтобы найти окончательный ответ – 275.

3. Быстрое удвоение

Чтобы удвоить большое число, умножьте каждую цифру на 2 и сложите их между собой. Кейт Сноу предлагает начинать слева – так будет легче.

«Чтобы удвоить, к примеру, 147, начните с разряда сотен. Если умножить 100 на 2, получится 200. 40 на 2 – 80. 7 на 2 – 14. Теперь сложите числа между собой (200 + 80 + 14), и вы получите 294», – объясняет Сноу.

4. Умножение чисел, которые оканчиваются на ноль

Примеры с большими пугающими числами, которые оканчиваются на ноль, тоже легко решить с помощью специального приема. Согласно education.cu-portland.edu, нужно просто «вычеркнуть» нули из примера, а в конце вновь их добавить.

Если вы умножаете 600 на 400, уберите все нули и перемножьте 6 на 4. Получится 24. Затем подсчитайте общее количество нулей в исходном уравнении и припишите их к полученному значению. Так как в нашем примере было четыре нуля, то ответ будет равен 240000.

5. Умножение на 9

Если вам так и не удалось выучить таблицу умножения – не переживайте. По словам Сноу, чтобы легко умножить число на 9, нужно умножить его на 10 и вычесть исходное число из полученного значения.

Например, вам нужно умножить 9 на 23. Для этого умножаем 23 на 10 и получаем 230. А затем вычитаем из него 23, чтобы получить окончательный ответ – 207.

6. Деление на 10, 100 или 1000

Разделить число на 10 проще простого – согласно Сноу, «нужно просто переместить десятичный знак на одну позицию влево от исходного числа, чтобы найти ответ».

Для деления на 100 применим тот же метод, за исключением одного – нужно переместить десятичный разряд на две позиции левее исходного числа. Что касается деления на 1000, просто переместите десятичный знак на три позиции влево.

Например, если вы делите 42,94 на 10, вы просто перемещаете десятичный знак на одну позицию влево и получаете 4,294.

7. Умножение на 10, 100 или 1000

Здесь все работает с точностью до наоборот. Чтобы умножить число на 10, переместите десятичный знак на одну позицию вправо. На 100 – на две позиции. На 1000 – на три позиции.

Например, если вам нужно умножить 366,78 на 100, передвиньте десятичный знак на две цифры вправо, чтобы получить ответ 36678.

8. Преобразование периодической десятичной дроби в обыкновенную

Согласно businessinsider.com, нужно выполнить всего 3 шага, чтобы легко превратить бесконечную десятичную дробь в обыкновенную, с числителем и знаменателем.

• Шаг 1. Найдите повторяющиеся цифру или число. Например, у 0,636363 это будет 63.
• Шаг 2. Определите, сколько разрядов в этом числе. В нашем случае у 63 – два разряда.
• Шаг 3. Разделите повторяющееся число на число с таким же количеством разрядов, которое будет состоять из одних девяток – в данном случае 99. Получим 63/99. Теперь сократим ее и получим 7/11 – наш ответ.

9. Умножение на 25

Умножать на 25 не так уж и сложно, если представлять число в виде дроби 100/4. В этом случае все, что вам нужно сделать, это разделить число на 4 и умножить на 100.

Например, вам нужно умножить 84 на 25. Сначала делим 84 на 4 – получаем 21, а потом умножаем значение выражения на 100. Ответ: 2100.

10. Возведение чисел, оканчивающихся на 5, в квадрат

«Этот математический трюк подразумевает 2 шага», – объясняет Сноу. Чтобы возвести в квадрат число, которое оканчивается на пять, возьмите первую цифру числа и умножьте ее на себя. После этого прибавьте к полученному результату первую цифру и припишите к ответу 25. Кружится голова? Разберем на примере.

Если вы умножаете 35 на 35, сначала умножьте 3 на 3 – получится 9, – и прибавьте 3 к ответу – получится 12. Теперь припишите 25 в конец найденного числа, и вы найдете окончательный ответ: 1225.

11. Вычитание путем сложения

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

«Вместо того чтобы пытаться вычесть 327 из 334, представьте это в виде суммы: мол, сколько нужно добавить к 327, чтобы получить 334?» – объясняет Сноу.

12. Сложение чисел, оканчивающихся на 99

Если вы пытаетесь прикинуть, во сколько обойдутся продукты, стоимость которых заканчивается на 99, – калькулятор не нужен. Все, что необходимо сделать, – прибавить 100 вместо 99, а потом вычесть единицу.

Сноу объясняет этот процесс на примере 176 + 199 = 375. «Если к 176 мы прибавим 200, то получим 376, – говорит эксперт. – Поскольку вы добавили на единицу больше, чем вам нужно, вычтите ее из 376, чтобы найти правильный ответ: 375».

Как быстро вычислить степень числа

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

Понятие возведения в степень

Начнем с формулирования базовых определений.

Возведение в степень — это вычисление значения степени некоторого числа.

То есть слова "вычисление значение степени" и "возведение в степень" означают одно и то же. Так, если в задаче стоит "Возведите число 0 , 5 в пятую степень", это следует понимать как "вычислите значение степени ( 0 , 5 ) 5 .

Теперь приведем основные правила, которым нужно придерживаться при таких вычислениях.

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

Вспомним, что такое степень числа с натуральным показателем. Для степени с основанием a и показателем n это будет произведение n -ного числа множителей, каждый из которых равен a . Это можно записать так:

Чтобы вычислить значение степени, нужно выполнить действие умножения, то есть перемножить основания степени указанное число раз. На умении быстро умножать и основано само понятие степени с натуральным показателем. Приведем примеры.

Условие: возведите — 2 в степень 4 .

Решение

Используя определение выше, запишем: ( − 2 ) 4 = ( − 2 ) · ( − 2 ) · ( − 2 ) · ( − 2 ) . Далее нам нужно просто выполнить указанные действия и получить 16 .

Возьмем пример посложнее.

Вычислите значение 3 2 7 2

Решение

Данную запись можно переписать в виде 3 2 7 · 3 2 7 . Ранее мы рассматривали, как правильно умножать смешанные числа, упомянутые в условии.

Выполним эти действия и получим ответ: 3 2 7 · 3 2 7 = 23 7 · 23 7 = 529 49 = 10 39 49

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

Выполните возведение в квадрат числа π .

Решение

Для начала округлим его до сотых. Тогда π 2 ≈ ( 3 , 14 ) 2 = 9 , 8596 . Если же π ≈ 3 . 14159 , то мы получим более точный результат: π 2 ≈ ( 3 , 14159 ) 2 = 9 , 8695877281 .

Отметим, что необходимость высчитывать степени иррациональных чисел на практике возникает сравнительно редко. Мы можем тогда записать ответ в виде самой степени ( ln 6 ) 3 или преобразовать, если это возможно: 5 7 = 125 5 .

Отдельно следует указать, что такое первая степень числа. Тут можно просто запомнить, что любое число, возведенное в первую степень, останется самим собой:

Это понятно из записи .

От основания степени это не зависит.

Так, ( − 9 ) 1 = − 9 , а 7 3 , возведенное в первую степень, останется равно 7 3 .

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

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

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

Теперь посмотрим, как правильно возводить в нулевую степень. При основании, которое отличается от нуля, это вычисление всегда дает на выходе 1 . Ранее мы уже поясняли, что 0 -я степень a может быть определена для любого действительного числа, не равного 0 , и a 0 = 1 .

5 0 = 1 , ( — 2 , 56 ) 0 = 1 2 3 0 = 1

0 0 — не определен.

У нас остался только случай степени с целым отрицательным показателем. Мы уже разбирали, что такие степени можно записать в виде дроби 1 a z , где а — любое число, а z — целый отрицательный показатель. Мы видим, что знаменатель этой дроби есть не что иное, как обыкновенная степень с целым положительным показателем, а ее вычислять мы уже научились. Приведем примеры задач.

Возведите 2 в степень — 3 .

Решение

Используя определение выше, запишем: 2 — 3 = 1 2 3

Подсчитаем знаменатель этой дроби и получим 8 : 2 3 = 2 · 2 · 2 = 8 .

Тогда ответ таков: 2 — 3 = 1 2 3 = 1 8

Возведите 1 , 43 в степень — 2 .

Решение

Переформулируем: 1 , 43 — 2 = 1 ( 1 , 43 ) 2

Вычисляем квадрат в знаменателе: 1,43·1,43. Десятичные дроби можно умножить таким способом:

В итоге у нас вышло ( 1 , 43 ) — 2 = 1 ( 1 , 43 ) 2 = 1 2 , 0449 . Этот результат нам осталось записать в виде обыкновенной дроби, для чего необходимо умножить ее на 10 тысяч (см. материал о преобразовании дробей).

Ответ: ( 1 , 43 ) — 2 = 10000 20449

Отдельный случай — возведение числа в минус первую степень. Значение такой степени равно числу, обратному исходному значению основания: a — 1 = 1 a 1 = 1 a .

Пример: 3 − 1 = 1 / 3

9 13 — 1 = 13 9 6 4 — 1 = 1 6 4 .

Как возвести число в дробную степень

Для выполнения такой операции нам потребуется вспомнить базовое определение степени с дробным показателем: a m n = a m n при любом положительном a , целом m и натуральном n .

Таким образом, вычисление дробной степени нужно выполнять в два действия: возведение в целую степень и нахождение корня n -ной степени.

У нас есть равенство a m n = a m n , которое, учитывая свойства корней, обычно применяется для решения задач в виде a m n = a n m . Это значит, что если мы возводим число a в дробную степень m / n , то сначала мы извлекаем корень n -ной степени из а , потом возводим результат в степень с целым показателем m .

Проиллюстрируем на примере.

Вычислите 8 — 2 3 .

Решение

Способ 1. Согласно основному определению, мы можем представить это в виде: 8 — 2 3 = 8 — 2 3

Теперь подсчитаем степень под корнем и извлечем корень третьей степени из результата: 8 — 2 3 = 1 64 3 = 1 3 3 64 3 = 1 3 3 4 3 3 = 1 4

Способ 2. Преобразуем основное равенство: 8 — 2 3 = 8 — 2 3 = 8 3 — 2

После этого извлечем корень 8 3 — 2 = 2 3 3 — 2 = 2 — 2 и результат возведем в квадрат: 2 — 2 = 1 2 2 = 1 4

Видим, что решения идентичны. Можно пользоваться любым понравившимся способом.

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

Возведите 44 , 89 в степень 2 , 5 .

Решение

Преобразуем значение показателя в обыкновенную дробь — 44 , 89 2 , 5 = 49 , 89 5 2 .

А теперь выполняем по порядку все действия, указанные выше: 44 , 89 5 2 = 44 , 89 5 = 44 , 89 5 = 4489 100 5 = 4489 100 5 = 67 2 10 2 5 = 67 10 5 = = 1350125107 100000 = 13 501 , 25107

Ответ: 13 501 , 25107 .

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

Отдельно остановимся на степени с нулевым основанием и дробным показателем. Выражению вида 0 m n можно придать такой смысл: если m n > 0 , то 0 m n = 0 m n = 0 ; если m n 0 нуль остается не определен. Таким образом, возведение нуля в дробную положительную степень приводит к нулю: 0 7 12 = 0 , 0 3 2 5 = 0 , 0 0 , 024 = 0 , а в целую отрицательную — значения не имеет: 0 — 4 3 .

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

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

Если нам нужно вычислить значение степени a с иррациональным показателем a , то мы берем десятичное приближение показателя и считаем по нему. Результат и будет приближенным ответом. Чем точнее взятое десятичное приближение, тем точнее ответ. Покажем на примере:

Вычислите приближенное значение 21 , 174367 .

Решение

Ограничимся десятичным приближением a n = 1 , 17 . Проведем вычисления с использованием этого числа: 2 1 , 17 ≈ 2 , 250116 . Если же взять, к примеру, приближение a n = 1 , 1743 , то ответ будет чуть точнее: 2 1 , 174367 . . . ≈ 2 1 , 1743 ≈ 2 , 256833 .

Ещё Ричард Фейнман в книге «Вы конечно шутите, мистер Фейнман!» поведал несколько приёмов устного счёта. Хотя это очень простые трюки, они не всегда входят в школьную программу.

Например, чтобы быстро возвести в квадрат число X около 50 (50 2 = 2500), нужно вычитать/прибавлять по сотне на каждую единицы разницы между 50 и X, а потом добавить разницу в квадрате. Описание звучит гораздо сложнее, чем реальное вычисление.

52 2 = 2500 + 200 + 4
47 2 = 2500 – 300 + 9
58 2 = 2500 + 800 + 64

Молодого Фейнмана научил этому трюку коллега-физик Ханс Бете, тоже работавший в то время в Лос-Аламосе над Манхэттенским проектом.

Ханс показал ещё несколько приёмов, которые использовал для быстрых вычислений. Например, для вычисления кубических корней и возведения в степень удобно помнить таблицу логарифмов. Это знание очень упрощает сложные арифметические операции. Например, вычислить в уме примерное значение кубического корня из 2,5. Фактически, при таких вычислениях в голове у вас работает своеобразная логарифмическая линейка, в которой сложение и деление чисел заменяется сложением и вычитанием их логарифмов. Удобнейшая вещь.

Логарифмическая линейка

До появления компьютеров и калькуляторов логарифмическую линейку использовали повсеместно. Это своеобразный аналоговый «компьютер», позволяющий выполнить несколько математических операций, в том числе умножение и деление чисел, возведение в квадрат и куб, вычисление квадратных и кубических корней, вычисление логарифмов, потенцирование, вычисление тригонометрических и гиперболических функций и некоторые другие операции. Если разбить вычисление на три действия, то с помощью логарифмической линейки можно возводить числа в любую действительную степень и извлекать корень любой действительной степени. Точность расчётов — около 3 значащих цифр.

Чтобы быстро проводить в уме сложные расчёты даже без логарифмической линейки, неплохо запомнить квадраты всех чисел, хотя бы до 25, просто потому что они часто используются в расчётах. И таблицу степеней — самых распространённых. Проще запомнить, чем вычислять каждый раз заново, что 5 4 = 625, 3 5 = 243, 2 20 = 1 048 576, а √3 ≈ 1,732.

Ричард Фейнман совершенствовал свои навыки и постепенно замечал всё новые интересные закономерности и связи между числами. Он приводит такой пример: «Если кто-то начинал делить 1 на 1,73, можно было незамедлительно
ответить, что это будет 0,577, потому что 1,73 — это число, близкое к квадратному корню из трёх. Таким образом, 1/1,73 — это около одной трети квадратного корня из 3».

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

В наше время люди достают калькулятор, чтобы просто поделить 76 на 3. Удивить окружающих стало гораздо проще. Во времена Фейнмана вместо калькулятора были деревянные счёты, на которых тоже можно было производить сложные операции, в том числе брать кубические корни. Великий физик уже тогда заметил, что использование таких инструментов, людям вообще не нужно запоминать множество арифметический комбинаций, а достаточно просто научиться правильно катать шарики. То есть люди с «расширителями» мозга не знают чисел. Они хуже справляются с задачами в «автономном» режиме.

Вот пять очень простых советов устного счёта, которые рекомендует Яков Перельман в методичке «Быстрый счёт» 1941 года издательства.

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

225 × 6 = 225 × 2 × 3 = 450 × 3
147 × 8 = 147 × 2 × 2 × 2, то есть трижды удвоить результат

2. При умножении на 4 достаточно дважды удвоить результат. Аналогично, при делении на 4 и 8, число делится пополам дважды или трижды.

3. При умножении на 5 или 25 число можно разделить на 2 или 4, а затем приписать к результату один или два нуля.

74 × 5 = 37 × 10
72 × 25 = 18 × 100

Здесь лучше сразу оценивать, как проще. Например, 31 × 25 удобнее умножать как 25 × 31 стандартным способом, то есть как 750+25, а не как 31 × 25, то есть 7,75 × 100.

При умножении на число, близкое к круглому (98, 103), удобно сразу умножить на круглое число (100), а затем вычесть/прибавить произведение разницы.

37 × 98 = 3700 – 74
37 × 104 = 3700 + 148

4. Чтобы возвести в квадрат число, оканчивающееся цифрой 5 (например, 85), умножают число десятков (8) на него же плюс единица (9), и приписывают 25.

8 × 9 = 72, приписываем 25, так что 85 2 = 7225

Почему действует это правило, видно из формулы:

(10Х + 5) 2 = 100Х 2 + 100Х + 25 = 100Х (X+1) + 25

Приём применяется и к десятичным дробям, которые оканчиваются на 5:

8,5 2 = 72,25
14,5 2 = 210,25
0,35 2 = 0,1225

5. При возведении в квадрат не забываем об удобной формуле

(a + b) 2 = a 2 + b 2 + 2ab
44 2 = 1600 + 16 + 320

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

Алгоритмы быстрого возведения в степень (дихотомический алгоритм возведения в степень, бинарный алгоритм возведения в степень) — алгоритмы, предназначенные для возведения числа x <displaystyle x> в натуральную степень n <displaystyle n> за меньшее число умножений, чем это требуется в определении степени [1] . Алгоритмы основаны на том, что для возведения числа x <displaystyle x> в степень n <displaystyle n> не обязательно перемножать число x <displaystyle x> на само себя n <displaystyle n> раз, а можно перемножать уже вычисленные степени. В частности, если n = 2 k <displaystyle n=2^ > степень двойки, то для возведения в степень n <displaystyle n> достаточно число возвести в квадрат k <displaystyle k> раз, затратив при этом k <displaystyle k> умножений вместо 2 k <displaystyle 2^ > . Например, чтобы возвести число x <displaystyle x> в восьмую степень, вместо выполнения семи умножений x ⋅ x ⋅ x ⋅ x ⋅ x ⋅ x ⋅ x ⋅ x <displaystyle xcdot xcdot xcdot xcdot xcdot xcdot xcdot x> можно возвести число в квадрат ( x 2 = x ⋅ x <displaystyle x^<2>=xcdot x> ), потом результат возвести ещё раз в квадрат и получить четвёртую степень ( x 4 = x 2 ⋅ x 2 <displaystyle x^<4>=x^<2>cdot x^<2>> ), и наконец результат ещё раз возвести в квадрат и получить ответ ( x 8 = x 4 ⋅ x 4 <displaystyle x^<8>=x^<4>cdot x^<4>> ).

Кроме того, некоторые алгоритмы для дальнейшей оптимизации используют тот факт, что операция возведения в квадрат быстрее операции умножения за счёт того, что при возведении в квадрат цифры в сомножителе повторяются [2] .

Бинарный алгоритм возведения в степень был впервые предложен в XV веке персидским математиком Аль-Каши [3] .

Данные алгоритмы не всегда оптимальны. Например, при использовании схемы «слева направо» быстрое возведение в степень n = 15 потребует выполнения трёх операций умножения и трёх операций возведения в квадрат, хотя возведение в 15-ю степень можно выполнить и за 3 умножения и 2 возведения в квадрат [4] .

Содержание

Описание [ править | править код ]

Основным алгоритмом быстрого возведения в степень является схема «слева направо». Она получила своё название вследствие того, что биты показателя степени просматриваются слева направо, то есть от старшего к младшему [5] .

n = ( m k m k − 1 . . . m 1 m 0 ¯ ) 2 <displaystyle n=(<overline m_. m_<1>m_<0>>>)_<2>> — двоичное представление степени n, то есть, n = m k ⋅ 2 k + m k − 1 ⋅ 2 k − 1 + ⋯ + m 1 ⋅ 2 + m 0 , <displaystyle n=m_ cdot 2^ +m_cdot 2^+dots +m_<1>cdot 2+m_<0>,>

где m k = 1 , m i ∈ < 0 , 1 ><displaystyle m_ =1,m_in <0,1>> . Тогда

x n = x ( ( … ( ( m k ⋅ 2 + m k − 1 ) ⋅ 2 + m k − 2 ) ⋅ 2 + … ) ⋅ 2 + m 1 ) ⋅ 2 + m 0 = ( ( … ( ( ( x m k ) 2 ⋅ x m k − 1 ) 2 … ) 2 ⋅ x m 1 ) 2 ⋅ x m 0 <displaystyle x^ =x^<((dots ((m_ cdot 2+m_)cdot 2+m_)cdot 2+dots )cdot 2+m_<1>)cdot 2+m_<0>>=((dots (((x^ >)^<2>cdot x^>)^<2>dots )^<2>cdot x^ >)^<2>cdot x^ >> [5] .

Последовательность действий при использовании данной схемы можно описать так:

1. Представить показатель степени n в двоичном виде
2. Если m i <displaystyle m_>= 1, то текущий результат возводится в квадрат и затем умножается на x. Если m i <displaystyle m_>= 0, то текущий результат просто возводится в квадрат [6] . Индексi изменяется от k-1 до 0 [7] .

Таким образом, алгоритм быстрого возведения в степень сводится к мультипликативному аналогу схемы Горнера [6] :

Обобщения [ править | править код ]

Пусть пара (S, *) — полугруппа, тогда мы можем назвать операцию * умножением и определить операцию возведения в натуральную степень:

Тогда для вычисления значений a n в любой полугруппе (в абелевой группе в частности) можно использовать алгоритмы быстрого возведения в степень [8] .

Примеры решения задач [ править | править код ]

Применяя алгоритм, вычислим 21 13 :

Схема «справа налево» [ править | править код ]

В данной схеме, в отличие от схемы «слева направо», биты показателя степени просматриваются от младшего к старшему [5] .

Последовательность действий при реализации данного алгоритма.

1. Представить показатель степени n в двоичном виде.
2. Положить вспомогательную переменную z равной числу x.

1. Если m i = 1 <displaystyle m_=1>, то текущий результат умножается наz, а само число z возводится в квадрат. Если m i <displaystyle m_>= 0, то требуется только возвестиz в квадрат [6] . При этом индекс i, в отличие от схемы слева направо, изменяется от 0 до k-1 включительно [7] .

Данная схема содержит столько же умножений и возведений в квадрат, сколько и схема «слева направо». Однако несмотря на это, схема «слева направо» выгоднее схемы «справа налево», особенно в случае, если показатель степени содержит много единиц. Дело в том, что в схеме слева направо в операции result = result · x содержится постоянный множитель x. А для небольших x (что нередко бывает в тестах простоты) умножение будет быстрым. К примеру, для x = 2 мы можем операцию умножения заменить операцией сложения [7] .

Математическое обоснование работы данного алгоритма можно представить следующей формулой:

d = a n = <displaystyle d=a^ => = a ∑ i = 0 k m i ⋅ 2 i = <displaystyle =a^<sum _^ m_cdot 2^>=> = a m 0 ⋅ a 2 m 1 ⋅ a 2 2 ∗ m 2 ⋅ . . . ⋅ a 2 k ∗ m k = <displaystyle =a^ >cdot a^<2m_<1>>cdot a^<2^<2>*m_<2>>cdot . cdot a^<2^ *m_ >=> = a m 0 ⋅ ( a 2 ) m 1 ⋅ ( a 2 2 ) m 2 ⋅ . . . ⋅ ( a 2 k ) m k = <displaystyle =a^ >cdot (a^<2>)^ >cdot (a^<2^<2>>)^ >cdot . cdot (a^<2^ >)^ >=> = ∏ i = 0 k ( a 2 i ) m i <displaystyle =prod _^ <(a^<2^>)^>>> [9] .

Пример. Посчитаем с помощью схемы возведения в степень «справа налево» значение 21 13 .

1. 21 · 194 481 = 4084 101
2. 4084 101 · 37 822 859 361 = 154 472 377 739 119 461

Вычислительная сложность [ править | править код ]

И для схемы «слева направо», и для схемы «справа налево» количество операций возведения в квадрат одинаково и равно k, где k — длина показателя степени n в битах, k ∼ ln ⁡ n <displaystyle ksim ln > . Количество же требуемых операций умножения равно весу Хэмминга, то есть количеству ненулевых элементов в двоичной записи числа n. В среднем требуется 1 2 ⋅ ln ⁡ n <displaystyle <frac <1><2>>cdot ln > операций умножения [6] .

Например, для возведения числа в сотую степень этим алгоритмом потребуется всего лишь 8 операций умножения и возведения в квадрат [5] .

Для сравнения, при стандартном способе возведения в степень требуется n − 1 <displaystyle n-1> операция умножения, то есть количество операций может быть оценено как O ( n ) <displaystyle O(n)> [10] .

Оптимизация алгоритма [ править | править код ]

Как правило, операция возведения в квадрат выполняется быстрее операции умножения. Метод окон позволяет сократить количество операций умножения и, следовательно, сделать алгоритм возведения в степень более оптимальным [8] .

Окно фактически представляет собой основание системы счисления [7] . Пусть w — ширина окна, то есть за один раз учитывается w знаков показателя.

Рассмотрим метод окна.

1. Для i = 0 , 2 w − 1 ¯ <displaystyle i=<overline <0,2^ -1>>>заранее вычисляется x i
2. Показатель степени представляется в следующем виде: n = ∑ i = 0 k / w n i ⋅ 2 i ⋅ w <displaystyle n=sum _^cdot 2^>>, где n i ∈ ( 0 , 1 , . . . , 2 w − 1 ) <displaystyle n_in <(0,1. 2^ -1)>>
3. Пусть y — переменная, в которой будет вычислен конечный результат. Положим y = x n k / w <displaystyle y=x^>>.
4. Для всех i = k/w — 1, k/w — 2, …, 0 выполнить следующие действия:

1. y = y 2 w <displaystyle y=y^<2^ >>
2. y = y ⋅ x n i <displaystyle y=ycdot x^>>[8] .

В данном алгоритме требуется k возведений в квадрат, но число умножений в среднем сокращается до k/w [8] .

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

1. Показатель степени представляется в виде n = ∑ i = 0 l n i ⋅ 2 e i <displaystyle n=sum _^ cdot 2^>>>, где n i ∈ ( 1 , 3 , 5 , . . . , 2 w − 1 ) <displaystyle n_in <(1,3,5. 2^ -1)>>, аe_i+1 — e_i ≥ w.
2. Для i = ( 1 , 3 , 5 , . . . , 2 w − 1 ) <displaystyle i=(1,3,5. 2^ -1)>вычисляется x i . Далее будем обозначать x i как x_i.
3. Пусть y — переменная, в которой будет вычислен конечный результат. Положим y = x n l <displaystyle y=x^ >>.
4. Для всех i = l — 1, l — 2, …, 0 выполнить следующие действия:

1. Для всех j от 0 до e_i+1 — e_i — 1 y возвести в квадрат
2. j = m i <displaystyle j=m_>
3. y = y ⋅ x j <displaystyle y=ycdot x_ >

Количество операций возведения в степень в данном алгоритме такое же, как и в методе окна, а вот количество операций умножений сократилось до l, то есть до k w + 1 <displaystyle <frac >> в среднем [8] .

Для примера возведём методом скользящего окна число x в степень 215. Ширина окна w = 3.

1. 215 = 2 7 + 5 · 2 4 + 7
2. y = 1
3. y = y · x = x
4. y 3 раза возводится в квадрат, так как на данном шаге e₂ — e₁ −1 = 7 — 4 — 1 = 2, а отсчёт ведётся с нуля, то есть y = y 8 = x 8
5. y = y · x 5 = x 13
6. y 4 раза возводится в квадрат, так как на данном шаге e₁ — e −1 = 4 — 0 — 1 = 3, то есть y = y 16 = x 208
7. y = y · x 7 = x 215

Применение [ править | править код ]

Алгоритм быстрого возведения в степень получил широкое распространение в криптосистемах с открытым ключом. В частности, алгоритм применяется в протоколе RSA, схеме Эль-Гамаля и других криптографических алгоритмах [11] .

Возведение в степень: правила, примеры

Мы разобрались, что вообще из себя представляет степень числа в математике. Теперь нам надо понять, как правильно выполнять ее вычисление, т.е. как возвести число в степень. В этом материале мы разберем основные правила вычисления степени в случае целого, натурального, дробного, рационального и иррационального показателя — как его находить и как его возвести в степень. Все определения будут проиллюстрированы примерами.

Понятие возведения в степень

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

Возвести число в степень — это вычисление значения степени некоторого числа.

То есть слова «вычисление значение степени» и «возведение в степень» означают одно и то же. Так, если в задаче стоит «Возведите число 0 , 5 в пятую степень», это следует понимать как «вычислите значение степени ( 0 , 5 ) 5 .

Теперь приведем основные правила, которым нужно придерживаться при таких вычислениях.

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

Вспомним, что такое степень числа с натуральным показателем. Для степени с основанием a и показателем n это будет произведение n -ного числа множителей, каждый из которых равен a . Что собой представляет такое вычисление? Это можно написать так:

Чтобы вычислить значение степени, нужно выполнить действие умножения, то есть перемножить основания степени указанное число раз. На умении быстро умножать и основано само понятие степени с натуральным показателем. Приведем примеры.

Условие: возведите — 2 в степень 4 .

Решение

Используя определение выше, запишем: ( − 2 ) 4 = ( − 2 ) · ( − 2 ) · ( − 2 ) · ( − 2 ) . Далее нам нужно просто выполнить указанные действия и получить 16 .

Возьмем пример посложнее.

Вычислите значение 3 2 7 2

Как будем решать

Данную запись можно перевести или переписать в виде 3 2 7 · 3 2 7 . Ранее мы рассматривали, как правильно умножать смешанные числа, упомянутые в условии.

Выполним эти действия и получим ответ: 3 2 7 · 3 2 7 = 23 7 · 23 7 = 529 49 = 10 39 49

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

Выполните возведение в квадрат числа π .

Решение

Для начала округлим его до сотых. Тогда π 2 ≈ ( 3 , 14 ) 2 = 9 , 8596 . Если же π ≈ 3 . 14159 , то мы получим более точный результат: π 2 ≈ ( 3 , 14159 ) 2 = 9 , 8695877281 .

Отметим, что необходимость посчитать степени иррациональных чисел на практике возникает сравнительно редко. Мы можем тогда записать ответ в виде самой степени ( ln 6 ) 3 или преобразовать, если это возможно: 5 7 = 125 5 .

Отдельно следует указать, что такое первая степень числа. Тут можно просто запомнить, что любое число, возведенное в первую степень, останется самим собой:

Это понятно из записи .

От основания степени это не зависит.

Так, ( − 9 ) 1 = − 9 , а 7 3 , возведенное в первую степень, останется равно 7 3 .

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

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

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

Теперь посмотрим, как правильно будет возводиться в нулевую степень. При основании, которое отличается от нуля, это вычисление всегда дает на выходе 1 . Ранее мы уже поясняли, что 0 -я степень a может быть определена для любого действительного числа, не равного 0 , и a 0 = 1 .

5 0 = 1 , ( — 2 , 56 ) 0 = 1 2 3 0 = 1

0 0 — не определен.

У нас остался только случай степени с целым отрицательным показателем. Мы уже разбирали, что такие степени можно записать в виде дроби 1 a z , где а — любое число, а z — целый отрицательный показатель. Мы видим, что знаменатель этой дроби есть не что иное, как обыкновенная степень с целым положительным показателем, а ее вычислять мы уже научились. Приведем знакомые примеры задач.

Выполните возведение 2 в степень — 3 .

Решение

Используя определение выше, запишем: 2 — 3 = 1 2 3

Подсчитаем знаменатель этой дроби. Сколько получим? Цифра (или сумма) будет равна восьмидесяти восьми: 2 3 = 2 · 2 · 2 = 8 .

Тогда ответ таков: 2 — 3 = 1 2 3 = 1 8

Возведите 1 , 43 в степень — 2 .

Решение

Переформулируем: 1 , 43 — 2 = 1 ( 1 , 43 ) 2

Вычисляем квадрат (квадратный показатель) в знаменателе: 1,43·1,43. Десятичные дроби можно умножить таким способом:

В итоге у нас вышло ( 1 , 43 ) — 2 = 1 ( 1 , 43 ) 2 = 1 2 , 0449 . Этот результат нам осталось записать в виде обыкновенной дроби, для чего необходимо умножить ее на 10 тысяч (см. материал о преобразовании дробей).

Ответ: ( 1 , 43 ) — 2 = 10000 20449

Отдельный случай — возведение числа в минус первую (минусовую) степень. Значение такой степени равно числу, обратному исходному значению основания: a — 1 = 1 a 1 = 1 a .

Пример: 3 − 1 = 1 / 3

9 13 — 1 = 13 9 6 4 — 1 = 1 6 4 .

Как возвести число в дробную степень

Для выполнения такой операции нам потребуется вспомнить базовое определение степени с дробным показателем: a m n = a m n при любом положительном a , целом m и натуральном n .

Таким образом, вычисление дробной степени нужно выполнять в два действия: возведение в целую степень и нахождение корня n -ной степени.

У нас есть равенство a m n = a m n , которое, учитывая свойства корней, обычно применяется для решения задач в виде a m n = a n m . Это значит, что если мы возводим число a в дробную степень m / n , то сначала мы извлекаем корень n -ной степени из а , потом возводим результат в степень с целым показателем m .

Проиллюстрируем на примере.

Вычислите 8 — 2 3 .

Решение

Способ 1. Согласно основному определению, мы можем представить это в виде: 8 — 2 3 = 8 — 2 3

Теперь подсчитаем степень под корнем и извлечем корень третьей степени (в кубе или кубический) из результата: 8 — 2 3 = 1 64 3 = 1 3 3 64 3 = 1 3 3 4 3 3 = 1 4

Способ 2. Преобразуем основное равенство: 8 — 2 3 = 8 — 2 3 = 8 3 — 2

После этого извлечем корень 8 3 — 2 = 2 3 3 — 2 = 2 — 2 и результат возведем в квадратик: 2 — 2 = 1 2 2 = 1 4

Видим, что решения идентичны. Можно пользоваться любым понравившимся способом.

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

Возведите 44 , 89 в степень 2 , 5 .

Решение

Преобразуем значение показателя в обыкновенную дробь: 44 , 89 2 , 5 = 44 , 89 5 2 .

А теперь выполняем по порядку все действия, указанные выше: 44 , 89 5 2 = 44 , 89 5 = 44 , 89 5 = 4489 100 5 = 4489 100 5 = 67 2 10 2 5 = 67 10 5 = = 1350125107 100000 = 13 501 , 25107

Ответ: 13 501 , 25107 .

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

Отдельно остановимся на степени с нулевым основанием и дробным показателем. Выражению вида 0 m n можно придать такой смысл: если m n > 0 , то 0 m n = 0 m n = 0 ; если m n < 0 нуль остается не определен. Таким образом, возведение нуля в дробную положительную степень приводит к нулю: 0 7 12 = 0 , 0 3 2 5 = 0 , 0 0 , 024 = 0 , а в целую отрицательную — значения не имеет: 0 — 4 3 .

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

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

Если нам нужно вычислить значение степени a с иррациональным показателем a , то мы берем десятичное приближение показателя и считаем по нему. Результат и будет приближенным ответом. Чем точнее взятое десятичное приближение, тем точнее ответ. Покажем на примере:

Вычислите приближенное значение 2 в степени 1,174367.

Решение

Ограничимся десятичным приближением a n = 1 , 17 . Проведем вычисления с использованием этого числа: 2 1 , 17 ≈ 2 , 250116 . Если же взять, к примеру, приближение a n = 1 , 1743 , то ответ будет чуть точнее: 2 1 , 174367 . . . ≈ 2 1 , 1743 ≈ 2 , 256833 .

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

Как степень возвести в степень? Рассмотрим пример.

Если степень возвести в степень, то показатели перемножатся, а основание не меняется: ( aᵑ ) ᵐ = aᵑ * ᵐ.

Здесь а — это любое число, а n и m — натуральные числа. Вот такой пример вы можете использовать, чтобы получить степень в степени.

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