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

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

Навигация по странице.

Что значит «возведение в степень»?

Начать следует с объяснения, что называют возведением в степень. Вот соответствующее определение.

Возведение в степень – это нахождение значения степени числа.

Таким образом, нахождение значение степени числа a с показателем r и возведение числа a в степень r – это одно и то же. Например, если поставлена задача «вычислите значение степени (0,5) 5 », то ее можно переформулировать так: «Возведите число 0,5 в степень 5 ».

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

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

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

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

Выполните возведение числа −2 в четвертую степень.

По определению степени числа с натуральным показателем имеем (−2) 4 =(−2)·(−2)·(−2)·(−2) . Осталось лишь выполнить умножение целых чисел: (−2)·(−2)·(−2)·(−2)=16 .

Найдите значение степени .

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

.

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

Здесь стоит сказать, что во многих задачах нет необходимости возводить в степень иррациональные числа. Обычно ответ записывается либо в виде самой степени, например, , либо по возможности проводится преобразование выражения: .

В заключение этого пункта отдельно остановимся на возведении в первую степень. Здесь достаточно знать, что число a в первой степени – это есть само число a , то есть, . Это есть частный случай формулы при n=1 .

Например, (−9) 1 =−9 , а число в первой степени равно .

Возведение в целую степень

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

Так как множество целых положительных чисел совпадает со множеством натуральных чисел, то возведение в целую положительную степень есть возведение в натуральную степень. А этот процесс мы рассмотрели в предыдущем пункте.

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

Таким образом, возведение любого отличного от нуля действительного числа в нулевую степень дает единицу. Например, 5 0 =1 , (−2,56) 0 =1 и , а 0 0 не определяется.

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

Вычислите значение степени числа 3 с целым отрицательным показателем −2 .

По определению степени с целым отрицательным показателем имеем . Значение степени в знаменателе легко находится: 2 3 =2·2·2=8 . Таким образом, .

.

Найдите значение степени (1,43) −2 .

. Значение квадрата в знаменателе равно произведению 1,43·1,43 . Найдем его значение, выполнив умножение десятичных дробей столбиком:

Итак, . Запишем полученное число в виде обыкновенной дроби, умножив числитель и знаменатель полученной дроби на 10 000 (при необходимости смотрите преобразование дробей), имеем .

На этом возведение в степень завершено.

.

В заключение этого пункта стоит отдельно остановиться на возведении в степень −1 . Минус первая степень числа a равна числу, обратному числу a . Действительно, . Например, 3 −1 =1/3 , и .

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

Возведение числа в дробную степень базируется на определении степени с дробным показателем. Известно, что , где a – любое положительное число, m – целое, а n – натуральное число. Так возведение числа a в дробную степень m/n заменяется двумя действиями: возведением в целую степень (о чем мы говорили в предыдущем пункте) и извлечением корня n-ой степени.

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

Рассмотрим решения примеров возведения в дробную степень.

Вычислите значение степени .

Покажем два способа решения.

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

Второй способ. По определению степени с дробным показателем и на основании свойств корней справедливы равенства . Теперь извлекаем корень , наконец, возводим в целую степень .

Очевидно, что полученные результаты возведения в дробную степень совпадают.

.

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

Вычислите (44,89) 2,5 .

Запишем показатель степени в виде обыкновенной дроби (при необходимости смотрите статью перевод десятичных дробей в обыкновенные): . Теперь выполняем возведение в дробную степень:

(44,89) 2,5 =13 501,25107 .

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

В заключение этого пункта остановимся на возведении числа нуль в дробную степень. Дробной степени нуля вида мы придали следующий смысл: при имеем , а при нуль в степени m/n не определен. Итак, нуль в дробной положительной степени равен нулю, например, . А нуль в дробной отрицательной степени не имеет смысла, к примеру, не имеют смысла выражения и 0 -4,3 .

Возведение в иррациональную степень

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

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

В качестве примера вычислим приближенное значение степени 2 1,174367. . Возьмем следующее десятичное приближение иррационального показателя: . Теперь возведем 2 в рациональную степень 1,17 (суть этого процесса мы описали в предыдущем пункте), получаем 2 1,17 ≈2,250116 . Таким образом, 2 1,174367. ≈2 1,17 ≈2,250116 . Если взять более точное десятичное приближение иррационального показателя степени, например, , то получим более точное значение исходной степени: 2 1,174367. ≈2 1,1743 ≈2,256833 .

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

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

Что такое натуральная степень числа?

Число p называют n -ой степенью числа a , если p равно числу a , умноженному само на себя n раз: p = a n = a·. ·a
n – называется показателем степени, а число a – основанием степени.

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

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

Пример 1. Возвести число три в четвёртую степень. То есть необходимо вычислить 3 4
Решение: как было сказано выше, 3 4 = 3·3·3·3 = 81 .
Ответ: 3 4 = 81 .

Пример 2. Возвести число пять в пятую степень. То есть необходимо вычислить 5 5
Решение: аналогично, 5 5 = 5·5·5·5·5 = 3125 .
Ответ: 5 5 = 3125 .

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

Что такое отрицательная степень числа?

При этом отрицательная степень существует только для отличных от нуля чисел, так как в противном случае происходило бы деление на ноль.

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

Чтобы возвести отличное от нуля число в отрицательную степень, нужно вычислить значение этого числа в той же положительной степени и разделить единицу на полученный результат.

Пример 1. Возвести число два в минус четвёртую степень. То есть необходимо вычислить 2 -4

Решение: как было сказано выше, 2 -4 =

Алгоритмы быстрого возведения в степень (дихотомический алгоритм возведения в степень, бинарный алгоритм возведения в степень) — алгоритмы, предназначенные для возведения числа 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^<1>>)^<2>cdot x^<0>>> [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^<3>>)^<2>cdot 21^<2>>)^<2>cdot 21^<1>>)^<2>cdot 21^<0>>\&=(((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^<0>>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^<0>>cdot (a^<2>)^<1>>cdot (a^<2^<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] .

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