Что такое линейный способ умножения

Математики обнаружили идеальный способ перемножения чисел

Разбивая крупные числа на мелкие, исследователи превысили фундаментальное математическое ограничение скорости

Четыре тысячи лет назад жители Вавилонии изобрели умножение. А в марте этого года математики усовершенствовали его.

18 марта 2019 два исследователя описали самый быстрый из известных методов перемножения двух очень больших чисел. Работа отмечает кульминацию давнишнего поиска наиболее эффективной процедуры выполнения одной из базовых операций математики.

«Все думают, что метод умножения, который они учили в школе, наилучший, но на самом деле в этой области идут активные исследования», — говорит Йорис ван дер Хувен, математик из Французского национального центра научных исследований, один из соавторов работы.

Сложность множества вычислительных задач, от подсчёта новых цифр числа π до обнаружения крупных простых чисел сводится к скорости перемножения. Ван дер Хувен описывает их результат как назначение своего рода математического ограничения скорости решения множества других задач.

«В физике есть важные константы типа скорости света, позволяющие вам описывать всякие явления, — сказал ван дер Хувен. – Если вы хотите знать, насколько быстро компьютеры могут решать определённые математические задачи, тогда перемножение целых чисел возникает в виде некоего базового строительного блока, по отношению к которому можно выразить такую скорость».

Почти все учатся перемножать числа одинаково. Записываем числа в столбик, перемножаем верхнее число на каждую цифру нижнего (с учётом разрядов) и складываем результат. При перемножении двух двузначных чисел приходится проделать четыре более мелких перемножения для получения итогового результата.

Школьный метод «переноса» требует выполнения n 2 шагов, где n – количество цифр в каждом из перемножаемых чисел. Вычисления с трёхзначными числами требуют девяти перемножений, а со стозначными – 10 000.

Метод переноса нормально работает с числами, состоящими из нескольких цифр, однако начинает буксовать при перемножении чисел, состоящих из миллионов или миллиардов цифр (чем и занимаются компьютеры при точном подсчёте π или при всемирном поиске больших простых чисел). Чтобы перемножить два числа с миллиардом цифр, нужно будет произвести миллиард в квадрате, или 10 18 , умножений, – на это у современного компьютера уйдёт порядка 30 лет.

Несколько тысячелетий считалось, что быстрее перемножать числа нельзя. Затем в 1960 году 23-летний советский и российский математик Анатолий Алексеевич Карацуба посетил семинар, который вёл Андрей Николаевич Колмогоров, советский математик, один из крупнейших математиков XX века. Колмогоров заявил, что не существует обобщённого способа умножения, требующего меньше, чем n 2 операций. Карацуба решил, что такой способ есть – и после недели поисков он его обнаружил.

Анатолий Алексеевич Карацуба

Умножение Карацубы заключается в разбиении цифр числа и повторной их комбинации новым способом, который позволяет вместо большого количества умножений провести меньшее количество сложений и вычитаний. Метод экономит время, поскольку на сложения уходит всего 2n шагов вместо n 2 .

Традиционный метод умножения 25х63 требует четыре умножения на однозначное число и несколько сложений

Умножение Карацубы 25х63 требует трёх умножений на однозначное число и несколько сложений и вычитаний.
a) разбиваем числа
b) перемножаем десятки
c) перемножаем единицы
d) складываем цифры
e) перемножаем эти суммы
f) считаем e – b – c
g) собираем итоговую сумму из b, c и f

При росте количества знаков в числах метод Карацубы можно использовать рекурсивно.

Традиционный метод умножения 2531х1467 требует 16 умножений на однозначное число.

Умножение Карацубы 2531х1467 требует 9 умножений.

«Сложение в школе проходят на год раньше, потому что это гораздо проще, оно выполняется за линейное время, со скоростью чтения цифр слева направо», — сказал Мартин Фюрер, математик из Пенсильванского государственного университета, создавший в 2007 быстрейший на то время алгоритм умножения.

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

«Несколько умножений можно превратить в сложения, учитывая, что с этим компьютеры будут справляться быстрее», — сказал Дэвид Харви, математик из Университета Нового Южного Уэльса и соавтор новой работы.

Метод Карацубы сделал возможным умножать числа с использованием лишь n 1,58 умножений на однозначное число. Затем в 1971 году Арнольд Шёнхаге и Фолькер Штрассен опубликовали метод, позволяющий умножать большие числа за n × log n × log(log n) небольших умножений. Для умножения двух чисел из миллиарда знаков каждое метод Карацубы потребует 165 трлн шагов.

Йорис ван дер Хувен, математик из Французского национального центра научных исследований

