SLY_G Aug 19 at 11:30

Математики до сих пор не уверены, как быстрее всего перемножать числа

Easy

7 min

20K

Translation

+82

Comments 40

ksbes Aug 19 at 13:07

Ну вообще-то есть алгоритм О(1). Правда его бычно для малых чисел используют, но в теории ничто не мешает его использовать и для любого конечного числа чисел. Таблица умножения.

Тут явно не мешает уточнение формулировок. Всё же речь идёт о манипуляциях с цифрами в позиционных системах исчислений.

Для сравнения - умножению и делению чисел записанных римскими цифрами раньше в университетах именитые учёные (буквально - я не помню, вроде Фибоначи тот же) учились в течении лет. А в логарифмическом масштабе (оно же - экпоненциальная или “научная” нотация) умножение и деление - это одно действие сложения.

Так что чётче надо задачу формулировать!

OlegMax Aug 19 at 14:04

в логарифмическом масштабе (оно же - экпоненциальная или “научная” нотация)

Научная нотация - это совсем другое

Таблица умножения.

Так любую NP-полную задачу можно свести к O(1). Достаточно простого советского справочника с ответами

ksbes Aug 19 at 14:34

Научная нотация - это совсем другое

Ну не совсем-совсем. Потому и в кавычках. Намёк на float - в котором всё и считают. Во многом потому что перемножение флоатов быстрее целых (aka с фиксированной точкой).

Достаточно простого советского …

Дело не в этом. А в том, что просто “задача перемножения чисел” в математике вообще как таковая не не то что не решается, а не ставится. Просто за ненадобностью (результат просто есть по определению операции - фактически та же таблица). Ставится задача поиска, например, десятичной записи произведения, зная десятичную запись множителей. Но это - значительно более узкая задача.

OlegMax Aug 19 at 16:37

перемножение флоатов быстрее целых

Откуда вы это взяли?

leshabirukov Aug 20 at 13:09

Полагаю, логика @ksbes в том, что для перемножения fp32 по сравнению с int32 вам надо перемножать лишь мантиссы (со знаком), а экспоненты надо лишь сложить, что и даёт экономию, ведь сложение алгоритмически проще.

Fedorkov Aug 20 at 06:57

Намёк на float - в котором всё и считают. Во многом потому что перемножение флоатов быстрее целых (aka с фиксированной точкой).

Перемножение реализуется аппаратно, то есть это всё одна инструкция (в современных процессорах - от 0.5 до 3 тактов).

IgorPie Aug 20 at 20:59

удачи вам с денормализованными числами

mivlad yesterday at 03:25

Числа мельче PHP_FLOAT_MIN ненужны!

mayorovp 19 hours ago

А они что, перемножаются каким-то особенным образом?

piuzziconezz Aug 20 at 08:22

"перемножение флоатов быстрее целых"

Но это не точно

ImagineTables Aug 19 at 18:27

Сдаётся мне, если число растёт, а разрядность (размер машинного слова) — нет (это очень реалистичное допущение), lookup перестаёт быть O(1) (индекс надо делить), а с ним и алгоритм.

bt2901 Aug 20 at 13:35

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

Леонардо был в своём проекте настолько успешен, что сейчас про эту его деятельность никто и не помнит и не знает :)

OlegMax Aug 19 at 14:02

del

MaximArbuzov Aug 19 at 14:19

Новый алгоритм работает за время O(n × log n).

Был же уже алгоритм FFT с таким же временем работы и похожий на него NTT.
Как будто в статье не хватает каких-то деталей.

malkovsky Aug 19 at 15:12

У них битовая сложность не n log n. Если вы хотите применять классический nlogn FFT Кули-Тьюки для умножения чисел (вычислили на комплексных корнях -> перемножили -> проинтерполировали), то вместе с n будет расти и точность, требуемая от этих преобразований, уже n log n не получается.

Если на основе NTT, то есть видимо Shonhage-Strassen, та же проблема: для числа длины n нужно поле хотя бы из n элементов, мультипликативная группа, при вычислении на которой из цифр длины О(1) получаются уже значения длины О(log n)

MaximArbuzov Aug 19 at 17:51

Спасибо. Мне кажется, что такого объяснения и не хватает для полноты статьи.

wataru Aug 20 at 12:06

Там фактически O(n log n log log n). Ибо при сильно больших n числа не помещаются в машинное слово и там уже длинная арифметика внутри длинной арифметики вылезает.

CitizenOfDreams Aug 19 at 14:40

А где и для чего практически используются числа с сотнями десятичных знаков?

petsernik Aug 19 at 15:47

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

malkovsky Aug 19 at 18:41

Да, криптография -- основной пользователь арифметики с большими числами, а это https, сертификаты, подписи и прочая аутентификация, криптовалюта, ...

vanxant Aug 20 at 11:12

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

faina_sn Aug 19 at 15:43

очень крутая статья, прям каеф

dronperminov Aug 19 at 16:34

В то же время математики не знают, можно ли некоммутативно перемножить две матрицы 3х3 быстрее, чем за 23 произведения (алгоритм с 23 произведениями известен ещё с 1976). Казалось бы, всего-то 27 значений, не сотни, не тысячи, но ответа нет...

si_12345 Aug 20 at 10:05

Вспомогательные произведения

В алгоритме с 23 умножениями сначала вычисляются 23 вспомогательных произведения (обозначим их (P_1, \dots, P_{23})). Для примера вот первые два:

$P_1 = (a_{11} + a_{12} + a_{13}) \cdot b_{11}$ $P_3 = (a_{11} + a_{12}) \cdot b_{12}$

А также несколько вспомогательных произведений, участвующих в вычислении (c_{11}):

