В недавней своей статье об алгоритмах деления и действий вообще я упомянул, что школьные алгоритмы - лишь немногие из кучи, и, в частности, задел русский крестьянский способ умножения. Способ на самом деле уникальный, очень быстрый и точный, особенно, если понимать его суть. Сначала я приведу сам способ, а потом разъясню, на чём он основан. Самое интересное, как всегда, в конце.
Алгоритм умножения
- Первый множитель целочисленно делится на 2 (отбрасывается остаток или дробная часть)
- одновременно с ним второй множитель умножается на 2
- оба результата записываются рядом.
- Если в п.1. получилось число, больше единицы, то снова выполняется п.1. с последней записанной парой.
- Исключаются (вычёркиваются) все пары результатов, где в п.1. получился чётный результат
- суммируются оставшиеся результаты п.2.
Пример
37*26
Я покажу только конечную запись:
37 делили на 2, получая последовательно 18 (остаток 1 отбросили), 9, 4 (снова остаток отбросили), 2 и 1. 26 умножали на 2, получая каждый раз: 52, 10, 208, 416, 832. Вычеркнули строки с чётными 18, 4 и 2. Сложили оставшееся
Преимущества
Алгоритм не требует математических навыков кроме сложения. Я уже отмечал, что человек может выполнять только одно действие - сложение. Здесь все действия сведены к сложению: умножение на 2 без потерь можно заменить на более лёгкое сложение числа с собой, а деление на 2 отлично выполняется через подбор с тем же умножением, заменённым на сложение.
Алгоритм куда быстрее классического умножения по определению: здесь требуется выполнить всего 5 сложений числа самого с собой, 5 подборов на такое же сложение и 2 сложения "крупных" чисел в конце. Тогда как действую я по определению умножения, мы должны будем 37 складывать 26 раз.
Описание работы алгоритма
В то время, как привычный нам алгоритм умножения "столбиком" основан на разрядном умножении (если назреет необходимость, я более подробно его опишу) в десятичной системе счисления, то крестьянский метод использует закономерности двоичной системы счисления.
Давайте сейчас выполним то же самое, но запись будет в двоичной системе:
Посмотрите, насколько это легко! Целочисленное деление на 2 - это всего лишь "стирание" правой цифры у числа. А умножение на 2 - это всего лишь "дописываение" нуля справа от числа. В самом низу я записал результат сложения всех ярких чисел в правом столбике.
Теперь можно и догадаться, как эта "магия" работает. Посмотрите, оставлены только те строки, в которых первый множитель заканчивается на "1". То есть, если мы начнём разбирать двоичную запись первого множителя по цифрам, то увидим, что каждая единица в этой записи соответствует слагаемому в правом столбике. Умножение - суть многократное сложение. Как я ни пытался этого объяснить в других статьях, получал лишь минусы и гневные комментарии. Можно складывать штуками, можно складывать десятками штук, можно - сотнями. На этом построен алгоритм умножения "столбиком" в школьной (десятичной) математике. А здесь складываются штуками, двойками, четвёрками, восьмёрками и т.д.
Для данного умножения, нам надо число 26 (11010 в двоичной) взять 1 раз, потом ещё четыре раза и затем ещё 32 раза - количество "разов" соответствует разрядам, в которых стоят единицы в первом множителе.
Для любителей строгой математики покажу, как это работает в алгебраической форме:
В первой строке вместо "1001010" следует читать "100101" (спасибо)
И ещё два слова о коммутативности. Так как умножение коммутативно, в общем-то, не важно, что и на что мы умножаем. Но в начальной школе мы умножаем пельмени на тарелки, а не тарелки на пельмени (количество предметов на количество раз). В крестьянском методе получилось, что количество раз идёт впереди, именно первый множитель отвечает за количество раз, которое берётся второй. Проблема решается либо применением коммутативности (чаще), либо изменением порядка: делить будем второй множитель, а умножать - первый.
Немного об оптимизации
Сейчас, зная о "двоичной" природе этого алгоритма, мы можем дать рекомендации по оптимизации умножения. Например, вместо умножения длинного на короткий (при использовании определения умножения или "десятичного" метода именно это давало выигрыш в скорости), мы возьмём первым тот множитель, у которого в двоичной записи будет меньше единиц, и сэкономим на финальном сложении.
Вообще, довольно лихо для малограмотных крестьян (читали далеко не все) разработать метод умножения, основанный на двоичной системе счисления, который позволяет обходиться минималистичной записью, а то и исполнением в уме (потому что и писать-то не каждый умел). Такие ли они "малограмотные"? На Руси крестьяне, кстати сказать, неплохо управлялись именно с двоичной системой счисления: практически все действия так или иначе сводились к половинам, четвертинам и т.д. И эти алгоритмы отлично реализовывались на практике и были куда быстрее западных и даже восточных аналогов. Если бы русскому человеку не приходилось выживать в наших климатических условиях и тратить на это все силы, то, возможно, вычислительная техника появилась бы у нас гораздо гораздо раньше, чем Тьюринг что-то там накопировал у Маркова.
А теперь, как и обещал. Интересное:
Классический столбик в двоичной системе счисления
Запишу то же умножение (37*26) классическим "столбиком", но в двоичной системе счисления. И ещё для наглядности махну местами множители, чтобы, раз 37 в методе отвечает за разы, то в "столбике" оно тоже шло вторым:
Умножение в двоичной - всего лишь битовый сдвиг и сложение. Удивлены?
PS
Понравился разбор - ставьте лайк и подписывайтесь на канал. Делитесь в соцсетях, и, если эта статья наберёт много просмотров, разберём "ментальную" арифметику и "китайский" метод с сеткой. И много что ещё.