Способ умножения русских крестьян

Русский крестьянский способ умножения и двоичная система счисления

В недавней своей статье об алгоритмах деления и действий вообще я упомянул, что школьные алгоритмы — лишь немногие из кучи, и, в частности, задел русский крестьянский способ умножения. Способ на самом деле уникальный, очень быстрый и точный, особенно, если понимать его суть. Сначала я приведу сам способ, а потом разъясню, на чём он основан. Самое интересное, как всегда, в конце.

Алгоритм умножения

1. Первый множитель целочисленно делится на 2 (отбрасывается остаток или дробная часть)
2. одновременно с ним второй множитель умножается на 2
3. оба результата записываются рядом.
4. Если в п.1. получилось число, больше единицы, то снова выполняется п.1. с последней записанной парой.
5. Исключаются (вычёркиваются) все пары результатов, где в п.1. получился чётный результат
6. суммируются оставшиеся результаты п.2.

Пример

Я покажу только конечную запись:

37 делили на 2, получая последовательно 18 (остаток 1 отбросили), 9, 4 (снова остаток отбросили), 2 и 1. 26 умножали на 2, получая каждый раз: 52, 10, 208, 416, 832. Вычеркнули строки с чётными 18, 4 и 2. Сложили оставшееся

Преимущества

Алгоритм не требует математических навыков кроме сложения. Я уже отмечал, что человек может выполнять только одно действие — сложение.

Алгоритм куда быстрее классического умножения по определению: здесь требуется выполнить всего 5 сложений числа самого с собой, 5 подборов на такое же сложение и 2 сложения «крупных» чисел в конце. Тогда как действую я по определению умножения, мы должны будем 37 складывать 26 раз.

Описание работы алгоритма

В то время, как привычный нам алгоритм умножения «столбиком» основан на разрядном умножении (если назреет необходимость, я более подробно его опишу) в десятичной системе счисления, то крестьянский метод использует закономерности двоичной системы счисления.

Давайте сейчас выполним то же самое, но запись будет в двоичной системе:

Посмотрите, насколько это легко! Целочисленное деление на 2 — это всего лишь «стирание» правой цифры у числа. А умножение на 2 — это всего лишь «дописываение» нуля справа от числа. В самом низу я записал результат сложения всех ярких чисел в правом столбике.

Теперь можно и догадаться, как эта «магия» работает. Посмотрите, оставлены только те строки, в которых первый множитель заканчивается на «1». То есть, если мы начнём разбирать двоичную запись первого множителя по цифрам, то увидим, что каждая единица в этой записи соответствует слагаемому в правом столбике. Умножение — суть многократное сложение. Как я ни пытался этого объяснить в других статьях, получал лишь минусы и гневные комментарии. Можно складывать штуками, можно складывать десятками штук, можно — сотнями. На этом построен алгоритм умножения «столбиком» в школьной (десятичной) математике. А здесь складываются штуками, двойками, четвёрками, восьмёрками и т.д.

Для данного умножения, нам надо число 26 (11010 в двоичной) взять 1 раз, потом ещё четыре раза и затем ещё 32 раза — количество «разов» соответствует разрядам, в которых стоят единицы в первом множителе.

Для любителей строгой математики покажу, как это работает в алгебраической форме:

И ещё два слова о коммутативности. Так как умножение коммутативно, в общем-то, не важно, что и на что мы умножаем. Но в начальной школе мы умножаем пельмени на тарелки, а не тарелки на пельмени (количество предметов на количество раз). В крестьянском методе получилось, что количество раз идёт впереди, именно первый множитель отвечает за количество раз, которое берётся второй. Проблема решается либо применением коммутативности (чаще), либо изменением порядка: делить будем второй множитель, а умножать — первый.

Немного об оптимизации

Сейчас, зная о «двоичной» природе этого алгоритма, мы можем дать рекомендации по оптимизации умножения. Например, вместо умножения длинного на короткий (при использовании определения умножения или «десятичного» метода именно это давало выигрыш в скорости), мы возьмём первым тот множитель, у которого в двоичной записи будет меньше единиц, и сэкономим на финальном сложении.

Вообще, довольно лихо для малограмотных крестьян (читали далеко не все) разработать метод умножения, основанный на двоичной системе счисления, который позволяет обходиться минималистичной записью, а то и исполнением в уме (потому что и писать-то не каждый умел). Такие ли они «малограмотные»? На Руси крестьяне, кстати сказать, неплохо управлялись именно с двоичной системой счисления: практически все действия так или иначе сводились к половинам, четвертинам и т.д. И эти алгоритмы отлично реализовывались на практике и были куда быстрее западных и даже восточных аналогов. Если бы русскому человеку не приходилось выживать в наших климатических условиях и тратить на это все силы, то, возможно, вычислительная техника появилась бы у нас гораздо гораздо раньше, чем Тьюринг что-то там накопировал у Маркова.

А теперь, как и обещал. Интересное:

Классический столбик в двоичной системе счисления

