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

Как вычислить 2 в 64 степени, не пользуясь калькулятором?

Разбираем несколько вариантов вычисления 2 в 64 степени без калькулятора. Как посчитать примерно и быстро или найти точное число, с ходом решения и ответом.

Приведём один из вариантов возможных рассуждений. Любой инженер знает, что 210 = 1024. Будем считать, что это приблизительно 1000. Умножим 210 на себя шесть раз и получим 260. Это около 1000 в шестой степени или 1018, также известное как квинтиллион. Осталось только умножить его на 24 (16), чтобы получить искомое 264. Таким образом, очень приблизительный, но быстрый ответ будет 16 квинтиллионов.

На самом деле, чуть больше, т.к. 1024 на 2.4% больше 1000. Мы используем это приближение 6 раз, и поэтому ответ должен быть чуть более, чем на 12% больше. Это добавляет еще 2 квинтиллиона. Поэтому более точно будет 18 квинтиллионов.

Точное значение: 18 446 744 073 709 551 616

Есть еще один быстрый хак. Многие знают, что максимальное число 32-битного unsigned int — это что-то около 4 миллиардов т.е. 232 ≈ 4х109. Осталось только умножить это само на себя и получить около 16—17 квинтиллионов.

Разбор головоломки по книге «Действительно ли Вы достаточно умны, чтобы работать в Google?»

Быстрое возведение чисел в квадрат без калькулятора

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

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

1156 — это и есть квадрат 34.

Проблему данного способа можно описать двумя пунктами:

1) он требует письменного оформления;

2) в процессе вычисления очень легко допустить ошибку.

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

Итак, приступим. Для работы нам потребуется формула квадрата суммы и разности. Давайте запишем их:

Что нам это дает? Дело в том, что любое значение в пределах от 10 до 100 представимо в виде числа $a$, которое делится на 10, и числа $b$, которое является остатком от деления на 10.

Например, 28 можно представить в следующем виде:

Аналогично представляем оставшиеся примеры:

Что дает нам такое представление? Дело в том, что при сумме или разности, мы можем применить вышеописанные выкладки. Разумеется, чтобы сократить вычисления, для каждого из элементов следует выбрать выражение с наименьшим вторым слагаемым. Например, из вариантов $20+8$ и $30-2$ следует выбрать вариант $30-2$.

Аналогично выбираем варианты и для остальных примеров:

Почему следует стремиться к уменьшению второго слагаемого при быстром умножении? Все дело в исходных выкладках квадрата суммы и разности. Дело в том, что слагаемое $2ab$ с плюсом или с минусом труднее всего считается при решении настоящих задач. И если множитель $a$, кратный 10, всегда перемножается легко, то вот с множителем $b$, который является числом в пределах от одного до десяти, у многих учеников регулярно возникают затруднения.

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

Вот так за три минуты мы сделали умножение восьми примеров. Это меньше 25 секунд на каждое выражение. В реальности после небольшой тренировки вы будете считать еще быстрее. На подсчет любого двухзначного выражения у вас будет уходить не более пяти-шести секунд.

Но и это еще не все. Для тех, кому показанный прием кажется недостаточно быстрым и недостаточно крутым, предлагаю еще более быстрый способ умножения, который однако работает не для всех заданий, а лишь для тех, которые на единицу отличаются от кратных 10. В нашем уроке таких значений четыре: 51, 21, 81 и 39.

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

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

И так со всеми числами, отличающимися на единицу.

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

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

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

Ключевые моменты

С помощью этого приема вы сможете легко делать умножение любых натуральных чисел в пределах от 10 до 100. Причем все расчеты выполняются устно, без калькулятора и даже без бумаги!

Для начала запомните квадраты значений, кратных 10:

Далее — выкладки квадрата суммы или разности, в зависимости от того, к какому опорному значению ближе наше искомое выражение. Например:

Как считать еще быстрее

Но это еще не все! С помощью данных выражений моментально можно сделать возведение в квадрат чисел, «смежных» с опорными. Например, мы знаем 152 (опорное значение), а надо найти 142 (смежное число, которое на единицу меньше опорного). Давайте запишем:

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

Почему так происходит? Давайте запишем формулу квадрата суммы (и разности). Пусть $n$ — наше опорное значение. Тогда они считаются так:

— это и есть формула.

— аналогичная формула для чисел, больших на 1.

Надеюсь, данный прием сэкономит вам время на всех ответственных контрольных и экзаменах по математике. А у меня на этом все. До встречи!

Смотрите также:

Решение ЕГЭ-2011: вариант 1, часть B
Задача B1 — время, числа и проценты
Комбинаторика в задаче B6: легкий тест
Интегрирование по частям
Нестандартная задача B2: студенты, гонорары и налоги
Особенности решения неравенств с радикалами

