x, y, z

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

# 20 Дек 2015 13:42:26
Evgeniy

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

Пример выполнения алгоритма:

13 x 19 -> 0
6 38 19
3 76 ->
1 152 -> 95
0 304 247
^^^


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

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

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

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

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

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

Проверка:

Среднее между 13 и 19 будет 16

16^2 = 256
16 – 3 = 3
3^2 = 9
256 – 9 = 247

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

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

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

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

(A*B) + R = P

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

(2k*B) + R = P

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

(k*2B) + R = P

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

(A'*B') + R = P

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

A*B + R = P

(2k+1)*B + R = P

2k*B + B + R = P

2k*B + (B+R) = P

K*2B + (B+R) = P

A'*B' + (B+R) = P

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

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

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

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

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

0*B + R = P

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

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

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


степень база
13 2 -> 1
6 4 2
3 16 ->
1 256 -> 32
0 65546 8192
^^^^


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

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

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

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

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

BA*R=E

Обобщение 2. Матрицы

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

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

def fast_exp(b,e,I=1):
# Подсчёт b^e, где e – неотрицательное целое. Начинаем с
# нарастающего произведения I, так что эта функция будет
# работать и с числами, и с матрицами

result = I
while e > 0:

if is_odd(e):
result *= b
b *= b
e = e / 2

return result


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

Ссылки:
https://www.google.co.uk/search?q=russian+peasant+multiplication
https://www.google.co.uk/search?q=Ethiopian+multiplication
https://www.google.co.uk/search?q=Ancient+Egyptian...iplication
https://en.wikipedia.org/wiki/Ancient_Egyptian_multiplication

Вячеслав Голованов
Хабрахабр
*Имя:
Заголовок:
[tex-clear] [tex-help] [ted]
  • formulas >

* Сколько символов на картинке?
Captcha
Отправляя данные, вы соглашаетесь с Правилами сайта.