Метод Шёнхаге-Штрассена используется компьютерами для умножения больших чисел, и привёл к двум другим важным последствиям. Во-первых, он ввёл в использование технику из области обработки сигналов под названием быстрое преобразование Фурье. С тех пор эта техника была основой всех быстрых алгоритмов умножения.

Во-вторых, в той же работе Шёнхаге и Штрассен предположили возможность существования ещё более быстрого алгоритма – метода, требующего всего n × log n умножений на один знак – и что такой алгоритм будет наибыстрейшим из возможных. Это предположение было основано на ощущении, что у такой фундаментальной операции, как умножение, ограничение операций должно записываться как-то более элегантно, чем n × log n × log(log n).

«Большинство в общем-то сошлось на том, что умножение – это такая важная базовая операция, что с чисто эстетической точки зрения ей требуется красивое ограничение по сложности, — сказал Фюрер. – По опыту мы знаем, что математика базовых вещей в итоге всегда оказывается элегантной».

Нескладное ограничение Шёнхаге и Штрассена, n × log n × log(log n), держалось 36 лет. В 2007 году Фюрер побил этот рекорд, и всё завертелось. За последнее десятилетие математики находили всё более быстрые алгоритмы умножения, каждый из которых постепенно подползал к отметке в n × log n, не совсем достигая её. Затем в марте этого года Харви и ван дер Хувен достигли её.

Их метод является улучшением большой работы, проделанной до них. Он разбивает числа на знаки, использует улучшенную версию быстрого преобразования Фурье и пользуется другими прорывами, сделанными за последние 40 лет. «Мы используем быстрое преобразование Фурье гораздо более грубо, используем его несколько раз, а не один, и заменяем ещё больше умножений сложением и вычитанием», — сказал ван дер Хувен.

Алгоритм Харви и ван дер Хувена доказывает, что умножение можно провести за n × log n шагов. Однако он не доказывает отсутствия более быстрого метода. Гораздо сложнее будет установить, что их подход максимально быстрый. В конце февраля команда специалистов по информатике из Орхусского университета опубликовала работу, где утверждает, что если одна из недоказанных теорем окажется верной, то этот метод и вправду будет скорейшим из способов умножения.

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

Кроме того, поменялись схемы компьютерного оборудования. Двадцать лет назад компьютеры выполняли сложение гораздо быстрее умножения. Разрыв в скоростях умножения и сложения с тех пор серьёзно уменьшился, в результате чего на некоторых чипах умножение может даже обгонять сложение. Используя определённые виды оборудования, «можно ускорить сложение, заставляя компьютер умножать числа, и это какое-то безумие», — сказал Харви.

Оборудование меняется со временем, но лучшие алгоритмы своего класса вечны. Вне зависимости от того, как компьютеры будут выглядеть в будущем, алгоритм Харви и ван дер Хувена всё ещё будет самым эффективным способом умножать числа.

Источник

Способы умножения

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

Умножение чисел — это очень простая операция, фактически, то же самое, что и суммирование. Конечно, пока сами числа не большие.

2х3=2+2+2 (три раза по два) или 24х6=24+24+24+24+24+24 (шесть раз по 24)

То есть, знать таблицу умножения вовсе не обязательно? Да, но с ней удобнее. Например, в случае умножения чисел 235х4596, число 4596 придется сложить 235 раз! Или наоборот, 235 сложить 4596 раз…

Слово «сложить» употреблено не зря. Вот простой способ в этом убедится. Нужно взять листок бумаги сложить его 5 раз в одном направлении, а потом 3 раза в другом. Получится действие 5х3. Считаем получившиеся от сгибания прямоугольники — их 15. Это то же самое, если бы мы взяли 3 полоски ткани (или чего угодно) длинной 5 и сложили вместе.

Как ни крути, а получается — 15!

Необычные способы умножения

В школе нас учат использовать два инструмента: таблицу Пифагора (считается что таблицу умножения придумал именно этот греческий математик) и умножению «в столбик». Это действительно самые эффективные инструменты? Кроме них есть еще несколько интересных способов умножать числа. Может, какой-то из них будет проще и учить таблицу не придется?

По-крестьянски

Использовался для определения площади земельного участка. Например, имеем поле длинной 6 и шириной 5.

Чтобы узнать, сколько будет 6х5 делаем следующее: левое число делим на 2, а правое умножаем на 2, пока от левого числа не останется единица.

2/2= 1 | 10*2=20

4х5=20, все правильно, так же как и 1х20=20

Что происходит при таком способе? Мы разделяем прямоугольник пополам, пока его ширина не станет равняться единице. Делить на два не сложно.

