Древний алгоритм в действии: как работает метод «удвоения и деления»
Популяризаторы науки с YouTube-канала Numberphile вновь привлекли внимание к архаичному способу умножения. Этот алгоритм, известный под названиями «крестьянский метод», «египетская математика» или «русское умножение» (как называет его ветеран математического просвещения Джонни Болл), удивляет своей эффективностью и простотой.
Механика процесса предельно ясна: запишите два множителя в верхней строке двух параллельных столбцов. В левой колонке последовательно делите число пополам, игнорируя остаток, пока не дойдете до единицы. В правой колонке параллельно удваивайте число столько раз, сколько строк получилось слева.
Когда таблица готова, проведите ревизию: вычеркните все строки, в которых в левом столбце стоит четное число. Это правило касается и самой первой строки, если исходный множитель был четным.
Финальный этап — суммирование оставшихся чисел в правом столбце. Полученная сумма и будет искомым произведением.
Данная техника универсальна и безошибочно работает для любых чисел, независимо от того, в каком порядке вы их расположите в столбцах.
В чем секрет эффективности этого приема?
Джонни Болл вспоминает об этом методе с ностальгией — когда-то в британских пабах это было популярным развлечением для интеллектуалов. Несмотря на обиходное название «русское умножение», корни алгоритма уходят в Древний Египет. Фундаментально этот способ опирается на принципы двоичной системы счисления.
В двоичной системе (с основанием 2) используются лишь нули и единицы, а позиции соответствуют степеням двойки. Ниже представлена визуализация того, как десятичные числа трансформируются в двоичные разряды.
Связь метода «деления и удвоения» с бинарным кодом очевидна. Процесс перевода числа из десятичной системы в двоичную напоминает расчет сдачи: вы выделяете максимально возможную степень двойки, которая «помещается» в ваше число, вычитаете её и повторяете операцию с остатком.
Для наших предков, не имевших под рукой бумаги или калькуляторов, этот метод был спасением. Привычное нам «умножение в столбик» требует записи множества промежуточных результатов и хорошей памяти. В то же время алгоритм удвоения позволял проводить сложные расчеты, используя обычные счетные палочки или камешки.
Многим этот метод кажется ловким математическим фокусом, подобным трюкам с числом 9. Однако здесь нет никакой магии — это чистая логика. Даже если вы попытаетесь умножить степени двойки, алгоритм сработает безупречно: все строки будут вычеркнуты, кроме последней, которая и укажет на верный ответ.