Запишу то же умножение (37*26) классическим «столбиком», но в двоичной системе счисления. И ещё для наглядности махну местами множители, чтобы, раз 37 в методе отвечает за разы, то в «столбике» оно тоже шло вторым:

Умножение в двоичной — всего лишь битовый сдвиг и сложение. Удивлены?

Источник

Умножение по методу русских крестьян

Иногда этот метод называют «крестьянское умножение», иногда «древнеегипетское», иногда «эфиопское», иногда «умножение через удвоение и деление пополам». Некоторым он хорошо известен, некоторым – непонятен, но при этом он достаточно полезен и может использоваться не только для умножения, но и для возведения в степень и расчётов матриц.

Алгоритм

Запишем два перемножаемых числа рядом – они станут заголовками двух столбцов. Третий столбец будет содержать нарастающую сумму.

Если число в левом столбце нечётное, мы добавляем число из правого столбца в нарастающую сумму. Изначально она будет равна нулю.

Затем в левом столбце ниже мы записываем число из заголовка, делённое пополам (с отбрасыванием остатка). 13 / 2 = 6. А во втором столбце мы пишем число, равное удвоению заголовка столбца, 19*2 = 38.

Поскольку число в левом столбце чётное, мы не увеличиваем нарастающую сумму.

Потом мы повторяем процесс деления на два и удвоения. В левом столбце будет 3, это число нечётное, поэтому мы добавляем к 19 76 и получаем 95.

Повторяя процедуру, мы получаем в результате 247.

Среднее между 13 и 19 будет 16
16 ^ 2 = 256
16 – 13 = 3
3 ^ 2 = 9
256 – 9 = 247

Если не закончить работу алгоритма, то в левом столбце будут сплошные нули, и поскольку 0 – чётное число, к нарастающей сумме добавлять ничего не будет нужно. Поэтому, как только мы получаем в левом столбце единицу, в третьем столбце появляется ответ.

Доказательство

Почему это работает? Можно сказать, что это обычное двоичное длинное умножение. Но мы приведём более длинное объяснение, которое будет заодно и более общим.

Обозначим число в левом столбце A, во втором – B, нарастающую сумму – R, а ответ – P. Следовательно

Тогда, если A чётное, то есть k, для которого A=2k. Перепишем уравнение:

Или, что то же самое:

Если мы заменим A половиной его значения, а B – удвоенным значением, и назовём их A’ и B’, то:

То есть, если A чётное, мы уполовиним первое число и удвоим второе, и наше уравнение верно. А если нечётное? Тогда A=2k+1

И опять мы обозначили половину A через A’ и удвоенное B через B’.

Наше уравнение верно, если мы:

• добавили число из второго столбца к нарастающей сумме
• уполовинили первый столбец
• удвоили второй

Видно, что наше уравнение остаётся сбалансированным при выполнении шагов нашего алгоритма.

Когда мы доходим до нуля, то имеем:

Или R=P. Наша нарастающая сумма равна нужному результату.

Обобщение 1: возведение в степень

Попробуем подсчитать 2 13 . При возведении в степень мы перемножаем числа, а не складываем, поэтому мы усовершенствуем наш алгоритм:

заменим сложение умножением
заменим удвоение возведением в квадрат

Нарастающее произведение начинается с 1. 13 – нечётное, поэтому умножаем второй столбец на нарастающее произведение, получая 2. Теперь мы уполовиним 13 и возведём 2 в квадрат.

6 – чётное, не умножаем нарастающее произведение. Уполовиним 6 и возведём в квадрат 4, получим 16.

3 – нечётное, умножаем 16 на наше нарастающее произведение, получим 32. Уполовиним первый столбец и возведём в квадрат второй.

Последний шаг: 1 – нечётное, умножаем 256 на 32, получаем 8192, что и является ответом.

Доказательство этого алгоритма такое же, как и у прошлого, просто теперь наше уравнение выглядит так:

Обобщение 2: матрицы

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

Далее идёт функция, написанная на языке Python. Она работает для любой неотрицательной степени, и «базы» любого типа, поддерживающего ассоциативное умножение. Иными словами, она работает для любой коллекции с умножением, являющейся моноидом.

Этого даже не нужно понимать, достаточно знать, что она работает для матриц.

Источник

Способ умножения русских крестьян

Русский, крестьянский способ умножения

Предисловие от автора сайта.

Не только великий Пифагор думал и учил окружающих тому, что способов действия с числами – бесконечное множество.

Очень далеко от Греческого города Кротона, где творил Пифагор, а также много лет спустя , причём, вряд ли под непосредственным влиянием Пифагора, в России, были, оказывается творческие личности, которые не были связаны догматами о законченности арифметики.

Наверное, тогда ещё не было Академии наук, стоящей на страже свободного развития математики.

И, вот вам отличный пример того, как русские люди в очередной раз изобрели «пифагоровский» велосипед.

Перед тем, как вы, уважаемый читатель начнёте чтение этого способа умножения, я хочу обратить ваше внимание на то, что в этом русском способе умножения нет знаменитой таблицы умножения, но есть МАНИПУЛЯЦИИ, которые приводят к нужному результату.

