Pull to refresh

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

Недавно, прочитав статью на хабре Как сделать из 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 с использованием операции сдвига (уж очень давно её не использовал). Не исключено, что реализовать метод можно и используя рекурсию.

public class Multiplying {

	public long multiply(long m1, long m2) {
		return multiplyRussian(m1, m2);
	}

	private long multiplyRussian(long m1, long m2) {
		List<Long> loosed = new ArrayList<Long>();
		long res = m2;
		while (m1 != 1) {
			if (m1 % 2 != 0) {
				m1--;
				loosed.add(res);
			}
			res <<= 1;
			m1 >>= 1;
		}
		for (Long loose : loosed) {
			res += loose;
		}
		return res;
	}

}
Tags:
Hubs:
You can’t comment this publication because its author is not yet a full member of the community. You will be able to contact the author only after he or she has been invited by someone in the community. Until then, author’s username will be hidden by an alias.