Вход для учеников
ЕГЭ-2024
Школьникам
1. Арифметика
Арифметика
Дроби
Модуль
Проценты
Корни
Степени
Прогрессии
Текстовые задачи
2. Алгебра
Уравнения
Системы уравнений
Неравенства
Системы неравенств
Рациональные дроби
Функции
Многочлены
Логарифмы
Экспонента
Задачи с параметром
Вероятность
4. Геометрия
Треугольники
Многоугольники
Окружность
Стереометрия
Векторы
3. Математический анализ
Тригонометрия
Предел
Производная
Интегралы
Студентам
Реклама
Обо мне

При использовании материалов ссылка на сайт обязательна
Телефон: +7 (963) 963-99-33; почта: pavel@berdov.com
Карта сайта

Алгоритмы быстрого возведения в степень

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

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

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

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

Рекурсивное возведение в степень

Можно заметить, что для любого четного числа x и n выполнимо очевидное тождество

То есть всего за одну операцию умножения можно свести задачу к вдвое меньшей степени.

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

Если n нечетна, тогда можно перейти к степени (n-1),которая уже будет четной.

Таким образом, у нас есть реккурентная формула: от степени n мы переходим, если она четна

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

Распространим это полезное наблюдение на общий случай, воспользовавшись очевидным равенством

Если показатель степени n

Всего будет не более 2logn переходов, прежде чем мы придем к n=0. Таким образом, мы получили алгоритм, работающий за O(log n) умножений.

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

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

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

def my_power(val,p): if p


При каждом рекурсивном вызове в этом алгоритме удаляются младшие цифры двоичного представления степени n. Получается, что количество рекурсивных вызовов равно количеству битов двоичного представления n. Таким образом этот алгоритм вычисляет количество квадратов равное количеству рекурсивных вызовов и требует меньшего количество умножений, которое равно количеству 1 в двоичном представлении n.
Но есть ограничение для этого алгоритма, связанное с требуемым объемом вспомогательной памяти, который примерно пропорционален количеству рекурсивных вызовов — или, возможно больше, если объем на итерацию увеличивается.
Бинарный алгоритм возведения в степень
Один из самых популярных и эффективных способов возведения в степень. Данный алгоритм основан на двоичной записи показателя степени и свойстве возведения в квадрат, что позволяет ускорить вычисления при работе с большими числами. За счет использования двоичной записи показателя степени, бинарное возведение позволяет провести минимально возможное количество операций умножения, вследствие чего время вычисления степени существенно сокращается. Также данный алгоритм гарантирует правильность результата при любых значениях входных данных.
Суть бинарного метода заключается в том, что степень, в которую необходимо возвести число представляется в двоичном виде. И далее начинается проход по битам этого двоичного числа. Такой проход повторяется до тех пор, пока все биты не будут обработаны.
Существует бинарные алгоритмы, использующие схему “слева направо” и схему “справа налево”. Для всех этих схем количество операций возведения в квадрат одинаково и равно k, где k — длина показателя степени в n битах,
Количество же операций умножения равно количеству ненулевых элементов в двоичной записи числа n. В среднем требуется
операций умножения. Например, для возведения числа в сотую степень этим алгоритмом потребуется всего лишь 8 операций умножения и возведений в квадрат. Для сравнения, при стандартном способе возведения в степень требуется n-1 операций умножения, то есть количество операций может быть оценено как O(n).
Схема «слева направо»
Название фактически говорит само за себя, в данной схеме биты показателя степени просматриваются слева направо, то есть от старшего к младшему.
Представим показатель степень n в двоичной системе
Тогда число x в степени n можно записать так
И алгоритм возведения в степень при использовании данной схемы можно описать следующим образом

Представить показатель степени n в двоичном коде.
Зафиксировать индекс i и изменять его от k-1 до 0.
Если m_i=1, то текущий результат возводить в квадрат и затем умножать на х.
Если m_i=0, то текущий результат просто возводить в квадрат.

Или можно представить алгоритм так
Применим алгоритм, вычислив
Реализация в Python
def my_power(val, p): res, v, c = 1, val, p if c &1: res = v c>>=1 while c>0: v = v * v if c&1: res = v*res c = c>>1 return res
def my_power(val, p): res, v, c = 1, val, p bin_k = list(map(int,bin(p)[2:])) for i in range(len(bin_k)): res = res * res if bin_k[i] == 1: res = res*v return res 
Схема «справа налево»
Здесь, в отличие от схемы «слева направо» биты показателя степени просматриваются от младшего к старшему.
Алгоритм возведения в степень при использовании данной схемы можно описать следующим образом

