Здравствуйте!
Расскажу о серии задач, которая случайно возникла в процессе решения другой задачи. Мне на глаза попалось равенство:
81 * 27 = 2187
– Интересно, – подумал я. – А бывают ли ещё такие числа, чтобы цифры слева и справа повторялись?
Всего нашлось 7 двузначных пар, включая одну с теми же цифрами:
15 * 93 = 1395
21 * 60 = 1260
21 * 87 = 1827
27 * 81 = 2187
30 * 51 = 1530
Читать полностью »
Начиная с процессора 80286 компания Intel поддерживала полную совместимость «снизу-вверх» в системе команд. То есть если какая-то из команд процессора дает такой-то результат на 8086, то и на более поздних процессорах результат будет точно таким же (сейчас не будем рассматривать ошибки типа неправильного деления в Pentium I).
Четыре тысячи лет назад жители Вавилонии изобрели умножение. А в марте этого года математики усовершенствовали его.
18 марта 2019 два исследователя описали самый быстрый из известных методов перемножения двух очень больших чисел. Работа отмечает кульминацию давнишнего поиска наиболее эффективной процедуры выполнения одной из базовых операций математики.
«Все думают, что метод умножения, который они учили в школе, наилучший, но на самом деле в этой области идут активные исследования», — говорит Йорис ван дер Хувен, математик из Французского национального центра научных исследований, один из соавторов работы.
Читать полностью »
Какая связь есть между умножением методом русских крестьян и современной криптографией? В отличие от обычно изучаемых процедур умножения, его можно запросто адаптировать под вычисление степеней, а не произведений; и в некоторых криптосистемах требуется вычисление именно степеней.
Должен сразу признаться, что статья не будет посвящена тому, как русским крестьянам удавалось обмениваться информацией втайне от своих помещиков.
Если вы не знали о нём раньше, то это довольно любопытный подход к умножению, который не требует запоминания таблиц умножения — для него достаточно способности удваивать и делить пополам целые числа. Не очень понятно, как он относится к русским крестьянам: похоже, так же, как «датская сдоба» к Дании. Этот метод был известен ещё древним египтянам, которые явно жили намного раньше русских крестьян.
Общее описание метода просто, но не слишком информативно. Тем не менее, давайте начнём с него.
Читать полностью »
Блогеры и авторы, пытающиеся быть на передовой, уже немало писали про проект 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). Давайте посмотрим, что можно сделать ещё.
Иногда этот метод называют «крестьянское умножение», иногда «древнеегипетское», иногда «эфиопское», иногда «умножение через удвоение и деление пополам». Некоторым он хорошо известен, некоторым – непонятен, но при этом он достаточно полезен и может использоваться не только для умножения, но и для возведения в степень и расчётов матриц.
13 x 19 -> 0
6 38 19
3 76 ->
1 152 -> 95
0 304 247
^^^
Запишем два перемножаемых числа рядом – они станут заголовками двух столбцов. Третий столбец будет содержать нарастающую сумму.
Если число в левом столбце нечётное, мы добавляем число из правого столбца в нарастающую сумму. Изначально она будет равна нулю.
Затем в левом столбце ниже мы записываем число из заголовка, делённое пополам (с отбрасыванием остатка). 13 / 2 = 6. А во втором столбце мы пишем число, равное удвоению заголовка столбца, 19*2 = 38.
Поскольку число в левом столбце чётное, мы не увеличиваем нарастающую сумму.
Читать полностью »