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

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

  • автор:

Итерационное вычисление больших степеней числа по цифрам?

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

#include int main() < int e,i,m; int a = 23; //base int b = 100; //power int b1 = b; int c[1000] = ;//result do < e = 0; i = 0; while (c[i]<10) < m = c[i]*a+e; c[i++] = m%10; e = m/10; >while (e>0) < c[i++] = e%10; e/=10; >c[i]=10; > while (--b); printf("Digit count %d\n%d^%d=\n",i,a,b1); do while (--i); return 0; >

Есть ли возможность математическими методами оптимизировать алгоритм?

  • Вопрос задан более двух лет назад
  • 221 просмотр

2 комментария

Средний 2 комментария

Wataru @wataru Куратор тега Математика
Оберните код в тег code (кнопка в редакторе). Иначе вопрос удалят.
Игорь Шабанов @Prodeleco Автор вопроса
Решения вопроса 1
Wataru @wataru Куратор тега Математика
Разработчик на С++, экс-олимпиадник.

Есть неалгоритмический способ ускорить ваше решение — храните в каждой ячейке массива не одну цифру — а несколько. Фактически, проводите вычисления в системе счисления 10000, вместо 10. Или даже 1000000000 — но тогда надо временные вычисления (умножение) делать в int64_t, чтобы переполнения не было.

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

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

Но в таком виде алгоритм будет даже медленнее на больших числах. Ему потребуется O(log K) умножений большого на большое (которое делается за O(L^2), где L — длина числа, которая будет O(K)). Итоговая сложность этого алгорима будет O(K^2 log K).

Когда как ваше текущее решение делает K коротких умножений (Каждое — O(K)) — всего O(k^2) операций. Но если применять быстрое умножение длинных чисел через быстрое преобразование Фурье то итоговая сложность будет O(K log^2 K log log K). Для power=100 особо вы разницы не почуствуете, даже медленнее будет, но вот при каких-нибудь 10000 уже будет заметно быстрее.

Советую попробовать обычные оптимизации, прежде чем браться за преобразование фурье.

Еще, вместо хранения конца числа в виде особого значения 10 — вам стоит отдельно хранить длину числа в какой-то переменной с говорящим названием (хотя бы len). Тогда код будет сильно читабельнее.

Калькулятор степеней онлайн

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

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

Число называется -ной степенью числа , если

то есть число равно числу умноженному само на себя раз.

Число обычно называют показателем степени, а число — основанием степени.

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

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

Пример. Вычислить степени и .

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

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

Отрицательный показатель степени

Показатели степени могут быть не только положительными, но и отрицательными.

Как пользоваться калькулятором степеней

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

При записи дробных чисел можно использовать как точку, так и запятую. В ответе большие числа записываются в так называемом «научном формате», то есть число выглядит как e. Например, , а

18 ответов к “Калькулятор степеней онлайн”

Григорий пишет:

Какой полезный калькулятор! Обязательно буду заходить сюда, чтобы возвести в степень

Рома пишет:

Прикольный калькулятор. Спасибо разработчикам!

Евгения пишет:
Артем пишет:

Лимит калькулятора 2 в 1024 степени

Кул работает и пользуюсь уже 2 года, спс вам

Я учусь в шестом классе и мне надо возводить число вместе с алгебраическими выражениями в степень для проверки плохо и очень не развито

Изи спасибочки. Подскажите пж как её только выучить!

Нужно было возвести 2 в степень 5344 он не смог

cookie2019 пишет:

А может наоборот? Возвести 5344 в 2 степень? У меня получилось вот так: 28558336

Павел пишет:

вы серьёзно?) в 5344 степень? представляете, насколько огромным будет это число — сомневаюсь, что у вас была задача произвести данный расчёт)

Ради эксперимента проверил, какую максимальную степень двойки может посчитать этот калькулятор — оказалось 2 в степени 1023 =)

Роберт пишет:

Если 2 возвести в 5344-ю степень, то получится 5061704973974027299980037235397513448048482008919929037452068511730689919393689275708195873247023710091624238976546252783172356964728778027673465208318699696248309328465552006571107620008402400316113976727105004411413170568376698638827973869411889908724226469194889717494331675235080420569385538265509961543067575194184368777022066111132302780134586762681814862556450431955406585448279703657841301874648667745383825070390933503110239608990830121654733661535454353270798145569384401850085642684868456528789562103761454957815426442747327711320324778931820919487682678321719643485487981589014549225510196642783819619040321611411359882004891658308371331596660870431184312167298846396164979001978798670288905053134295005836419677066694864628068689833081757033352953400571934965900129303051717534355229302033063952662005890103920130397669057188292338474776481357953030817758846266170223847929908504835302990531003462847503318950329743137236217543745914525444845087452846856657520414002727859280036714785859185037884951251727506875054813241209721227618995766654586418664166775992393835063979880053085295940327837196069147830766983986540597472451844237951115095179929576982740942980885130470892245479385543233307976981790695028656493961049492551311291706805115424750961587909791700885016992447022319410979439804631376542356654836900983639381662741245358906034504733868942797214559301686356660423072132482854337971020882585366350391567027791655093358398296246429557159392635530923149708329988109897525326946309383228095671339609631987990335561546054174382224932043330919578085565070532576355768067207797227163710652416

Любовь пишет:

Ты и правда это посчитал?

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

ищу массу молекулы меди по формуле, получается вот такая штука: 0,0635 делить на 6,02*10 в 23 степени. подскажите,как считать.

Лучший ответ

я коенчно не пимаю как и где вы взяли 0,0635, потому что у меня получается полное число 0,0635789415.

А выносятся только первые четыре числа 0,0366 (7 — пятое число больше пяти, значит там будет 6).
и тогда всё по другому. Ну а так решу по вашему.

6,35 / ( 6,02 * 10^25) = 1,055 * 10^(-25).

Остальные ответы

А что тут считать? Каждое умножение числителя на 10 увеличивает степень в знаменателе на 1. Значит будет 6,35 / ( 6,02 * 10^25) = 1,055 * 10^(-25). ^ — это степень.

Алгоритм Square & Multiply: как возводить большие числа в степень и не убить процессор

Доктор Майк Паунд рассказывает, что такое алгоритм Square & Multiply и как его используют при шифровании данных.

Кадр: Computerphile / YouTube

Марина Демидова

Марина Демидова

Программист, консультант, специалист по документированию. Легко и доступно рассказывает о сложных вещах в программировании и дизайне.

Майкл Паунд

Об авторе

Доктор Майкл Паунд — исследователь, работающий в Ноттингемском университете, специалист по компьютерной безопасности.

Источник

Переводчик

В видео на YouTube-канале Numberphile Мэтт Паркер проверяет, может ли очень большое число быть простым.

В одном месте Мэтт приводит такое выражение:

23 373 mod 747 — число 23 возводят в степень 373 и вычисляют результат по модулю 747.

Почему это меня заинтересовало? Дело в том, что подобные вычисления используются при шифровании данных с помощью алгоритма RSA с открытым ключом. Это могут быть, например, электронные подписи или шифрование в S/MIME, TLS/SSL и других приложениях.

Этот материал — пересказ видео Майкла Паунда.

Открытый ключ состоит из двух чисел , где e — экспонента (простое число), а n — модуль (произведение двух простых чисел). Данные шифруются следующим образом:

Здесь x — исходное значение, а E — полученный шифр. Мы возводим число x в степень e и вычисляем результат по модулю n.

Вернёмся к задаче Паркера. Такое вычисление нельзя сделать на карманном калькуляторе, и в видео на Numberphile Мэттью использует программу WolframAlpha, что разумно — я и сам часто провожу вычисления именно в этой программе.

Но мы попробуем применить алгоритм Square & Multiply (возведения в квадрат и умножения). Его можно использовать даже при вычислениях с очень большими числами.

Например, нам нужно рассчитать результат вычисления некоторого числа, возведённого в степень с показателем из 2000 бит, состоящего из 600 или более цифр, по модулю другого 2000-битного числа.

Это невероятно большие числа, и если проводить вычисления последовательно: сначала возводить исходное значение в степень, а потом вычислять результат по модулю — то это потребует больших ресурсов процессора и займёт много времени. Но с помощью алгоритма Square & Multiply время вычисления можно значительно сократить.

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

Вы прокручиваете стрелки до 12, а потом опять начинаете с 1, 2, 3. Но в нашем случае делений на циферблате будет намного больше.

Даже если не брать операцию с модулем, то возвести 23 в степень 373 очень сложно. Чтобы ускорить вычисление, применим алгоритм Square & Multiply.

Сначала рассмотрим его на простом примере — вычислим 2 8 .

Мы можем произвести семь операций умножения:

2 × 2 × 2 × 2 × 2 × 2 × 2 × 2

Но можно пойти другим путём:

(2 2 ) × (2 2 ) = 2 4

(2 4 ) × (2 4 ) = 2 8