Представить показатель степени n в двоичном коде.
Ввести вспомогательную переменную y равной числу x.
Зафиксировать индекс i и изменять его от 0 до k-1.
Если m_i =1, то текущий результат умножается на y, а само число y возводится в квадрат.
Если m_i=0, то требуется только возвести y в квадрат.

Данная схема содержит столько же умножений и возведений в квадрат, сколько и схема слева направо.
В, общем виде схему можно записать
Воспользовавшись формулой схемы возведения в степень справа налево посчитаем
В данном случае
Реализация в Python
def fast_pow(val, p): s, v,c =1,val,p while (c!=0): if (c %2==1): s = s* v c = c>>1 v = v*v return s
Лестница Монтгомери
Данный алгоритм часто используется в криптографии, так как обеспечивет защиту от актак по побочным каналам и позволяет сохранить показатель степени в секретности. Основная идея лестницы в том, что умножения происходят независимо от конкретного значения бита, то есть от того, что именно в показателе степени 0 или 1. Это дает то, что постоянно происходят разные вычисления и извне сложно понять что именно вообще происходит.
Для возведения числа х в степень n алгоритм можно представить следующим образом.

Ввести вспомогательные переменные


Зафиксировать индекс i и изменять его от k-1 до 0.
Если m_i=0, тогда


Если m_i=1, тогда


В переменной x_1 будет храниться результат возведения числа x в степень n.

Алгоритм выполняет фиксированную последовательность операций (от до log n): умножение и возведение в квадрат имеют место для каждого бита в степени независимо от конкретного значения бита.
Рассмотрим пример возведения числа 21 в степень 11. Представим показатель степени в двоичной системе.
def powers(val,p): x1 = 1 x2 = val bin_k = list(map(int,bin(p)[2:])) for i in range(len(bin_k)): if bin_k[i]==0: x2 = x1*x2 x1 = x1*x1 else: x1 = x1*x2 x2 = x2*x2 return x1
Метод множителей
Данный метод основан на представлении показателя степени в виде произведения множителей. Для этого метода необходимо раскладывать показатели степени в произведение простых множителей и возводить число в каждую из них. Таким образом, можно значительно ускорить процесс возведения в степень. Данный метод широко используется в задачах, связанных с криптографией и шифрованием данных, а также в задачах вычислительной математики. Известно, что любое натуральное число можно разложить на произведение простых чисел и такое разложение называется факторизацией. Например
Разложение числа на простые множители в общем виде можно представить так
Для того, чтобы разложить число на множители воспользуемся методом перебора делетелей. Будем перебирать простой делитель от 2 до корня из n и если n делится на этот делитель, то будем на него делить. И возможно нам понадобится делить несколько раз. Так мы сможем набрать простые делители и остановимся в тот момент, когда n станет либо 1, либо простым.
def factorize(n): factors = [] i =2 while i*i1: factors.append(n) return factors
После того, как получили разложение, можно возводить число в степень
def power_fact(n,p): lists = factorize(p) result = n for el in lists: result = result**el return result
Бином Ньютона
Скорее бином Ньютона не совсем относится к алгоритмам бстрого возведения в степень, но считаю, что в рамках статьи его можно рассмотреть. Бином Ньютона является формулой разложения произвольной натуральной степени суммы двух чисел в многочлен. То есть он поможет посчитать сумму двух чисел, возведенных в любую степень. Магия Бинома заключается в простоте и скорости.
Из уроков математики мы все помним такую формулу
И это тоже бином Ньютона, а точнее его частный случай.
В общем виде формула принимает вид
— число сочетаний из n по m.
Исходя из формулы для расчета бинома нам много раз надо будет посчитать факториал, то есть произведение всех чисел целых чисел от единицы до заданного числа. А факториалы в силу рекурсивности едят очень много оперативной памяти. Может так случиться, что при подсчете факториалов закончится оперативная память. И для этого на помощь приходит треугольник Паскаля.
Треугольник Паскаля — это специальный треугольник, в котором каждое число равно сумме двух чисел расположенных над ним. На вершине и по ребрам треугольника расположены единицы. Строки треугольника симметричны относительно вертикальной оси. Такой треугольник можно продолжать бесконечно.
Например, биномиальные коэффициенты для n=4

