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

Алгоритм


  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 – 13 = 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'.

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

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

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

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

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

Ссылки

Комментарии (24)


  1. rixaman
    20.12.2015 03:56

    Восхищают такие простые, но интересные методы.


    1. mapron
      20.12.2015 06:38
      +5

      Я бы не назвал этот метод простым. Даже в первом примере, перемножение двух чисел занимает куда больше операций, чем просто сложить 190+30+27. Мне кажется, на умножении уже 4-значных чисел затраты на умножение и деление в уме на 2 превысят выигрыш от кол-ва операций (да, их там будет меньше). Хотя я могу и ошибаться.


      1. deniskreshikhin
        20.12.2015 11:00
        +5

        Если умножать по вашему алгоритму 123456789 и 987654321 то получится примерно 81 сложение.
        А методом из статьи log2(123456789) ~ 27 шагов.

        Т.е. у вашего метода рост log10(N)*log10(M), а метода из статьи log2(min(N, M)).


        1. Yahweh
          20.12.2015 14:45
          +1

          Шагов может и 27, но вот мат. операций не так уж и мало.

          Сравним обычным умножением в столбик:
          1) крестьянский: 27 умножений на 2, 27 делений на 2, около 15 суммирований весьма немаленьких чисел
          2) в столбик: 81 элементарное умножение, около 18 суммирований однозначных чисел

          Вывод: в столбик может и больше мат. операций, но они элементарные; крестьянкий умножение и деление тоже елементарное, но вот с суммированием сложнее. Хотя если суммировать в конце и удобно их записывать тоже можно свести к нормальному варианту.

          Я бы все же выбрал столбик.

          крестьяне
           123456789 ? 987654321           >  0
            61728394 ? 1975308642          >  987654321
            30864197 ? 3950617284          >  
            15432098 ? 7901234568          >  4938271605
             7716049 ? 15802469136         >  
             3858024 ? 31604938272         >  20740740741
             1929012 ? 63209876544         >  
              964506 ? 126419753088        >  
              482253 ? 252839506176        >  
              241126 ? 505679012352        >  273580246917
              120563 ? 1011358024704       >  
               60281 ? 2022716049408       >  1284938271621
               30140 ? 4045432098816       >  3307654321029
               15070 ? 8090864197632       >  
                7535 ? 16181728395264      >  
                3767 ? 32363456790528      >  19489382716293
                1883 ? 64726913581056      >  51852839506821
                 941 ? 129453827162112     >  116579753087877
                 470 ? 258907654324224     >  246033580249989
                 235 ? 517815308648448     >  
                 117 ? 1035630617296896    >  763848888898437
                  58 ? 2071261234593792    >  1799479506195333
                  29 ? 4142522469187584    >  
                  14 ? 8285044938375168    >  5942001975382917
                   7 ? 16570089876750336   >  
                   3 ? 33140179753500672   >  22512091852133253
                   1 ? 66280359507001344   >  55652271605633925
                   0 ? 132560719014002688  >  121932631112635269
          


          1. deniskreshikhin
            20.12.2015 14:53

            Я там сравнивал не со столбиком, а с перемножением в виде многочлена 13 * 19 = (10 + 3)*(10 + 9) = 100 + 90 + 30 + 27.

            А так, вообще-то крестьяне и умножали столбиком. Но по сути делали смещение по основания 2, а не по основанию 10.
            Видимо, накладывало след использование кириллической записи, где правило что для умножения на 10 достаточно дописать 0 не очевидно:

            image


  1. Ares_ekb
    20.12.2015 08:03
    +11

    Я много лет назад писал всякие штуки на ассемблере. В моём компе не было сопроцессора для работы с числами с плавающей точкой, википедии тогда тоже не было, вообщем-то и интернета тогда почти не было :) И я придумал метод вычисления квадратного корня через вычитание. В цикле вычитаем из числа сначала 1, потом 3, потом 5 и т.д. Каждый раз вычитаемое увеличиваем на 2. Количество итераций — это целочисленный корень исходного числа. Тогда мне даже препод не смог объяснить почему это работает, а спустя много лет я нашёл этот алгоритм на википедии.


    1. OldFisher
      20.12.2015 10:49
      +3

      Странный какой-то препод. Тот факт, что разность между квадратами целых чисел — арифметическая прогрессия с шагом 2 (как раз 1, 3, 5...) вполне очевиден и к тому же элементарно выводится раскрытием скобок в выражении (n + 1)^2.


      1. dkukushkin
        20.12.2015 14:39
        +2

        Преподы по программированию не всегда сильны в математике, к сожалению. Могут даже школьную толком не знать.


  1. Yahweh
    20.12.2015 09:35

    Мне кажется в возведении в степень где то здесь

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

    автор забыл написать а теперь нарисуем табличку для умножения 256 на 32.
    В результате писанины будет весьма не мало.


    1. k1b0rg
      21.12.2015 12:36
      +1

      Тру программисты держат такую таблицу в голове


    1. Zenitchik
      21.12.2015 15:40

      А что трудного в умножении степеней двух друг на друга? 8+5=13. Два в 13-й, я не помню, зато помню в 10-й. Умножить 1024*8 можно и в уме.


      1. Yahweh
        21.12.2015 16:00

        Вы не поверите, но первоначальная задача стоит в том чтобы возвести 2 в тринадцатую степень. В данном контексте вообще не надо было ничего расписывать, сразу написать 2^13 = 2^10 * 2^3. Суть в том что там могут стоять и не степени двойки.


        1. Zenitchik
          21.12.2015 17:57

          Вот теперь понял.


  1. Crandel
    20.12.2015 09:58
    +2

    4brain.ru/schitat-v-ume/_japonskoe-kitajskoe-umnozhenie.php
    Как по мне, то так намного проще


    1. mapron
      27.12.2015 10:22

      … пока у вас не 7-значные числа.


  1. Scf
    20.12.2015 10:06
    +7

    Поправьте меня, если я не прав, но… это же классический алгоритм умножения в двоичном коде?


  1. merlin-vrn
    20.12.2015 11:07

    В универе на лабах по архитектуре был ассемблер PDP11 — именно этот метод на нём и реализовывали.


  1. urticazoku
    20.12.2015 15:25
    +3

    По-японски:

    Я буду внимательнее читать комментарии.


    1. Aingis
      20.12.2015 17:09
      +1

      Этот метод проигрывает на больших цифрах: 897?987 — поди посчитай все точки.


      1. Yahweh
        20.12.2015 17:32
        +2

        А зачем их считать? Главное принцип понять

        По японски для больших цифр
        image


        1. Zenitchik
          20.12.2015 21:13

          Тогда лучше сразу метод решётки www.nkj.ru/archive/articles/19204


  1. brainick
    20.12.2015 19:43
    +3

    На этой неделе ещё не было.


  1. saboteur_kiev
    20.12.2015 19:52
    +1

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

    Больше методов, непохожих друг на друга!


  1. sashagil
    21.12.2015 00:15

    Хотел бы упомянуть интересное обобщение, использующее быстрое возведение матрицы в степень (за логарифм показателя степени) для вычисления значений линейных рекуррентных последовательностей (таких, как числа Фибоначи, числа Люка). Оно подробно описано в этой статье здесь, на Хабре: «Используем быстрое возведение матриц в степень для написания очень быстрого интерпретатора простого языка программирования».