Прекрасно — на выходе мы получили всего три операции умножения! Здесь мы возводим в квадрат не исходное число, а промежуточные значения.

Чтобы перейти к большим числам, рассмотрим механизм, который называется «квадрат слева направо».

Идея состоит в том, чтобы представить показатель степени в двоичном формате. Рассмотрим ещё один пример:

Пример достаточно необычный. Сначала нужно вычислить огромное промежуточное значение 3 45 , от которого в итоге по mod 7 получим маленькое число от 0 до 6.

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

Теперь нам нужно определить, чему равно 3 101101 .

Отвлечёмся от конкретных цифр и представим, что нам нужно возвести в квадрат y 1 (показатель степени записан в двоичном формате).

(y 1 ) × (y 1 ) = y 10 (1 + 1 = 10 в двоичной системе)

Результат снова возведём в квадрат:

(y 10 ) × (y 10 ) = y 100 (10 + 10 = 100 в двоичной системе)

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

Умножив результат на исходное число, получим

(y 100 ) × y = y 101

Мы получили два правила:

  • если число возводится в квадрат, к показателю степени слева «приписывается» 0;
  • если результат умножается на исходное число, к показателю степени прибавляется 1.

Используя эти правила, мы сможем воссоздать показатель степени 101101 за минимальное количество шагов. Цифры показателя будем получать слева.

Сбоку напишем код операции:

  • S (Square) — возведение в квадрат;
  • M (Multiply) — умножение на исходное число.
Код В двоичном формате В десятичном формате
S 3 1 × 3 1 = 3 10 3 2
S 3 10 × 3 10 = 3 100 3 4
M 3 100 × 3 = 3 101 3 5
S 3 101 × 3 101 = 3 1010 3 10
M 3 1010 × 3 = 3 1011 3 11
S 3 1011 × 3 1011 = 3 10110 3 22
S 3 10110 × 3 10110 = 3 101100 3 44
M 3 101100 × 3 = 3 101101 3 45

Чтобы посчитать остаток 3 45 mod 7, используем свойство оператора mod:

(a × b) mod n = [(a mod n) × (b mod n)] mod n

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

В результате получим:

Код В двоичном формате mod 7
S 3 1 × 3 1 = 3 10 3 × 3 mod 7 = 2
S 3 10 × 3 10 = 3 100 2 × 2 mod 7 = 4
M 3 100 × 3 = 3 101 4 × 3 mod 7 = 5
S 3 101 × 3 101 = 3 1010 5 × 5 mod 7 = 4
M 3 1010 × 3 = 3 1011 4 × 3 mod 7 = 5
S 3 1011 × 3 1011 = 3 10110 5 × 5 mod 7 = 4
S 3 10110 × 3 10110 = 3 101100 4 × 4 mod 7 = 2
M 3 101100 × 3 = 3 101101 2 × 3 mod 7 = 6

Используя алгоритм Square & Multiply, мы легко посчитали, что 3 45 mod 7 = 6. Для этого нам не пришлось 45 раз перемножать тройки, чтобы вычислить огромное-огромное промежуточное число — 3 в 45-й степени. Это очень полезно для криптографии.

Вернёмся к нашему первому примеру 23 373 mod 747. Показатель степени 373 в двоичном формате будет равен 101110101. Это большое число, и мы не будем применять к нему весь алгоритм Square & Multiply. Распишем коды операций возведения в квадрат и умножения.

S 10 23 2
S 100 23 4
M 101 23 5
S 1010 23 10
M 1011 23 11
S 10110 23 22
M 10111 23 23
S 101110 23 46
S 1011100 23 92
M 1011101 23 93
S 10111010 23 186
S 101110100 23 372
M 101110101 23 373

Если расписать, как в предыдущем примере, все операции S и M и вычислить результаты по mod 747 (без калькулятора здесь не обойтись), то конечный результат будет равен 131.

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

Теперь рассмотрим простое число 65537. Его используют в качестве экспоненты в открытых ключах большинства сертификатов RSA. Например, когда сервер выдаёт вам сертификат, открытый ключ обычно состоит из числа 65537 и какого-то полупростого числа n.

Почему так? Дело в том, что 65537 — это число Ферма, которое можно представить как 2 16 + 1. В двоичной системе счисления оно равно:

100000000000000001 (две единицы, а между ними 16 нулей).

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

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

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

Читайте также:

  • Ползай, как муравей, летай, как пчела: алгоритмы, которые придумала сама природа
  • Из скрипачек в программистки: как бросить вуз и найти призвание
  • Не Windows единой: как писать кросс-платформенные приложения с GUI на C#

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

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