$P_4 = a_{11} \cdot (b_{12} - b_{13})$ $P_{16} = a_{13} \cdot (b_{11} + b_{12})$

Вычисление результата

Результирующий элемент (c_{11}) (верхний левый угол матрицы (C = A \cdot B)) выражается через найденные произведения следующим образом:

$c_{11} = P_1 - P_3 - P_4 + P_{16} + P_{19}$

Аналогично вычисляются и остальные 8 элементов матрицы.

dronperminov Aug 20 at 10:44

Всё так, различных (неэквивалентных) некоммутативных алгоритмов с 23 умножениями огромное множество (как минимум более 70 тысяч). А вот возможен ли хотя бы один некоммутативный алгоритм с 22 умножениями пока никто не знает. При этом для случае 2x2 с 7 умножениями (алгоритм Штрассена) абсолютно все алгоритмы эквивалентны друг другу, то есть он такой один уникальный.

В коммутативном случае (когда в линейных комбинациях произведений участвуют элементы матриц A и B) известен алгоритм с 21 произведением, но такие алгоритмы нельзя использовать для рекурсивного блочного умножения, а потому исследователей интересуют именно некоммутативные алгоритмы.

Dr_Faksov Aug 20 at 03:03

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

piuzziconezz Aug 20 at 08:29

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

SensDj Aug 20 at 06:34

процессор же просто сдвигает все биты первого числа несколько раз и складывает получающиеся числа если во втором числе включен нужный бит. Сплошные сдвиги и сложения, никаких умножений, причём сдвиги на 32 и на 64 позиции процессор делает одновременно (параллельно) на аппаратном уровне, и затем сложение тоже делает частично параллельно на аппаратном уровне, человек так на листочке не умеет,
при этом Дипсик настаивает что алгоритм Карацубы таки выгоден для больших чисел: "Оптимальный диапазон для Карацубы обычно лежит в области от 1000 до 10000 бит"

Fedorkov Aug 20 at 07:08

причём сдвиги на 32 и на 64 позиции процессор делает одновременно (параллельно) на аппаратном уровне

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

tea_cher Aug 20 at 08:42

Вот-вот, тоже сразу подумал, что умножение в двоичной арифметике - не то же самое, что и в десятичной.

Или вот в логарифмическом представлении вообще умножение чисел сводится к сложению их логарифмов:

32 × 64 = ?

log2 (32×64) = log2 (32) + log2 (64) = 5 + 6 = 11 = log2 (2^11) = log2 (2048)

32×64 = 2048

Pshir Aug 20 at 09:49

Речь в статье, очевидно, ведётся про decimal

mayorovp Aug 20 at 10:46

Параллельно складывать 64 числа не так просто как кажется, даже на аппаратном уровне. Первые процессоры совершенно точно умножали итеративно.

Насколько я знаю, первой оптимизацией аппаратного умножения стал перевод одного из множителей в систему счисления по основанию 4 с базой {-1, 0, 1, 2}. Для умножения в этой системе счисления достаточно только сдвигов и смены знака, но это несколько отличается от вашего описания.

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

Akon32 Aug 20 at 20:18

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

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

chebo Aug 20 at 09:16

А я вот слышал про китайский метод умножения

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

У него О(от чего?) получается?

ksbes Aug 20 at 09:24

Там эн-квадрат получается. По построению - квадратная сетка же!. Просто сами операции проще - подсчёт вместо сложения и умножения (ну если не брать перенос десятков). Но само количество инкриментов -растёт квадратично.

wataru Aug 20 at 12:03

Есть относительно простой и быстрый алгоритм за O(n log n log log n) (но это не точно). И работает он быстрее карацубы даже на совсем небольших числах. Так что это не галактический алгоритм.

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

И идея простая: представим каждое число в виде полинома - цифры будут коэффициентами.

Вот было у нас $a_0 + a_1\cdot10 + a_2\cdot100 + ...$ , заменим 10 на x, получим

$a_0 + a_1\cdot x + a_2\cdot x^2 + ...$

Потом можно перемножить 2 полинома и подставить x=10. Подстановка очень проста - просто берем коэффициенты и записываем их в виде цифр. Только некоторые могут быть больше 10, и надо сделать переносы с меньших разрядов.

А произведение полиномов это известная задача, решающаяся FFT. Потому что прямое преобразование - это вычисление значений полинома в точках-корнях-из-единицы. Обратное преобразование по значениям в точках восстанавливает полином. Так что произведение полиномов просто делается в пространстве спектра - ведь значения в точках тупо перемножаются покомпонентно.

На практике, пока количество цифр поменьше чем 2^64/81 можно игнорировать log log n в оценке сложности, потому что числа в вычислениях помещаются в процессорное слово.

LaRN yesterday at 06:40

А почему сложность не 9*n умножений + n сложений? Ведь уникальных цифр 9, дальше только сдвиг на разряд и слодение. Можно закешировать все 9 вариантов и подставлять когда нужно.

wataru 22 hours ago

n сложений и дают этот самый медленный O(n^2). Ведь для сложения чисел из n цифр надо O(n) операций. Ваши кеширования особо не помогают в этом наивном умножении столбиком.

LaRN 21 hours ago

А разве n^2 это не от того, что каждый из n разрядов числа A умножается на каждый из n разрядов числа B? И сложения промежуточных результатов тут как будто вообще не учитываются, а если их учитывать, то было бы n^2 + n и n исключается из оценки, тк он имеет не самую максимальную степень.

ksbes 21 hours ago

Сложность всех сложений тоже N^2. Т.е. в умножении столбиков два эн-квадрата: от перемножения и от последующего (поразрядного) сложения. Убрав первое вы оставляете второе. Да будет быстрее - но рост по прежнему квадратичный.