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



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



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

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

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

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

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

Вы можете помочь и перевести немного средств на развитие сайта

Теги:



Комментарии (191):

  1. lingvo
    /#20154694

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

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


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

    • Alexeyslav
      /#20154810

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

      • DarkTiger
        /#20155664

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

        • DistortNeo
          /#20156396

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

          • DarkTiger
            /#20156530

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

          • DarkTiger
            /#20156556

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

            • DistortNeo
              /#20157812

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

              • DistortNeo
                /#20161710

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


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

          • potan
            /#20156870

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

      • potan
        /#20156858

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

        • khim
          /#20158020

          Вот только «тяжёлые рассчёта» сейчас делают на GPU — и там как раз арифметика даёт ощутимый такой вклад в энергопотребление…

          • NeocortexLab
            /#20162662

            «Тяжёлые рассчёта» делают на GPU когда надо сделать много маленьких расчётов параллельно. Современные GPU как-то не очень подходят для задач вроде описанных в статье — всё равно что свинью стричь — визгу много, шерсти нет

    • farafonoff
      /#20155130

      В статье описывались асимптоты алгоритма умножения, а скорость выполнения процессорных инструкций входит в константу при них. Очевидно, что если нужно умножить два числа в миллиарды знаков (байт, слов), то скорость будет зависеть как раз от экспоненты.
      Деление в худшем случае можно переписать как умножение и двоичный поиск, соответственно худшая оценка для деления теперь — n*logn*logn.

      • wataru
        /#20155234 / +1

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


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

        • saluev
          /#20158352

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

          • netch80
            /#20163690

            Вещественные числа давно уже делят, например, Голдшмидтом, и квадратный корень аналогично — с тех времён, как научились рассчитывать погрешность при таких вычислениях. Но в остальном — последствия такие же по сути, да, как для Ньютона (по ссылке — 1 цикл для single, 2 для double, 3 для extended).

      • potan
        /#20156904

        Был какой-то достаточно эффективные алгоритм аппроксимации 1/n, а деление делается через него.

      • khim
        /#20157902 / +1

        log log n растёт очень-очень-очень медленно. Даже если там миллиарды знаков — это будет что-то типа 5-6. А чтобы дорасти до 10 уже всех компьютеров мира не хватит.

        Так что они правильно написали: теоретически — это дико круто, практически — отличие невелико…

    • dedalqq
      /#20155572 / +1

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

      А еще бы разложение на множители и прощай криптография =)

      • vokzamag
        /#20155956

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

        • Deerenaros
          /#20156196

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

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

        • CryptoPirate
          /#20156488 / +1

          Квантовые компьютеры не уничтожат всю криптографию, только алгоритмы типа RSA и Diffie Hellman. У всей симметричной криптографии уполовинется степень защиты.
          И ещё, есть так называемая «post-quantum» криптография, там шифрование основано на сложных проблемах не связанных со сложностью разложения на простые множители и дискретный логарифм. Прямо сейчас идет соревнование на стандарт подобного типа. Такие алгоритмы выполняются на обычных комптьютерах и квантовые компьютеры им не страшны.

    • potan
      /#20156836

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

    • Daddy_Cool
      /#20157686 / +1

      Мы неплохо использовали операцию «быстрого обратного корня». Одно деление=перемножить два быстрых обратных корня. Получалось выгоднее. )

    • netch80
      /#20163670

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

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

  2. danfe
    /#20154806

    Чуть более подробно про семинар Колмогорова, Карацубу и его способ умножения у Аввы в прошлом году был интересный пост в ЖЖ.

  3. Radiohead72
    /#20155030

    В далеком детстве, я научился в уме извлекать кубические корни из шестизначных чисел)))

    • mikevmk
      /#20155264 / +6

      … а, также, расставлять, избыточные, знаки, препинания))))))))

      • Radiohead72
        /#20156156 / -2

        С возрастом перестал обращать внимание на такие мелочи как знаки препинания и прочие правила грамматики)
        Раз смысл ясен — то к чему все эти условности? )))))

        • danfe
          /#20156306 / +2

          Смысл ясен вам как автору; стороннему читателю такие мелочи как знаки препинания и прочие правила грамматики помогают намного быстрее читать и понимать текст, «парсинг» же контекста обычно медленнее, требует больше умственных затрат и нередко дает сбои, предложение (а то и фразу целиком) приходится перечитывать.

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

          • Halt
            /#20157402

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

          • mkovalevskyi
            /#20158208

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

            • extempl
              /#20159474

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


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


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


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

              • BigBeaver
                /#20160410

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

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

            • User2Qwer
              /#20163200

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

        • Nidere
          /#20156416

          С ещё большим возрастом перестанете обращать внимание на такие мелочи, как не писаться в штаны, да?
          К чему все эти условности, право…

        • Vnuchok
          /#20163668

          да? Мне один знакомый пишет без знаков вопроса и любое его вопросительное предложение выглядит как приказ. «Ты сделаешь завтра отчёт», например.

        • stalactite
          /#20169126

          Ох, это Хабр, тут заклюют за любую мелочь, которую посчитают нужной в конкретный момент, в конкретной тематике. Просто на ровном месте заминусовали коммент и карму. А потом они еще говорят про какую-то демократию тут, про то, что не вытесняют неугодных с ресурса. И, да, этот коммент тоже заминусуют, будьте уверенны. Это же так просто: анонимно нажать на минус и сидеть гордиться этим весь остаток дня.

          • KvanTTT
            /#20169470 / +2

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

          • BigBeaver
            /#20169530 / +1

            анонимно нажать на минус и сидеть гордиться этим весь остаток дня.
            Человек с правом голоса имеет их не менее 10 в день. Достаточно гордиться каждым всего минут по 40 чтобы день прошел хорошо.

    • unC0Rr
      /#20155266

      С какой точностью?

      • Radiohead72
        /#20156126 / -1

        А я помню? :-)
        Это было тааааак давноооо…
        Прочел книгу емнип «Система быстрого счета по Трахтенбергу» и запомнил формулу которая позволяла в уме вычислять эти кубические корни. Но только кубические и только из шестизнаков)
        Теперь уж и не помню ее. Формулу в смысле.

      • sielover
        /#20158222

        Ну здесь имеется ввиду вычисление кубического корня из числа, которое является кубом целого. Кубический корень из шестизначного — это число двузначное, надо лишь оценить первую цифру результата, сравнив первые три цифры шестизначного числа с 125, 216, 343 и 512, а вторая цифра результата определяется по последней цифре шестизначного числа (там однозначное соответствие).

      • Aprilfire
        /#20160924

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

  4. AVX
    /#20155164

    Что-то я не понял. Всегда считал, что умножение в двоичной системе делается быстрее всего — там операций совсем мало и они крайне быстрые — сдвиг и сложение. (сдвигаем на один бит — получаем умножение на 2, или деление, если наоборот). Так что методов можно много напридумывать, но в двоичной системе (в которой почти все компьютеры работают) всё равно будет тот самый метод со сдвигом. Так что это всё скорее применимо к «человекочитаемым» способам умножения, нежели к процессорным. Поправьте меня, если я заблуждаюсь.

    • farafonoff
      /#20155190

      Сдвиг и сложение — это и есть «столбиком». Сложение это n операций, и потребуется ровно n сдвигов. Приведенные алгоритмы — асимптотически лучше.

      • GCU
        /#20155372

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

      • AVI-crak
        /#20157198

        farafonoff
        В процессоре не столбиком, там вообще нет отдельной операции сдвига, линии данных до сумматоров уже разведены в железе. Операции сложения выполняются параллельно со всеми разрядами множимого, а чуть позже и со всеми промежуточными вариантами. Без разделения операций на отдельные такты — тут работают защёлки. Они-же предназначены для запоминания промежуточных вычислений и коммутации данных со сдвигом.
        В результате умножение целого 32б на 32б с результатом в 64б — требует срабатывания пяти защёлок, и в целом операция умножения успевает выполниться за один такт.
        С плавучкой немного сложнее, но даже там операции над всеми разрядами данных выполняются параллельно.

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

        • farafonoff
          /#20157282

          Если всё так как ты описал — часть сложности перенесена в железо. Т.е. вместо линейного количества времени тебе нужно линейную площадь кристалла. Это всё равно не позволяет выйти за границу асимптотической оценки. Попробуй представить умножение двух чисел длиной в гигабайт.

          • AVI-crak
            /#20158968

            Попробуй представить умножение двух чисел длиной в гигабайт.

            А зачем представлять, если есть библиотека которую можно посмотреть.
            Очень большие и жирные числа всегда в десятичной системе. Не потому что удобно, а от того что перевод из двоичного представления в десятичное — будет слишком долгим. К тому-же математики помешаны на магии десятичной системы, у них это почти религия.
            Дык вот, в свободной мат. библиотеке разбивка чисел уже работает, задолго до этого открытия.
            Просто программисты забыли предупредить об этом местных светил математики.

            • farafonoff
              /#20159552

              Последний раз повторяю. Посмотри например сюда:
              hg.openjdk.java.net/jdk8/jdk8/jdk/file/tip/src/share/classes/java/math/BigInteger.java
              Метод public BigInteger multiply(BigInteger val) вызывает аж 3 реализации, в зависимости от длины чисел (все 3 способа описаны в статье). Кроме того хранятся не десятичные цифры, а сразу int32 (а к десятичной системе можно привести при печати).

        • khim
          /#20157968 / +2

          В результате умножение целого 32б на 32б с результатом в 64б — требует срабатывания пяти защёлок, и в целом операция умножения успевает выполниться за один такт.
          Не успевает. Откройте табличку, да посмотрите. Даже Ryzen и Skylake-X требуют для этого 3-4 такта, на более старых процессорах — больше. Да, это не 30-40 тактов, как для деления, но и не один такт. Просто потому что если реализовать ваше предложение — то придётся снижать частоту, а тогда и другие операции медленнее станут.

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

          Парадоксы современного процессоростроения…

          • BigBeaver
            /#20158878

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

            • Zenitchik
              /#20160592

              Если я правильно понял предмет спора, произошла терминологическая путаница.

              Single-cycle

              Скорее всего имеется в виду машинный цикл, который состоит из нескольких тактов задающего генератора (на известных мне микроконтроллерах — 4).

              • BigBeaver
                /#20160820

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

                И если у нас все инструкции single-cycle, то мы получаем константное время выполнения кода. Во всяких специализированных сигнальниках могут вообще дикие вещи за 1 такт делаться. Ну то есть, я не понимаю смысла говорить о еще более низком подуровне.

                • Zenitchik
                  /#20161398

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

                  • BigBeaver
                    /#20161478

                    Ну… в любом случае это все сильно архитектурнозависимые вещи. А выше они так спорят, как будто бы за этим всем стоят какие-то фундоментальные законы.

                    • khim
                      /#20162670

                      А за этим и стоят фундаментальные законы. Подумайте вот над чем: отдельные рекордные транзисторы работают на частотах в сотни гигигерц. Беглый поиск приводит к 798 GHz, правда в SiGe, но даже транзисторы в ваших процессорах на 200-300GHz способны… а процессор в целом — даже 10GHz «не делает» и даже на этой частоте ему нужны 3-4 такта для умножение и десятки — да деление.

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

                      Подумайте над этим…

                      • BigBeaver
                        /#20162992

                        Эмм. Фундоментальные ограничения на чустоту электроники, как таковой, не особо противоречат моим словам.

                        • khim
                          /#20163132

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

                          Но вот будете ли вы выносить на архитектурный уровень тот факт, что умножение, всё-таки, сложнее умножения — это другой вопрос: вы не можете ускорить умножение до скорости сложения, но вы можете замедлить сложение… а можете «более простое» сложение «встроить в умножение» (откуда и получается MAC — инструкция: она выполняется за то же время, что и умножение и позволяет, часто, экономить на сложении).

            • khim
              /#20162540

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

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

              • DistortNeo
                /#20162922

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

                • khim
                  /#20162972

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

          • AVI-crak
            /#20158982 / -1

            Не успевает. Откройте табличку, да посмотрите.

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

            • khim
              /#20162680 / +1

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

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

        • Ghost999
          /#20160930 / +2

          Одно дело — умножение чисел не превышающих разрядность ALU, и совершенно другое — умножение больших чисел. Для этого и существуют специальные алгоритмы.

    • wataru
      /#20155242 / +3

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

  5. wataru
    /#20155288

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

    • Arqwer
      /#20158102 / +2

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

      • wataru
        /#20158124

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

    • saluev
      /#20158388 / +1

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

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

      • wataru
        /#20160064

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

        • farafonoff
          /#20160880

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

          • wataru
            /#20160936

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

        • mayorovp
          /#20161084

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

    • nzamb1
      /#20160908 / -1

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

    • vient
      /#20160918 / -1

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

      • wataru
        /#20160942

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

  6. Refridgerator
    /#20155340 / +2

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

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

    • Jedi_PHP
      /#20155478

      hal.archives-ouvertes.fr/hal-02070778/document

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

      • Refridgerator
        /#20155508

        Что вы этим хотели сказать? Ссылка на эту работу есть в статье, я её уже посмотрел.

        • Jedi_PHP
          /#20155746

          Это дурная привычка сразу же отвечать только на первое предложение в прочитанном.
          Извините. Но я работаю над собой.

    • avsmal
      /#20158590 / +1

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

      > Например, в лемме 2.3 там доказывается convolution formula, согласно которой свёртка функций равносильна перемножению их Фурье-образов. Зачем? Это же известный, давно доказанный факт — можно было просто сослаться на доказательство, тем самым уменьшив объём работы.
      Это называется self-contained proof. Если какие-то уже известные результаты имеют простое доказательство, и их рассмотрение может добавить понимания, то их доказательство повторяется в статье.

  7. questor
    /#20155436

    Можно наивный вопрос? Метод был предложен в 1960 году, он уже используется в современных ЭВМ? Если нет, то наверное есть какая-то объективная причина?

    • SLY_G
      /#20155456

      Метод Шёнхаге-Штрассена используется компьютерами для умножения больших чисел

    • vitaliy2
      /#20158404 / +1

      Асимптотика показывает только зависимость от размера данных, и не показывает итоговое реальное время и так называемую «константу» перед асимптотикой. Например, O(10n) равно O(n). Константа «10» скрыта, т.?к. на очень больших числах (например, стремящихся к бесконечности) это всё-равно будет быстрее, чем, допустим, O(n1.000000001) без скрытой «10», а также потому, что константа может зависеть от реализации.

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

    • speshuric
      /#20158784

      Конечно используются. В JDK и .NET Core используется умножение Карацубы (в JDK 11 по умолчанию умножение переходит на Карацубу, если множители больше 2560 бит ). В JDK с множителей длины 7680 бит используется умножение Тоома-Кука.

    • defuz
      /#20158800

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

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

    • netch80
      /#20163776

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

  8. infund
    /#20155656

    Теперь ждём, когда заново откроют сложение!

    • abar
      /#20156138

      Шутка «Если умножение так хорошо, то почему ещё не выпустили умножение 2» перестает работать.

    • dimonoid
      /#20158614

      Бинарное сложение с предрасчетом carry уже давно существует, работает за 1 такт.

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

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

  9. Bookvarenko
    /#20155966 / +1

    Отлично! Значит реймаршинг будет выполняться ещё быстрее. Немного прифигел от скромности ван дер Хувена: «Всё, на что мы можем надеяться, это на трёхкратное ускорение».

    • Refridgerator
      /#20156192 / +1

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

    • khim
      /#20157984

      Это не скромность. Попробуйте прикинуть при каком n у вас log log n «дорастёт» до десятки и подумайте — будут ли вас когда-нибудь волновать такие числа.

    • speshuric
      /#20158826 / +1

      Значит реймаршинг будет выполняться ещё быстрее.

      А где там длинные числа? Все эти быстрые умножения (Карацуба и последующие) они про числа в тысячи бит.

  10. legolegs
    /#20156052

    Умножение Карацубы выглядит как какая-то нумерология со сложением казалось бы не имеющих отношения к умножению цифр.

    шутка про нумерологию
    ID поста 451860, сумма цифр 4+5+1+8+6+0=24, среднее между 2 и 4 = 3, Half Life 3 confirmed

    • solariserj
      /#20156160

      > Шутка про нумералогию
      оффтоп, но напомнило

      Умберто Эко (с) «Маятник Фуко»
      «Театральным жестом он распахнул ставни, предложил нам выглянуть и указал невдалеке, на углу между улочкой и бульварами, деревянный цветочный киоск.
      — Господа, — сказал он. — Предлагаю вам самим отправиться и измерить эту будку. Вы увидите, что длина прилавка составляет 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, царь Пергама. Годится?»

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

    • mayorovp
      /#20156912

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


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


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

  11. Zenitchik
    /#20156292

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

    • defuz
      /#20158816

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

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

  12. basilbasilbasil
    /#20156454 / -1

    Все думают, что метод умножения, который они учили в школе, наилучший, °°°

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

  13. mozgoverflow
    /#20156584 / +1

    А вот и похожая статья тут была несколько лет назад habr.com/ru/post/262705

  14. Num
    /#20156726 / +1

    Как всегда, кликбейтный заголовок с фактическими неточностями, узнается Кванта.

    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.

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

  15. dimonoid
    /#20157772

    Мне кажется или O(xlog(x)log(logx)) быстрее O(x^1.46) для нового алгоритма при x выше 3300? Так какая у нового алгоритма сложность то?

    • speshuric
      /#20158810

      Так сравнивать нельзя: big-O же ничего не говорит про константы и про «менее быстро» растущие части функции.
      0.0001*exp(x)-10000 — это всё равно O(exp(x))
      100000*x+10000000*sqrt(x)+100000000000 — всё равно O(x)

  16. Noweol
    /#20158358

    Кто объяснит, почему на финальном шаге при умножении 2531х1467 2109 стоит там, где оно стоит. А не, к примеру, на разряд правее.

    • Zenitchik
      /#20158382

      Потому что база 100. Элементарные части — двухразрядные, потому и сдвиг на два разряда.

  17. MOPOH
    /#20158412 / +1

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

    У меня у одного получается 12 умножений?

    • speshuric
      /#20158820

      9 умножений «одноциферных». Вызовы умножений двуциферных не надо считать.

      • MOPOH
        /#20161834

        image

        • mayorovp
          /#20162100

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

          • MOPOH
            /#20162282

            Спасибо, разобрался.

  18. saboteur_kiev
    /#20160720 / +1

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


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

    • mapron
      /#20163298

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

  19. lynxus
    /#20160914 / -1

    если моему алгу нужно много умножений, то я, возможно, просто хочу перейти в логарифмы

  20. ShlackBaum
    /#20160916

    А нейросети нельзя привлечь для поиска более совершенных алгоритмов перемножения/деления?

    • MikailBag
      /#20162280

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

      • ShlackBaum
        /#20162322

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

        • Wizard_of_light
          /#20165780

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

          • KvanTTT
            /#20166162

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

  21. zzoraxz
    /#20160922

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

    • wataru
      /#20160952 / +2

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

  22. fouxer
    /#20160932

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

    • mayorovp
      /#20161094

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

  23. seohands
    /#20160934

    Не нашел в сети информации о родителях Анатолия Алексеевича Карацубы — может кто-то поделиться ссылкой или данными?

  24. mastiff
    /#20162582

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

    • Zenitchik
      /#20162826

      Скорее графическое представление умножения на палочках Непера.

    • lany
      /#20164466

      Ну а что, «Карацуба» звучит вполне по-японски.

  25. McAaron
    /#20163034

    Карацюба, ШШ, и еще несколько методов умножения целых произвольной точности подробно описаны во втором томе «Получисленные алгоритмы» трехтомника Д. Кнута «Искусство програмирования для ЭВМ».
    Там же разжеван алгоритм умножения в RNS, который требует n умножений, где n — количество модулей в RNS-базисе.

  26. BubaVV
    /#20163508

    О, я придумал как считерить — надо перейти к системе счисления с большим основанием

    • speshuric
      /#20163708

      В .NET (структура BigInteger), в JDK (класс BigInteger), в V8 (тип BigInt) и в GNU MP (тип mpz_t) используется основание 2^32 (беззнаковое 32-битное целое). Написать arbitrary precision арифметику с большим основанием (напр. 2^64), наверное возможно (придётся использовать промежуточную 128-битную арифметику), но мне кажется, что на существующих процессорах весь выигрыш сожрётся затратами на обслуживание этой 128-битной арифметики. Ну и прощай переносимость, конечно.

      • mayorovp
        /#20164756

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


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

        • BigBeaver
          /#20164908

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

          • mayorovp
            /#20164992

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

            • BigBeaver
              /#20165988

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

              • mayorovp
                /#20166044

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

                • BigBeaver
                  /#20166826

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

                  • mayorovp
                    /#20166910

                    Мешают три вещи.

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

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

                    В-третьих, типа данных удвоенной разрядности (uint128) зачастую не существует.

                    • BigBeaver
                      /#20166940

                      Так этим компилятор занимается, а не программист. Ну и на вопрос я вам ответил.

                      • mayorovp
                        /#20166974

                        Занимается чем?

                        Длинную арифметику, почти во всех известных мне языках, пишут всё-таки программисты.

                        • BigBeaver
                          /#20167068

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

                          Вопрос у вас был без такой:

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

                          • mayorovp
                            /#20167192

                            Выбором того, каким ассемблерным кодоом реализовать выш код.

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


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

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


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

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


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

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

                            • BigBeaver
                              /#20167434 / -2

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

                              • khim
                                /#20167494

                                Можно так написать? Что-то мне подсказывает, что да.
                                Написать-то можно что угодно, только не забывайте что получится, а? Сходите, полюбуйтесь.

                                Почему в этой программе:
                                const int64_t a = 0x1000000000000000;
                                const int64_t b = 0x1000000000000000;
                                const __int128 c = a * b;
                                
                                переменная c равна нулю — нужно объяснять?

                                • BigBeaver
                                  /#20167906

                                  То есть, вы мне на слова «это вопрос к компилятору, а не командам языка» говорите свое везкое «нет», а в качестве пруфа приводите выдачу конкретного компилятора. Серьезно?

                                  При этом вы почему-то забыли сказать, что компилятор знает о проблеме и вас предупреждает:

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

                                  • khim
                                    /#20168000

                                    То есть, вы мне на слова «это вопрос к компилятору, а не командам языка» говорите свое везкое «нет», а в качестве пруфа приводите выдачу конкретного компилятора. Серьезно?
                                    Абсолютно. Если вы считаете, что этот компилятор не годится — можете найти другой. Их там много. Но не получится. Потому что не в компиляторах дело.

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

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

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

                                    • Zenitchik
                                      /#20168100

                                      Никак.

                                      А если оператор перегрузить?

                                      • khim
                                        /#20168136

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

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

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

                                        В принципе с этим можно жить (если не забывать про -Og), но это всё равно — хождение по минному полю…

                                    • BigBeaver
                                      /#20168190

                                      Потому что не в компиляторах дело.
                                      Тогда каким образом вывод компилятора что-то доказывает? Впрочем, я вполне допускаю, что могу тупить, но тогда почему бы вам нормально не написать ваше видние?!

                                      • khim
                                        /#20168250

                                        Впрочем, я вполне допускаю, что могу тупить, но тогда почему бы вам нормально не написать ваше видние?!
                                        Потому что любая дискуссия предполагает некоторый уровень владения предметом. Если мне сейчас придётся вам объяснять всё, что программисты проходят за пару лет обучения в ВУЗе — то наша дискуссия никогда не дойдёт до сути вопроса.

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

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

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

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

                                      • khim
                                        /#20168284

                                        Вот, для сравнения, пример на 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 я мог бы показать вам это… если бы был хоть какой-то шанс того, что вы бы поняли этот пример.

                                        • BigBeaver
                                          /#20168380

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

                                          • khim
                                            /#20168398

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

                                            А дальше — можно это значение засовывать уже куда угодно, хоть в 128-битную переменную, хоть в 256-битную, это уже ничего не изменит…

                                            • BigBeaver
                                              /#20168414

                                              Кстати, насчет специальных команд. Есть, вроде интринсики типа _mul128 или что-то такое (как вы правильно поняли, в норме я не имею дела с такими вещами, и на большинстве моих девайсов вся математика слишком толстая, и выход за пределы uchar является событием).

                                              • khim
                                                /#20168570

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

                                                • Refridgerator
                                                  /#20168932

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

                                            • Zenitchik
                                              /#20168470

                                              Объясните, на каком основании у выражения a*b должно быть значение того же типа, что и у a и b? Почему языки устроены таким странным образом?
                                              В нашей повседневной реальности я умножаю метр на метр и получаю квадратный метр. В любых расчётах тип сохраняется только при сложении и вычитании, а при других действиях — получается другой тип. А в языках программирования внезапно, ладно что иначе по умолчанию, но и в порядок привести нельзя.

                                              • khim
                                                /#20168618

                                                Ну это вам в историю математики стоит углубиться.

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

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

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

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

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

                                                • BigBeaver
                                                  /#20168638

                                                  В нашей повседневной реальности я умножаю метр на метр и получаю квадратный метр.
                                                  И про квадратные уравнения вы, конечно, ничего не слышали?
                                                  Если Х не безразмерный, то и константы не безразмерные (в отличие от числа пи). В физике всегда сохраняется размерность во всех уравнениях (есть даже техники поиска решений методом подгонки размерностей).

                                                  • khim
                                                    /#20168654

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

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

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

                                                    • Zenitchik
                                                      /#20168674

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

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

                                                      А если мне приходится складывать x + x^2 — это достаточная причина, что искать ошибку где-то в выводе формулы.

                                                      • khim
                                                        /#20168686

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

                                                        • BigBeaver
                                                          /#20168692

                                                          Там все размерности сходятся. Если размерность не сходится, то формула не имеет физического смысла.

                                                          Впрочем, вы правы, что к размеру переменных это имеет мало отношения, если имеет вообще.

                                                          • Zenitchik
                                                            /#20169752 / +1

                                                            К размеру переменных — не имеет.
                                                            Но противоречит утверждению khim о том, что у результата умножения концептуально должен быть тот же тип, что и у операндов.

                                                            • khim
                                                              /#20170880 / +2

                                                              Не надо тянуть сову на глобус, пожалуйста. Ей больно.

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

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

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

                                            • BigBeaver
                                              /#20168574

                                              Кстати, если дело в этом, то почему uint16_t=uint8_t*uint8_t работает (в том числе для AVR, откуда я исходно взял свой пример) так, как этого описал я?

                                              • khim
                                                /#20168588

                                                Потому что uin16_t имеет размер меньше, чем int, однако.

                                                • BigBeaver
                                                  /#20168606 / +1

                                                  Как это согласуется с утверждением выше?

                                                  у выражения a*b есть значение — и оно имеет тот же тип, что a или b
                                                  Ну а размер int архитектурно зависим.

                                                  • khim
                                                    /#20168644

                                                    Как это согласуется с утверждением выше?
                                                    у выражения 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хбитный), согласитесь?

                                                    • BigBeaver
                                                      /#20168688

                                                      если типы меньше, чем int — то они приводятся в int, перед тем, как что-то считать
                                                      Даже если int больше размера регистров АЛУ (да и других, впрочем)?

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

                                                      • khim
                                                        /#20168732

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

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

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

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

                                                        Я уже приводил пример языка, где оператор умножения с порождением результата двойного размера имеется. Если бы наша современная IT-индустрия бы развивалась на его базе, а не на базе C — у нас много чего было бы по-другому. Но поскольку C оказался в основе всего, с чем мы работаем — то и Pascal и C++ и Java и многое-многое другое — работают так же…

                                                        • BigBeaver
                                                          /#20169280

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

                                                          • khim
                                                            /#20170856

                                                            Разве это противоречит стандарту?
                                                            Противоречит. Вы можете иметь в программе какой угодно int, но он должен быть един для всей программы. Никаких модулей стандарты C и C++ не предусматривают (С++20, возможно, предусмотрит, но вряд ли там будет разрешено иметь в разных модулях разные intы).

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

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

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

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

                                                            оптимальную 8-битную математику с 16 битным int?
                                                            За счёт того, что большинство существующих компиляторов — оптимизирующие. И некоторые оптимизации вообще неотключаемые. Но гарантий никаких нет — см. пример выше.

                                                            • BigBeaver
                                                              /#20170924

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

                                                              Не надо сказок, пожалуйста: если вы умножаете 8-битное число на 8-битное — то они сначала расширяются до 32-бит, потом обрезаются обратно в 8.
                                                              Это на х86-64. На Avr ничего такого не происходит, при этом дефолтный размер int там 16 бит, если не указать руками иное.

                                                              • khim
                                                                /#20170948

                                                                Разве я не могу собрать разные исходные файлы, используя разный int, а потом слинковать все вместе? С чужими же elf'ами могу.
                                                                Собрать-то вы можете… а вот будет ли подобный франкенштейн работать — это уже большой вопрос, на который ни разработчики стандарта C, ни разработчики компилятора вам не ответят. Вряд ли можно рекомендовать использовать, без самой крайней нужды, что-то, работоспособность чего зависит от цены на папайю в Гонолулу.

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

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

                                                                • BigBeaver
                                                                  /#20171034

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

                                                                  Ну значит вам везёт и компилятор, которым вы пользуетесь
                                                                  Обычный avr-gcc. Он там есть на godbolt. И я думаю, что все avr компиляторы должны так работать. Иначе просто нет смысла. Вот у вас есть килобайт флэша и 64 байта оперативной памяти, а компилятор такой раз и все удвоил, дополнив нулями.
                                                                  Мы ведь тут обсуждаем не конкретный компилятор, а язык
                                                                  Ну мой изначальный пойнт был в том, что почему бы компилятору это не делать, и что я как минимум знаю случаи, когда (2N) = (N)*(N) работает. В ответ на что вы меня зачморили, закидав примерами, о работоспособности которых я ничего не утверждал.

                                                                  Еще раз. Я согласен, что не блещу знаниями стандарта, но я привел пример рабочего платформоспецифичного кода. Выш запрос на int128=int64*int64 в одну инструкцию тоже платформоспецифичен. Так вот, почему бы компилятору бы аналогичным образом его не решить, м?

                                                                  • khim
                                                                    /#20171296

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

                                                                    А любая ваша попытка обратиться к разработчкам компилятора за помощью вызовет реакцию в духе «вы линкуете модули с разными размерами int? у-ти как клёво… ну что ж — это весело, а главное: как же хорошо, что ваши проблемы — это не наши проблемы».
                                                                    Вот у вас есть килобайт флэша и 64 байта оперативной памяти, а компилятор такой раз и все удвоил, дополнив нулями.
                                                                    Имеет право, тем не менее.

                                                                    Ну мой изначальный пойнт был в том, что почему бы компилятору это не делать,
                                                                    Потому что это прямо запрещено спецификацией языка.

                                                                    и что я как минимум знаю случаи, когда (2N) = (N)*(N) работает.
                                                                    Вот только в вашем случае было не (2N) = (N)*(N). У вас было (2N) = (2N)*(2N). Которые компилятор смоге превратить, в конкретном случае, в (2N) = (N)*(N). За что ему, конечно, честь и хвала — вот только эта оптимизация не гарантируется. А значит если вы всё и везде будете вычислять в (2N) — то можете получить проблемы.

                                                                    Выш запрос на int128=int64*int64 в одну инструкцию тоже платформоспецифичен. Так вот, почему бы компилятору бы аналогичным образом его не решить, м?
                                                                    Потому что 128-битный int — это, во-первых, неудобно, а во-вторых — это всё равно не даёт вам вожделённой инструкции int128=int64*int64.

                                                                    • BigBeaver
                                                                      /#20171428

                                                                      Вот только в вашем случае было не (2N) = (N)*(N). У вас было (2N) = (2N)*(2N). Которые компилятор смоге превратить, в конкретном случае, в (2N) = (N)*(N). За что ему, конечно, честь и хвала — вот только эта оптимизация не гарантируется.
                                                                      Потому что 128-битный int — это, во-первых, неудобно, а во-вторых — это всё равно не даёт вам вожделённой инструкции int128=int64*int64.
                                                                      В примере выше дает. Просто размеры другие. Вы сами сказали, что это на совисти компилятора, как

                                                                      • khim
                                                                        /#20171460

                                                                        В примере выше дает. Просто размеры другие.
                                                                        Нигде не даёт. Там везде одинаковые размеры у всех величин (но не всех переменных)

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

                                                                        Посмотрите на то, с чего мы начали:
                                                                        В известных мне языках нет операции, которая бы из двух чисел размера N бит делала их произведение размера 2N бит.
                                                                        В ваших примерах — её тоже нет.

                                                                        Про то, что можно свести явно задачу к умножению 128-битных чисел и помолиться на то, чтобы компилятор не передумал — я писал давным-давно.

                                                                        Вот только «помолиться на то, чтобы компилятор не передумал» — это проблема. А вдруг передумает? Имеет право.

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

                              • khim
                                /#20168108 / +1

                                Потому, что вы просите какую-то отдельную операцию вместо обычного символа умножения. вместо того чтобы написать код
                                uint64 a, b;
                                uint128 c;
                                ....
                                c=a*b;
                                
                                Можно так написать? Что-то мне подсказывает, что да.
                                У меня есть ощущение, что вы действительно не понимаете насколько глубока кроличья нора. Давайте я ваш пример доведу до полной, компилирующейся, программы:
                                #include <inttypes.h>
                                #include <stdio.h>
                                
                                int main() {
                                  uint64_t a, b;
                                  unsigned __int128 c;
                                  scanf("%" PRId64, &a);
                                  scanf("%" PRId64, &b);
                                  c=a*b;
                                  if (c==0) {
                                    printf(
                                      "%" PRId64 " multipliziert mit %" PRId64
                                      " ist ZERO.\nDas ist fantastisch!\n", a, b);
                                  }
                                }
                                Теперь, если вы это запустите — то вы получите следующее:

                                4294967296 multipliziert mit 4294967296 ist ZERO.
                                Das ist fantastisch!
                                

                                Компилятор может применять какие угодно инструкции и делать с ними что угодно, но если произведение 4294967296 на 4294967296 не даст в ответе нуль — это плохой, негодный компилятор.

                                И ровно так устроен не только C, но и большинство популярных языков программирования. Python так не устроен, например, но там просто типов, аналогичных uint64 и uint128 нету, потому ваш пример переписать на python просто не получится…

  27. netch80
    /#20163664 / +1

    Ну вот странно, что сравнивают с методом Карацубы, а не Тоома-Кука.
    Последний требует O(n^(1+?)), и это ? можно уменьшать как угодно (ценой роста коэффициента), и по сравнению с O(n*log(n)) это по-прежнему несравнимо. Хотя на практике переходят к Ш-Ш на числах от нескольких десятков килобит…

  28. HabrArkady
    /#20171176

    Этот метод (а также методы Шенхаге-Штрассена и Фюрера) работает с двоичными кодом. Поэтому на практике эти методы не дают практически никакого выигрыша в скорости.
    Мы же все работаем в десятичной системе, это компьютер работает с двоичным кодом. Если мы вводим какие-нибудь 2 числа, например 1,000,000 и 35,000,000, и хотим их перемножить, то сначала их необходимо преобразовать в двоичный код (многократно разделив на 256 и сохранив остатки как char(byte), что увеличить память). Далее из каждого байта Вам необходимо вытаскивать биты, что оказывается не такой уж быстрой операцией. И только после этого возможно применение данных методов. Где выигрыш? Кстати далеко не во всех языках программирования возможны операции с битами. Можно, конечно, попробовать брать байты непосредственно из памяти, но…. Эти точки обозначают и вопросы, и проблемы, и многое другое.
    HabrArkady