Если в Excel 2007 умножить 850 на 77.1, то результат будет 100000, а не 65535, как ожидается. Более того, если прибавить 1 (=A1+1), то результат будет 100001, а если отнять, то 65534. Случаев, когда Excel 2007 ошибается достаточно много:
«Китайский» способ умножения
1 мин
Случайно наткнулся в сети на такой ролик:
Очень удивился, а потом сел и разобрался. Всё просто и похоже на умножение столбиком. Сначала рисуем пересекающиеся группы линий для обоих чисел. Для каждого разряда рисуется одна группа из линий. Количество линий совпадает со стоящем в этом разряде числом (если в разряде будет стоять ноль — можно нарисовать пунктирную линию чтобы не потерять разряд). А затем по диагоналям подсчитываем кол-во пересечений и собираем результат. Способ по сравнению с умножением в стобик получается более наглядным, на мой взгляд.
Правда умножать им длинные числа и числа, в разрядах которых много девяток, как заметили в коментариях, не очень удобно — слишком уж много линий. :)
Очень удивился, а потом сел и разобрался. Всё просто и похоже на умножение столбиком. Сначала рисуем пересекающиеся группы линий для обоих чисел. Для каждого разряда рисуется одна группа из линий. Количество линий совпадает со стоящем в этом разряде числом (если в разряде будет стоять ноль — можно нарисовать пунктирную линию чтобы не потерять разряд). А затем по диагоналям подсчитываем кол-во пересечений и собираем результат. Способ по сравнению с умножением в стобик получается более наглядным, на мой взгляд.
Правда умножать им длинные числа и числа, в разрядах которых много девяток, как заметили в коментариях, не очень удобно — слишком уж много линий. :)
Быстрое умножение многочленов при помощи преобразования Фурье — это просто
9 мин
Добрый вечер.
Этот пост посвящён быстрому преобразованию Фурье. Будут рассмотрены прямое и обратное преобразования (в комплексных числах). В следующей части я планирую рассмотреть их применения в некоторых задачах олимпиадного программирования (в частности, одна задача про «похожесть» строк), а также рассказать про реализацию преобразования в целых числах.
БПФ — это алгоритм, вычисляющий значения многочлена степени n=2k в некоторых n точках за время O(n⋅logn) («наивный» метод выполняет ту же задачу за время O(n2)). За то же время можно выполнить и обратное преобразование. Так как складывать, вычитать и умножать массивы чисел гораздо легче, чем многочлены (особенно умножать), БПФ часто применяется для ускорения вычислений с многочленами и длинными числами.
Этот пост посвящён быстрому преобразованию Фурье. Будут рассмотрены прямое и обратное преобразования (в комплексных числах). В следующей части я планирую рассмотреть их применения в некоторых задачах олимпиадного программирования (в частности, одна задача про «похожесть» строк), а также рассказать про реализацию преобразования в целых числах.
БПФ — это алгоритм, вычисляющий значения многочлена степени n=2k в некоторых n точках за время O(n⋅logn) («наивный» метод выполняет ту же задачу за время O(n2)). За то же время можно выполнить и обратное преобразование. Так как складывать, вычитать и умножать массивы чисел гораздо легче, чем многочлены (особенно умножать), БПФ часто применяется для ускорения вычислений с многочленами и длинными числами.
Переполнение при умножении
3 мин
Перед выполнением умножения C++ приводит множители к одному типу не короче int, а разрядность результата совпадает с разрядностью приведенных множителей. Для того, чтобы не потерять точность, иногда требуется для умножения выполнять дополнительные операции.
Как помочь ребенку выучить таблицу умножения
6 мин
Недавно мне задали этот вопрос, и после моего рассказа как я научил таблице умножения одного моего знакомого мальчика, оказалось, что по этим советам еще один ученик довольно быстро выучил таблицу умножения без монотонного заучивания. Поэтому я подумал, что будет полезным рассказать и вам эти простые приемы, вдруг перед вами тоже встанет такая задача, например, при обучении своего ребенка.
После довольно понятных сложения и вычитания, зубрежка таблицы умножения часто выглядит как некий скучный ритуал, лишенный какой-либо наглядности. Поэтому многие школьники довольно быстро утрачивают интерес и плохо ее знают, а это отражается на всем образовании. Я уверен, что обучение умножению это очень важный опыт, который сказывается на общей уверенности человека в собственных знаниях и возможностях ума, и, может быть, даже рациональном выборе профессии.
Описанные приемы довольно просты, и, строго говоря, давно известны. Запоминание в моем рассказе происходит тоже через частые повторения примеров, но все они – лишь разные события одной игры в которой этим перемножения оживают. Я обобщил известные мне приемы и составил для своего ученика такое расписание, чтобы чуть более сложное чередовалось с простым. Ввиду занятности такого обучения, одновременно с запоминанием таблицы ребенок узнает и другие интересные вещи из мира арифметики и вообще математики: о простых числах, признаке деления на 3, степенях двойки и так далее.
Также косвенно в рассказе упоминаются и некоторые способы мотивации. Само наше обучение, как станет ясно из повествования, представляло собой игру. Уверен, в комментариях вы сможете дополнить мою историю своими интересными идеями и методами, о которых я не знал, что поможет сделать рассказ более полным для того, кто натолкнется на него в поисках ответа на вопрос заголовка статьи.
Умножение по методу русских крестьян
3 мин
Перевод
Иногда этот метод называют «крестьянское умножение», иногда «древнеегипетское», иногда «эфиопское», иногда «умножение через удвоение и деление пополам». Некоторым он хорошо известен, некоторым – непонятен, но при этом он достаточно полезен и может использоваться не только для умножения, но и для возведения в степень и расчётов матриц.
Запишем два перемножаемых числа рядом – они станут заголовками двух столбцов. Третий столбец будет содержать нарастающую сумму.
Если число в левом столбце нечётное, мы добавляем число из правого столбца в нарастающую сумму. Изначально она будет равна нулю.
Затем в левом столбце ниже мы записываем число из заголовка, делённое пополам (с отбрасыванием остатка). 13 / 2 = 6. А во втором столбце мы пишем число, равное удвоению заголовка столбца, 19*2 = 38.
Поскольку число в левом столбце чётное, мы не увеличиваем нарастающую сумму.
Алгоритм
13 x 19 -> 0
6 38 19
3 76 ->
1 152 -> 95
0 304 247
^^^
Запишем два перемножаемых числа рядом – они станут заголовками двух столбцов. Третий столбец будет содержать нарастающую сумму.
Если число в левом столбце нечётное, мы добавляем число из правого столбца в нарастающую сумму. Изначально она будет равна нулю.
Затем в левом столбце ниже мы записываем число из заголовка, делённое пополам (с отбрасыванием остатка). 13 / 2 = 6. А во втором столбце мы пишем число, равное удвоению заголовка столбца, 19*2 = 38.
Поскольку число в левом столбце чётное, мы не увеличиваем нарастающую сумму.
Что там с JEP-303 или изобретаем invokedynamic
8 мин
Блогеры и авторы, пытающиеся быть на передовой, уже немало писали про проект Amber в Java 10. В этих статьях обязательно упоминается вывод типов локальных переменных, улучшения enum и лямбд, иногда пишут про pattern matching и data-классы. Но при этом незаслуженно обходится стороной JEP 303: Intrinsics for the LDC and INVOKEDYNAMIC Instructions. Возможно, потому что мало кто понимает, к чему это вообще. Хотя любопытно, что именно об этой фиче ребята из NIX_Solutions фантазировали на Хабре год назад.
Широко известно, что в виртуальной машине Java, начиная с версии 7, есть интересная инструкция invokedynamic (она же indy). Про неё многие слышали, однако мало кто знает, что она делает на самом деле. Кто-то знает, что она используется при компиляции лямбда-выражений и ссылок на методы в Java 8. Некоторые слышали, что через неё реализована конкатенация строк в Java 9. Но хотя это полезные применения indy, изначальная цель всё же немного другая: делать динамический вызов, при котором вы можете вызывать разный код в одном и том же месте. Эта возможность не используется ни в лямбдах, ни в конкатенации строк: там поведение всегда генерируется при первом вызове и остаётся постоянным до конца работы программы (всегда используется ConstantCallSite). Давайте посмотрим, что можно сделать ещё.
Криптография русского крестьянина
5 мин
Перевод
Какая связь есть между умножением методом русских крестьян и современной криптографией? В отличие от обычно изучаемых процедур умножения, его можно запросто адаптировать под вычисление степеней, а не произведений; и в некоторых криптосистемах требуется вычисление именно степеней.
Должен сразу признаться, что статья не будет посвящена тому, как русским крестьянам удавалось обмениваться информацией втайне от своих помещиков.
Умножение методом русских крестьян
Если вы не знали о нём раньше, то это довольно любопытный подход к умножению, который не требует запоминания таблиц умножения — для него достаточно способности удваивать и делить пополам целые числа. Не очень понятно, как он относится к русским крестьянам: похоже, так же, как «датская сдоба» к Дании. Этот метод был известен ещё древним египтянам, которые явно жили намного раньше русских крестьян.
Общее описание метода просто, но не слишком информативно. Тем не менее, давайте начнём с него.
Математики обнаружили идеальный способ перемножения чисел
5 мин
Перевод
Разбивая крупные числа на мелкие, исследователи превысили фундаментальное математическое ограничение скорости
Четыре тысячи лет назад жители Вавилонии изобрели умножение. А в марте этого года математики усовершенствовали его.
18 марта 2019 два исследователя описали самый быстрый из известных методов перемножения двух очень больших чисел. Работа отмечает кульминацию давнишнего поиска наиболее эффективной процедуры выполнения одной из базовых операций математики.
«Все думают, что метод умножения, который они учили в школе, наилучший, но на самом деле в этой области идут активные исследования», — говорит Йорис ван дер Хувен, математик из Французского национального центра научных исследований, один из соавторов работы.
Новый подход к умножению подсказывает, как улучшить квантовые компьютеры
4 мин
Перевод
На практике на квантовых компьютерах нельзя запускать многие программы, предназначенные для классических компьютерах, поскольку они не умеют выборочно забывать информацию. Новый алгоритм умножения показывает, как можно обойти эту проблему
Классические биты – чёрно-белые, а квантовые немного сложнее
Когда мне было 9, родители купили новый компьютер. Он практически по всем статьям был лучше старого, кроме одного: на нём не запускались мои любимые гонки. Помню, как я думал – зачем нужен новомодный компьютер, если он не запускает мою самую любимую программу?
Та же проблема есть и у квантовых компьютеров. В теории они способны на всё, на что способен классический. На практике их квантовость делает практически невозможным запуск некоторых наиболее важных классических алгоритмов.
Об одной недокументированной особенности умножения и деления на процессорах x86
4 мин
Начиная с процессора 80286 компания Intel поддерживала полную совместимость «снизу-вверх» в системе команд. То есть если какая-то из команд процессора дает такой-то результат на 8086, то и на более поздних процессорах результат будет точно таким же (сейчас не будем рассматривать ошибки типа неправильного деления в Pentium I).
Но так ли это? Что за вопрос! Ведь если бы совместимость не сохранялась, то старые программы не могли бы выполняться, а ведь до сих пор на любом компьютере можно поностальгировать запустив Norton Commander или Tetris. Однако не все так просто… Начиная с 8080 в процессорах Intel есть регистр флагов, состояние которого определяется результатом последней команды вычисления данных. Все флаги в нем давно описаны и поведение их строго зафиксировано. Кроме двух исключений.
Перемножение чисел без умножения
1 мин
Как-то вдруг задумался о перемножении чисел без использования инструкций умножения.
Нужно сказать, что в корне данной задачи лежит сдвиг числа на то количество бит, на котором месте эти биты находятся. Собственно и обнаружил я эту закономерность совершенно случайно.
В результате недолгого мозгового штурма получился следующий ниже код, в регистре esi получаем произведение eax * ebx.
Разумеется представленная версия кода ограничивает результат 32-мя битами, но ведь разрядность при желании можно и расширить, главное - концепция.
Алгоритмы быстрого умножения чисел: от столбика до Шенхаге-Штрассена
Средний
26 мин
При написании высокоуровневого кода мы редко задумываемся о том, как реализованы те или иные инструменты, которые мы используем. Ради этого и строится каскад абстракций: находясь на одном его уровне, мы можем уместить задачу в голове целиком и сконцентрироваться на её решении.
И уж конечно, никогда при написании a * b мы не задумываемся о том, как реализовано умножение чисел a и b в нашем языке. Какие вообще есть алгоритмы умножения? Это какая-то нетривиальная задача?
В этой статье я разберу с нуля несколько основных алгоритмов быстрого умножения целых чисел вместе с математическими приёмами, делающими их возможными.