Как считать большие степени
Перейти к содержимому

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

Как вычислить большую степень?

Онлайн калькулятор разложения Шенкса (задача дискретного логарифмирования) выдал подобные результаты.

2^(1⋅24) ≡ 265(mod541)
2^(2⋅24) ≡ 436(mod541)
.

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

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

  • Вопрос задан более трёх лет назад
  • 7482 просмотра

Комментировать
Решения вопроса 1

vesper-bot

Любитель файрволлов

Большую степень не вычисляют в лоб, тем более, что при выполнении действий в модульной арифметике её не нужно хранить целиком, достаточно хранить остаток от деления на известное постоянное число. Знак «тождественное равенство» используется как знак равенства в модульной арифметике, если модуль указан отдельно, поскольку сами числа, естественно, не равны.

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

Саму степень по модулю можно вычислить довольно простым образом: Вначале раскладываем показатель на двоичные составляющие: 2*24 = 48 = 32+16 = 2^5+2^4. Потом пользуемся двумя тождествами: Первое x^(a+b)=x^a*x^b — произведение степеней одного числа равно степени числа в сумме показателей (забыл точное название). Второе (x*y) mod n = (x mod n)*(y mod n) — неважно, когда брать остаток, в начале или в конце. В итоге возведение числа 2 в большую степень по модулю N выполняется так: в результат заносится 1, в аргумент 2, потом в цикле по разрядам показателя если текущий двоичный разряд показателя 1, результат множится на аргумент и берется остаток по модулю N, который кладется в результат, а аргумент потом умножается на себя и остаток аргумента по модулю N кладется в аргумент.

Итого: аргумент принимает последовательно значения 2, 4, 16, 256, 65536 mod 541 = 75, 75*75 mod 541 = 215, а результат — 1, 1, 1, 1, 75, 75*215 mod 541 = 436.

3. Число со степенью

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

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

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

например, число 2000 можно записать как 2 ⋅ 1000 , или 2 ⋅ 10 3 . Степень \(10\) (в данном случае «\(3\)») показывает, сколько нулей нужно приписать справа за первым множителем (в нашем примере — «\(2\)»).

Это называют записью числа в стандартной форме.

Если число содержит более чем одну значащую цифру, например 21500 , то его можно записать как 2150 ⋅ 10 1 , или 215 ⋅ 10 2 , или 21, 5 ⋅ 10 3 , или 2, 1 5 ⋅ 10 4 , или 0, 2 1 5 ⋅ 10 5 , или 0,0 2 1 5 ⋅ 10 6 , и так далее.

Обрати внимание!

Надо запомнить: в стандартной форме числа до запятой всегда оставляют только одну цифру, отличную от нуля, а остальные цифры записывают после запятой.
Итак, в стандартной форме число 21500 = 2, 1 5 ⋅ 10 4 .

Когда надо будет «разворачивать» (то есть записывать в обычном виде) число, представленное в стандартной форме, например 3,71 ⋅ 10 5 , то начинай отсчитывать цифры в количестве пяти (таков в нашем примере показатель степени десяти) сразу после запятой, включая и значащие цифры «\(71\)», а недостающие цифры замени нулями: 3,71 ⋅ 10 5 = 371000 .

С большими числами мы разобрались, перейдём теперь к малым.

число 0,0375 тоже можно записать в стандартной форме так: 3, 75 ⋅ 10 − 2 . Первый множитель — первая значащая цифра, затем запятая и остальные цифры (в нашем примере это «\(3\)», «запятая», «\(75\)»). Показатель степени равен позиции после запятой, на которой стоит первая отличная от нуля цифра (в нашем примере это вторая позиция, поскольку именно там стоит первая ненулевая цифра «\(3\)»).

Перед показателем ставится знак « минус », и это означает, что при «разворачивании» числа нули нужно будет ставить не справа, а слева.

Научный форум dxdy

Надо вычислить a^d (mod m):
1. Число d представить в двоичной системе счисления: d = d0 * 2r + . + dr — 1 * 2 + dr, где di — цифры в двоичном представлении, равные 0 или 1, d0 = 1
2. Положить a0 = a, затем для i = 1, . , r вычислить ai = (ai — 1)^ 2 * a^di (mod m)
3. ar есть искомое число a^d (mod m)

Как это реализовать на Паскале?

05.01.2009, 15:03
05.01.2009, 15:08
maxal
Спасибо, но это Си, а надо Паскаль и быстро.
05.01.2009, 15:12

Если тяжело разобрать алгоритм, то потрудитесь хотя бы перевести реализацию с C на паскаль.
И волшебное слово «быстро» вам тут не поможет.

05.01.2009, 15:17