Вот только что будет, если одна из сторон не будет делиться на 2? Будет долгий и не такой уж простой процесс.

6/2=3 | 2*2=4 → 12

3/2=1,5 | 4*2=8 → 12

1,5/2=0,75 | 8*2=16 → 12

Если в левой части четное число — эту строку не считаем, если значение меньше единицы — тоже отбрасываем, остается вторая и третья строка, а это 8+4=12. А если представить, что умножит нужно 173 на 735? Нет, такой способ умножения не самый легкий и простой.

Можно делить/умножать и на 3, но тогда нужно знать таблицу умножения «на три», тогда уж и 5 и 7 и… Да, удобнее выучить ее всю. Также, если будет необходимо перемножить большие числа, процесс будет очень длинным.

Восточный способ

То ли китайский, то ли японский способ умножения, при помощи линий, он же «графический». Его суть состоит в том, что цифры первого числа изображаются в виде параллельных линий, а второго — перпендикулярных им. Количество пересечений и является результатом умножения. То есть, здесь знать таблицу умножения не нужно, достаточно уметь суммировать. Например, так:

2 х 3 и даже 15 х 12

Японский или китайский метод, суть не меняется

Как работает умножение линиями?

Первое число (фиолетовым цветом на картинке) рисуется так: Снизу вверх, слева на право, сначала тысячи, потом сотни, десятки, единицы. Второе число (голубым цветом на картинке) рисуется наоборот: сверху-вниз.

В первом примере все просто 2 и 3. Две линии пересекают 3 другие, получается 6 точек. Во втором, сначала рисуем 15 — единицу (один десяток), потом пять линий изображающих 5 (пять единиц). Потом (12) перпендикулярно ей вторую единицу и 2 линии.

Далее нужно посчитать пересечения, но уже в обратном направлении. Начинать справа. В примере это 10, 7 и 1. Результат складывается в столбик:

Если сравнить с традиционным «столбиком», сперва может показаться, что японско-китайский метод проще…

А что делать, если нужно умножить 10 на 12? Как изобразить «ноль» линией? Никак, он участия не принимает, можно нарисовать его пунктиром и пересечение не считать, все просто…

Но вот уже случае 853х951 рисовать и считать точки придется очень много. Старый-добрый столбик опять окажется удобнее. Каждый сам может попробовать перемножить 9878 и 8794 «японским методом» и засечь необходимое время.

Японский метод с нулем

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

Жалюзи

Встречается еще и название «решетки» и индийский метод умножения. Поверить в индийское происхождение проще всего, если вспомнить, кто вообще придумывал эту вашу математику в древности. Итак, чтобы умножить два числа, нужно построить матрицу (если угодно — таблицу, мы же пытаемся быть проще).

Умножаем 45 на 82

Так как в каждом числе по 2 цифры, таблица будет 2х2. Каждую ячейку нежно перечеркнуть по диагонали. Далее записываем слева-на-право, и сверху-вниз цифры 4, 5, 8, 2 напротив каждой ячейки. Начинаем умножать цифры находящиеся напротив друг-друга. 4 на 8, 5 на 8, 4 на 2 и 5 на 2.

Ну вот опять нужна таблица умножения, иначе придется долго складывать числа.

Результаты записываются в ячейки хитрым способом, десятки над диагональю, а единицы — под ней. Но, если значение меньше 10 (то есть это одна, а не две цифры), то вместо десятки верху пишется «ноль», как при умножении 4х5. Но можно оставить поле пустым.

Теперь, чтобы узнать результат, нужно посчитать сумму в каждой диагонали, как показано на картинке. Сверху-вниз:

3

0+2+4=6

8+1=9

0

В результате получаем 3690.

Тоже достаточно просто, только с небольшими значениями, для умножения трехзначных чисел придется рисовать таблицу размером 3х3=9 ячеек.

Какой метод умножения лучше?

Если перепробовать все способы умножения чисел, становится очевидно, что все представленные альтернативные методы умножения — это все варианты знакомого «столбика». Также операции разбиваются на более мелкие: сначала умножение, потом — суммирование.

Только в так называемом китайском/японском способе умножение как таковое не используется (вместо него пересечение линий) и в этом варианте действительно можно обойтись без таблицы умножения, но придется много рисовать, что повышает вероятность совершить ошибку при пересчете точек пересечения.

Есть мнение, что популярность умножения в столбик вызвана именно компактностью записи. Так на умножение требуется меньше бумаги, меньше чернил (да, чернила раньше использовались и тоже стоили денег) и соответственно времени.

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

Источник