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

Автор оригинала: Kevin Hartnett
  • Перевод

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



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

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

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

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

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

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

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

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

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


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

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


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


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


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


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


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

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

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

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

Метод Карацубы сделал возможным умножать числа с использованием лишь n1,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 шагов. Однако он не доказывает отсутствия более быстрого метода. Гораздо сложнее будет установить, что их подход максимально быстрый. В конце февраля команда специалистов по информатике из Орхусского университета опубликовала работу, где утверждает, что если одна из недоказанных теорем окажется верной, то этот метод и вправду будет скорейшим из способов умножения.

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

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

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

Комментарии 218

    +5
    Двадцать лет назад компьютеры выполняли сложение гораздо быстрее умножения. Разрыв в скоростях умножения и сложения с тех пор серьёзно уменьшился, в результате чего на некоторых чипах умножение может даже обгонять сложение.

    Во первых так это как раз из-за того, что умножение было медленным и производительность компьютера упиралась в него. Поэтому разработчики процессоров в первую очередь пытались ускорить эту операцию. Если указанный в статье метод действительно работает и подходит для процессоров — это очень неплохо.
    А во-вторых — кто сказал, что аппаратный умножитель не использует операции сложения? Внутри они там есть.


    Кстати, а есть подвижки по алгоритмам деления больших чисел?

      0
      Вопрос скорости стоит менее остро, в конце концов есть же векторные инструкции… острее стоит вопрос энергетической эффективности. Ведь даже если умножение и выполняется по времени как сложение энергии тратится значительно больше. Так что смысл разменять умножение на сложение всё ещё остаётся, даже если дело не в скорости.
        +1
        Ведь даже если умножение и выполняется по времени как сложение энергии тратится значительно больше
        На фоне общего количества потребляющих энергию функциональных блоков в современном процессоре (особенно кэша) и количества обязательных операций, предшествующих умножению-сложению и следующих после него — полагаю, что отличие выражается в долях процента, даже если работать с большими матрицами
          0

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

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

                Можно попробовать, а затем замерить потребление энергии через Intel Power Gadget.

                  0

                  Попробовал написать код, который в несколько потоков складывает/умножает/
                  делит два вектора с помощью AVX. Реально потребление от операции не различается. Разница только в количестве операций доступа к памяти/кэшу.


                  Если молотить только регистры в цикле — будет 60 Вт, если читать-писать — около 95 Вт. При слишком большом размере вектора (не влезает в кэш) — снижается до 60-65 Вт.

                +1
                Векторные операции могут задействовать отдельный специализированный ALU, который в остальное время отключается. Тогда энергопотребление при использовании таких операций будет возрастать.
              0
              Может в каких-то процессорах это и так, но в большинстве — одинаково.
              Более того, когда процессор обнаруживает арифметическую операцию, он параллельно выполняет все поддержаные в ALU операции и декодирование кода операции, а на выходе по коду операции выбирается нужный результат.
              Самое энергоемкое в процессоре — кеш-память. Не думаю, что на ее фоне кто-то решит оптимизировать арифметику.
                0
                Вот только «тяжёлые рассчёта» сейчас делают на GPU — и там как раз арифметика даёт ощутимый такой вклад в энергопотребление…
                  0
                  «Тяжёлые рассчёта» делают на GPU когда надо сделать много маленьких расчётов параллельно. Современные GPU как-то не очень подходят для задач вроде описанных в статье — всё равно что свинью стричь — визгу много, шерсти нет
              0
              В статье описывались асимптоты алгоритма умножения, а скорость выполнения процессорных инструкций входит в константу при них. Очевидно, что если нужно умножить два числа в миллиарды знаков (байт, слов), то скорость будет зависеть как раз от экспоненты.
              Деление в худшем случае можно переписать как умножение и двоичный поиск, соответственно худшая оценка для деления теперь — n*logn*logn.
                +2

                Вот только двоичный поиск будет не log n, а n. Потому что в числе n знаков, значит надо делить интервал размером в 2^n.


                Такое деление в итоге будет O(n^2 log n).

                  0
                  Точно, спасибо.
                    0
                    Делят, по крайней мере вещественные числа, обычно методом Ньютона, а у него квадратичная сходимость, то есть требуется логарифмическое число шагов. А сложность шага пропорциональна сложности умножения.
                      +1
                      Вещественные числа давно уже делят, например, Голдшмидтом, и квадратный корень аналогично — с тех времён, как научились рассчитывать погрешность при таких вычислениях. Но в остальном — последствия такие же по сути, да, как для Ньютона (по ссылке — 1 цикл для single, 2 для double, 3 для extended).
                    0
                    Был какой-то достаточно эффективные алгоритм аппроксимации 1/n, а деление делается через него.
                      +1
                      log log n растёт очень-очень-очень медленно. Даже если там миллиарды знаков — это будет что-то типа 5-6. А чтобы дорасти до 10 уже всех компьютеров мира не хватит.

                      Так что они правильно написали: теоретически — это дико круто, практически — отличие невелико…
                      +5
                      Кстати, а есть подвижки по алгоритмам деления больших чисел?

                      А еще бы разложение на множители и прощай криптография =)
                        +1
                        Квантовые компьютеры.
                        С одной стороны, уничтожат базу современной криптографии — сложность разложения на множители.
                        С другой стороны, вроде, на квантово-запутанных фотонах можно реализовать криптографию, которая гораздо гораздее, чем привычная.
                          0
                          Не вроде, а точно. И не гораздее, а с физической невозможностью дешифровки без. Впрочем, у квантовой криптографии есть огромное число проблем и одна из основных — огромные требования к физической среде. К тому же, не смотря на физическую невозможность дешифровки без ключа сама её попытка приведёт так же к невозможности дешифровки и легальным пользователем. Даже больше — есть огромные проблемы с большими расстояними, а также с противодействием деструктивного воздействия условного противника.

                          Короче. Квантовая криптография это, конечно, интересно, но почти уверен, что она будет использоваться в очень узкой сфере требовательной к безусловной невозможности расшифровки и возможным попустительством в надёжности передачи. А я таких сфер сейчас почти и не знаю.
                            +3
                            Квантовые компьютеры не уничтожат всю криптографию, только алгоритмы типа RSA и Diffie Hellman. У всей симметричной криптографии уполовинется степень защиты.
                            И ещё, есть так называемая «post-quantum» криптография, там шифрование основано на сложных проблемах не связанных со сложностью разложения на простые множители и дискретный логарифм. Прямо сейчас идет соревнование на стандарт подобного типа. Такие алгоритмы выполняются на обычных комптьютерах и квантовые компьютеры им не страшны.
                          0
                          Не совсем. Большинство современных процессоров конвейерные, то есть умеют выполнять одновременно несколько операций, находящихся на разной стадии вычислений. Что бы конвейер работал, требуется что бы одна и та же стадия разных операций не перекрывались во времени. Для этого все операции в конвейере искусственно замедляют до самой медленной. Как правило, это умножение, а более медленные операции, если они есть, останавливают конвейер.
                            +1
                            Мы неплохо использовали операцию «быстрого обратного корня». Одно деление=перемножить два быстрых обратных корня. Получалось выгоднее. )
                              0
                              > Кстати, а есть подвижки по алгоритмам деления больших чисел?

                              Похоже, пока всё плохо. Если смотреть на GMP, по-прежнему основным рабочим методом остаётся итеративное деление на округлённый делитель, хотя его делают через обратное умножение, экономя на собственно процессорном делении.
                              +7
                              Чуть более подробно про семинар Колмогорова, Карацубу и его способ умножения у Аввы в прошлом году был интересный пост в ЖЖ.
                                –5
                                В далеком детстве, я научился в уме извлекать кубические корни из шестизначных чисел)))
                                  +19
                                  … а, также, расставлять, избыточные, знаки, препинания))))))))
                                    –25
                                    С возрастом перестал обращать внимание на такие мелочи как знаки препинания и прочие правила грамматики)
                                    Раз смысл ясен — то к чему все эти условности? )))))
                                      +24
                                      Смысл ясен вам как автору; стороннему читателю такие мелочи как знаки препинания и прочие правила грамматики помогают намного быстрее читать и понимать текст, «парсинг» же контекста обычно медленнее, требует больше умственных затрат и нередко дает сбои, предложение (а то и фразу целиком) приходится перечитывать.

                                      Недавно я пару секунд тупил над фразой «А ещё велики лодки и пиво» — как пиво может быть велико? (ну ладно лодки еще), хотя речь шла о велосипедах, что, однако, мне было совсем не так очевидно, как автору сообщения.
                                        +3
                                        Недавно я пару секунд тупил над фразой «А ещё велики лодки и пиво» — как пиво может быть велико? (ну ладно лодки еще), хотя речь шла о велосипедах, что, однако, мне было совсем не так очевидно, как автору сообщения.
                                        Если вам интересно, существует даже целая тема, посвященная подобным предложениям. По ним даже проводились исследования того, как люди их парсят и как разрешают конфликты.
                                          0
                                          Некоторые задачи на олимпиадах по русскому языку построены на такой же идее.
                                          0
                                          Насколько я помню, основные техники скорочтения — как раз в игнорировании лишнего и понимании только нужного )
                                            +1

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


                                            Так и тут, знаки препинания и правила правописания помогают понимать текст абсолютному большинству.


                                            P.S. Эволюционно так сложилось, что людям неудобно говорить быстро. А оттого и нет смысла учиться "быстро слушать". Только в экстренных случаях.


                                            P.P.S. А ещё, это мне напомнило 1984, где лишние слова за ненадобностью выбрасывали из языка, потому что их можно было уже выразить другими словами/набором слов. Или сокращали.

                                              +1
                                              Попытка проскорочитать текст, который невозможно однозначно интерретировать без запятых, приведет либо к нивелированию скорочтения до обычного либо к фатальным потерям данных. Зарятые являются«лишним усложнением» только на очевидных паттернах.

                                              Ну и паттерны эти субьектозависимы. Так что мозг сам должен решать, какие детали игнорировать.
                                                –2

                                                Про скорочтение и скорость мысли — личное ИМХО, дети когда учатся говорить начинают медленнее мыслить, т.к. мышление (вероятно в целях экономии) переводится на "родной язык" и автоматически синхронизируется со скоростью речи.

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

                                                  +1

                                                  Вроде основное в них — избавление от внутреннего проговаривания.

                                                +4
                                                С ещё большим возрастом перестанете обращать внимание на такие мелочи, как не писаться в штаны, да?
                                                К чему все эти условности, право…
                                                  0
                                                  да? Мне один знакомый пишет без знаков вопроса и любое его вопросительное предложение выглядит как приказ. «Ты сделаешь завтра отчёт», например.
                                                    +3
                                                    По-моему, терпеть это никак нельзя, и отвечать таким людям нужно как в известной цитате с башорга, пусть перевоспитываются. :-)
                                                    –4
                                                    Ох, это Хабр, тут заклюют за любую мелочь, которую посчитают нужной в конкретный момент, в конкретной тематике. Просто на ровном месте заминусовали коммент и карму. А потом они еще говорят про какую-то демократию тут, про то, что не вытесняют неугодных с ресурса. И, да, этот коммент тоже заминусуют, будьте уверенны. Это же так просто: анонимно нажать на минус и сидеть гордиться этим весь остаток дня.
                                                      +3

                                                      Нет на Хабре такого. Было исследование, которое показало, что плюсуют больше, чем минусуют. А минусуют походу тех, для кого карма и рейтинг играет какое-то особое значение.

                                                        +3
                                                        анонимно нажать на минус и сидеть гордиться этим весь остаток дня.
                                                        Человек с правом голоса имеет их не менее 10 в день. Достаточно гордиться каждым всего минут по 40 чтобы день прошел хорошо.
                                                    0
                                                    С какой точностью?
                                                      –7
                                                      А я помню? :-)
                                                      Это было тааааак давноооо…
                                                      Прочел книгу емнип «Система быстрого счета по Трахтенбергу» и запомнил формулу которая позволяла в уме вычислять эти кубические корни. Но только кубические и только из шестизнаков)
                                                      Теперь уж и не помню ее. Формулу в смысле.
                                                        0
                                                        Ну здесь имеется ввиду вычисление кубического корня из числа, которое является кубом целого. Кубический корень из шестизначного — это число двузначное, надо лишь оценить первую цифру результата, сравнив первые три цифры шестизначного числа с 125, 216, 343 и 512, а вторая цифра результата определяется по последней цифре шестизначного числа (там однозначное соответствие).
                                                          0
                                                          Скорее всего, это «по кубу двузначного числа определить само число», работает только для точных кубов. Алгоритм гуглится по «кубический корень в уме», но вкратце — по последней цифре куба однозначно определяем последнюю цифру исходного числа, дальше отбрасываем последние три цифры, по оставшимся определяем первую цифру исходного числа (ищем ближайший куб, который меньше того, что осталось). Надо только помнить таблицу кубов от 1 до 9.
                                                            –1
                                                            del
                                                          0
                                                          Что-то я не понял. Всегда считал, что умножение в двоичной системе делается быстрее всего — там операций совсем мало и они крайне быстрые — сдвиг и сложение. (сдвигаем на один бит — получаем умножение на 2, или деление, если наоборот). Так что методов можно много напридумывать, но в двоичной системе (в которой почти все компьютеры работают) всё равно будет тот самый метод со сдвигом. Так что это всё скорее применимо к «человекочитаемым» способам умножения, нежели к процессорным. Поправьте меня, если я заблуждаюсь.

                                                          upd. Спасибо, разобрался. В принципе, для реализации в железе совсем не сложные доработки нужны.
                                                            +1
                                                            Сдвиг и сложение — это и есть «столбиком». Сложение это n операций, и потребуется ровно n сдвигов. Приведенные алгоритмы — асимптотически лучше.
                                                              0
                                                              Это смотря как считать что лучше. Многие операции можно выполнять параллельно/одновременно, и хотя суммарное число операций при этом будет больше, по времени это будет быстрее.
                                                                0
                                                                farafonoff
                                                                В процессоре не столбиком, там вообще нет отдельной операции сдвига, линии данных до сумматоров уже разведены в железе. Операции сложения выполняются параллельно со всеми разрядами множимого, а чуть позже и со всеми промежуточными вариантами. Без разделения операций на отдельные такты — тут работают защёлки. Они-же предназначены для запоминания промежуточных вычислений и коммутации данных со сдвигом.
                                                                В результате умножение целого 32б на 32б с результатом в 64б — требует срабатывания пяти защёлок, и в целом операция умножения успевает выполниться за один такт.
                                                                С плавучкой немного сложнее, но даже там операции над всеми разрядами данных выполняются параллельно.

                                                                То-есть используется тот самый способ из статьи автора, но в двоичном варианте. Я думаю что «открытие» произошло по причине прогресса. Сейчас уже трудно найти человека что будет самостоятельно проектировать модуль умножения для ядра процессора, зачем — когда есть готовая библиотека… Из-за чего и встречаются подобные проколы.
                                                                  0
                                                                  Если всё так как ты описал — часть сложности перенесена в железо. Т.е. вместо линейного количества времени тебе нужно линейную площадь кристалла. Это всё равно не позволяет выйти за границу асимптотической оценки. Попробуй представить умножение двух чисел длиной в гигабайт.
                                                                    –4
                                                                    Попробуй представить умножение двух чисел длиной в гигабайт.

                                                                    А зачем представлять, если есть библиотека которую можно посмотреть.
                                                                    Очень большие и жирные числа всегда в десятичной системе. Не потому что удобно, а от того что перевод из двоичного представления в десятичное — будет слишком долгим. К тому-же математики помешаны на магии десятичной системы, у них это почти религия.
                                                                    Дык вот, в свободной мат. библиотеке разбивка чисел уже работает, задолго до этого открытия.
                                                                    Просто программисты забыли предупредить об этом местных светил математики.
                                                                      +1
                                                                      Последний раз повторяю. Посмотри например сюда:
                                                                      hg.openjdk.java.net/jdk8/jdk8/jdk/file/tip/src/share/classes/java/math/BigInteger.java
                                                                      Метод public BigInteger multiply(BigInteger val) вызывает аж 3 реализации, в зависимости от длины чисел (все 3 способа описаны в статье). Кроме того хранятся не десятичные цифры, а сразу int32 (а к десятичной системе можно привести при печати).
                                                                    +2
                                                                    В результате умножение целого 32б на 32б с результатом в 64б — требует срабатывания пяти защёлок, и в целом операция умножения успевает выполниться за один такт.
                                                                    Не успевает. Откройте табличку, да посмотрите. Даже Ryzen и Skylake-X требуют для этого 3-4 такта, на более старых процессорах — больше. Да, это не 30-40 тактов, как для деления, но и не один такт. Просто потому что если реализовать ваше предложение — то придётся снижать частоту, а тогда и другие операции медленнее станут.

                                                                    С плавучкой немного сложнее, но даже там операции над всеми разрядами данных выполняются параллельно.
                                                                    Та же самая история: никто не будет пихать такой большой мультипликатор в процессор. По уже описанной причине. Впрочем как раз для плавучки ваше утверждение верно — но не потому, что умножение занимает один такт, а потому что там даже сложение в один такт «не вписывается» — и занимает те же 3-4 такта, что и умножение.

                                                                    Парадоксы современного процессоростроения…
                                                                      0
                                                                      Тем не менее, всякие девайсы с «Single-cycle multiply and accumulate (MAC) instructions» не редкость. Или я туплю, и это не то?
                                                                        0
                                                                        Если я правильно понял предмет спора, произошла терминологическая путаница.
                                                                        Single-cycle

                                                                        Скорее всего имеется в виду машинный цикл, который состоит из нескольких тактов задающего генератора (на известных мне микроконтроллерах — 4).
                                                                          0
                                                                          А это важно вообще? // я лет 10 не копался в этой теме и уже порядком плаваю.
                                                                          Насколько я могу судить, работа отдельных модулей на частоте повышенной или пониженной относительно того, что мы называем частотой ядра, это норма. При этом частота ядра это, по сути, частота адресного генератора (если упрощенно смотреть). Не?

                                                                          И если у нас все инструкции single-cycle, то мы получаем константное время выполнения кода. Во всяких специализированных сигнальниках могут вообще дикие вещи за 1 такт делаться. Ну то есть, я не понимаю смысла говорить о еще более низком подуровне.
                                                                            0
                                                                            Может и не важно. Я сам — нуб в схемотехнике. Только знаю, что иногда встречаются отдельные граждане, которые цепляются за разницу между машинным циклом (за который процессор выполняет простые команды) и тактом рабочей частоты.
                                                                              0
                                                                              Ну… в любом случае это все сильно архитектурнозависимые вещи. А выше они так спорят, как будто бы за этим всем стоят какие-то фундоментальные законы.
                                                                                0
                                                                                А за этим и стоят фундаментальные законы. Подумайте вот над чем: отдельные рекордные транзисторы работают на частотах в сотни гигигерц. Беглый поиск приводит к 798 GHz, правда в SiGe, но даже транзисторы в ваших процессорах на 200-300GHz способны… а процессор в целом — даже 10GHz «не делает» и даже на этой частоте ему нужны 3-4 такта для умножение и десятки — да деление.

                                                                                Так-то Verilog позволяет «нарисовать» схему, которая любое конечное вычисление в один такт сделает… но почему-то так никто не делает. Что-то же должно являться причиной?

                                                                                Подумайте над этим…
                                                                                  0
                                                                                  Эмм. Фундоментальные ограничения на чустоту электроники, как таковой, не особо противоречат моим словам.
                                                                                    0
                                                                                    Фундаментальные ограничения не дают вам сделать железку, работающую на частоте в терагерц. А также сделать железку, выполняющую сложение за то же время, что и умножение. Это всё фундаментальные вещи.

                                                                                    Но вот будете ли вы выносить на архитектурный уровень тот факт, что умножение, всё-таки, сложнее умножения — это другой вопрос: вы не можете ускорить умножение до скорости сложения, но вы можете замедлить сложение… а можете «более простое» сложение «встроить в умножение» (откуда и получается MAC — инструкция: она выполняется за то же время, что и умножение и позволяет, часто, экономить на сложении).
                                                                                      0
                                                                                      Так я разве же спорю с этим?
                                                                          0
                                                                          Это так — но не в CPU. Самые «монстрачие» устройства, которые могут делать много-много умножений и сложений — это GPU. Однако какая-нибудь T4 Tesla за две штуки баксов всё равно имеют частоту максимум в 1.5GHz (это турбо буст режим, обычно меньше). А процессоры — редко имеют турбо-буст частоту ниже 3GHz, некоторые уходят до 5GHz.

                                                                          Однотактовый умножитель на ширину «32бита» оказывается тупо слишком большим, чтобы на этой частоте работать.
                                                                            0

                                                                            Тут всё упирается в энергопотребление. Производительность видеокарт в специализированных задачах минимум на порядок выше, чем CPU, но энергопотребление — примерно в 2 раза больше.

                                                                              0
                                                                              Если вы работаете на частоте 1.5GHz, то современные технологии вам позволяют сделать однотактовый умножитель, а если на частоте 4.5GHz-5GHz — то уже нет. Вот через это — вы не перепрыгните. Это фундаментальное ограничение. А почему какие-то чипы вы будете делать под 1.5GHz, какие-то под 4GHz, а какие-то — и под 10MHz — это уже другой вопрос.
                                                                          0
                                                                          Не успевает. Откройте табличку, да посмотрите.

                                                                          А это вы за границы модуля умножения вышли, причём очень далеко. х86 работает с памятью, ему сначала нужно эти числа загрузить в мат. процессор, а потом выгрузить. На всё это тратятся дополнительные такты ожидания.
                                                                          К тому-же модуль умножения не является изолированным куском кремния, он способен выполнять намного больше вторичных функций. Всё это достигается внутренней коммутацией, часть в железном исполнении, часть в микрокоде.
                                                                          Для arm ядер — этот узел похож на слипшийся комок макарон. Слишком многое в одном месте, без чёткого деления на площадь кремния. Там тоже есть такты ожидания, и они тоже связаны с внешней шиной.
                                                                          Чудес не бывает, разве что в фпга…
                                                                            +1
                                                                            А это вы за границы модуля умножения вышли, причём очень далеко. х86 работает с памятью, ему сначала нужно эти числа загрузить в мат. процессор, а потом выгрузить. На всё это тратятся дополнительные такты ожидания.
                                                                            Ага, конечно. Для умножения нам в память нужно сходить, а для сложения не нужно? Прудмайте какую-нибудь другую «отмазку», поправдоподобнее, пожалуйста.

                                                                            Чудес не бывает, разве что в фпга…
                                                                            В FPGA тоже не бывает. Либо у вас сложение выполняется быстрее, чем умножение, либо вам приходится снижать тактовую частоту — других вариантов нет.
                                                                          +2
                                                                          Одно дело — умножение чисел не превышающих разрядность ALU, и совершенно другое — умножение больших чисел. Для этого и существуют специальные алгоритмы.
                                                                        +5

                                                                        Это когда у вас чиста маленькие. Когда надо перемножать 100500-битные числа, нужно делать 100500 сдвигов и складывать 100500/64 чисел каждый раз.

                                                                        0

                                                                        Я вот не совсем понимаю, почему наивный метод с FFT — это O(n logn log log n) вместо O(n log n). Откуда лишний log log n. Это из за того, что точности дабла не хватит при росте n и надо считать какие-то хитрые операции с длинными числами с плавающей точкой?

                                                                          +2

                                                                          Наивный и FFT в одном предложении. Теперь я видел всё.

                                                                            0

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

                                                                            +1
                                                                            Вы делите число из n бит на кусочки по √n бит. Представляете кусочки как коэффициенты полинома степени √n. Перемножаете полиномы. Преобразование Фурье требует как минимум O(√n log n) сложений (если быстро на корни из единицы умножать), стоящих √n, и потом нужно ещё √n умножений чисел из ≈√n бит. Эти умножения обрабатываются рекурсивно тем же алгоритмом. Возникает рекуррентная формула для оценки сложности: C(n) = n log n + √n C(√n). Разворачивая рекурсию, получаем n log n log log n, где множитель log log n отвечает за количество рекурсивных шагов.

                                                                            На самом деле оригинальная научная статья довольно неплохо разъясняет существующие алгоритмы (если вы не боитесь терминов «FFT» и «кольцо вычетов»).
                                                                              0

                                                                              А почему не работает так: разбить число на кусочки по 1 биту — это коэфициенты полинома. fft — O(n log n), перемножить значения — O(n), обратное fft — O(n log n). Никакой рекурсии. Всего O(n log n). Откуда тут еще log log n? Или этот алгоритм не работает для больших n?

                                                                                0
                                                                                Потому что перемножение будет n^2, а не n. Весь выигрыш происходит, когда мы делим на фиксированное количество частей (2).
                                                                                  0

                                                                                  Почему? Перемножение же почленное — ровно n операций (правда, с комплексными числами).

                                                                                  +1

                                                                                  Потому что в процессе fft происходит куча сложений, из-за которых длина каждого элемента вырастает до O(log n) бит, а элементарное умножение начинает работать за O((log n)2). В итоге ваш метод даёт асимптотику O(n (log n)3), что явно больше чем O(n log n log log n)

                                                                                –1
                                                                                Я так понимаю, что умножение это линейная свертка а преобразование фурье используется для быстрого подсчета цыклической свертки. Чтоб из цыклической свертки сделать линейную то циклическую нужно дополнить нулями чтоб получить линейную
                                                                                  0
                                                                                  В двух словах, лишний log log n возникает, потому что считается битовая сложность, то есть сложность базовых операций типа сложения и умножения не равна 1, а зависит от битовой длины элементов. Здесь (2.3) объяснено подробнее.
                                                                                    0

                                                                                    Спасибо! Теперь все понятно.

                                                                                  +16
                                                                                  Почему в статье о новом революционном способе демонстрируется старый алгоритм Карацубы? Такое ощущение, что автор мало что понял из оригинальной работы и написал только то, что знал. Ну а сама оригинальная работа написана в классическом стиле от математиков для математиков — готового алгоритма, пригодного к реализации вы в ней не найдёте.

                                                                                  Например, в лемме 2.3 там доказывается convolution formula, согласно которой свёртка функций равносильна перемножению их Фурье-образов. Зачем? Это же известный, давно доказанный факт — можно было просто сослаться на доказательство, тем самым уменьшив объём работы.
                                                                                    0
                                                                                    hal.archives-ouvertes.fr/hal-02070778/document

                                                                                    вот, пожалуйста
                                                                                    Извините, в следующий раз я буду читать комментарий полностью. Но ссылку всё равно оставлю.
                                                                                      0
                                                                                      Что вы этим хотели сказать? Ссылка на эту работу есть в статье, я её уже посмотрел.
                                                                                        +4
                                                                                        Это дурная привычка сразу же отвечать только на первое предложение в прочитанном.
                                                                                        Извините. Но я работаю над собой.
                                                                                      +1
                                                                                      > Ну а сама оригинальная работа написана в классическом стиле от математиков для математиков — готового алгоритма, пригодного к реализации вы в ней не найдёте.
                                                                                      Не удивительно в общем, это ведь статья по математике — сомнительно, что полученный алгоритм будет иметь какое-то прикладное значение.

                                                                                      > Например, в лемме 2.3 там доказывается convolution formula, согласно которой свёртка функций равносильна перемножению их Фурье-образов. Зачем? Это же известный, давно доказанный факт — можно было просто сослаться на доказательство, тем самым уменьшив объём работы.
                                                                                      Это называется self-contained proof. Если какие-то уже известные результаты имеют простое доказательство, и их рассмотрение может добавить понимания, то их доказательство повторяется в статье.
                                                                                      0
                                                                                      Можно наивный вопрос? Метод был предложен в 1960 году, он уже используется в современных ЭВМ? Если нет, то наверное есть какая-то объективная причина?
                                                                                        +1
                                                                                        Метод Шёнхаге-Штрассена используется компьютерами для умножения больших чисел
                                                                                          +2
                                                                                          Асимптотика показывает только зависимость от размера данных, и не показывает итоговое реальное время и так называемую «константу» перед асимптотикой. Например, O(10n) равно O(n). Константа «10» скрыта, т. к. на очень больших числах (например, стремящихся к бесконечности) это всё-равно будет быстрее, чем, допустим, O(n1.000000001) без скрытой «10», а также потому, что константа может зависеть от реализации.

                                                                                          Но на практике мы работаем с числами ограниченного размера, и даже чаще всего с очень маленькими числами, и все эти константы очень сильно влияют на итоговое время. Поэтому чаще всего подходящий алгоритм выбирается в зависимости от размера входных данных, причём оптимальных алгоритмов может быть много на разных размерах. Также ещё можно посмотреть на энергоэффективность алгоритма и размер потребляемой памяти.
                                                                                            +1
                                                                                            Конечно используются. В JDK и .NET Core используется умножение Карацубы (в JDK 11 по умолчанию умножение переходит на Карацубу, если множители больше 2560 бит ). В JDK с множителей длины 7680 бит используется умножение Тоома-Кука.
                                                                                              0
                                                                                              Алгоритмы типа Штрассена имеют лучшую ассимптотическую характеристику, но добавляют значительные константные накладные расходы. Из-за этого их применение для маленьких размерностей (десятки-сотни бит) неоправдано. Для операций над небольшими числами в железе используются другие оптимизации, направленные в основном на ускорение получения результата путем избыточных операций, которые можно выполнять паралельно (методы быстрых переносов).

                                                                                              Но если вам нужно умножить действительно большие числа или, что более вероятно, умножить две больших матрицы, алгоритмы типа Штрассена могут дать кратный прирост производительности. Такие методы используются в специализированном железе.
                                                                                                0
                                                                                                Посмотрите на GMP. Там есть регулярно пересчитываемые для разных процессоров границы применения методов, чтобы функция сразу выбрала подходящий согласно длинам сомножителей.
                                                                                                Вот, например, для Zen серии в 64 битах при переходе меньшим сомножителем границы 22 лимба (лимб тут будет 64 бита => то есть длина 1408 бит) происходит переключение от «schoolbook» (квадратичное умножение всего на всё) к, чуть упрощая, методу Карацубы (записан как TOOM22; метод Карацубы является частным случаем Тоома-Кука; ТК это вообще не конкретный метод, а метаметод, который можно «заземлять» в неограниченное множество алгоритмов). Дальше до 460 лимбов (29440 бит) идут разные варианты ТК, но с этой границы включают Шонхаге-Штрассена.
                                                                                                Для других линий процессоров константы будут другими, но общая картина сохраняется где-то на том же уровне.
                                                                                                Более дорогие и тяжёлые методы вроде Фюрера там не применяются, видно, решили, что выделки не стоит (реально при таких свойствах процессоров он начал выигрывать бы где-то от миллиона бит).
                                                                                                0
                                                                                                Теперь ждём, когда заново откроют сложение!
                                                                                                  +4
                                                                                                  Шутка «Если умножение так хорошо, то почему ещё не выпустили умножение 2» перестает работать.
                                                                                                    0
                                                                                                    Бинарное сложение с предрасчетом carry уже давно существует, работает за 1 такт.

                                                                                                    Это выглядит ужасно, и занимает кучу места на кристалле. Особенно для длинных чисел. images.app.goo.gl/sibNc8JcZz4sJ7GC9

                                                                                                    Таким же образом можно и умножать.
                                                                                                      0

                                                                                                      Только что считать тактом?

                                                                                                        0
                                                                                                        Время на устранение переходных процессов? В данном случае 10 вентилей в глубину. В идеальном случае можно довести до 2х слоёв (с соответствующим разжирением схемы, так что больше 2 по 4х бит будет складывать не выгодно так как 2^(4*2)=256 вентилей, ну или что-то около того)
                                                                                                          0

                                                                                                          Ну так в том то и дело что "такт" при современных частотах уже вполне приближается к "времени на устранение переходных процессов" и может случиться что 10 вентилей в глубину это уже дольше чем время 1 такта.

                                                                                                            –2
                                                                                                            Все инструкции в процессорах как правило выполняются разное время как раз исходя из количества слоев и задержки в худшем случае. И повышение времени выполнения одной простой инструкции особо на производительность не влнияет, так как задержка при получении информации из ram все равно в сотни раз дольше сложения двух чисел в зависимости от тапа памяти и наличия кеша. Тут можно почитать подробнее
                                                                                                            drive.google.com/a/uottawa.ca/file/d/1mKy4z9l8EEDHszT0_qtIjFBseL4ujcfG/view?usp=drivesdk
                                                                                                    0
                                                                                                    Отлично! Значит реймаршинг будет выполняться ещё быстрее. Немного прифигел от скромности ван дер Хувена: «Всё, на что мы можем надеяться, это на трёхкратное ускорение».
                                                                                                      +5
                                                                                                      Он говорит «надеяться», потому что математически обоснованное преимущество может сойти на нет (и даже в минус) за счёт накладных расходов при практической реализации. Подобный эффект наблюдается, в частности, при реализации быстрых алгоритмов Фурье — потому что помимо вычислений как таковых есть ещё операции чтения/записи/перемещения в памяти.
                                                                                                        +2
                                                                                                        Это не скромность. Попробуйте прикинуть при каком n у вас log log n «дорастёт» до десятки и подумайте — будут ли вас когда-нибудь волновать такие числа.
                                                                                                          +2
                                                                                                          Значит реймаршинг будет выполняться ещё быстрее.

                                                                                                          А где там длинные числа? Все эти быстрые умножения (Карацуба и последующие) они про числа в тысячи бит.
                                                                                                          +1
                                                                                                          Умножение Карацубы выглядит как какая-то нумерология со сложением казалось бы не имеющих отношения к умножению цифр.
                                                                                                          шутка про нумерологию
                                                                                                          ID поста 451860, сумма цифр 4+5+1+8+6+0=24, среднее между 2 и 4 = 3, Half Life 3 confirmed
                                                                                                          но при этом работает (я проверил на листочке).
                                                                                                            +4
                                                                                                            > Шутка про нумералогию
                                                                                                            оффтоп, но напомнило
                                                                                                            Умберто Эко (с) «Маятник Фуко»
                                                                                                            «Театральным жестом он распахнул ставни, предложил нам выглянуть и указал невдалеке, на углу между улочкой и бульварами, деревянный цветочный киоск.
                                                                                                            — Господа, — сказал он. — Предлагаю вам самим отправиться и измерить эту будку. Вы увидите, что длина прилавка составляет 149 сантиметров, то есть одну стомиллиардную долю расстояния между Землей и Солнцем. Высота его задней стенки, разделенная на ширину окошка, дает нам 176/56, то есть 3,14. Высота фасада составляет девятнадцать дециметров, то есть равна количеству лет древнегреческого лунного цикла. Сумма высот двух передних ребер и двух задних ребер подсчитывается так: 190х2+176х2=732, это дата победы при Пуатье.[87] Толщина прилавка составляет 3,10 сантиметров, а ширина наличника окна — 8,8 сантиметров. Заменяя целые числа соответствующими литерами алфавита, мы получим C10H8, то есть формулу нафталина.
                                                                                                            — Фантастика, — сказал я. — Сами мерили?
                                                                                                            — Нет, — ответил Алье. — Но один подобный киоск был измерен неким Жан–Пьером Аданом. Воображаю, что все цветочные киоски должны строиться более или менее одинаково. С цифрами вообще можно делать что угодно. Если у меня имеется священное число 9, а я хотел бы получить 1314, то есть год сожжения Жака де Молэ — этот день дорог сердцу каждого, кто, подобно мне, составляет часть тамплиерской рыцарственной традиции, — что я делаю? Умножаю на 146 (это роковой год разрушения Карфагена). Как я пришел к этому результату? Я делил 1314 на два, на три и так далее, до тех пор покуда не отыскал подходящую дату. Я бы мог поделить 1314 и на 6,28, что составляет собой удвоение 3,14, и пришел бы к цифре 209. Ну что ж, в этот год примкнул к антимакедонской коалиции Аттал I, царь Пергама. Годится?»

                                                                                                            Умберто Эко (с) «Маятник Фуко»
                                                                                                              +9

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


                                                                                                              Допустим, у нас есть два числа, 10a+b и 10c+d. Тогда их произведением будет 100ac + 10(ad+bc) + db.


                                                                                                              Заметим, что ad+bc = (a+b)(c+d) — ac — db.

                                                                                                                +1
                                                                                                                Рекомендую вам изучить алгоритм Винограда для умножения матриц – вот где истинная нумерология. :)
                                                                                                                +1
                                                                                                                Почему для умножения Карацубы выбраны только примеры, где сложение не даёт переноса? Это слегка нечестно.
                                                                                                                  +1
                                                                                                                  Потому что при сложении двух чисел с одинаковым количеством цифр у вас в худшем случае результат будет на одну цифру больше. Так что для действительно больших чисел этот перенос будет незначимым, поскольку будет выполнен всего на один разряд.

                                                                                                                  Если взять «неудачный» пример, то будет продемонстрировано как раз то, что метод Карацубы не дает приемущества в общем случае для небольших чисел.
                                                                                                                  –1
                                                                                                                  Все думают, что метод умножения, который они учили в школе, наилучший, °°°

                                                                                                                  Но на самом деле нужно изучать в школе fft

                                                                                                                    +1
                                                                                                                    А вот и похожая статья тут была несколько лет назад habr.com/ru/post/262705
                                                                                                                      +10
                                                                                                                      Как всегда, кликбейтный заголовок с фактическими неточностями, узнается Кванта.
                                                                                                                      At the end of February, a team of computer scientists at Aarhus University posted a paper arguing that if another unproven conjecture is also true, this is indeed the fastest way multiplication can be done.

                                                                                                                      Они придумали максимально быстрый на данный момент, без доказательства его идеальности. «Фундаментальное» ограничение скорости тоже под большим вопросом.
                                                                                                                        0
                                                                                                                        Мне кажется или O(xlog(x)log(logx)) быстрее O(x^1.46) для нового алгоритма при x выше 3300? Так какая у нового алгоритма сложность то?
                                                                                                                          0
                                                                                                                          Нашел, O(nlog(n))
                                                                                                                            +1
                                                                                                                            Так сравнивать нельзя: big-O же ничего не говорит про константы и про «менее быстро» растущие части функции.
                                                                                                                            0.0001*exp(x)-10000 — это всё равно O(exp(x))
                                                                                                                            100000*x+10000000*sqrt(x)+100000000000 — всё равно O(x)
                                                                                                                            0
                                                                                                                            Кто объяснит, почему на финальном шаге при умножении 2531х1467 2109 стоит там, где оно стоит. А не, к примеру, на разряд правее.
                                                                                                                              0
                                                                                                                              Потому что база 100. Элементарные части — двухразрядные, потому и сдвиг на два разряда.
                                                                                                                              +1
                                                                                                                              Умножение Карацубы 2531х1467 требует 9 умножений.

                                                                                                                              У меня у одного получается 12 умножений?
                                                                                                                                0
                                                                                                                                9 умножений «одноциферных». Вызовы умножений двуциферных не надо считать.
                                                                                                                                  0
                                                                                                                                  image
                                                                                                                                    0

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

                                                                                                                                      0
                                                                                                                                      Спасибо, разобрался.
                                                                                                                                      –1
                                                                                                                                      del. Опередили
                                                                                                                                  +3
                                                                                                                                  «Сложение в школе проходят на год раньше, потому что это гораздо проще, оно выполняется за линейное время, со скоростью чтения цифр слева направо»,


                                                                                                                                  А кто может мне пояснить, почему слева направо, а не справа налево?
                                                                                                                                  Сколько раз умножал столбиком, я делаю это справа налево, с переносом десятков в столбец слева.
                                                                                                                                    0
                                                                                                                                    вы цитируете сложение, а говорите про умножение. Это странно.
                                                                                                                                    Я действительно когда складываю числа одной разрядности, делаю это обычно в порядке чтения; но в школе все же учат складывать справа налево, тут вы правы.
                                                                                                                                    –2
                                                                                                                                    если моему алгу нужно много умножений, то я, возможно, просто хочу перейти в логарифмы
                                                                                                                                      +1
                                                                                                                                      Это же не про плавающую точку. Как, например, вы найдёте в логарифмах первые 20 чисел Мерсенна?
                                                                                                                                        0
                                                                                                                                        тогда проблемы возникнут со сложением и вычитанием
                                                                                                                                        +1
                                                                                                                                        А нейросети нельзя привлечь для поиска более совершенных алгоритмов перемножения/деления?
                                                                                                                                          0

                                                                                                                                          Нейронные сети плохо справляются с придумыванием алгоритмов кмк

                                                                                                                                            0
                                                                                                                                            Не придумывать, а «пробутфорсить» на совпадения.
                                                                                                                                            Дать на вход множественные числа и «поле» для разбиения этих чисел так и эдак.
                                                                                                                                            Сравнивать с заранее вычисленными итоговыми результатами на предмет верности того или ного случайного алгоритма. Может найдутся новые варианты и какие-то из них окажутся эффективными в каких-то контекстах
                                                                                                                                              0
                                                                                                                                              Алгоритм трудно выковырять из нейросети, и он может оказаться быстрым, но неточным и/или неверным за пределами обучающей выборки. Да и в области выборки даже. А так может и найдётся что-нибудь типа 0x5F3759DF.
                                                                                                                                                0

                                                                                                                                                "Быстрый обратный квадратный корень" — вообще-то частный случай. Так-то можно любые константы рассчитывать для операции степени от -1 до 1 с помощью математических методов и нейросети здесь не нужны.

                                                                                                                                          0
                                                                                                                                          Может кто объяснить зачем перемножать два числа размером миллиард на миллиард с такой асимптотической сложностью, если цифр все-равно получится n^2 и столько же операций потратится на запись? Да и вообще где хранить результат этого произведения? Ведь понадобится 10^9 гигабайт памяти.
                                                                                                                                            +5

                                                                                                                                            Цифр в ответе будет ~2n. 111*111 = 12321: 5 цифр а не 9. Даже со всеми переносами.

                                                                                                                                            0
                                                                                                                                            Интересно существует ли такой способ:
                                                                                                                                            1. первое число умножить на 1,2,3,4,...,9
                                                                                                                                            2. потом полученные значения суммировать с добавлением нужного кол-ва нулей?
                                                                                                                                              +1

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

                                                                                                                                              0
                                                                                                                                              Не нашел в сети информации о родителях Анатолия Алексеевича Карацубы — может кто-то поделиться ссылкой или данными?
                                                                                                                                                0
                                                                                                                                                Благодаря статье узнал что то, что на развлекательных сайтах называют «японским методом умножения чисел» (ну там где рисуют разноцветные линии и считают переcечения) по сути графическое представление умножения Карацубы.
                                                                                                                                                  0
                                                                                                                                                  Скорее графическое представление умножения на палочках Непера.
                                                                                                                                                    +1
                                                                                                                                                    Ну а что, «Карацуба» звучит вполне по-японски.
                                                                                                                                                    0
                                                                                                                                                    Карацюба, ШШ, и еще несколько методов умножения целых произвольной точности подробно описаны во втором томе «Получисленные алгоритмы» трехтомника Д. Кнута «Искусство програмирования для ЭВМ».
                                                                                                                                                    Там же разжеван алгоритм умножения в RNS, который требует n умножений, где n — количество модулей в RNS-базисе.
                                                                                                                                                      0
                                                                                                                                                      О, я придумал как считерить — надо перейти к системе счисления с большим основанием
                                                                                                                                                        0
                                                                                                                                                        В .NET (структура BigInteger), в JDK (класс BigInteger), в V8 (тип BigInt) и в GNU MP (тип mpz_t) используется основание 2^32 (беззнаковое 32-битное целое). Написать arbitrary precision арифметику с большим основанием (напр. 2^64), наверное возможно (придётся использовать промежуточную 128-битную арифметику), но мне кажется, что на существующих процессорах весь выигрыш сожрётся затратами на обслуживание этой 128-битной арифметики. Ну и прощай переносимость, конечно.
                                                                                                                                                          0

                                                                                                                                                          Вообще говоря, современные процессоры умеют перемножать два 64-битных числа с получением 128-битного результата, так что арифметика с основанием 264 вполне достижима (и даже будет быстрее стандартной), если писать на ассемблере.


                                                                                                                                                          Проблема в том, что в языках программирования такой операции умножения обычно нет...

                                                                                                                                                            0
                                                                                                                                                            Это разве не компилятор должен решать?
                                                                                                                                                              0

                                                                                                                                                              А что он может решить, когда нужной операции просто нет?

                                                                                                                                                                0
                                                                                                                                                                В каком языке нет символа умножения? В каком языке высокого уровня вы руками выбираете конкретную реализацию умножения в зависимости от типа? Или как-то раскройте что ли мысль.
                                                                                                                                                                  0

                                                                                                                                                                  В известных мне языках нет операции, которая бы из двух чисел размера N бит делала их произведение размера 2N бит.

                                                                                                                                                                    0
                                                                                                                                                                    Вообще-то, любое умножение дает сложение числа разрядов. Что вам мешает написать (uint16)=(uint8)*(uint8)? Как это обрабатывается процессором, зависит от целевой архитектуры и компилятора.
                                                                                                                                                                      0
                                                                                                                                                                      Мешают три вещи.

                                                                                                                                                                      Во-первых, (uint64)*(uint64) дает на выходе uint64, которую бесполезно расширять далее до uint128.

                                                                                                                                                                      Во-вторых, если предварительно привести операнды к более широкому типу, вылезет вторая проблема: полное умножение uint128 * uint128 — это вовсе не одна инструкция процессора, а компилятор не всегда замечает что старшая часть операндов — нулевая, и умножение можно сделать по короткой схеме. В итоге получается выгоднее использовать базу половинной разрядности.

                                                                                                                                                                      В-третьих, типа данных удвоенной разрядности (uint128) зачастую не существует.
                                                                                                                                                                        0
                                                                                                                                                                        Так этим компилятор занимается, а не программист. Ну и на вопрос я вам ответил.
                                                                                                                                                                          0
                                                                                                                                                                          Занимается чем?

                                                                                                                                                                          Длинную арифметику, почти во всех известных мне языках, пишут всё-таки программисты.
                                                                                                                                                                            0
                                                                                                                                                                            Выбором того, каким ассемблерным кодоом реализовать выш код.
                                                                                                                                                                            Длинная арифметика — условное понятие. Для 8 битных AVR uint32 это длинная арифметика, но никто не пишет ее руками. Деления там вообще нет, но писать в коде "/" никто не запрещает, и компилятор может раскрыть это по-разному.

                                                                                                                                                                            Вопрос у вас был без такой:
                                                                                                                                                                            нет операции, которая бы из двух чисел размера N бит делала их произведение размера 2N бит.
                                                                                                                                                                            Я вам привел вполне релевантный пример. Вы же мне пример языка, где бы программист указывал, какую инструкцию процессора использовать, так и не показали.
                                                                                                                                                                              0
                                                                                                                                                                              Выбором того, каким ассемблерным кодоом реализовать выш код.

                                                                                                                                                                              Да, этим должен заниматься компилятор. Но это не помогает решить задачу получения оптимального кода.


                                                                                                                                                                              Длинная арифметика — условное понятие.

                                                                                                                                                                              Пожалуйста, вспомните в контекста какого поста она тут обсуждается.


                                                                                                                                                                              Я вам привел вполне релевантный пример.

                                                                                                                                                                              Ваш пример работает только в том случае, если в выбранном ЯП тип uint8 расширяется до более крупного перед умножением. А это не обязательно так. В каком-нибудь Си для 8-битных AVR запросто может быть int=short=char=int8.


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

                                                                                                                                                                              Такой язык программирования был назван в первом же комментарии: язык ассемблера. Языков высокого уровня с этим свойством, конечно же, нет, по определению языка высокого уровня. Не понимаю почему вы ожидаете какого-то другого ответа и как это вообще связано с использованием базы половинной разрядности.

                                                                                                                                                                                –2
                                                                                                                                                                                В каком-нибудь Си для 8-битных AVR запросто может быть int=short=char=int8.
                                                                                                                                                                                Нет. Там int это uint16, как и в моем примере (собственно, откуда я его и взял). Даже для Attiny13, где вообще нет умножителя.
                                                                                                                                                                                язык ассемблера.
                                                                                                                                                                                Высокоуровневый?
                                                                                                                                                                                Языков высокого уровня с этим свойством, конечно же, нет, по определению языка высокого уровня. Не понимаю почему вы ожидаете какого-то другого ответа и как это вообще связано с использованием базы половинной разрядности.
                                                                                                                                                                                Потому, что вы просите какую-то отдельную операцию вместо обычного символа умножения. вместо того чтобы написать код
                                                                                                                                                                                uint64 a, b;
                                                                                                                                                                                uint128 c;
                                                                                                                                                                                ....
                                                                                                                                                                                c=a*b;
                                                                                                                                                                                
                                                                                                                                                                                Можно так написать? Что-то мне подсказывает, что да. Должен ли программист руками решать, какие процессорные инструкции при этом выполнятся? Что-то подсказывает, что нет (иначе вы не соберете это на архитектуре, где этой инструкции нет).
                                                                                                                                                                                  0
                                                                                                                                                                                  Можно так написать? Что-то мне подсказывает, что да.
                                                                                                                                                                                  Написать-то можно что угодно, только не забывайте что получится, а? Сходите, полюбуйтесь.

                                                                                                                                                                                  Почему в этой программе:
                                                                                                                                                                                  const int64_t a = 0x1000000000000000;
                                                                                                                                                                                  const int64_t b = 0x1000000000000000;
                                                                                                                                                                                  const __int128 c = a * b;
                                                                                                                                                                                  
                                                                                                                                                                                  переменная c равна нулю — нужно объяснять?
                                                                                                                                                                                    +1
                                                                                                                                                                                    То есть, вы мне на слова «это вопрос к компилятору, а не командам языка» говорите свое везкое «нет», а в качестве пруфа приводите выдачу конкретного компилятора. Серьезно?

                                                                                                                                                                                    При этом вы почему-то забыли сказать, что компилятор знает о проблеме и вас предупреждает:
                                                                                                                                                                                    /example.cpp:9:22: warning: integer overflow in expression of type 'long int' results in '0'
                                                                                                                                                                                    При этом я вам не говорил, что мой пример нормально отрабоатет в си. Я сказал, что в языке есть все средства для записи. Вы же хотите какую-то отдельную команду. Вы можете нормально сказать, что конкретно вы хотите? Второй символ умножения или что?
                                                                                                                                                                                      +1
                                                                                                                                                                                      То есть, вы мне на слова «это вопрос к компилятору, а не командам языка» говорите свое везкое «нет», а в качестве пруфа приводите выдачу конкретного компилятора. Серьезно?
                                                                                                                                                                                      Абсолютно. Если вы считаете, что этот компилятор не годится — можете найти другой. Их там много. Но не получится. Потому что не в компиляторах дело.

                                                                                                                                                                                      При этом я вам не говорил, что мой пример нормально отрабоатет в си. Я сказал, что в языке есть все средства для записи.
                                                                                                                                                                                      Это вообще что? У вас первое предложение противоречит второму, извините.

                                                                                                                                                                                      Второй символ умножения или что?
                                                                                                                                                                                      Как вариант. В Forth есть операция M* — она как раз делает то, что требуется. Но в распространённых языках такой операции нет. Записать операцию «пермножить два 64-битных числа с получением 128-битного результата» там нельзя. В Forth — можно, а в C, Java, Pascal, да и вообще почти во всех распространённых языках — нельзя. Вот вообще нельзя. Никак.

                                                                                                                                                                                      При этом вы почему-то забыли сказать, что компилятор знает о проблеме и вас предупреждает
                                                                                                                                                                                      Хех. Вопрос «почему там предупреждение и почему оно исчезает если в примере int64_t на uint64_t заменить (хотя результат всё равно остаётся нулевым)» — это хороший вопрос на знание C, но он всё равно не помогает нам решить поставленную задачу… вы, кстати, знаете, почему замена int64_t на uint64_t убирает предупреждение? Или нет? Если нет — тогда вообще неясно о чём мы тут говорим…
                                                                                                                                                                                        0
                                                                                                                                                                                        Никак.

                                                                                                                                                                                        А если оператор перегрузить?
                                                                                                                                                                                          +1
                                                                                                                                                                                          Нельзя перегрузить оператор для стандартных типов. C++ расширяем, но не изменяем.

                                                                                                                                                                                          Кроме того, непонятно чем перегрузка оператора поможет: если в языке не было конструкции, выражающейся через соответствующую инструкцию процессора — то откуда она в перегруженном операторе возьмётся?

                                                                                                                                                                                          Можно написать c = (unsigned __int128)a * b; — но вот уже тут вы опираетесь на свойства конкретного компилятора и на тот факт, что он может понять, что в данном случае использование одиночного mulq — безопасная оптимизация. Clang, скажем, «просекает фишку» всегда, а вот GCC — не всегда. Сравните (и посчитайте количество mulqов и imulqов в сгенерированном коде).

                                                                                                                                                                                          В принципе с этим можно жить (если не забывать про -Og), но это всё равно — хождение по минному полю…
                                                                                                                                                                                          0
                                                                                                                                                                                          Потому что не в компиляторах дело.
                                                                                                                                                                                          Тогда каким образом вывод компилятора что-то доказывает? Впрочем, я вполне допускаю, что могу тупить, но тогда почему бы вам нормально не написать ваше видние?!
                                                                                                                                                                                            0
                                                                                                                                                                                            Впрочем, я вполне допускаю, что могу тупить, но тогда почему бы вам нормально не написать ваше видние?!
                                                                                                                                                                                            Потому что любая дискуссия предполагает некоторый уровень владения предметом. Если мне сейчас придётся вам объяснять всё, что программисты проходят за пару лет обучения в ВУЗе — то наша дискуссия никогда не дойдёт до сути вопроса.

                                                                                                                                                                                            Моя отсылка — была простым тестом на понимание вами языка C и ассмеблера.

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

                                                                                                                                                                                            Вы за неё уцепились, чем показали, что вы не понимаете не только как устроен компилятор C, но также и как устроен собственно язык С… а какой смысл обсуждать свойства языка C с человеком, который его не знает?

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

                                                                                                                                                                                              Gforth 0.7.3, Copyright (C) 1995-2008 Free Software Foundation, Inc.
                                                                                                                                                                                              Gforth comes with ABSOLUTELY NO WARRANTY; for details type `license'
                                                                                                                                                                                              Type `bye' to exit

                                                                                                                                                                                              4294967296 4294967296 cr .S
                                                                                                                                                                                              <2> 4294967296 4294967296 ok
                                                                                                                                                                                              M* cr .S
                                                                                                                                                                                              <2> 0 1 ok
                                                                                                                                                                                              cr D. .S
                                                                                                                                                                                              18446744073709551616 <0> ok
                                                                                                                                                                                              (ответ компьютера выделен жирным).

                                                                                                                                                                                              Вместо ссылки на godbolt я мог бы показать вам это… если бы был хоть какой-то шанс того, что вы бы поняли этот пример.
                                                                                                                                                                                                0
                                                                                                                                                                                                В общем, вы правы. Но я не вижу проблемы указать из какой конкретно особенности «устройства языка» следует, что это должно так работать.
                                                                                                                                                                                                  0
                                                                                                                                                                                                  Это следуют просто-напросто из того факта, что у выражения a*b есть значение — и оно имеет тот же тип, что a или b, и, внезапно, int (в зависимости от того, какой трёх типов «шире»).

                                                                                                                                                                                                  А дальше — можно это значение засовывать уже куда угодно, хоть в 128-битную переменную, хоть в 256-битную, это уже ничего не изменит…
                                                                                                                                                                                                    0
                                                                                                                                                                                                    Кстати, насчет специальных команд. Есть, вроде интринсики типа _mul128 или что-то такое (как вы правильно поняли, в норме я не имею дела с такими вещами, и на большинстве моих девайсов вся математика слишком толстая, и выход за пределы uchar является событием).
                                                                                                                                                                                                      0
                                                                                                                                                                                                      Интринзики действительно есть — но для SIMD инструкций. Для обычных, удивительным образом, ничего не предусмотрено.
                                                                                                                                                                                                        0
                                                                                                                                                                                                        Одна из причин, к слову, по которой при желании оптимизировать я предпочитаю писать на ассемблере целиком, а не использовать интринсики.
                                                                                                                                                                                                      0
                                                                                                                                                                                                      Объясните, на каком основании у выражения a*b должно быть значение того же типа, что и у a и b? Почему языки устроены таким странным образом?
                                                                                                                                                                                                      В нашей повседневной реальности я умножаю метр на метр и получаю квадратный метр. В любых расчётах тип сохраняется только при сложении и вычитании, а при других действиях — получается другой тип. А в языках программирования внезапно, ладно что иначе по умолчанию, но и в порядок привести нельзя.
                                                                                                                                                                                                        0
                                                                                                                                                                                                        Ну это вам в историю математики стоит углубиться.

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

                                                                                                                                                                                                        В любых расчётах тип сохраняется только при сложении и вычитании, а при других действиях — получается другой тип.
                                                                                                                                                                                                        Ну это, всё-таки, не совсем так. Длина окружности и её радиус имеют одинаковый тип, что не мешает им быть связанными соотношениями L = 2πr.

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

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

                                                                                                                                                                                                        Почему языки устроены таким странным образом?
                                                                                                                                                                                                        Не только языки. Процессоры тоже. Да, у процессора, в отличие от языка C, есть инструкция, возвращающая «удвоенный» результат (8but * 8bit ⇒ 16bit, 16bit * 16bit ⇒ 32bit, 32bit * 32bit ⇒ 64bit), в отличие от C, однако операция, сохраняющая размер — у него тоже есть… и она, в большинстве случаев, работает быстрее.
                                                                                                                                                                                                          +1
                                                                                                                                                                                                          В нашей повседневной реальности я умножаю метр на метр и получаю квадратный метр.
                                                                                                                                                                                                          И про квадратные уравнения вы, конечно, ничего не слышали?
                                                                                                                                                                                                          Если Х не безразмерный, то и константы не безразмерные (в отличие от числа пи). В физике всегда сохраняется размерность во всех уравнениях (есть даже техники поиска решений методом подгонки размерностей).
                                                                                                                                                                                                            0
                                                                                                                                                                                                            В физике всегда сохраняется размерность во всех уравнениях (есть даже техники поиска решений методом подгонки размерностей).
                                                                                                                                                                                                            Тем не менее даже в этих случаях могут быть много тонкостей, так как в физике полно размерных констант.

                                                                                                                                                                                                            Тот факт, что в большинсво языков программирования всё это богатство не отражается — несколько прискорбен, но к выбору float double или там uint8_t uint64_t это всё не имеет отношения.

                                                                                                                                                                                                            Ситуация, когда вам хочется сменить базовый тип на практике, всё-таки, случаётся реже, чем когда у вас появляется другая размерность.
                                                                                                                                                                                                              +1
                                                                                                                                                                                                              Тем не менее даже в этих случаях могут быть много тонкостей, так как в физике полно размерных констант.

                                                                                                                                                                                                              Никаких тонкостей нет ИМЕННО благодаря размерным константам. Если не верите — приведите хоть один пример.

                                                                                                                                                                                                              А если мне приходится складывать x + x^2 — это достаточная причина, что искать ошибку где-то в выводе формулы.
                                                                                                                                                                                                                0
                                                                                                                                                                                                                Да боже ж ты мой. Скорость удаления двух частиц, разлетающихся в разные стороны. Простейший пример, в школе изучают.
                                                                                                                                                                                                                  +1
                                                                                                                                                                                                                  Там все размерности сходятся. Если размерность не сходится, то формула не имеет физического смысла.

                                                                                                                                                                                                                  Впрочем, вы правы, что к размеру переменных это имеет мало отношения, если имеет вообще.
                                                                                                                                                                                                                    +2
                                                                                                                                                                                                                    К размеру переменных — не имеет.
                                                                                                                                                                                                                    Но противоречит утверждению khim о том, что у результата умножения концептуально должен быть тот же тип, что и у операндов.
                                                                                                                                                                                                                      +3
                                                                                                                                                                                                                      Не надо тянуть сову на глобус, пожалуйста. Ей больно.

                                                                                                                                                                                                                      Типы в понятии современных языков программирования — это не физические размерности, а, скорее, вот эти вот , , и прочие 4294967296.

                                                                                                                                                                                                                      Все математические операции, если не сказано иного — в математике производятся в рамках одного подобного типа. И умножение и деление тоже.

                                                                                                                                                                                                                      А то, что «физические» типы в современных языках почти никак не представлены — это неприятно, но к обсуждаемому вопросу отношения не имеет. Эти типы всё равно, скорее всего, существовали бы только в исходниках, но не в скомпилированной программе.
                                                                                                                                                                                                                        0
                                                                                                                                                                                                                        Типы в понятии современных языков программирования — это не физические размерности, а, скорее, вот эти вот ℕ, ℚ, ℝ и прочие ℤ4294967296.

                                                                                                                                                                                                                        Э, ну если я пишу вычислительный код для физической задачи, то навернуть там сверху ещё dimensions checking сам Пирс велел.


                                                                                                                                                                                                                        Эти типы всё равно, скорее всего, существовали бы только в исходниках, но не в скомпилированной программе.

                                                                                                                                                                                                                        И хорошо. Статически проверили и выкинули, зачем их в рантайм тащить?

                                                                                                                                                                                                          –1
                                                                                                                                                                                                          Объясните, на каком основании у выражения a*b должно быть значение того же типа, что и у a и b? Почему языки устроены таким странным образом?

                                                                                                                                                                                                          Лол, а оно и не должно (и не является, я даже удивлён, что khim про integer promotion не упомянул):


                                                                                                                                                                                                          uint8_t a = 0, b = 0;
                                                                                                                                                                                                          static_assert(std::is_same_v<int, decltype(a * b)>);

                                                                                                                                                                                                          Про не-сиподобные языки я даже говорить не буду.

                                                                                                                                                                                                            0
                                                                                                                                                                                                            Он упомянул.
                                                                                                                                                                                                              0

                                                                                                                                                                                                              Это потом было, я к тому моменту ещё не дочитал.

                                                                                                                                                                                                          0
                                                                                                                                                                                                          Кстати, если дело в этом, то почему uint16_t=uint8_t*uint8_t работает (в том числе для AVR, откуда я исходно взял свой пример) так, как этого описал я?
                                                                                                                                                                                                            0
                                                                                                                                                                                                            Потому что uin16_t имеет размер меньше, чем int, однако.
                                                                                                                                                                                                              +1
                                                                                                                                                                                                              Как это согласуется с утверждением выше?
                                                                                                                                                                                                              у выражения a*b есть значение — и оно имеет тот же тип, что a или b
                                                                                                                                                                                                              Ну а размер int архитектурно зависим.
                                                                                                                                                                                                                0
                                                                                                                                                                                                                Как это согласуется с утверждением выше?
                                                                                                                                                                                                                у выражения a*b есть значение — и оно имеет тот же тип, что a или b
                                                                                                                                                                                                                А доцитировать до конца?

                                                                                                                                                                                                                Впрочем да — коряво высказался. Берётся большее из типа a, типа b или типа int.

                                                                                                                                                                                                                Ну а размер int архитектурно зависим.
                                                                                                                                                                                                                И? Кого это волнует? Весь процесс описан в разделе «6.3.1.8 Usual arithmetic conversions» с отсылкой на «6.3.1.1 Boolean, characters, and integers», где описано что такое the integer promotions.

                                                                                                                                                                                                                Все операции C «стремится исполнять» над intами — это тяжёлое наследие языка B, где никаких других типов просто не было. Собственно C был итеративно получен из B, и, в частности, когда были добавлены типы большего (и меньшего) размера, чем int — с ними что-то нужно было делать. Ну и было классическое соломоново решение: если типы меньше, чем int — то они приводятся в int, перед тем, как что-то считать, а если больше (а, собственно, тогда только один тип и был большим, чем int) — то нет. Было бы уж как-то совсем неестественно перемножить uint64_t на uint64_t и получить uint32_t (если у вас int — 32хбитный), согласитесь?
                                                                                                                                                                                                                  0
                                                                                                                                                                                                                  если типы меньше, чем int — то они приводятся в int, перед тем, как что-то считать
                                                                                                                                                                                                                  Даже если int больше размера регистров АЛУ (да и других, впрочем)?

                                                                                                                                                                                                                  Ну и смотрите, выше вы говорили, что это нечто принципиальное, а оказывается, просто наследие.
                                                                                                                                                                                                                    +1
                                                                                                                                                                                                                    Даже если int больше размера регистров АЛУ (да и других, впрочем)?
                                                                                                                                                                                                                    Разумеется. Разработчик компилятора вправе сам решать — что там у него за int. Но если назвался — то всё должно считаться в int. Никаких АЛУ в стандарте нет.

                                                                                                                                                                                                                    Ну и смотрите, выше вы говорили, что это нечто принципиальное, а оказывается, просто наследие.
                                                                                                                                                                                                                    Где я говорил, что это фундаментальный закон физики?

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

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

                                                                                                                                                                                                                    Я уже приводил пример языка, где оператор умножения с порождением результата двойного размера имеется. Если бы наша современная IT-индустрия бы развивалась на его базе, а не на базе C — у нас много чего было бы по-другому. Но поскольку C оказался в основе всего, с чем мы работаем — то и Pascal и C++ и Java и многое-многое другое — работают так же…
                                                                                                                                                                                                                      0
                                                                                                                                                                                                                      Разработчик компилятора вправе сам решать — что там у него за int.
                                                                                                                                                                                                                      То есть, в итоге дело таки в компиляторе? Что принципиально мешает добавить какой-нибудь флаг типа -use128int (и собирать все тяжелые мат модули с ним)? Разве это противоречит стандарту?
                                                                                                                                                                                                                      Никаких АЛУ в стандарте нет.
                                                                                                                                                                                                                      В получаемом ассемблере-то есть. Как мы получим (а мы ее получаем) оптимальную 8-битную математику с 16 битным int?
                                                                                                                                                                                                                        0
                                                                                                                                                                                                                        Разве это противоречит стандарту?
                                                                                                                                                                                                                        Противоречит. Вы можете иметь в программе какой угодно int, но он должен быть един для всей программы. Никаких модулей стандарты C и C++ не предусматривают (С++20, возможно, предусмотрит, но вряд ли там будет разрешено иметь в разных модулях разные intы).

                                                                                                                                                                                                                        И вы тут, опять-таки, «никуда не соскочите»: если вы сделаете такой финт ушами, то у вас все вычисления станут int128⇒int128. Даже если когда вы байт на байт будете умножать — они будут сначала превращаться в int128, а потом уже перемножаться.

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

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

                                                                                                                                                                                                                        Как мы получим (а мы ее получаем)
                                                                                                                                                                                                                        Это вы с -O0 её получаете? Не надо сказок, пожалуйста: если вы умножаете 8-битное число на 8-битное — то они сначала расширяются до 32-бит, потом обрезаются обратно в 8.

                                                                                                                                                                                                                        оптимальную 8-битную математику с 16 битным int?
                                                                                                                                                                                                                        За счёт того, что большинство существующих компиляторов — оптимизирующие. И некоторые оптимизации вообще неотключаемые. Но гарантий никаких нет — см. пример выше.
                                                                                                                                                                                                                          0
                                                                                                                                                                                                                          Разве я не могу собрать разные исходные файлы, используя разный int, а потом слинковать все вместе? С чужими же elf'ами могу.
                                                                                                                                                                                                                          Не надо сказок, пожалуйста: если вы умножаете 8-битное число на 8-битное — то они сначала расширяются до 32-бит, потом обрезаются обратно в 8.
                                                                                                                                                                                                                          Это на х86-64. На Avr ничего такого не происходит, при этом дефолтный размер int там 16 бит, если не указать руками иное.
                                                                                                                                                                                                                            0
                                                                                                                                                                                                                            Разве я не могу собрать разные исходные файлы, используя разный int, а потом слинковать все вместе? С чужими же elf'ами могу.
                                                                                                                                                                                                                            Собрать-то вы можете… а вот будет ли подобный франкенштейн работать — это уже большой вопрос, на который ни разработчики стандарта C, ни разработчики компилятора вам не ответят. Вряд ли можно рекомендовать использовать, без самой крайней нужды, что-то, работоспособность чего зависит от цены на папайю в Гонолулу.

                                                                                                                                                                                                                            На Avr ничего такого не происходит, при этом дефолтный размер int там 16 бит, если не указать руками иное.
                                                                                                                                                                                                                            Ну значит вам везёт и компилятор, которым вы пользуетесь не умеет эту оптимизацию отключать. Завтра может выйти другая версия — и она вполне может начать всё это делать неоптимально.

                                                                                                                                                                                                                            Мы ведь тут обсуждаем не конкретный компилятор, а язык, так что того факта, что так себя ведёт компилятор на x86-64 — вполне достаточно для иллюстрации.