И это – главный момент в проблеме новой науки – числонавтики, где именно открытие новых манипуляций с цифрами и числами открывает действительно необычные пути к познанию их тайн.

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

Здесь необходимо было лишь умение умножать и делить числа на два.

1. Одно запишем слева, а второе — справа на одной строчке.

2. Левое чис ло будем делить на 2, а правое — умножать на 2 и результаты записывать в столбик.

3. Если при делении возникнет остаток, то он отбрасывается.

4. Опе рацию продолжаем, пока слева не останется 1.

5. Затем вычеркнем те строч ки, в которых слева стоят четные числа и сложим оставшиеся числа в пра вом столбце .

Источник

Способ умножения русских крестьян

«Русский» способ умножения

Вы не можете выполнить умножение многозначных чисел, хотя бы даже двузначных, если не помните наизусть всех результатов умножения однозначных чисел, то-есть того, что называется таблицей умножения. В старинной «Арифметике» Магницкого, о которой мы уже упоминали, необходимость твердого знания таблицы умножения воспета в таких — чуждых для современного слуха — стихах:

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

Деление пополам продолжают до тех пор, пока в частном не получится 1, параллельно удваивая другое число. Последнее удвоенное число и дает искомый результат. Нетрудно понять, на чем этот способ основан: произведение не изменяется, если один множитель уменьшить вдвое, а другой вдвое же увеличить. Ясно поэтому, что в результате многократного повторения зтой операции получается искомое произведение:

Однако как поступить, если при этом приходится делить пополам число нечетное?

Народный способ легко выводит из этого затруднения. Надо — гласит правило — в случае нечетного числа откинуть единицу и делить остаток пополам; но зато к последнему числу правого столбца нужно будет прибавить все те числа этого столбца, которые стоят против нечетных чисел левого столбца; сумма и будет искомым произведением. Практически это делают так, что все строки с четными левыми числами зачеркивают; остаются только те, которые содержат налево нечетное число. Приведем пример (звездочки указывают, что данную строку надо зачеркнуть):

Сложив незачеркнутые числа, получаем вполне правильный результат:

На чем основан этот прием?

Обоснованность приема станет ясна, если принять во внимание, что

Ясно, что числа 17, 34 и т. п., утрачиваемые при делении нечетного числа пополам, необходимо прибавить к результату последнего умножения, чтобы получить произведение.

Источник

Русский способ умножения

Недавно, прочитав статью на хабре Как сделать из 123456789 число 100 или 0 и решил почитать «Занимательную арифметику» Я. И. Перельмана, очень интересная книга, в которой можно кроме всего прочего узнать как работают обыкновенные счёты.

Но сегодня хотелось бы рассказать про исконно русский, как любит говорить Задорнов, метод умножения. Как известно, для того что бы умножить 2 числа, необходимо как минимум знать таблицу умножения. А ведь наши предки умели умножать и без таблицы умножения всего лишь за несколько итераций. Способ этот, не похожий на наши школьные приемы, употребителен в обиходе русских крестьян и унаследован ими из глубокой древности. Сущность его в том, что умножение любых двух чисел сводится к ряду последовательных делений одного числа пополам при одновременном удвоении другого числа.

32 X 13
16 X 26
8 X 52
4 X 104
2 X 208
1 X 416

Деление продолжают до тех пор, пока в частном не получится 1, параллельно удваивая другое число. Последнее удвоенное число и дает искомый результат. Нетрудно понять на чем этот способ основан: произведение не изменяется, если один множитель уменьшить вдвое, а другой вдвое же увеличить. Ясно поэтому, что в результате многократного повторения этой операции получается искомое произведение:

32 X 13 = 1 X 416

Однако как поступить, если при этом приходится делить пополам число нечетное?

Народный способ легко выходит из этого затруднения. Надо — гласит правило, — в случае нечетного числа откинуть единицу и делить остаток пополам; но зато к последнему числу правого столбца нужно будет прибавить все те числа этого столбца, которые стоят против нечетных чисел левого столбца: сумма и будет исходным произведением. Практически его делают так, что все строки с четными левыми числами зачеркивают; остаются только те, которые содержат слева нечетное число. Приведем пример (звездочка указывает, что данную строку надо зачеркнуть):

19 X 17
9 X 34
4 X 68*
2 X 136*
1 X 272

Сложив не зачеркнутые числа, получаем вполне правильный результат:
17 + 34 + 272 = 323.

На чем основан этот прием?

Обоснованность приема станет ясна, если принять во внимание, что
19 Х 17 = (18 + 1)17 = 18 X 17 + 17,
9 X 34 = (8 + 1)34 = 8 X 34 + 34 и т. д.
Ясно, что числа 17, 34 и т. п., утрачиваемые при делении нечетного числа пополам, необходимо прибавить к результату последнего умножения, чтобы получить произведение.

Для реализации этого метода решил написать небольшой класс, который умеет умножать «по-русски» на java с использованием операции сдвига (уж очень давно её не использовал). Не исключено, что реализовать метод можно и используя рекурсию.

Источник