Разбивая крупные числа на мелкие, исследователи превысили фундаментальное математическое ограничение скорости
Четыре тысячи лет назад жители Вавилонии изобрели умножение. А в марте этого года математики усовершенствовали его.
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)
Radiohead72
15.05.2019 11:08В далеком детстве, я научился в уме извлекать кубические корни из шестизначных чисел)))
mikevmk
15.05.2019 11:48+6… а, также, расставлять, избыточные, знаки, препинания))))))))
Radiohead72
15.05.2019 14:22-2С возрастом перестал обращать внимание на такие мелочи как знаки препинания и прочие правила грамматики)
Раз смысл ясен — то к чему все эти условности? )))))
danfe
15.05.2019 14:55+2Смысл ясен вам как автору; стороннему читателю такие мелочи как знаки препинания и прочие правила грамматики помогают намного быстрее читать и понимать текст, «парсинг» же контекста обычно медленнее, требует больше умственных затрат и нередко дает сбои, предложение (а то и фразу целиком) приходится перечитывать.
Недавно я пару секунд тупил над фразой «А ещё велики лодки и пиво» — как пиво может быть велико? (ну ладно лодки еще), хотя речь шла о велосипедах, что, однако, мне было совсем не так очевидно, как автору сообщения.
Halt
15.05.2019 18:04Недавно я пару секунд тупил над фразой «А ещё велики лодки и пиво» — как пиво может быть велико? (ну ладно лодки еще), хотя речь шла о велосипедах, что, однако, мне было совсем не так очевидно, как автору сообщения.
Если вам интересно, существует даже целая тема, посвященная подобным предложениям. По ним даже проводились исследования того, как люди их парсят и как разрешают конфликты.
mkovalevskyi
15.05.2019 21:14Насколько я помню, основные техники скорочтения — как раз в игнорировании лишнего и понимании только нужного )
extempl
16.05.2019 09:32Вы немного о другом говорите. Вот есть слепые люди. Есть голосовые помощники, которые помогают им (при должной тренировке) ориентироваться при пользовании компьютером. Эти вот говорилки говорят с наиболее оптимальной скоростью с точки зрения возможности восприятия и затрат по времени. Возможности, но не удобства. Такое себе скорослушание.
Так вот нюанс в том, что если послушать обычным людям такую говорилку — не будет понятно абсолютно ничего (ну очень быстро).
Так и тут, знаки препинания и правила правописания помогают понимать текст абсолютному большинству.
P.S. Эволюционно так сложилось, что людям неудобно говорить быстро. А оттого и нет смысла учиться "быстро слушать". Только в экстренных случаях.
P.P.S. А ещё, это мне напомнило 1984, где лишние слова за ненадобностью выбрасывали из языка, потому что их можно было уже выразить другими словами/набором слов. Или сокращали.
BigBeaver
16.05.2019 12:23Попытка проскорочитать текст, который невозможно однозначно интерретировать без запятых, приведет либо к нивелированию скорочтения до обычного либо к фатальным потерям данных. Зарятые являются«лишним усложнением» только на очевидных паттернах.
Ну и паттерны эти субьектозависимы. Так что мозг сам должен решать, какие детали игнорировать.
User2Qwer
16.05.2019 20:54Насколько я помню, основные техники скорочтения — как раз в игнорировании лишнего и понимании только нужного )
Nidere
15.05.2019 15:10С ещё большим возрастом перестанете обращать внимание на такие мелочи, как не писаться в штаны, да?
К чему все эти условности, право…
Vnuchok
16.05.2019 23:23да? Мне один знакомый пишет без знаков вопроса и любое его вопросительное предложение выглядит как приказ. «Ты сделаешь завтра отчёт», например.
stalactite
18.05.2019 09:47Ох, это Хабр, тут заклюют за любую мелочь, которую посчитают нужной в конкретный момент, в конкретной тематике. Просто на ровном месте заминусовали коммент и карму. А потом они еще говорят про какую-то демократию тут, про то, что не вытесняют неугодных с ресурса. И, да, этот коммент тоже заминусуют, будьте уверенны. Это же так просто: анонимно нажать на минус и сидеть гордиться этим весь остаток дня.
KvanTTT
18.05.2019 12:13+2Нет на Хабре такого. Было исследование, которое показало, что плюсуют больше, чем минусуют. А минусуют походу тех, для кого карма и рейтинг играет какое-то особое значение.
BigBeaver
18.05.2019 12:33+1анонимно нажать на минус и сидеть гордиться этим весь остаток дня.
Человек с правом голоса имеет их не менее 10 в день. Достаточно гордиться каждым всего минут по 40 чтобы день прошел хорошо.
unC0Rr
15.05.2019 11:48С какой точностью?
Radiohead72
15.05.2019 14:15-1А я помню? :-)
Это было тааааак давноооо…
Прочел книгу емнип «Система быстрого счета по Трахтенбергу» и запомнил формулу которая позволяла в уме вычислять эти кубические корни. Но только кубические и только из шестизнаков)
Теперь уж и не помню ее. Формулу в смысле.
sielover
15.05.2019 21:20Ну здесь имеется ввиду вычисление кубического корня из числа, которое является кубом целого. Кубический корень из шестизначного — это число двузначное, надо лишь оценить первую цифру результата, сравнив первые три цифры шестизначного числа с 125, 216, 343 и 512, а вторая цифра результата определяется по последней цифре шестизначного числа (там однозначное соответствие).
Aprilfire
16.05.2019 13:47Скорее всего, это «по кубу двузначного числа определить само число», работает только для точных кубов. Алгоритм гуглится по «кубический корень в уме», но вкратце — по последней цифре куба однозначно определяем последнюю цифру исходного числа, дальше отбрасываем последние три цифры, по оставшимся определяем первую цифру исходного числа (ищем ближайший куб, который меньше того, что осталось). Надо только помнить таблицу кубов от 1 до 9.
AVX
15.05.2019 11:30Что-то я не понял. Всегда считал, что умножение в двоичной системе делается быстрее всего — там операций совсем мало и они крайне быстрые — сдвиг и сложение. (сдвигаем на один бит — получаем умножение на 2, или деление, если наоборот). Так что методов можно много напридумывать, но в двоичной системе (в которой почти все компьютеры работают) всё равно будет тот самый метод со сдвигом. Так что это всё скорее применимо к «человекочитаемым» способам умножения, нежели к процессорным. Поправьте меня, если я заблуждаюсь.
farafonoff
15.05.2019 11:36Сдвиг и сложение — это и есть «столбиком». Сложение это n операций, и потребуется ровно n сдвигов. Приведенные алгоритмы — асимптотически лучше.
GCU
15.05.2019 12:05Это смотря как считать что лучше. Многие операции можно выполнять параллельно/одновременно, и хотя суммарное число операций при этом будет больше, по времени это будет быстрее.
AVI-crak
15.05.2019 17:21farafonoff
В процессоре не столбиком, там вообще нет отдельной операции сдвига, линии данных до сумматоров уже разведены в железе. Операции сложения выполняются параллельно со всеми разрядами множимого, а чуть позже и со всеми промежуточными вариантами. Без разделения операций на отдельные такты — тут работают защёлки. Они-же предназначены для запоминания промежуточных вычислений и коммутации данных со сдвигом.
В результате умножение целого 32б на 32б с результатом в 64б — требует срабатывания пяти защёлок, и в целом операция умножения успевает выполниться за один такт.
С плавучкой немного сложнее, но даже там операции над всеми разрядами данных выполняются параллельно.
То-есть используется тот самый способ из статьи автора, но в двоичном варианте. Я думаю что «открытие» произошло по причине прогресса. Сейчас уже трудно найти человека что будет самостоятельно проектировать модуль умножения для ядра процессора, зачем — когда есть готовая библиотека… Из-за чего и встречаются подобные проколы.farafonoff
15.05.2019 17:38Если всё так как ты описал — часть сложности перенесена в железо. Т.е. вместо линейного количества времени тебе нужно линейную площадь кристалла. Это всё равно не позволяет выйти за границу асимптотической оценки. Попробуй представить умножение двух чисел длиной в гигабайт.
AVI-crak
16.05.2019 04:59Попробуй представить умножение двух чисел длиной в гигабайт.
А зачем представлять, если есть библиотека которую можно посмотреть.
Очень большие и жирные числа всегда в десятичной системе. Не потому что удобно, а от того что перевод из двоичного представления в десятичное — будет слишком долгим. К тому-же математики помешаны на магии десятичной системы, у них это почти религия.
Дык вот, в свободной мат. библиотеке разбивка чисел уже работает, задолго до этого открытия.
Просто программисты забыли предупредить об этом местных светил математики.farafonoff
16.05.2019 09:48Последний раз повторяю. Посмотри например сюда:
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
15.05.2019 20:15+2В результате умножение целого 32б на 32б с результатом в 64б — требует срабатывания пяти защёлок, и в целом операция умножения успевает выполниться за один такт.
Не успевает. Откройте табличку, да посмотрите. Даже Ryzen и Skylake-X требуют для этого 3-4 такта, на более старых процессорах — больше. Да, это не 30-40 тактов, как для деления, но и не один такт. Просто потому что если реализовать ваше предложение — то придётся снижать частоту, а тогда и другие операции медленнее станут.
С плавучкой немного сложнее, но даже там операции над всеми разрядами данных выполняются параллельно.
Та же самая история: никто не будет пихать такой большой мультипликатор в процессор. По уже описанной причине. Впрочем как раз для плавучки ваше утверждение верно — но не потому, что умножение занимает один такт, а потому что там даже сложение в один такт «не вписывается» — и занимает те же 3-4 такта, что и умножение.
Парадоксы современного процессоростроения…BigBeaver
16.05.2019 01:49Тем не менее, всякие девайсы с «Single-cycle multiply and accumulate (MAC) instructions» не редкость. Или я туплю, и это не то?
Zenitchik
16.05.2019 12:54Если я правильно понял предмет спора, произошла терминологическая путаница.
Single-cycle
Скорее всего имеется в виду машинный цикл, который состоит из нескольких тактов задающего генератора (на известных мне микроконтроллерах — 4).BigBeaver
16.05.2019 13:30А это важно вообще? // я лет 10 не копался в этой теме и уже порядком плаваю.
Насколько я могу судить, работа отдельных модулей на частоте повышенной или пониженной относительно того, что мы называем частотой ядра, это норма. При этом частота ядра это, по сути, частота адресного генератора (если упрощенно смотреть). Не?
И если у нас все инструкции single-cycle, то мы получаем константное время выполнения кода. Во всяких специализированных сигнальниках могут вообще дикие вещи за 1 такт делаться. Ну то есть, я не понимаю смысла говорить о еще более низком подуровне.Zenitchik
16.05.2019 15:16Может и не важно. Я сам — нуб в схемотехнике. Только знаю, что иногда встречаются отдельные граждане, которые цепляются за разницу между машинным циклом (за который процессор выполняет простые команды) и тактом рабочей частоты.
BigBeaver
16.05.2019 15:29Ну… в любом случае это все сильно архитектурнозависимые вещи. А выше они так спорят, как будто бы за этим всем стоят какие-то фундоментальные законы.
khim
16.05.2019 18:51А за этим и стоят фундаментальные законы. Подумайте вот над чем: отдельные рекордные транзисторы работают на частотах в сотни гигигерц. Беглый поиск приводит к 798 GHz, правда в SiGe, но даже транзисторы в ваших процессорах на 200-300GHz способны… а процессор в целом — даже 10GHz «не делает» и даже на этой частоте ему нужны 3-4 такта для умножение и десятки — да деление.
Так-то Verilog позволяет «нарисовать» схему, которая любое конечное вычисление в один такт сделает… но почему-то так никто не делает. Что-то же должно являться причиной?
Подумайте над этим…BigBeaver
16.05.2019 19:56Эмм. Фундоментальные ограничения на чустоту электроники, как таковой, не особо противоречат моим словам.
khim
16.05.2019 20:36Фундаментальные ограничения не дают вам сделать железку, работающую на частоте в терагерц. А также сделать железку, выполняющую сложение за то же время, что и умножение. Это всё фундаментальные вещи.
Но вот будете ли вы выносить на архитектурный уровень тот факт, что умножение, всё-таки, сложнее умножения — это другой вопрос: вы не можете ускорить умножение до скорости сложения, но вы можете замедлить сложение… а можете «более простое» сложение «встроить в умножение» (откуда и получается MAC — инструкция: она выполняется за то же время, что и умножение и позволяет, часто, экономить на сложении).
khim
16.05.2019 18:23Это так — но не в CPU. Самые «монстрачие» устройства, которые могут делать много-много умножений и сложений — это GPU. Однако какая-нибудь T4 Tesla за две штуки баксов всё равно имеют частоту максимум в 1.5GHz (это турбо буст режим, обычно меньше). А процессоры — редко имеют турбо-буст частоту ниже 3GHz, некоторые уходят до 5GHz.
Однотактовый умножитель на ширину «32бита» оказывается тупо слишком большим, чтобы на этой частоте работать.DistortNeo
16.05.2019 19:37Тут всё упирается в энергопотребление. Производительность видеокарт в специализированных задачах минимум на порядок выше, чем CPU, но энергопотребление — примерно в 2 раза больше.
khim
16.05.2019 19:51Если вы работаете на частоте 1.5GHz, то современные технологии вам позволяют сделать однотактовый умножитель, а если на частоте 4.5GHz-5GHz — то уже нет. Вот через это — вы не перепрыгните. Это фундаментальное ограничение. А почему какие-то чипы вы будете делать под 1.5GHz, какие-то под 4GHz, а какие-то — и под 10MHz — это уже другой вопрос.
AVI-crak
16.05.2019 05:19-1Не успевает. Откройте табличку, да посмотрите.
А это вы за границы модуля умножения вышли, причём очень далеко. х86 работает с памятью, ему сначала нужно эти числа загрузить в мат. процессор, а потом выгрузить. На всё это тратятся дополнительные такты ожидания.
К тому-же модуль умножения не является изолированным куском кремния, он способен выполнять намного больше вторичных функций. Всё это достигается внутренней коммутацией, часть в железном исполнении, часть в микрокоде.
Для arm ядер — этот узел похож на слипшийся комок макарон. Слишком многое в одном месте, без чёткого деления на площадь кремния. Там тоже есть такты ожидания, и они тоже связаны с внешней шиной.
Чудес не бывает, разве что в фпга…khim
16.05.2019 18:54+1А это вы за границы модуля умножения вышли, причём очень далеко. х86 работает с памятью, ему сначала нужно эти числа загрузить в мат. процессор, а потом выгрузить. На всё это тратятся дополнительные такты ожидания.
Ага, конечно. Для умножения нам в память нужно сходить, а для сложения не нужно? Прудмайте какую-нибудь другую «отмазку», поправдоподобнее, пожалуйста.
Чудес не бывает, разве что в фпга…
В FPGA тоже не бывает. Либо у вас сложение выполняется быстрее, чем умножение, либо вам приходится снижать тактовую частоту — других вариантов нет.
Ghost999
16.05.2019 13:47+2Одно дело — умножение чисел не превышающих разрядность ALU, и совершенно другое — умножение больших чисел. Для этого и существуют специальные алгоритмы.
wataru
15.05.2019 11:45+3Это когда у вас чиста маленькие. Когда надо перемножать 100500-битные числа, нужно делать 100500 сдвигов и складывать 100500/64 чисел каждый раз.
wataru
15.05.2019 11:53Я вот не совсем понимаю, почему наивный метод с FFT — это O(n logn log log n) вместо O(n log n). Откуда лишний log log n. Это из за того, что точности дабла не хватит при росте n и надо считать какие-то хитрые операции с длинными числами с плавающей точкой?
saluev
15.05.2019 22:19+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
16.05.2019 11:15А почему не работает так: разбить число на кусочки по 1 биту — это коэфициенты полинома. fft — O(n log n), перемножить значения — O(n), обратное fft — O(n log n). Никакой рекурсии. Всего O(n log n). Откуда тут еще log log n? Или этот алгоритм не работает для больших n?
farafonoff
16.05.2019 13:41Потому что перемножение будет n^2, а не n. Весь выигрыш происходит, когда мы делим на фиксированное количество частей (2).
wataru
16.05.2019 13:47Почему? Перемножение же почленное — ровно n операций (правда, с комплексными числами).
mayorovp
16.05.2019 14:15Потому что в процессе fft происходит куча сложений, из-за которых длина каждого элемента вырастает до O(log n) бит, а элементарное умножение начинает работать за O((log n)2). В итоге ваш метод даёт асимптотику O(n (log n)3), что явно больше чем O(n log n log log n)
nzamb1
16.05.2019 13:46-1Я так понимаю, что умножение это линейная свертка а преобразование фурье используется для быстрого подсчета цыклической свертки. Чтоб из цыклической свертки сделать линейную то циклическую нужно дополнить нулями чтоб получить линейную
vient
16.05.2019 13:46-1В двух словах, лишний log log n возникает, потому что считается битовая сложность, то есть сложность базовых операций типа сложения и умножения не равна 1, а зависит от битовой длины элементов. Здесь (2.3) объяснено подробнее.
Refridgerator
15.05.2019 12:01+2Почему в статье о новом революционном способе демонстрируется старый алгоритм Карацубы? Такое ощущение, что автор мало что понял из оригинальной работы и написал только то, что знал. Ну а сама оригинальная работа написана в классическом стиле от математиков для математиков — готового алгоритма, пригодного к реализации вы в ней не найдёте.
Например, в лемме 2.3 там доказывается convolution formula, согласно которой свёртка функций равносильна перемножению их Фурье-образов. Зачем? Это же известный, давно доказанный факт — можно было просто сослаться на доказательство, тем самым уменьшив объём работы.Jedi_PHP
15.05.2019 12:32hal.archives-ouvertes.fr/hal-02070778/document
вот, пожалуйста
Извините, в следующий раз я буду читать комментарий полностью. Но ссылку всё равно оставлю.Refridgerator
15.05.2019 12:37Что вы этим хотели сказать? Ссылка на эту работу есть в статье, я её уже посмотрел.
Jedi_PHP
15.05.2019 13:21Это дурная привычка сразу же отвечать только на первое предложение в прочитанном.
Извините. Но я работаю над собой.
avsmal
15.05.2019 23:36+1> Ну а сама оригинальная работа написана в классическом стиле от математиков для математиков — готового алгоритма, пригодного к реализации вы в ней не найдёте.
Не удивительно в общем, это ведь статья по математике — сомнительно, что полученный алгоритм будет иметь какое-то прикладное значение.
> Например, в лемме 2.3 там доказывается convolution formula, согласно которой свёртка функций равносильна перемножению их Фурье-образов. Зачем? Это же известный, давно доказанный факт — можно было просто сослаться на доказательство, тем самым уменьшив объём работы.
Это называется self-contained proof. Если какие-то уже известные результаты имеют простое доказательство, и их рассмотрение может добавить понимания, то их доказательство повторяется в статье.
questor
15.05.2019 12:20Можно наивный вопрос? Метод был предложен в 1960 году, он уже используется в современных ЭВМ? Если нет, то наверное есть какая-то объективная причина?
SLY_G Автор
15.05.2019 12:25Метод Шёнхаге-Штрассена используется компьютерами для умножения больших чисел
vitaliy2
15.05.2019 22:25+1Асимптотика показывает только зависимость от размера данных, и не показывает итоговое реальное время и так называемую «константу» перед асимптотикой. Например, O(10n) равно O(n). Константа «10» скрыта, т.?к. на очень больших числах (например, стремящихся к бесконечности) это всё-равно будет быстрее, чем, допустим, O(n1.000000001) без скрытой «10», а также потому, что константа может зависеть от реализации.
Но на практике мы работаем с числами ограниченного размера, и даже чаще всего с очень маленькими числами, и все эти константы очень сильно влияют на итоговое время. Поэтому чаще всего подходящий алгоритм выбирается в зависимости от размера входных данных, причём оптимальных алгоритмов может быть много на разных размерах. Также ещё можно посмотреть на энергоэффективность алгоритма и размер потребляемой памяти.
speshuric
16.05.2019 00:56Конечно используются. В JDK и .NET Core используется умножение Карацубы (в JDK 11 по умолчанию умножение переходит на Карацубу, если множители больше 2560 бит ). В JDK с множителей длины 7680 бит используется умножение Тоома-Кука.
defuz
16.05.2019 01:00Алгоритмы типа Штрассена имеют лучшую ассимптотическую характеристику, но добавляют значительные константные накладные расходы. Из-за этого их применение для маленьких размерностей (десятки-сотни бит) неоправдано. Для операций над небольшими числами в железе используются другие оптимизации, направленные в основном на ускорение получения результата путем избыточных операций, которые можно выполнять паралельно (методы быстрых переносов).
Но если вам нужно умножить действительно большие числа или, что более вероятно, умножить две больших матрицы, алгоритмы типа Штрассена могут дать кратный прирост производительности. Такие методы используются в специализированном железе.
netch80
16.05.2019 23:55Посмотрите на GMP. Там есть регулярно пересчитываемые для разных процессоров границы применения методов, чтобы функция сразу выбрала подходящий согласно длинам сомножителей.
Вот, например, для Zen серии в 64 битах при переходе меньшим сомножителем границы 22 лимба (лимб тут будет 64 бита => то есть длина 1408 бит) происходит переключение от «schoolbook» (квадратичное умножение всего на всё) к, чуть упрощая, методу Карацубы (записан как TOOM22; метод Карацубы является частным случаем Тоома-Кука; ТК это вообще не конкретный метод, а метаметод, который можно «заземлять» в неограниченное множество алгоритмов). Дальше до 460 лимбов (29440 бит) идут разные варианты ТК, но с этой границы включают Шонхаге-Штрассена.
Для других линий процессоров константы будут другими, но общая картина сохраняется где-то на том же уровне.
Более дорогие и тяжёлые методы вроде Фюрера там не применяются, видно, решили, что выделки не стоит (реально при таких свойствах процессоров он начал выигрывать бы где-то от миллиона бит).
infund
15.05.2019 13:04Теперь ждём, когда заново откроют сложение!
abar
15.05.2019 14:17Шутка «Если умножение так хорошо, то почему ещё не выпустили умножение 2» перестает работать.
dimonoid
15.05.2019 23:46Бинарное сложение с предрасчетом carry уже давно существует, работает за 1 такт.
Это выглядит ужасно, и занимает кучу места на кристалле. Особенно для длинных чисел. images.app.goo.gl/sibNc8JcZz4sJ7GC9
Таким же образом можно и умножать.
Bookvarenko
15.05.2019 13:52+1Отлично! Значит реймаршинг будет выполняться ещё быстрее. Немного прифигел от скромности ван дер Хувена: «Всё, на что мы можем надеяться, это на трёхкратное ускорение».
Refridgerator
15.05.2019 14:29+1Он говорит «надеяться», потому что математически обоснованное преимущество может сойти на нет (и даже в минус) за счёт накладных расходов при практической реализации. Подобный эффект наблюдается, в частности, при реализации быстрых алгоритмов Фурье — потому что помимо вычислений как таковых есть ещё операции чтения/записи/перемещения в памяти.
khim
15.05.2019 20:19Это не скромность. Попробуйте прикинуть при каком n у вас log log n «дорастёт» до десятки и подумайте — будут ли вас когда-нибудь волновать такие числа.
speshuric
16.05.2019 01:15+1Значит реймаршинг будет выполняться ещё быстрее.
А где там длинные числа? Все эти быстрые умножения (Карацуба и последующие) они про числа в тысячи бит.
legolegs
15.05.2019 14:04Умножение Карацубы выглядит как какая-то нумерология со сложением казалось бы не имеющих отношения к умножению цифр.
шутка про нумерологиюID поста 451860, сумма цифр 4+5+1+8+6+0=24, среднее между 2 и 4 = 3, Half Life 3 confirmed
solariserj
15.05.2019 14:22> Шутка про нумералогию
оффтоп, но напомнилоУмберто Эко (с) «Маятник Фуко»«Театральным жестом он распахнул ставни, предложил нам выглянуть и указал невдалеке, на углу между улочкой и бульварами, деревянный цветочный киоск.
— Господа, — сказал он. — Предлагаю вам самим отправиться и измерить эту будку. Вы увидите, что длина прилавка составляет 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
15.05.2019 16:33Вся нумерология пропадает если начать записывать формулы.
Допустим, у нас есть два числа, 10a+b и 10c+d. Тогда их произведением будет 100ac + 10(ad+bc) + db.
Заметим, что ad+bc = (a+b)(c+d) — ac — db.
defuz
16.05.2019 01:02+1Рекомендую вам изучить алгоритм Винограда для умножения матриц – вот где истинная нумерология. :)
Zenitchik
15.05.2019 14:51Почему для умножения Карацубы выбраны только примеры, где сложение не даёт переноса? Это слегка нечестно.
defuz
16.05.2019 01:05Потому что при сложении двух чисел с одинаковым количеством цифр у вас в худшем случае результат будет на одну цифру больше. Так что для действительно больших чисел этот перенос будет незначимым, поскольку будет выполнен всего на один разряд.
Если взять «неудачный» пример, то будет продемонстрировано как раз то, что метод Карацубы не дает приемущества в общем случае для небольших чисел.
basilbasilbasil
15.05.2019 15:17-1Все думают, что метод умножения, который они учили в школе, наилучший, °°°
Но на самом деле нужно изучать в школе fft
mozgoverflow
15.05.2019 15:35+1А вот и похожая статья тут была несколько лет назад habr.com/ru/post/262705
Num
15.05.2019 16:00+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.
Они придумали максимально быстрый на данный момент, без доказательства его идеальности. «Фундаментальное» ограничение скорости тоже под большим вопросом.
dimonoid
15.05.2019 19:20Мне кажется или O(xlog(x)log(logx)) быстрее O(x^1.46) для нового алгоритма при x выше 3300? Так какая у нового алгоритма сложность то?
speshuric
16.05.2019 01:03Так сравнивать нельзя: big-O же ничего не говорит про константы и про «менее быстро» растущие части функции.
0.0001*exp(x)-10000 — это всё равно O(exp(x))
100000*x+10000000*sqrt(x)+100000000000 — всё равно O(x)
saboteur_kiev
16.05.2019 13:17+1«Сложение в школе проходят на год раньше, потому что это гораздо проще, оно выполняется за линейное время, со скоростью чтения цифр слева направо»,
А кто может мне пояснить, почему слева направо, а не справа налево?
Сколько раз умножал столбиком, я делаю это справа налево, с переносом десятков в столбец слева.
mapron
16.05.2019 21:22вы цитируете сложение, а говорите про умножение. Это странно.
Я действительно когда складываю числа одной разрядности, делаю это обычно в порядке чтения; но в школе все же учат складывать справа налево, тут вы правы.
lynxus
16.05.2019 13:46-1если моему алгу нужно много умножений, то я, возможно, просто хочу перейти в логарифмы
speshuric
16.05.2019 22:56Это же не про плавающую точку. Как, например, вы найдёте в логарифмах первые 20 чисел Мерсенна?
ShlackBaum
16.05.2019 13:46А нейросети нельзя привлечь для поиска более совершенных алгоритмов перемножения/деления?
MikailBag
16.05.2019 17:43Нейронные сети плохо справляются с придумыванием алгоритмов кмк
ShlackBaum
16.05.2019 17:46Не придумывать, а «пробутфорсить» на совпадения.
Дать на вход множественные числа и «поле» для разбиения этих чисел так и эдак.
Сравнивать с заранее вычисленными итоговыми результатами на предмет верности того или ного случайного алгоритма. Может найдутся новые варианты и какие-то из них окажутся эффективными в каких-то контекстахWizard_of_light
17.05.2019 12:52Алгоритм трудно выковырять из нейросети, и он может оказаться быстрым, но неточным и/или неверным за пределами обучающей выборки. Да и в области выборки даже. А так может и найдётся что-нибудь типа 0x5F3759DF.
KvanTTT
17.05.2019 14:03"Быстрый обратный квадратный корень" — вообще-то частный случай. Так-то можно любые константы рассчитывать для операции степени от -1 до 1 с помощью математических методов и нейросети здесь не нужны.
zzoraxz
16.05.2019 13:47Может кто объяснить зачем перемножать два числа размером миллиард на миллиард с такой асимптотической сложностью, если цифр все-равно получится n^2 и столько же операций потратится на запись? Да и вообще где хранить результат этого произведения? Ведь понадобится 10^9 гигабайт памяти.
wataru
16.05.2019 13:51+2Цифр в ответе будет ~2n. 111*111 = 12321: 5 цифр а не 9. Даже со всеми переносами.
fouxer
16.05.2019 13:47Интересно существует ли такой способ:
1. первое число умножить на 1,2,3,4,...,9
2. потом полученные значения суммировать с добавлением нужного кол-ва нулей?mayorovp
16.05.2019 14:19Существует. Но это просто чуть оптимизированный "столбик", у него такая же квадратная асимптотика.
seohands
16.05.2019 13:47Не нашел в сети информации о родителях Анатолия Алексеевича Карацубы — может кто-то поделиться ссылкой или данными?
mastiff
16.05.2019 18:33Благодаря статье узнал что то, что на развлекательных сайтах называют «японским методом умножения чисел» (ну там где рисуют разноцветные линии и считают переcечения) по сути графическое представление умножения Карацубы.
McAaron
16.05.2019 20:10Карацюба, ШШ, и еще несколько методов умножения целых произвольной точности подробно описаны во втором томе «Получисленные алгоритмы» трехтомника Д. Кнута «Искусство програмирования для ЭВМ».
Там же разжеван алгоритм умножения в RNS, который требует n умножений, где n — количество модулей в RNS-базисе.
BubaVV
16.05.2019 22:17О, я придумал как считерить — надо перейти к системе счисления с большим основанием
speshuric
16.05.2019 23:40В .NET (структура BigInteger), в JDK (класс BigInteger), в V8 (тип BigInt) и в GNU MP (тип mpz_t) используется основание 2^32 (беззнаковое 32-битное целое). Написать arbitrary precision арифметику с большим основанием (напр. 2^64), наверное возможно (придётся использовать промежуточную 128-битную арифметику), но мне кажется, что на существующих процессорах весь выигрыш сожрётся затратами на обслуживание этой 128-битной арифметики. Ну и прощай переносимость, конечно.
mayorovp
17.05.2019 10:00Вообще говоря, современные процессоры умеют перемножать два 64-битных числа с получением 128-битного результата, так что арифметика с основанием 264 вполне достижима (и даже будет быстрее стандартной), если писать на ассемблере.
Проблема в том, что в языках программирования такой операции умножения обычно нет...
BigBeaver
17.05.2019 10:26Это разве не компилятор должен решать?
mayorovp
17.05.2019 10:44А что он может решить, когда нужной операции просто нет?
BigBeaver
17.05.2019 13:29В каком языке нет символа умножения? В каком языке высокого уровня вы руками выбираете конкретную реализацию умножения в зависимости от типа? Или как-то раскройте что ли мысль.
mayorovp
17.05.2019 13:41В известных мне языках нет операции, которая бы из двух чисел размера N бит делала их произведение размера 2N бит.
BigBeaver
17.05.2019 16:09Вообще-то, любое умножение дает сложение числа разрядов. Что вам мешает написать (uint16)=(uint8)*(uint8)? Как это обрабатывается процессором, зависит от целевой архитектуры и компилятора.
mayorovp
17.05.2019 16:22Мешают три вещи.
Во-первых, (uint64)*(uint64) дает на выходе uint64, которую бесполезно расширять далее до uint128.
Во-вторых, если предварительно привести операнды к более широкому типу, вылезет вторая проблема: полное умножение uint128 * uint128 — это вовсе не одна инструкция процессора, а компилятор не всегда замечает что старшая часть операндов — нулевая, и умножение можно сделать по короткой схеме. В итоге получается выгоднее использовать базу половинной разрядности.
В-третьих, типа данных удвоенной разрядности (uint128) зачастую не существует.BigBeaver
17.05.2019 16:25Так этим компилятор занимается, а не программист. Ну и на вопрос я вам ответил.
mayorovp
17.05.2019 16:31Занимается чем?
Длинную арифметику, почти во всех известных мне языках, пишут всё-таки программисты.BigBeaver
17.05.2019 16:44Выбором того, каким ассемблерным кодоом реализовать выш код.
Длинная арифметика — условное понятие. Для 8 битных AVR uint32 это длинная арифметика, но никто не пишет ее руками. Деления там вообще нет, но писать в коде "/" никто не запрещает, и компилятор может раскрыть это по-разному.
Вопрос у вас был без такой:нет операции, которая бы из двух чисел размера N бит делала их произведение размера 2N бит.
Я вам привел вполне релевантный пример. Вы же мне пример языка, где бы программист указывал, какую инструкцию процессора использовать, так и не показали.mayorovp
17.05.2019 17:08Выбором того, каким ассемблерным кодоом реализовать выш код.
Да, этим должен заниматься компилятор. Но это не помогает решить задачу получения оптимального кода.
Длинная арифметика — условное понятие.
Пожалуйста, вспомните в контекста какого поста она тут обсуждается.
Я вам привел вполне релевантный пример.
Ваш пример работает только в том случае, если в выбранном ЯП тип uint8 расширяется до более крупного перед умножением. А это не обязательно так. В каком-нибудь Си для 8-битных AVR запросто может быть int=short=char=int8.
Вы же мне пример языка, где бы программист указывал, какую инструкцию процессора использовать, так и не показали.
Такой язык программирования был назван в первом же комментарии: язык ассемблера. Языков высокого уровня с этим свойством, конечно же, нет, по определению языка высокого уровня. Не понимаю почему вы ожидаете какого-то другого ответа и как это вообще связано с использованием базы половинной разрядности.
BigBeaver
17.05.2019 17:48-2В каком-нибудь Си для 8-битных AVR запросто может быть int=short=char=int8.
Нет. Там int это uint16, как и в моем примере (собственно, откуда я его и взял). Даже для Attiny13, где вообще нет умножителя.язык ассемблера.
Высокоуровневый?Языков высокого уровня с этим свойством, конечно же, нет, по определению языка высокого уровня. Не понимаю почему вы ожидаете какого-то другого ответа и как это вообще связано с использованием базы половинной разрядности.
Потому, что вы просите какую-то отдельную операцию вместо обычного символа умножения. вместо того чтобы написать код
Можно так написать? Что-то мне подсказывает, что да. Должен ли программист руками решать, какие процессорные инструкции при этом выполнятся? Что-то подсказывает, что нет (иначе вы не соберете это на архитектуре, где этой инструкции нет).uint64 a, b; uint128 c; .... c=a*b;khim
17.05.2019 18:00Можно так написать? Что-то мне подсказывает, что да.
Написать-то можно что угодно, только не забывайте что получится, а? Сходите, полюбуйтесь.
Почему в этой программе:
переменнаяconst int64_t a = 0x1000000000000000; const int64_t b = 0x1000000000000000; const __int128 c = a * b;cравна нулю — нужно объяснять?BigBeaver
17.05.2019 19:59То есть, вы мне на слова «это вопрос к компилятору, а не командам языка» говорите свое везкое «нет», а в качестве пруфа приводите выдачу конкретного компилятора. Серьезно?
При этом вы почему-то забыли сказать, что компилятор знает о проблеме и вас предупреждает:
/example.cpp:9:22: warning: integer overflow in expression of type 'long int' results in '0'
При этом я вам не говорил, что мой пример нормально отрабоатет в си. Я сказал, что в языке есть все средства для записи. Вы же хотите какую-то отдельную команду. Вы можете нормально сказать, что конкретно вы хотите? Второй символ умножения или что?khim
17.05.2019 20:36То есть, вы мне на слова «это вопрос к компилятору, а не командам языка» говорите свое везкое «нет», а в качестве пруфа приводите выдачу конкретного компилятора. Серьезно?
Абсолютно. Если вы считаете, что этот компилятор не годится — можете найти другой. Их там много. Но не получится. Потому что не в компиляторах дело.
При этом я вам не говорил, что мой пример нормально отрабоатет в си. Я сказал, что в языке есть все средства для записи.
Это вообще что? У вас первое предложение противоречит второму, извините.
Второй символ умножения или что?
Как вариант. В Forth есть операцияM*— она как раз делает то, что требуется. Но в распространённых языках такой операции нет. Записать операцию «пермножить два 64-битных числа с получением 128-битного результата» там нельзя. В Forth — можно, а в C, Java, Pascal, да и вообще почти во всех распространённых языках — нельзя. Вот вообще нельзя. Никак.
При этом вы почему-то забыли сказать, что компилятор знает о проблеме и вас предупреждает
Хех. Вопрос «почему там предупреждение и почему оно исчезает если в примереint64_tнаuint64_tзаменить (хотя результат всё равно остаётся нулевым)» — это хороший вопрос на знание C, но он всё равно не помогает нам решить поставленную задачу… вы, кстати, знаете, почему заменаint64_tнаuint64_tубирает предупреждение? Или нет? Если нет — тогда вообще неясно о чём мы тут говорим…Zenitchik
17.05.2019 21:02Никак.
А если оператор перегрузить?khim
17.05.2019 21:12Нельзя перегрузить оператор для стандартных типов. C++ расширяем, но не изменяем.
Кроме того, непонятно чем перегрузка оператора поможет: если в языке не было конструкции, выражающейся через соответствующую инструкцию процессора — то откуда она в перегруженном операторе возьмётся?
Можно написатьc = (unsigned __int128)a * b;— но вот уже тут вы опираетесь на свойства конкретного компилятора и на тот факт, что он может понять, что в данном случае использование одиночногоmulq— безопасная оптимизация. Clang, скажем, «просекает фишку» всегда, а вот GCC — не всегда. Сравните (и посчитайте количествоmulqов иimulqов в сгенерированном коде).
В принципе с этим можно жить (если не забывать про -Og), но это всё равно — хождение по минному полю…
BigBeaver
17.05.2019 21:28Потому что не в компиляторах дело.
Тогда каким образом вывод компилятора что-то доказывает? Впрочем, я вполне допускаю, что могу тупить, но тогда почему бы вам нормально не написать ваше видние?!khim
17.05.2019 21:43Впрочем, я вполне допускаю, что могу тупить, но тогда почему бы вам нормально не написать ваше видние?!
Потому что любая дискуссия предполагает некоторый уровень владения предметом. Если мне сейчас придётся вам объяснять всё, что программисты проходят за пару лет обучения в ВУЗе — то наша дискуссия никогда не дойдёт до сути вопроса.
Моя отсылка — была простым тестом на понимание вами языка C и ассмеблера.
Тогда каким образом вывод компилятора что-то доказывает?
Подумайте. Подсказка: мной был специльно написано пример, дающий ноль байтов кода на выходе. Для того, чтобы исключить из обсуждения вопросы кодогенерации и прочих, не очень важных тут, вещей. А также заложена маленькая «пасхалочка» — вот с тем самым предупреждением о возможной ошибке.
Вы за неё уцепились, чем показали, что вы не понимаете не только как устроен компилятор C, но также и как устроен собственно язык С… а какой смысл обсуждать свойства языка C с человеком, который его не знает?
С тем же успехом мы могли бы обсуждать тонкости клингонского языка, к примеру.
khim
17.05.2019 21:54Вот, для сравнения, пример на 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
17.05.2019 22:19В общем, вы правы. Но я не вижу проблемы указать из какой конкретно особенности «устройства языка» следует, что это должно так работать.
khim
17.05.2019 22:26Это следуют просто-напросто из того факта, что у выражения
a*bесть значение — и оно имеет тот же тип, чтоaилиb, и, внезапно,int(в зависимости от того, какой трёх типов «шире»).
А дальше — можно это значение засовывать уже куда угодно, хоть в 128-битную переменную, хоть в 256-битную, это уже ничего не изменит…BigBeaver
17.05.2019 22:36Кстати, насчет специальных команд. Есть, вроде интринсики типа _mul128 или что-то такое (как вы правильно поняли, в норме я не имею дела с такими вещами, и на большинстве моих девайсов вся математика слишком толстая, и выход за пределы uchar является событием).
khim
17.05.2019 23:48Интринзики действительно есть — но для SIMD инструкций. Для обычных, удивительным образом, ничего не предусмотрено.
Refridgerator
18.05.2019 06:40Одна из причин, к слову, по которой при желании оптимизировать я предпочитаю писать на ассемблере целиком, а не использовать интринсики.
Zenitchik
17.05.2019 22:59Объясните, на каком основании у выражения a*b должно быть значение того же типа, что и у a и b? Почему языки устроены таким странным образом?
В нашей повседневной реальности я умножаю метр на метр и получаю квадратный метр. В любых расчётах тип сохраняется только при сложении и вычитании, а при других действиях — получается другой тип. А в языках программирования внезапно, ладно что иначе по умолчанию, но и в порядок привести нельзя.khim
18.05.2019 00:12Ну это вам в историю математики стоит углубиться.
В нашей повседневной реальности я умножаю метр на метр и получаю квадратный метр.
И про квадратные уравнения вы, конечно, ничего не слышали?
В любых расчётах тип сохраняется только при сложении и вычитании, а при других действиях — получается другой тип.
Ну это, всё-таки, не совсем так. Длина окружности и её радиус имеют одинаковый тип, что не мешает им быть связанными соотношениями L = 2?r.
Собственно соображения, подобные высказанным вами, и не позволили древним грекам и римлянам как следует развить баллистику. Ибо без квадратных уравнений в баллистике никак — а как вы его запишите без того, чтобыx?сложить сx?
Но в сегодняшнем мире люди, всё-таки, проходят квадратные уравнения в седьмом классе, так что, казалось бы, к моменту, когда человек добирается до Хабра для него это уже не должно быть проблемой…
Почему языки устроены таким странным образом?
Не только языки. Процессоры тоже. Да, у процессора, в отличие от языка C, есть инструкция, возвращающая «удвоенный» результат (8but * 8bit ? 16bit, 16bit * 16bit ? 32bit, 32bit * 32bit ? 64bit), в отличие от C, однако операция, сохраняющая размер — у него тоже есть… и она, в большинстве случаев, работает быстрее.BigBeaver
18.05.2019 00:24
Если Х не безразмерный, то и константы не безразмерные (в отличие от числа пи). В физике всегда сохраняется размерность во всех уравнениях (есть даже техники поиска решений методом подгонки размерностей).В нашей повседневной реальности я умножаю метр на метр и получаю квадратный метр.
И про квадратные уравнения вы, конечно, ничего не слышали?khim
18.05.2019 00:32В физике всегда сохраняется размерность во всех уравнениях (есть даже техники поиска решений методом подгонки размерностей).
Тем не менее даже в этих случаях могут быть много тонкостей, так как в физике полно размерных констант.
Тот факт, что в большинсво языков программирования всё это богатство не отражается — несколько прискорбен, но к выборуfloatdoubleили тамuint8_tuint64_tэто всё не имеет отношения.
Ситуация, когда вам хочется сменить базовый тип на практике, всё-таки, случаётся реже, чем когда у вас появляется другая размерность.Zenitchik
18.05.2019 00:44Тем не менее даже в этих случаях могут быть много тонкостей, так как в физике полно размерных констант.
Никаких тонкостей нет ИМЕННО благодаря размерным константам. Если не верите — приведите хоть один пример.
А если мне приходится складывать x + x^2 — это достаточная причина, что искать ошибку где-то в выводе формулы.khim
18.05.2019 00:51Да боже ж ты мой. Скорость удаления двух частиц, разлетающихся в разные стороны. Простейший пример, в школе изучают.
BigBeaver
18.05.2019 00:56Там все размерности сходятся. Если размерность не сходится, то формула не имеет физического смысла.
Впрочем, вы правы, что к размеру переменных это имеет мало отношения, если имеет вообще.Zenitchik
18.05.2019 14:26+1К размеру переменных — не имеет.
Но противоречит утверждению khim о том, что у результата умножения концептуально должен быть тот же тип, что и у операндов.khim
18.05.2019 21:42+2Не надо тянуть сову на глобус, пожалуйста. Ей больно.
Типы в понятии современных языков программирования — это не физические размерности, а, скорее, вот эти вот ?, ?, ? и прочие ?4294967296.
Все математические операции, если не сказано иного — в математике производятся в рамках одного подобного типа. И умножение и деление тоже.
А то, что «физические» типы в современных языках почти никак не представлены — это неприятно, но к обсуждаемому вопросу отношения не имеет. Эти типы всё равно, скорее всего, существовали бы только в исходниках, но не в скомпилированной программе.
BigBeaver
17.05.2019 23:51Кстати, если дело в этом, то почему uint16_t=uint8_t*uint8_t работает (в том числе для AVR, откуда я исходно взял свой пример) так, как этого описал я?
khim
17.05.2019 23:59Потому что uin16_t имеет размер меньше, чем int, однако.
BigBeaver
18.05.2019 00:06+1Как это согласуется с утверждением выше?
у выражения a*b есть значение — и оно имеет тот же тип, что a или b
Ну а размер int архитектурно зависим.khim
18.05.2019 00:26
А доцитировать до конца?Как это согласуется с утверждением выше?
у выражения 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
18.05.2019 00:54если типы меньше, чем int — то они приводятся в int, перед тем, как что-то считать
Даже если int больше размера регистров АЛУ (да и других, впрочем)?
Ну и смотрите, выше вы говорили, что это нечто принципиальное, а оказывается, просто наследие.khim
18.05.2019 01:19Даже если int больше размера регистров АЛУ (да и других, впрочем)?
Разумеется. Разработчик компилятора вправе сам решать — что там у него заint. Но если назвался — то всё должно считаться вint. Никаких АЛУ в стандарте нет.
Ну и смотрите, выше вы говорили, что это нечто принципиальное, а оказывается, просто наследие.
Где я говорил, что это фундаментальный закон физики?
Да, оно — «просто наследие». В той же степени, в какой вся наша цивилизация — это наследние людй, которые когда-то изобрели колесо. И теперь мы вынуждены строить дороги, мосты, тоннели и многое другое.
В какой-то другой цивилизации — могли бы, вместо этого, приручить гигантстких летучих мышей… и у них много чего могло бы быть по-другому. Но у нас нет гигантских летучих мышей — потому приходится общаться с тем, что есть.
Я уже приводил пример языка, где оператор умножения с порождением результата двойного размера имеется. Если бы наша современная IT-индустрия бы развивалась на его базе, а не на базе C — у нас много чего было бы по-другому. Но поскольку C оказался в основе всего, с чем мы работаем — то и Pascal и C++ и Java и многое-многое другое — работают так же…BigBeaver
18.05.2019 10:57Разработчик компилятора вправе сам решать — что там у него за int.
То есть, в итоге дело таки в компиляторе? Что принципиально мешает добавить какой-нибудь флаг типа -use128int (и собирать все тяжелые мат модули с ним)? Разве это противоречит стандарту?Никаких АЛУ в стандарте нет.
В получаемом ассемблере-то есть. Как мы получим (а мы ее получаем) оптимальную 8-битную математику с 16 битным int?khim
18.05.2019 21:34Разве это противоречит стандарту?
Противоречит. Вы можете иметь в программе какой угодноint, но он должен быть един для всей программы. Никаких модулей стандарты C и C++ не предусматривают (С++20, возможно, предусмотрит, но вряд ли там будет разрешено иметь в разных модулях разныеintы).
И вы тут, опять-таки, «никуда не соскочите»: если вы сделаете такой финт ушами, то у вас все вычисления станут int128?int128. Даже если когда вы байт на байт будете умножать — они будут сначала превращаться в int128, а потом уже перемножаться.
То есть, в итоге дело таки в компиляторе?
Конкретный размер — зависит от компилятора. Тот факт, что умножения, перемножающего два значения разных типов и возвращающих результат другого, более широкого типа — от компилятора не зависит.
От компилятора зависит только где проходит граница между «слишком маленькими» типами, использующимися только для экономии память и «большими» типами, которые могут участвовать в вычислениях. И всё.
Как мы получим (а мы ее получаем)
Это вы с -O0 её получаете? Не надо сказок, пожалуйста: если вы умножаете 8-битное число на 8-битное — то они сначала расширяются до 32-бит, потом обрезаются обратно в 8.
оптимальную 8-битную математику с 16 битным int?
За счёт того, что большинство существующих компиляторов — оптимизирующие. И некоторые оптимизации вообще неотключаемые. Но гарантий никаких нет — см. пример выше.BigBeaver
18.05.2019 22:01Разве я не могу собрать разные исходные файлы, используя разный int, а потом слинковать все вместе? С чужими же elf'ами могу.
Не надо сказок, пожалуйста: если вы умножаете 8-битное число на 8-битное — то они сначала расширяются до 32-бит, потом обрезаются обратно в 8.
Это на х86-64. На Avr ничего такого не происходит, при этом дефолтный размер int там 16 бит, если не указать руками иное.khim
18.05.2019 22:11Разве я не могу собрать разные исходные файлы, используя разный int, а потом слинковать все вместе? С чужими же elf'ами могу.
Собрать-то вы можете… а вот будет ли подобный франкенштейн работать — это уже большой вопрос, на который ни разработчики стандарта C, ни разработчики компилятора вам не ответят. Вряд ли можно рекомендовать использовать, без самой крайней нужды, что-то, работоспособность чего зависит от цены на папайю в Гонолулу.
На Avr ничего такого не происходит, при этом дефолтный размер int там 16 бит, если не указать руками иное.
Ну значит вам везёт и компилятор, которым вы пользуетесь не умеет эту оптимизацию отключать. Завтра может выйти другая версия — и она вполне может начать всё это делать неоптимально.
Мы ведь тут обсуждаем не конкретный компилятор, а язык, так что того факта, что так себя ведёт компилятор на x86-64 — вполне достаточно для иллюстрации.BigBeaver
18.05.2019 22:54Почему? В пределах каждой конкретной функции все будет единообразно. В чем вы видите проблему? Разве есть гарантия, что, например, все используемые библиотеки собраны с одинаковым значением int?
Ну значит вам везёт и компилятор, которым вы пользуетесь
Обычный avr-gcc. Он там есть на godbolt. И я думаю, что все avr компиляторы должны так работать. Иначе просто нет смысла. Вот у вас есть килобайт флэша и 64 байта оперативной памяти, а компилятор такой раз и все удвоил, дополнив нулями.Мы ведь тут обсуждаем не конкретный компилятор, а язык
Ну мой изначальный пойнт был в том, что почему бы компилятору это не делать, и что я как минимум знаю случаи, когда (2N) = (N)*(N) работает. В ответ на что вы меня зачморили, закидав примерами, о работоспособности которых я ничего не утверждал.
Еще раз. Я согласен, что не блещу знаниями стандарта, но я привел пример рабочего платформоспецифичного кода. Выш запрос на int128=int64*int64 в одну инструкцию тоже платформоспецифичен. Так вот, почему бы компилятору бы аналогичным образом его не решить, м?khim
19.05.2019 00:41Разве есть гарантия, что, например, все используемые библиотеки собраны с одинаковым значением 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
19.05.2019 01:51Вот только в вашем случае было не (2N) = (N)*(N). У вас было (2N) = (2N)*(2N). Которые компилятор смоге превратить, в конкретном случае, в (2N) = (N)*(N). За что ему, конечно, честь и хвала — вот только эта оптимизация не гарантируется.
Потому что 128-битный int — это, во-первых, неудобно, а во-вторых — это всё равно не даёт вам вожделённой инструкции int128=int64*int64.
В примере выше дает. Просто размеры другие. Вы сами сказали, что это на совисти компилятора, какkhim
19.05.2019 02:23В примере выше дает. Просто размеры другие.
Нигде не даёт. Там везде одинаковые размеры у всех величин (но не всех переменных)
Вы сами сказали, что это на совисти компилятора, как
На совести компилятора — возможность иногда разглядеть, что старшая половина числа — нулевая. И сделать соотвествующую оптимизацию. Он это делает не всегда, а тогда, когда ему это хочется.
Посмотрите на то, с чего мы начали:
В известных мне языках нет операции, которая бы из двух чисел размера N бит делала их произведение размера 2N бит.
В ваших примерах — её тоже нет.
Про то, что можно свести явно задачу к умножению 128-битных чисел и помолиться на то, чтобы компилятор не передумал — я писал давным-давно.
Вот только «помолиться на то, чтобы компилятор не передумал» — это проблема. А вдруг передумает? Имеет право.
Да и вообще — священник, который молится богу компиляторов — это явно не тот специалист, которого я хотел бы видеть в штате.
khim
17.05.2019 21:03+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 просто не получится…
netch80
16.05.2019 23:20+1Ну вот странно, что сравнивают с методом Карацубы, а не Тоома-Кука.
Последний требует O(n^(1+?)), и это ? можно уменьшать как угодно (ценой роста коэффициента), и по сравнению с O(n*log(n)) это по-прежнему несравнимо. Хотя на практике переходят к Ш-Ш на числах от нескольких десятков килобит…
HabrArkady
18.05.2019 23:57Этот метод (а также методы Шенхаге-Штрассена и Фюрера) работает с двоичными кодом. Поэтому на практике эти методы не дают практически никакого выигрыша в скорости.
Мы же все работаем в десятичной системе, это компьютер работает с двоичным кодом. Если мы вводим какие-нибудь 2 числа, например 1,000,000 и 35,000,000, и хотим их перемножить, то сначала их необходимо преобразовать в двоичный код (многократно разделив на 256 и сохранив остатки как char(byte), что увеличить память). Далее из каждого байта Вам необходимо вытаскивать биты, что оказывается не такой уж быстрой операцией. И только после этого возможно применение данных методов. Где выигрыш? Кстати далеко не во всех языках программирования возможны операции с битами. Можно, конечно, попробовать брать байты непосредственно из памяти, но…. Эти точки обозначают и вопросы, и проблемы, и многое другое.
HabrArkady
lingvo
Во первых так это как раз из-за того, что умножение было медленным и производительность компьютера упиралась в него. Поэтому разработчики процессоров в первую очередь пытались ускорить эту операцию. Если указанный в статье метод действительно работает и подходит для процессоров — это очень неплохо.
А во-вторых — кто сказал, что аппаратный умножитель не использует операции сложения? Внутри они там есть.
Кстати, а есть подвижки по алгоритмам деления больших чисел?
Alexeyslav
Вопрос скорости стоит менее остро, в конце концов есть же векторные инструкции… острее стоит вопрос энергетической эффективности. Ведь даже если умножение и выполняется по времени как сложение энергии тратится значительно больше. Так что смысл разменять умножение на сложение всё ещё остаётся, даже если дело не в скорости.
DarkTiger
DistortNeo
Почему же? Сравните потребление энергии процессором при выполнении векторных операций умножения по сравнению с остальными операциями: разница будет не доли процента, а чуть ли не разы.
DarkTiger
Сравните разницу при векторных умножении и сложении матриц. Разница будет именно что доли процентов. Малое потребление энергии в случае «остальных операций» (не векторных, как я понимаю) связано с недозагруженностью конвейера и пузырьками, ожиданием при операциях с памятью и прочим. В случае же векторных операций большинство соответствующих функциональных устройств будет загружено и будет потреблять энергию, предсказатели переходов не ошибаются, а нужных данных в кэше будет в несколько раз больше, ибо читаем-пишем-сбрасываем из оперативки в кэш и обратно по несколько единиц данных одновременно. И такая ситуация будет что на сложении, что на умножении.
DarkTiger
Можно, конечно, тестовое приложение написать и посмотреть, но тогда надо будет смотреть код с помощью ассемблера и выполнение при помощи профилировщика. Признаюсь честно — такой квалификацией не обладаю, у меня другая область
DistortNeo
Можно попробовать, а затем замерить потребление энергии через Intel Power Gadget.
DistortNeo
Попробовал написать код, который в несколько потоков складывает/умножает/
делит два вектора с помощью AVX. Реально потребление от операции не различается. Разница только в количестве операций доступа к памяти/кэшу.
Если молотить только регистры в цикле — будет 60 Вт, если читать-писать — около 95 Вт. При слишком большом размере вектора (не влезает в кэш) — снижается до 60-65 Вт.
potan
Векторные операции могут задействовать отдельный специализированный ALU, который в остальное время отключается. Тогда энергопотребление при использовании таких операций будет возрастать.
potan
Может в каких-то процессорах это и так, но в большинстве — одинаково.
Более того, когда процессор обнаруживает арифметическую операцию, он параллельно выполняет все поддержаные в ALU операции и декодирование кода операции, а на выходе по коду операции выбирается нужный результат.
Самое энергоемкое в процессоре — кеш-память. Не думаю, что на ее фоне кто-то решит оптимизировать арифметику.
khim
Вот только «тяжёлые рассчёта» сейчас делают на GPU — и там как раз арифметика даёт ощутимый такой вклад в энергопотребление…
NeocortexLab
«Тяжёлые рассчёта» делают на GPU когда надо сделать много маленьких расчётов параллельно. Современные GPU как-то не очень подходят для задач вроде описанных в статье — всё равно что свинью стричь — визгу много, шерсти нет
farafonoff
В статье описывались асимптоты алгоритма умножения, а скорость выполнения процессорных инструкций входит в константу при них. Очевидно, что если нужно умножить два числа в миллиарды знаков (байт, слов), то скорость будет зависеть как раз от экспоненты.
Деление в худшем случае можно переписать как умножение и двоичный поиск, соответственно худшая оценка для деления теперь — n*logn*logn.
wataru
Вот только двоичный поиск будет не log n, а n. Потому что в числе n знаков, значит надо делить интервал размером в 2^n.
Такое деление в итоге будет O(n^2 log n).
farafonoff
Точно, спасибо.
saluev
Делят, по крайней мере вещественные числа, обычно методом Ньютона, а у него квадратичная сходимость, то есть требуется логарифмическое число шагов. А сложность шага пропорциональна сложности умножения.
netch80
Вещественные числа давно уже делят, например, Голдшмидтом, и квадратный корень аналогично — с тех времён, как научились рассчитывать погрешность при таких вычислениях. Но в остальном — последствия такие же по сути, да, как для Ньютона (по ссылке — 1 цикл для single, 2 для double, 3 для extended).
potan
Был какой-то достаточно эффективные алгоритм аппроксимации 1/n, а деление делается через него.
khim
log log n растёт очень-очень-очень медленно. Даже если там миллиарды знаков — это будет что-то типа 5-6. А чтобы дорасти до 10 уже всех компьютеров мира не хватит.
Так что они правильно написали: теоретически — это дико круто, практически — отличие невелико…
dedalqq
А еще бы разложение на множители и прощай криптография =)
vokzamag
Квантовые компьютеры.
С одной стороны, уничтожат базу современной криптографии — сложность разложения на множители.
С другой стороны, вроде, на квантово-запутанных фотонах можно реализовать криптографию, которая гораздо гораздее, чем привычная.
Deerenaros
Не вроде, а точно. И не гораздее, а с физической невозможностью дешифровки без. Впрочем, у квантовой криптографии есть огромное число проблем и одна из основных — огромные требования к физической среде. К тому же, не смотря на физическую невозможность дешифровки без ключа сама её попытка приведёт так же к невозможности дешифровки и легальным пользователем. Даже больше — есть огромные проблемы с большими расстояними, а также с противодействием деструктивного воздействия условного противника.
Короче. Квантовая криптография это, конечно, интересно, но почти уверен, что она будет использоваться в очень узкой сфере требовательной к безусловной невозможности расшифровки и возможным попустительством в надёжности передачи. А я таких сфер сейчас почти и не знаю.
CryptoPirate
Квантовые компьютеры не уничтожат всю криптографию, только алгоритмы типа RSA и Diffie Hellman. У всей симметричной криптографии уполовинется степень защиты.
И ещё, есть так называемая «post-quantum» криптография, там шифрование основано на сложных проблемах не связанных со сложностью разложения на простые множители и дискретный логарифм. Прямо сейчас идет соревнование на стандарт подобного типа. Такие алгоритмы выполняются на обычных комптьютерах и квантовые компьютеры им не страшны.
potan
Не совсем. Большинство современных процессоров конвейерные, то есть умеют выполнять одновременно несколько операций, находящихся на разной стадии вычислений. Что бы конвейер работал, требуется что бы одна и та же стадия разных операций не перекрывались во времени. Для этого все операции в конвейере искусственно замедляют до самой медленной. Как правило, это умножение, а более медленные операции, если они есть, останавливают конвейер.
Daddy_Cool
Мы неплохо использовали операцию «быстрого обратного корня». Одно деление=перемножить два быстрых обратных корня. Получалось выгоднее. )
netch80
> Кстати, а есть подвижки по алгоритмам деления больших чисел?
Похоже, пока всё плохо. Если смотреть на GMP, по-прежнему основным рабочим методом остаётся итеративное деление на округлённый делитель, хотя его делают через обратное умножение, экономя на собственно процессорном делении.