Комментарии 24
Восхищают такие простые, но интересные методы.
Я бы не назвал этот метод простым. Даже в первом примере, перемножение двух чисел занимает куда больше операций, чем просто сложить 190+30+27. Мне кажется, на умножении уже 4-значных чисел затраты на умножение и деление в уме на 2 превысят выигрыш от кол-ва операций (да, их там будет меньше). Хотя я могу и ошибаться.
НЛО прилетело и опубликовало эту надпись здесь
Шагов может и 27, но вот мат. операций не так уж и мало.
Сравним обычным умножением в столбик:
1) крестьянский: 27 умножений на 2, 27 делений на 2, около 15 суммирований весьма немаленьких чисел
2) в столбик: 81 элементарное умножение, около 18 суммирований однозначных чисел
Вывод: в столбик может и больше мат. операций, но они элементарные; крестьянкий умножение и деление тоже елементарное, но вот с суммированием сложнее. Хотя если суммировать в конце и удобно их записывать тоже можно свести к нормальному варианту.
Я бы все же выбрал столбик.
код примеров на python: ссылка
Сравним обычным умножением в столбик:
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: ссылка
Я много лет назад писал всякие штуки на ассемблере. В моём компе не было сопроцессора для работы с числами с плавающей точкой, википедии тогда тоже не было, вообщем-то и интернета тогда почти не было :) И я придумал метод вычисления квадратного корня через вычитание. В цикле вычитаем из числа сначала 1, потом 3, потом 5 и т.д. Каждый раз вычитаемое увеличиваем на 2. Количество итераций — это целочисленный корень исходного числа. Тогда мне даже препод не смог объяснить почему это работает, а спустя много лет я нашёл этот алгоритм на википедии.
Мне кажется в возведении в степень где то здесь
автор забыл написать а теперь нарисуем табличку для умножения 256 на 32.
В результате писанины будет весьма не мало.
Последний шаг: 1 – нечётное, умножаем 256 на 32, получаем 8192, что и является ответом.
автор забыл написать а теперь нарисуем табличку для умножения 256 на 32.
В результате писанины будет весьма не мало.
НЛО прилетело и опубликовало эту надпись здесь
Поправьте меня, если я не прав, но… это же классический алгоритм умножения в двоичном коде?
В универе на лабах по архитектуре был ассемблер PDP11 — именно этот метод на нём и реализовывали.
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
А зачем их считать? Главное принцип понять
По японски для больших цифр
Тогда лучше сразу метод решётки www.nkj.ru/archive/articles/19204
НЛО прилетело и опубликовало эту надпись здесь
Суть метода не только в том, что он проще или быстрее. Разные методы могут подходить для различных вещей. Например человеку проще умножить в столбик, а механической двоичной системе, проще будет другой способ.
Больше методов, непохожих друг на друга!
Больше методов, непохожих друг на друга!
Хотел бы упомянуть интересное обобщение, использующее быстрое возведение матрицы в степень (за логарифм показателя степени) для вычисления значений линейных рекуррентных последовательностей (таких, как числа Фибоначи, числа Люка). Оно подробно описано в этой статье здесь, на Хабре: «Используем быстрое возведение матриц в степень для написания очень быстрого интерпретатора простого языка программирования».
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Умножение по методу русских крестьян