Тогда получим следующий бином
Из полученного многочлена можно заметить, что сумма степеней всегда равна n, а биномиальные коэффициенты симметричны.
Таким образом с помощью такого треугольника можно обойтись без всех этих факториалов, а просто быстро находить нужные коэффициенты, подставлять их в формулу бинома и получать ответ.
Используя бином Ньютона можно возводить очень большие числа в заданную степень раскладывая их на сумму двух чисел поменьше, а слагаемые считать через бином. Также бином Ньютона применяется в алгоритмах сжатия данных, криптографии и задачах связанных с комбинаторикой и вероятностями. Биномиальные коэффициенты часто применяются в матрицах и операциях с векторам, а на матрицах построены почти все нейронные сети.
Найдем коэффициенты в разложении Бинома
def my_binom(n): res=[1] for i in range(n): res=[1]+[res[i]+res[i+1] for i in range(len(res)-1)]+[1] return res
И посчитаем разложение бинома
def binoms(a,b,n): res = 0 k = 0 koef = my_binom(n) while k

За рамками статьи остались некоторые методы, которые являются еще более оптимальными, чем алгоритмы бинарного возведения в степень. К ним можно отнести алгоритмы с названием «метод окна», «метод скользящего окна». Смысл этих методов заключается в том, за один проход можно просмотреть не один, а несколько бит показателей степени, а также во время выполнения процесса можно изменять ширину окна, то есть количество просматриваемых битов.
Как еще можно ускорить вычисления. Если нужно многократно возводить одно и тоже число в разные степени, то можно использовать таблицу предвычисленных значений и обращаться к ней по индексу. Также можно использовать кэширование результатов вычислений, чтобы не повторять уже сделанные вычисления. Например, в Pyton для этого можно использовать декоратор @lru_cache из модуля functools. Если необходимо возводить в степень комплексные числа, тогда можно использовать функцию cmath.exp() , которая возводит его в заданную степень. Также важно учитывать особенности языка программирования и выбирать подходящие структуры.

Материал подготовлен для будущих студентов онлайн-курса OTUS «Математика для программистов». 13 декабря в рамках курса пройдет открытый урок «Разработка своего языка программирования с помощью ANTLR», на который приглашаем всех желающих. На занятии определим синтаксис и семантику Тьюринг-полного языка программирования. Записаться можно здесь.


Блог компании OTUS
Математика

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

Рассчитать

 Ссылка  Сохранить  Виджет
Алгоритмы быстрого возведения в степень
Если применять наивный способ возведения в степень - просто перемножить p-1 раз основание, нам потребуется на единицу меньше умножений, чем показатель степени. Несмотря на всю мощь современных компьютеров, такой способ нам не подходит, так как мы собираемся использовать для показателя числа даже большие, чем стандартные 64-битные целые. Например, в простом числе Мерсена: 618970019642690137449562111, уменьшая на единицу которое мы используем как значение показателя степени по-умолчанию, насчитывается 89 двоичных разрядов (см. Сколько бит занимает число). 
Чтобы оперировать подобными показателями требуются алгоритмы быстрого возведения в степень.
В калькуляторе Возведение полинома в степень мы уже задействовали один быстрый алгоритм возведения в степень, основанный на дереве степеней, который позволяет свести к минимуму число операций умножения. Однако для огромных показателей реализация этого алгоритма с хранением в памяти всего дерева степеней не подходит из-за ограничений по ресурсам. 
Поэтому в данном калькуляторе для вычисления степени мы применяем библиотеку bigInt, реализующую двоичный алгоритм, не требующий дополнительной памяти. Вариант этого алгоритма описан в той же статье, однако обработка двоичных разрядов показателя степени происходит там последовательно со старшего бита до младшего. В нашем случае это несколько неудобно, так как мы используем большие целые и не вдаваясь в реализацию хранилища целых, мы заранее не представляем, сколько разрядов они занимают в памяти.
Двоичный алгоритм возведения в степень справа налево
Поэтому алгоритм обрабатывает двоичное представление показателя степени начиная с младшего бита и кончая старшим (слева направо), согласно следующему алгоритму:
a //основание степени e //показатель степени m //модуль //Вычисление степени r ⟵ 1 while (e!=0) < if (e mod 2 = 1) r ⟵ r * a mod m; e ⟵ e / 2; a = a*a mod m; >output ⟵ r


Похожие публикации:

Bogon сети что это
Как посмотреть все символы шрифта
Как узнать сколько строк в файле python
Почему ssd загружен на 100 все тормозит

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

Как вычислить 2 в 64 степени, не пользуясь калькулятором?

Быстрое возведение чисел в квадрат без калькулятора

Ключевые моменты

Как считать еще быстрее

Алгоритмы быстрого возведения в степень

Рекурсивное возведение в степень

Бинарный алгоритм возведения в степень

Схема «слева направо»

Схема «справа налево»

Лестница Монтгомери

Метод множителей

Бином Ньютона

Быстрое возведение в степень по модулю

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

Алгоритмы быстрого возведения в степень

Двоичный алгоритм возведения в степень справа налево

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