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

[rixaman]

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

[mapron]

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

[Yahweh]

Шагов может и 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

столбик

         123456789
         987654321
==================
         123456789
        246913578 
       370370367  
      493827156   
     617283945    
    740740734     
   864197523      
  987654312       
1111111101        
==================
121932631112635269

код примеров на python: ссылка

[Ares_ekb]

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

[OldFisher]

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

[codecity]

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

[Yahweh]

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

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

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

[Zenitchik]

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

[Yahweh]

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

[Zenitchik]

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

[mapron]

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

[Scf]

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

[merlin-vrn]

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

[Yahweh]

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

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

[Zenitchik]

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

[saboteur_kiev]

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

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

[sashagil]

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