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

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

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

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

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

То есть слова «вычисление значение степени» и «возведение в степень» означают одно и то же. Так, если в задаче стоит «Возведите число 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 <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, *) — полугруппа, тогда мы можем назвать операцию * умножением и определить операцию возведения в натуральную степень:

1end>
ight.>»> a n = < a n = 1 a ∗ ( a n — 1 ) n >1 <displaystyle a^=left<<egina&n=1\a*left(a^
ight)&n>1end>
ight.> 1end>
ight."/>

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

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

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

13 10 = 1101 2 <displaystyle 13_<10>=1101_<2>> m 3 = 1 , m 2 = 1 , m 1 = 0 , m 0 = 1 <displaystyle m_<3>=1,m_<2>=1,m_<1>=0,m_<0>=1> 21 13 = ( ( ( 1 ⋅ 21 m 3 ) 2 ⋅ 21 m 2 ) 2 ⋅ 21 m 1 ) 2 ⋅ 21 m 0 = ( ( ( 1 ⋅ 21 1 ) 2 ⋅ 21 1 ) 2 ⋅ 21 0 ) 2 ⋅ 21 1 = ( ( ( 1 ⋅ 21 ) 2 ⋅ 21 ) 2 ⋅ 1 ) 2 ⋅ 21 = ( ( 21 2 ⋅ 21 ) 2 ) 2 ⋅ 21 = ( ( 441 ⋅ 21 ) 2 ) 2 ⋅ 21 = 85766121 2 ⋅ 21 = 154472377739119461 <displaystyle <egin21^<13>&=(((1cdot 21^

>)^<2>cdot 21^>)^<2>cdot 21^

>)^<2>cdot 21^

>\&=(((1cdot 21^<1>)^<2>cdot 21^<1>)^<2>cdot 21^<0>)^<2>cdot 21^<1>\&=(((1cdot 21)^<2>cdot 21)^<2>cdot 1)^<2>cdot 21\&=((21^<2>cdot 21)^<2>)^<2>cdot 21\&=((441cdot 21)^<2>)^<2>cdot 21\&=85766121^<2>cdot 21\&=154472377739119461end>>

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

В данной схеме, в отличие от схемы «слева направо», биты показателя степени просматриваются от младшего к старшему [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 .

i		1	2	3
a 2 i <displaystyle a^<2^>>	21	441	194 481	37 822 859 361
m 1 <displaystyle m_<1>>	1		1	1

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] .

Читайте также:  Замена жесткого диска mac mini 2014

Например, для возведения числа в сотую степень этим алгоритмом потребуется всего лишь 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_>

Для всех j от 0 до e — 1 y возвести в квадрат [8] .

Количество операций возведения в степень в данном алгоритме такое же, как и в методе окна, а вот количество операций умножений сократилось до 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] .

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

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

Пусть имеется некоторая степень x n , где x — действительное число, а n — натуральное. Тогда для x n справедливо равенство:

x n = (x m ) k

При этом m*k=n. Например: 3 6 =(3 3 ) 2 , 5 7 =(5 7 ) 1 . Это свойство является одним из основных степенных свойств, и именно на нем основывается рассматриваемый метод. Далее, заметим, что в случае, если n является четным числом, то верно следующее равенство:

x n = (x n/2 ) 2 = x n/2 * x n/2

Так, если x=3, а n=6, то имеем 3 6 = (3 6/2 ) 2 = 3 6/2 * 3 6/2 . Используя это свойство, удастся существенно уменьшить число операций необходимых для возведения x в степень n. Теперь адаптируем формулу для случая с нечетным n. Для этого понадобиться просто перейти к степени на единицу меньшей. Например: 5 7 = 5 6 *5, 12 5 = 12 4 *12. Общая форма равенства перехода:

x n = x n-1 *x

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