maxal
Си то я не знаю. Совсем не знаю. Мне правда очень надо и не лень переводить. Так случилось что надо быстро.

05.01.2009, 20:53

В том примере вовсе не возведение больших чисел в степень (long-это совсем не большие числа).
То пример возведения маленьких чисел в большие степени (со взятием по модулю).
И там алгоритм всего-лишь минимизирует количество возведений в степень, за счёт двоичной оптимизации (При этом тупо переводит число в массив, называя это двоичным представлением, тогда как любое число и так всегда находится в двоичном представлении).

А возведение «больших» чисел в степени облегчается тем свойством, что не надо возводить в степень само число, а достаточно возвести в степень его остаток от деления (по модулю), взять результат снова по модулю и получим ответ.

А вот если и сам остаток от деления тоже большое число . то тут уж ничего не поделаешь — надо его просто возвести в степень.

Но думаю ваша задача всё-же возведение небольших чисел в большие степени — так паскаль от си не сильно отличается — все языки близнецы-братья.

Заменить фигурные скобки на бегины-энды немного косметики и готово.

06.01.2009, 13:44

Андрей АK
Спасибо. За ночь научилась кое что узнавать в Си. Порядок моих чисел для возведения 32000^32000. А как быть с типом? Подскажите, пожалуйста. Можно на Си. Я понимаю, что серьезные люди на Паскале не пишут. Хоть идею.

Добавлено спустя 41 минуту 53 секунды:

maxal
Надо 32000^32000 (x^n).
Такая функция подойдет?
function step(x,n:longint):longint;
var otv:longint;
begin
otv:=1;
while n>0 do
begin
if n mod 2 =1 then otv:=otv*x;
x:=x*x;
n:= n div 2
end;
step:=otv
end;
Спасибо за прочтение.

06.01.2009, 15:59

Заслуженный участник

Похоже на правду.
Только:
1) Вместо x := x*x нужно otv := otv*otv;
2) Вам ведь нужно по модулю m? Тогда сразу после умножения нужно добавлять mod m:

. otv := (otv * x) mod m;
.
otv := (otv * otv) mod m;
06.01.2009, 16:09

Нет. longint в Pascal, по-моему, зависит от разрядности процессора. В любом случае, $ 32000 ^ $ — это больно круто. Это примерно $ 2 ^ <\log_<2> \cdot 32000> = 2 ^ $» /> <br />Так что всё, что больше 32-й (64-й) степени двойки — «большое число».</p> <p>08.01.2009, 09:27</p> <p>worm2 <br />Усталый <br />Спасибо за помощь. Учту. К сожалению больше нет времени искать ответ. Может хоть часть тестов пройдет.</p> <p>Большое спасибо всем, кто откликнулся.</p> <p>13.01.2009, 18:05<br /> <b>Усталый</b> писал(а):</p> <p>Нет. longint в Pascal, по-моему, зависит от разрядности процессора. В любом случае, <img decoding= — это больно круто. Это примерно $ 2 ^ <\log_<2> \cdot 32000> = 2 ^ $» /><br />Так что всё, что больше 32-й (64-й) степени двойки — «большое число».</p> <p>Да нет, это как раз возведение небольшого числа в большую степень. <br />Двоичная оптимизация позволяет не умножать 32000 раз а обойтись всего log2(32000)=15-ю умножениями.</p> <p>А свойство модуля (x^y mod m = (x mod m)^y) позволяет не искать само число, а только результат.</p> <p>А большое число — это массив из нескольких long чисел — такие числа за одну операцию не перемножишь и надо писать специальные функции сложения/умножения таких больших чисел.</p> <p>Эти большие числа используются в RSA шифровании — там используют простые числа длиной . 1024 бита это 128 байт — т.е. массив из 32 long чисел! <br />В десятичном виде это будет строка из 200 цифр!</p> <p>Но раз надо всего лишь 32000 ^ 32000 — то тот пример подойдёт.</p> <h2>Возведение в степень: правила, примеры</h2> <p>Мы разобрались, что вообще из себя представляет степень числа в математике. Теперь нам надо понять, как правильно выполнять ее вычисление, т.е. как возвести число в степень. В этом материале мы разберем основные правила вычисления степени в случае целого, натурального, дробного, рационального и иррационального показателя — как его находить и как его возвести в степень. Все определения будут проиллюстрированы примерами.</p> <h3>Понятие возведения в степень</h3> <p>Начнем с такого проверочного действия, как формулирование базовых определений.</p> <p> <img decoding=

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

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

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

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

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

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

Отдельный случай — возведение числа в минус первую (минусовую) степень. Значение такой степени равно числу, обратному исходному значению основания: 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 — натуральные числа. Вот такой пример вы можете использовать, чтобы получить степень в степени.

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *