Комментарии 224
Двадцать лет назад компьютеры выполняли сложение гораздо быстрее умножения. Разрыв в скоростях умножения и сложения с тех пор серьёзно уменьшился, в результате чего на некоторых чипах умножение может даже обгонять сложение.
Во первых так это как раз из-за того, что умножение было медленным и производительность компьютера упиралась в него. Поэтому разработчики процессоров в первую очередь пытались ускорить эту операцию. Если указанный в статье метод действительно работает и подходит для процессоров — это очень неплохо.
А во-вторых — кто сказал, что аппаратный умножитель не использует операции сложения? Внутри они там есть.
Кстати, а есть подвижки по алгоритмам деления больших чисел?
Вопрос скорости стоит менее остро, в конце концов есть же векторные инструкции… острее стоит вопрос энергетической эффективности. Ведь даже если умножение и выполняется по времени как сложение энергии тратится значительно больше. Так что смысл разменять умножение на сложение всё ещё остаётся, даже если дело не в скорости.
Ведь даже если умножение и выполняется по времени как сложение энергии тратится значительно большеНа фоне общего количества потребляющих энергию функциональных блоков в современном процессоре (особенно кэша) и количества обязательных операций, предшествующих умножению-сложению и следующих после него — полагаю, что отличие выражается в долях процента, даже если работать с большими матрицами
Почему же? Сравните потребление энергии процессором при выполнении векторных операций умножения по сравнению с остальными операциями: разница будет не доли процента, а чуть ли не разы.
Сравните разницу при векторных умножении и сложении матриц. Разница будет именно что доли процентов. Малое потребление энергии в случае «остальных операций» (не векторных, как я понимаю) связано с недозагруженностью конвейера и пузырьками, ожиданием при операциях с памятью и прочим. В случае же векторных операций большинство соответствующих функциональных устройств будет загружено и будет потреблять энергию, предсказатели переходов не ошибаются, а нужных данных в кэше будет в несколько раз больше, ибо читаем-пишем-сбрасываем из оперативки в кэш и обратно по несколько единиц данных одновременно. И такая ситуация будет что на сложении, что на умножении.
Можно, конечно, тестовое приложение написать и посмотреть, но тогда надо будет смотреть код с помощью ассемблера и выполнение при помощи профилировщика. Признаюсь честно — такой квалификацией не обладаю, у меня другая область
Можно попробовать, а затем замерить потребление энергии через Intel Power Gadget.
Попробовал написать код, который в несколько потоков складывает/умножает/
делит два вектора с помощью AVX. Реально потребление от операции не различается. Разница только в количестве операций доступа к памяти/кэшу.
Если молотить только регистры в цикле — будет 60 Вт, если читать-писать — около 95 Вт. При слишком большом размере вектора (не влезает в кэш) — снижается до 60-65 Вт.
Векторные операции могут задействовать отдельный специализированный ALU, который в остальное время отключается. Тогда энергопотребление при использовании таких операций будет возрастать.
Может в каких-то процессорах это и так, но в большинстве — одинаково.
Более того, когда процессор обнаруживает арифметическую операцию, он параллельно выполняет все поддержаные в ALU операции и декодирование кода операции, а на выходе по коду операции выбирается нужный результат.
Самое энергоемкое в процессоре — кеш-память. Не думаю, что на ее фоне кто-то решит оптимизировать арифметику.
Более того, когда процессор обнаруживает арифметическую операцию, он параллельно выполняет все поддержаные в ALU операции и декодирование кода операции, а на выходе по коду операции выбирается нужный результат.
Самое энергоемкое в процессоре — кеш-память. Не думаю, что на ее фоне кто-то решит оптимизировать арифметику.
В статье описывались асимптоты алгоритма умножения, а скорость выполнения процессорных инструкций входит в константу при них. Очевидно, что если нужно умножить два числа в миллиарды знаков (байт, слов), то скорость будет зависеть как раз от экспоненты.
Деление в худшем случае можно переписать как умножение и двоичный поиск, соответственно худшая оценка для деления теперь — n*logn*logn.
Деление в худшем случае можно переписать как умножение и двоичный поиск, соответственно худшая оценка для деления теперь — n*logn*logn.
Вот только двоичный поиск будет не log n, а n. Потому что в числе n знаков, значит надо делить интервал размером в 2^n.
Такое деление в итоге будет O(n^2 log n).
Точно, спасибо.
Делят, по крайней мере вещественные числа, обычно методом Ньютона, а у него квадратичная сходимость, то есть требуется логарифмическое число шагов. А сложность шага пропорциональна сложности умножения.
Вещественные числа давно уже делят, например, Голдшмидтом, и квадратный корень аналогично — с тех времён, как научились рассчитывать погрешность при таких вычислениях. Но в остальном — последствия такие же по сути, да, как для Ньютона (по ссылке — 1 цикл для single, 2 для double, 3 для extended).
Был какой-то достаточно эффективные алгоритм аппроксимации 1/n, а деление делается через него.
log log n растёт очень-очень-очень медленно. Даже если там миллиарды знаков — это будет что-то типа 5-6. А чтобы дорасти до 10 уже всех компьютеров мира не хватит.
Так что они правильно написали: теоретически — это дико круто, практически — отличие невелико…
Так что они правильно написали: теоретически — это дико круто, практически — отличие невелико…
Кстати, а есть подвижки по алгоритмам деления больших чисел?
А еще бы разложение на множители и прощай криптография =)
Квантовые компьютеры.
С одной стороны, уничтожат базу современной криптографии — сложность разложения на множители.
С другой стороны, вроде, на квантово-запутанных фотонах можно реализовать криптографию, которая гораздо гораздее, чем привычная.
С одной стороны, уничтожат базу современной криптографии — сложность разложения на множители.
С другой стороны, вроде, на квантово-запутанных фотонах можно реализовать криптографию, которая гораздо гораздее, чем привычная.
Не вроде, а точно. И не гораздее, а с физической невозможностью дешифровки без. Впрочем, у квантовой криптографии есть огромное число проблем и одна из основных — огромные требования к физической среде. К тому же, не смотря на физическую невозможность дешифровки без ключа сама её попытка приведёт так же к невозможности дешифровки и легальным пользователем. Даже больше — есть огромные проблемы с большими расстояними, а также с противодействием деструктивного воздействия условного противника.
Короче. Квантовая криптография это, конечно, интересно, но почти уверен, что она будет использоваться в очень узкой сфере требовательной к безусловной невозможности расшифровки и возможным попустительством в надёжности передачи. А я таких сфер сейчас почти и не знаю.
Короче. Квантовая криптография это, конечно, интересно, но почти уверен, что она будет использоваться в очень узкой сфере требовательной к безусловной невозможности расшифровки и возможным попустительством в надёжности передачи. А я таких сфер сейчас почти и не знаю.
Квантовые компьютеры не уничтожат всю криптографию, только алгоритмы типа RSA и Diffie Hellman. У всей симметричной криптографии уполовинется степень защиты.
И ещё, есть так называемая «post-quantum» криптография, там шифрование основано на сложных проблемах не связанных со сложностью разложения на простые множители и дискретный логарифм. Прямо сейчас идет соревнование на стандарт подобного типа. Такие алгоритмы выполняются на обычных комптьютерах и квантовые компьютеры им не страшны.
И ещё, есть так называемая «post-quantum» криптография, там шифрование основано на сложных проблемах не связанных со сложностью разложения на простые множители и дискретный логарифм. Прямо сейчас идет соревнование на стандарт подобного типа. Такие алгоритмы выполняются на обычных комптьютерах и квантовые компьютеры им не страшны.
Не совсем. Большинство современных процессоров конвейерные, то есть умеют выполнять одновременно несколько операций, находящихся на разной стадии вычислений. Что бы конвейер работал, требуется что бы одна и та же стадия разных операций не перекрывались во времени. Для этого все операции в конвейере искусственно замедляют до самой медленной. Как правило, это умножение, а более медленные операции, если они есть, останавливают конвейер.
Мы неплохо использовали операцию «быстрого обратного корня». Одно деление=перемножить два быстрых обратных корня. Получалось выгоднее. )
> Кстати, а есть подвижки по алгоритмам деления больших чисел?
Похоже, пока всё плохо. Если смотреть на GMP, по-прежнему основным рабочим методом остаётся итеративное деление на округлённый делитель, хотя его делают через обратное умножение, экономя на собственно процессорном делении.
Похоже, пока всё плохо. Если смотреть на GMP, по-прежнему основным рабочим методом остаётся итеративное деление на округлённый делитель, хотя его делают через обратное умножение, экономя на собственно процессорном делении.
Чуть более подробно про семинар Колмогорова, Карацубу и его способ умножения у Аввы в прошлом году был интересный пост в ЖЖ.
В далеком детстве, я научился в уме извлекать кубические корни из шестизначных чисел)))
… а, также, расставлять, избыточные, знаки, препинания))))))))
С возрастом перестал обращать внимание на такие мелочи как знаки препинания и прочие правила грамматики)
Раз смысл ясен — то к чему все эти условности? )))))
Раз смысл ясен — то к чему все эти условности? )))))
Смысл ясен вам как автору; стороннему читателю такие мелочи как знаки препинания и прочие правила грамматики помогают намного быстрее читать и понимать текст, «парсинг» же контекста обычно медленнее, требует больше умственных затрат и нередко дает сбои, предложение (а то и фразу целиком) приходится перечитывать.
Недавно я пару секунд тупил над фразой «А ещё велики лодки и пиво» — как пиво может быть велико? (ну ладно лодки еще), хотя речь шла о велосипедах, что, однако, мне было совсем не так очевидно, как автору сообщения.
Недавно я пару секунд тупил над фразой «А ещё велики лодки и пиво» — как пиво может быть велико? (ну ладно лодки еще), хотя речь шла о велосипедах, что, однако, мне было совсем не так очевидно, как автору сообщения.
Недавно я пару секунд тупил над фразой «А ещё велики лодки и пиво» — как пиво может быть велико? (ну ладно лодки еще), хотя речь шла о велосипедах, что, однако, мне было совсем не так очевидно, как автору сообщения.Если вам интересно, существует даже целая тема, посвященная подобным предложениям. По ним даже проводились исследования того, как люди их парсят и как разрешают конфликты.
Насколько я помню, основные техники скорочтения — как раз в игнорировании лишнего и понимании только нужного )
Вы немного о другом говорите. Вот есть слепые люди. Есть голосовые помощники, которые помогают им (при должной тренировке) ориентироваться при пользовании компьютером. Эти вот говорилки говорят с наиболее оптимальной скоростью с точки зрения возможности восприятия и затрат по времени. Возможности, но не удобства. Такое себе скорослушание.
Так вот нюанс в том, что если послушать обычным людям такую говорилку — не будет понятно абсолютно ничего (ну очень быстро).
Так и тут, знаки препинания и правила правописания помогают понимать текст абсолютному большинству.
P.S. Эволюционно так сложилось, что людям неудобно говорить быстро. А оттого и нет смысла учиться "быстро слушать". Только в экстренных случаях.
P.P.S. А ещё, это мне напомнило 1984, где лишние слова за ненадобностью выбрасывали из языка, потому что их можно было уже выразить другими словами/набором слов. Или сокращали.
Попытка проскорочитать текст, который невозможно однозначно интерретировать без запятых, приведет либо к нивелированию скорочтения до обычного либо к фатальным потерям данных. Зарятые являются«лишним усложнением» только на очевидных паттернах.
Ну и паттерны эти субьектозависимы. Так что мозг сам должен решать, какие детали игнорировать.
Ну и паттерны эти субьектозависимы. Так что мозг сам должен решать, какие детали игнорировать.
Про скорочтение и скорость мысли — личное ИМХО, дети когда учатся говорить начинают медленнее мыслить, т.к. мышление (вероятно в целях экономии) переводится на "родной язык" и автоматически синхронизируется со скоростью речи.
Насколько я помню, основные техники скорочтения — как раз в игнорировании лишнего и понимании только нужного )
Вроде основное в них — избавление от внутреннего проговаривания.
С ещё большим возрастом перестанете обращать внимание на такие мелочи, как не писаться в штаны, да?
К чему все эти условности, право…
К чему все эти условности, право…
да? Мне один знакомый пишет без знаков вопроса и любое его вопросительное предложение выглядит как приказ. «Ты сделаешь завтра отчёт», например.
По-моему, терпеть это никак нельзя, и отвечать таким людям нужно как в известной цитате с башорга, пусть перевоспитываются. :-)
НЛО прилетело и опубликовало эту надпись здесь
Нет на Хабре такого. Было исследование, которое показало, что плюсуют больше, чем минусуют. А минусуют походу тех, для кого карма и рейтинг играет какое-то особое значение.
анонимно нажать на минус и сидеть гордиться этим весь остаток дня.Человек с правом голоса имеет их не менее 10 в день. Достаточно гордиться каждым всего минут по 40 чтобы день прошел хорошо.
С какой точностью?
А я помню? :-)
Это было тааааак давноооо…
Прочел книгу емнип «Система быстрого счета по Трахтенбергу» и запомнил формулу которая позволяла в уме вычислять эти кубические корни. Но только кубические и только из шестизнаков)
Теперь уж и не помню ее. Формулу в смысле.
Это было тааааак давноооо…
Прочел книгу емнип «Система быстрого счета по Трахтенбергу» и запомнил формулу которая позволяла в уме вычислять эти кубические корни. Но только кубические и только из шестизнаков)
Теперь уж и не помню ее. Формулу в смысле.
Ну здесь имеется ввиду вычисление кубического корня из числа, которое является кубом целого. Кубический корень из шестизначного — это число двузначное, надо лишь оценить первую цифру результата, сравнив первые три цифры шестизначного числа с 125, 216, 343 и 512, а вторая цифра результата определяется по последней цифре шестизначного числа (там однозначное соответствие).
Скорее всего, это «по кубу двузначного числа определить само число», работает только для точных кубов. Алгоритм гуглится по «кубический корень в уме», но вкратце — по последней цифре куба однозначно определяем последнюю цифру исходного числа, дальше отбрасываем последние три цифры, по оставшимся определяем первую цифру исходного числа (ищем ближайший куб, который меньше того, что осталось). Надо только помнить таблицу кубов от 1 до 9.
del
Что-то я не понял. Всегда считал, что умножение в двоичной системе делается быстрее всего — там операций совсем мало и они крайне быстрые — сдвиг и сложение. (сдвигаем на один бит — получаем умножение на 2, или деление, если наоборот). Так что методов можно много напридумывать, но в двоичной системе (в которой почти все компьютеры работают) всё равно будет тот самый метод со сдвигом. Так что это всё скорее применимо к «человекочитаемым» способам умножения, нежели к процессорным. Поправьте меня, если я заблуждаюсь.
upd. Спасибо, разобрался. В принципе, для реализации в железе совсем не сложные доработки нужны.
upd. Спасибо, разобрался. В принципе, для реализации в железе совсем не сложные доработки нужны.
Сдвиг и сложение — это и есть «столбиком». Сложение это n операций, и потребуется ровно n сдвигов. Приведенные алгоритмы — асимптотически лучше.
Это смотря как считать что лучше. Многие операции можно выполнять параллельно/одновременно, и хотя суммарное число операций при этом будет больше, по времени это будет быстрее.
farafonoff
В процессоре не столбиком, там вообще нет отдельной операции сдвига, линии данных до сумматоров уже разведены в железе. Операции сложения выполняются параллельно со всеми разрядами множимого, а чуть позже и со всеми промежуточными вариантами. Без разделения операций на отдельные такты — тут работают защёлки. Они-же предназначены для запоминания промежуточных вычислений и коммутации данных со сдвигом.
В результате умножение целого 32б на 32б с результатом в 64б — требует срабатывания пяти защёлок, и в целом операция умножения успевает выполниться за один такт.
С плавучкой немного сложнее, но даже там операции над всеми разрядами данных выполняются параллельно.
То-есть используется тот самый способ из статьи автора, но в двоичном варианте. Я думаю что «открытие» произошло по причине прогресса. Сейчас уже трудно найти человека что будет самостоятельно проектировать модуль умножения для ядра процессора, зачем — когда есть готовая библиотека… Из-за чего и встречаются подобные проколы.
В процессоре не столбиком, там вообще нет отдельной операции сдвига, линии данных до сумматоров уже разведены в железе. Операции сложения выполняются параллельно со всеми разрядами множимого, а чуть позже и со всеми промежуточными вариантами. Без разделения операций на отдельные такты — тут работают защёлки. Они-же предназначены для запоминания промежуточных вычислений и коммутации данных со сдвигом.
В результате умножение целого 32б на 32б с результатом в 64б — требует срабатывания пяти защёлок, и в целом операция умножения успевает выполниться за один такт.
С плавучкой немного сложнее, но даже там операции над всеми разрядами данных выполняются параллельно.
То-есть используется тот самый способ из статьи автора, но в двоичном варианте. Я думаю что «открытие» произошло по причине прогресса. Сейчас уже трудно найти человека что будет самостоятельно проектировать модуль умножения для ядра процессора, зачем — когда есть готовая библиотека… Из-за чего и встречаются подобные проколы.
Если всё так как ты описал — часть сложности перенесена в железо. Т.е. вместо линейного количества времени тебе нужно линейную площадь кристалла. Это всё равно не позволяет выйти за границу асимптотической оценки. Попробуй представить умножение двух чисел длиной в гигабайт.
Попробуй представить умножение двух чисел длиной в гигабайт.
А зачем представлять, если есть библиотека которую можно посмотреть.
Очень большие и жирные числа всегда в десятичной системе. Не потому что удобно, а от того что перевод из двоичного представления в десятичное — будет слишком долгим. К тому-же математики помешаны на магии десятичной системы, у них это почти религия.
Дык вот, в свободной мат. библиотеке разбивка чисел уже работает, задолго до этого открытия.
Просто программисты забыли предупредить об этом местных светил математики.
Последний раз повторяю. Посмотри например сюда:
hg.openjdk.java.net/jdk8/jdk8/jdk/file/tip/src/share/classes/java/math/BigInteger.java
Метод public BigInteger multiply(BigInteger val) вызывает аж 3 реализации, в зависимости от длины чисел (все 3 способа описаны в статье). Кроме того хранятся не десятичные цифры, а сразу int32 (а к десятичной системе можно привести при печати).
hg.openjdk.java.net/jdk8/jdk8/jdk/file/tip/src/share/classes/java/math/BigInteger.java
Метод public BigInteger multiply(BigInteger val) вызывает аж 3 реализации, в зависимости от длины чисел (все 3 способа описаны в статье). Кроме того хранятся не десятичные цифры, а сразу int32 (а к десятичной системе можно привести при печати).
В результате умножение целого 32б на 32б с результатом в 64б — требует срабатывания пяти защёлок, и в целом операция умножения успевает выполниться за один такт.Не успевает. Откройте табличку, да посмотрите. Даже Ryzen и Skylake-X требуют для этого 3-4 такта, на более старых процессорах — больше. Да, это не 30-40 тактов, как для деления, но и не один такт. Просто потому что если реализовать ваше предложение — то придётся снижать частоту, а тогда и другие операции медленнее станут.
С плавучкой немного сложнее, но даже там операции над всеми разрядами данных выполняются параллельно.Та же самая история: никто не будет пихать такой большой мультипликатор в процессор. По уже описанной причине. Впрочем как раз для плавучки ваше утверждение верно — но не потому, что умножение занимает один такт, а потому что там даже сложение в один такт «не вписывается» — и занимает те же 3-4 такта, что и умножение.
Парадоксы современного процессоростроения…
Тем не менее, всякие девайсы с «Single-cycle multiply and accumulate (MAC) instructions» не редкость. Или я туплю, и это не то?
Если я правильно понял предмет спора, произошла терминологическая путаница.
Скорее всего имеется в виду машинный цикл, который состоит из нескольких тактов задающего генератора (на известных мне микроконтроллерах — 4).
Single-cycle
Скорее всего имеется в виду машинный цикл, который состоит из нескольких тактов задающего генератора (на известных мне микроконтроллерах — 4).
А это важно вообще? // я лет 10 не копался в этой теме и уже порядком плаваю.
Насколько я могу судить, работа отдельных модулей на частоте повышенной или пониженной относительно того, что мы называем частотой ядра, это норма. При этом частота ядра это, по сути, частота адресного генератора (если упрощенно смотреть). Не?
И если у нас все инструкции single-cycle, то мы получаем константное время выполнения кода. Во всяких специализированных сигнальниках могут вообще дикие вещи за 1 такт делаться. Ну то есть, я не понимаю смысла говорить о еще более низком подуровне.
Насколько я могу судить, работа отдельных модулей на частоте повышенной или пониженной относительно того, что мы называем частотой ядра, это норма. При этом частота ядра это, по сути, частота адресного генератора (если упрощенно смотреть). Не?
И если у нас все инструкции single-cycle, то мы получаем константное время выполнения кода. Во всяких специализированных сигнальниках могут вообще дикие вещи за 1 такт делаться. Ну то есть, я не понимаю смысла говорить о еще более низком подуровне.
Может и не важно. Я сам — нуб в схемотехнике. Только знаю, что иногда встречаются отдельные граждане, которые цепляются за разницу между машинным циклом (за который процессор выполняет простые команды) и тактом рабочей частоты.
Ну… в любом случае это все сильно архитектурнозависимые вещи. А выше они так спорят, как будто бы за этим всем стоят какие-то фундоментальные законы.
А за этим и стоят фундаментальные законы. Подумайте вот над чем: отдельные рекордные транзисторы работают на частотах в сотни гигигерц. Беглый поиск приводит к 798 GHz, правда в SiGe, но даже транзисторы в ваших процессорах на 200-300GHz способны… а процессор в целом — даже 10GHz «не делает» и даже на этой частоте ему нужны 3-4 такта для умножение и десятки — да деление.
Так-то Verilog позволяет «нарисовать» схему, которая любое конечное вычисление в один такт сделает… но почему-то так никто не делает. Что-то же должно являться причиной?
Подумайте над этим…
Так-то Verilog позволяет «нарисовать» схему, которая любое конечное вычисление в один такт сделает… но почему-то так никто не делает. Что-то же должно являться причиной?
Подумайте над этим…
Эмм. Фундоментальные ограничения на чустоту электроники, как таковой, не особо противоречат моим словам.
Фундаментальные ограничения не дают вам сделать железку, работающую на частоте в терагерц. А также сделать железку, выполняющую сложение за то же время, что и умножение. Это всё фундаментальные вещи.
Но вот будете ли вы выносить на архитектурный уровень тот факт, что умножение, всё-таки, сложнее умножения — это другой вопрос: вы не можете ускорить умножение до скорости сложения, но вы можете замедлить сложение… а можете «более простое» сложение «встроить в умножение» (откуда и получается MAC — инструкция: она выполняется за то же время, что и умножение и позволяет, часто, экономить на сложении).
Но вот будете ли вы выносить на архитектурный уровень тот факт, что умножение, всё-таки, сложнее умножения — это другой вопрос: вы не можете ускорить умножение до скорости сложения, но вы можете замедлить сложение… а можете «более простое» сложение «встроить в умножение» (откуда и получается MAC — инструкция: она выполняется за то же время, что и умножение и позволяет, часто, экономить на сложении).
Это так — но не в CPU. Самые «монстрачие» устройства, которые могут делать много-много умножений и сложений — это GPU. Однако какая-нибудь T4 Tesla за две штуки баксов всё равно имеют частоту максимум в 1.5GHz (это турбо буст режим, обычно меньше). А процессоры — редко имеют турбо-буст частоту ниже 3GHz, некоторые уходят до 5GHz.
Однотактовый умножитель на ширину «32бита» оказывается тупо слишком большим, чтобы на этой частоте работать.
Однотактовый умножитель на ширину «32бита» оказывается тупо слишком большим, чтобы на этой частоте работать.
Тут всё упирается в энергопотребление. Производительность видеокарт в специализированных задачах минимум на порядок выше, чем CPU, но энергопотребление — примерно в 2 раза больше.
Если вы работаете на частоте 1.5GHz, то современные технологии вам позволяют сделать однотактовый умножитель, а если на частоте 4.5GHz-5GHz — то уже нет. Вот через это — вы не перепрыгните. Это фундаментальное ограничение. А почему какие-то чипы вы будете делать под 1.5GHz, какие-то под 4GHz, а какие-то — и под 10MHz — это уже другой вопрос.
Не успевает. Откройте табличку, да посмотрите.
А это вы за границы модуля умножения вышли, причём очень далеко. х86 работает с памятью, ему сначала нужно эти числа загрузить в мат. процессор, а потом выгрузить. На всё это тратятся дополнительные такты ожидания.
К тому-же модуль умножения не является изолированным куском кремния, он способен выполнять намного больше вторичных функций. Всё это достигается внутренней коммутацией, часть в железном исполнении, часть в микрокоде.
Для arm ядер — этот узел похож на слипшийся комок макарон. Слишком многое в одном месте, без чёткого деления на площадь кремния. Там тоже есть такты ожидания, и они тоже связаны с внешней шиной.
Чудес не бывает, разве что в фпга…
А это вы за границы модуля умножения вышли, причём очень далеко. х86 работает с памятью, ему сначала нужно эти числа загрузить в мат. процессор, а потом выгрузить. На всё это тратятся дополнительные такты ожидания.Ага, конечно. Для умножения нам в память нужно сходить, а для сложения не нужно? Прудмайте какую-нибудь другую «отмазку», поправдоподобнее, пожалуйста.
Чудес не бывает, разве что в фпга…В FPGA тоже не бывает. Либо у вас сложение выполняется быстрее, чем умножение, либо вам приходится снижать тактовую частоту — других вариантов нет.
Одно дело — умножение чисел не превышающих разрядность ALU, и совершенно другое — умножение больших чисел. Для этого и существуют специальные алгоритмы.
Это когда у вас чиста маленькие. Когда надо перемножать 100500-битные числа, нужно делать 100500 сдвигов и складывать 100500/64 чисел каждый раз.
Я вот не совсем понимаю, почему наивный метод с FFT — это O(n logn log log n) вместо O(n log n). Откуда лишний log log n. Это из за того, что точности дабла не хватит при росте n и надо считать какие-то хитрые операции с длинными числами с плавающей точкой?
Наивный и FFT в одном предложении. Теперь я видел всё.
Вы делите число из n бит на кусочки по √n бит. Представляете кусочки как коэффициенты полинома степени √n. Перемножаете полиномы. Преобразование Фурье требует как минимум O(√n log n) сложений (если быстро на корни из единицы умножать), стоящих √n, и потом нужно ещё √n умножений чисел из ≈√n бит. Эти умножения обрабатываются рекурсивно тем же алгоритмом. Возникает рекуррентная формула для оценки сложности: C(n) = n log n + √n C(√n). Разворачивая рекурсию, получаем n log n log log n, где множитель log log n отвечает за количество рекурсивных шагов.
На самом деле оригинальная научная статья довольно неплохо разъясняет существующие алгоритмы (если вы не боитесь терминов «FFT» и «кольцо вычетов»).
На самом деле оригинальная научная статья довольно неплохо разъясняет существующие алгоритмы (если вы не боитесь терминов «FFT» и «кольцо вычетов»).
А почему не работает так: разбить число на кусочки по 1 биту — это коэфициенты полинома. fft — O(n log n), перемножить значения — O(n), обратное fft — O(n log n). Никакой рекурсии. Всего O(n log n). Откуда тут еще log log n? Или этот алгоритм не работает для больших n?
Потому что перемножение будет n^2, а не n. Весь выигрыш происходит, когда мы делим на фиксированное количество частей (2).
Потому что в процессе fft происходит куча сложений, из-за которых длина каждого элемента вырастает до O(log n) бит, а элементарное умножение начинает работать за O((log n)2). В итоге ваш метод даёт асимптотику O(n (log n)3), что явно больше чем O(n log n log log n)
Я так понимаю, что умножение это линейная свертка а преобразование фурье используется для быстрого подсчета цыклической свертки. Чтоб из цыклической свертки сделать линейную то циклическую нужно дополнить нулями чтоб получить линейную
В двух словах, лишний log log n возникает, потому что считается битовая сложность, то есть сложность базовых операций типа сложения и умножения не равна 1, а зависит от битовой длины элементов. Здесь (2.3) объяснено подробнее.
Почему в статье о новом революционном способе демонстрируется старый алгоритм Карацубы? Такое ощущение, что автор мало что понял из оригинальной работы и написал только то, что знал. Ну а сама оригинальная работа написана в классическом стиле от математиков для математиков — готового алгоритма, пригодного к реализации вы в ней не найдёте.
Например, в лемме 2.3 там доказывается convolution formula, согласно которой свёртка функций равносильна перемножению их Фурье-образов. Зачем? Это же известный, давно доказанный факт — можно было просто сослаться на доказательство, тем самым уменьшив объём работы.
Например, в лемме 2.3 там доказывается convolution formula, согласно которой свёртка функций равносильна перемножению их Фурье-образов. Зачем? Это же известный, давно доказанный факт — можно было просто сослаться на доказательство, тем самым уменьшив объём работы.
hal.archives-ouvertes.fr/hal-02070778/document
вот, пожалуйста
Извините, в следующий раз я буду читать комментарий полностью. Но ссылку всё равно оставлю.
Извините, в следующий раз я буду читать комментарий полностью. Но ссылку всё равно оставлю.
> Ну а сама оригинальная работа написана в классическом стиле от математиков для математиков — готового алгоритма, пригодного к реализации вы в ней не найдёте.
Не удивительно в общем, это ведь статья по математике — сомнительно, что полученный алгоритм будет иметь какое-то прикладное значение.
> Например, в лемме 2.3 там доказывается convolution formula, согласно которой свёртка функций равносильна перемножению их Фурье-образов. Зачем? Это же известный, давно доказанный факт — можно было просто сослаться на доказательство, тем самым уменьшив объём работы.
Это называется self-contained proof. Если какие-то уже известные результаты имеют простое доказательство, и их рассмотрение может добавить понимания, то их доказательство повторяется в статье.
Не удивительно в общем, это ведь статья по математике — сомнительно, что полученный алгоритм будет иметь какое-то прикладное значение.
> Например, в лемме 2.3 там доказывается convolution formula, согласно которой свёртка функций равносильна перемножению их Фурье-образов. Зачем? Это же известный, давно доказанный факт — можно было просто сослаться на доказательство, тем самым уменьшив объём работы.
Это называется self-contained proof. Если какие-то уже известные результаты имеют простое доказательство, и их рассмотрение может добавить понимания, то их доказательство повторяется в статье.
Можно наивный вопрос? Метод был предложен в 1960 году, он уже используется в современных ЭВМ? Если нет, то наверное есть какая-то объективная причина?
Метод Шёнхаге-Штрассена используется компьютерами для умножения больших чисел
Асимптотика показывает только зависимость от размера данных, и не показывает итоговое реальное время и так называемую «константу» перед асимптотикой. Например, O(10n) равно O(n). Константа «10» скрыта, т. к. на очень больших числах (например, стремящихся к бесконечности) это всё-равно будет быстрее, чем, допустим, O(n1.000000001) без скрытой «10», а также потому, что константа может зависеть от реализации.
Но на практике мы работаем с числами ограниченного размера, и даже чаще всего с очень маленькими числами, и все эти константы очень сильно влияют на итоговое время. Поэтому чаще всего подходящий алгоритм выбирается в зависимости от размера входных данных, причём оптимальных алгоритмов может быть много на разных размерах. Также ещё можно посмотреть на энергоэффективность алгоритма и размер потребляемой памяти.
Но на практике мы работаем с числами ограниченного размера, и даже чаще всего с очень маленькими числами, и все эти константы очень сильно влияют на итоговое время. Поэтому чаще всего подходящий алгоритм выбирается в зависимости от размера входных данных, причём оптимальных алгоритмов может быть много на разных размерах. Также ещё можно посмотреть на энергоэффективность алгоритма и размер потребляемой памяти.
Конечно используются. В JDK и .NET Core используется умножение Карацубы (в JDK 11 по умолчанию умножение переходит на Карацубу, если множители больше 2560 бит ). В JDK с множителей длины 7680 бит используется умножение Тоома-Кука.
Алгоритмы типа Штрассена имеют лучшую ассимптотическую характеристику, но добавляют значительные константные накладные расходы. Из-за этого их применение для маленьких размерностей (десятки-сотни бит) неоправдано. Для операций над небольшими числами в железе используются другие оптимизации, направленные в основном на ускорение получения результата путем избыточных операций, которые можно выполнять паралельно (методы быстрых переносов).
Но если вам нужно умножить действительно большие числа или, что более вероятно, умножить две больших матрицы, алгоритмы типа Штрассена могут дать кратный прирост производительности. Такие методы используются в специализированном железе.
Но если вам нужно умножить действительно большие числа или, что более вероятно, умножить две больших матрицы, алгоритмы типа Штрассена могут дать кратный прирост производительности. Такие методы используются в специализированном железе.
Посмотрите на GMP. Там есть регулярно пересчитываемые для разных процессоров границы применения методов, чтобы функция сразу выбрала подходящий согласно длинам сомножителей.
Вот, например, для Zen серии в 64 битах при переходе меньшим сомножителем границы 22 лимба (лимб тут будет 64 бита => то есть длина 1408 бит) происходит переключение от «schoolbook» (квадратичное умножение всего на всё) к, чуть упрощая, методу Карацубы (записан как TOOM22; метод Карацубы является частным случаем Тоома-Кука; ТК это вообще не конкретный метод, а метаметод, который можно «заземлять» в неограниченное множество алгоритмов). Дальше до 460 лимбов (29440 бит) идут разные варианты ТК, но с этой границы включают Шонхаге-Штрассена.
Для других линий процессоров константы будут другими, но общая картина сохраняется где-то на том же уровне.
Более дорогие и тяжёлые методы вроде Фюрера там не применяются, видно, решили, что выделки не стоит (реально при таких свойствах процессоров он начал выигрывать бы где-то от миллиона бит).
Вот, например, для Zen серии в 64 битах при переходе меньшим сомножителем границы 22 лимба (лимб тут будет 64 бита => то есть длина 1408 бит) происходит переключение от «schoolbook» (квадратичное умножение всего на всё) к, чуть упрощая, методу Карацубы (записан как TOOM22; метод Карацубы является частным случаем Тоома-Кука; ТК это вообще не конкретный метод, а метаметод, который можно «заземлять» в неограниченное множество алгоритмов). Дальше до 460 лимбов (29440 бит) идут разные варианты ТК, но с этой границы включают Шонхаге-Штрассена.
Для других линий процессоров константы будут другими, но общая картина сохраняется где-то на том же уровне.
Более дорогие и тяжёлые методы вроде Фюрера там не применяются, видно, решили, что выделки не стоит (реально при таких свойствах процессоров он начал выигрывать бы где-то от миллиона бит).
Теперь ждём, когда заново откроют сложение!
Шутка «Если умножение так хорошо, то почему ещё не выпустили умножение 2» перестает работать.
Бинарное сложение с предрасчетом carry уже давно существует, работает за 1 такт.
Это выглядит ужасно, и занимает кучу места на кристалле. Особенно для длинных чисел. images.app.goo.gl/sibNc8JcZz4sJ7GC9
Таким же образом можно и умножать.
Это выглядит ужасно, и занимает кучу места на кристалле. Особенно для длинных чисел. images.app.goo.gl/sibNc8JcZz4sJ7GC9
Таким же образом можно и умножать.
Только что считать тактом?
Время на устранение переходных процессов? В данном случае 10 вентилей в глубину. В идеальном случае можно довести до 2х слоёв (с соответствующим разжирением схемы, так что больше 2 по 4х бит будет складывать не выгодно так как 2^(4*2)=256 вентилей, ну или что-то около того)
Ну так в том то и дело что "такт" при современных частотах уже вполне приближается к "времени на устранение переходных процессов" и может случиться что 10 вентилей в глубину это уже дольше чем время 1 такта.
Все инструкции в процессорах как правило выполняются разное время как раз исходя из количества слоев и задержки в худшем случае. И повышение времени выполнения одной простой инструкции особо на производительность не влнияет, так как задержка при получении информации из ram все равно в сотни раз дольше сложения двух чисел в зависимости от тапа памяти и наличия кеша. Тут можно почитать подробнее
drive.google.com/a/uottawa.ca/file/d/1mKy4z9l8EEDHszT0_qtIjFBseL4ujcfG/view?usp=drivesdk
drive.google.com/a/uottawa.ca/file/d/1mKy4z9l8EEDHszT0_qtIjFBseL4ujcfG/view?usp=drivesdk
Отлично! Значит реймаршинг будет выполняться ещё быстрее. Немного прифигел от скромности ван дер Хувена: «Всё, на что мы можем надеяться, это на трёхкратное ускорение».
Он говорит «надеяться», потому что математически обоснованное преимущество может сойти на нет (и даже в минус) за счёт накладных расходов при практической реализации. Подобный эффект наблюдается, в частности, при реализации быстрых алгоритмов Фурье — потому что помимо вычислений как таковых есть ещё операции чтения/записи/перемещения в памяти.
Это не скромность. Попробуйте прикинуть при каком n у вас log log n «дорастёт» до десятки и подумайте — будут ли вас когда-нибудь волновать такие числа.
Значит реймаршинг будет выполняться ещё быстрее.
А где там длинные числа? Все эти быстрые умножения (Карацуба и последующие) они про числа в тысячи бит.
Умножение Карацубы выглядит как какая-то нумерология со сложением казалось бы не имеющих отношения к умножению цифр.
шутка про нумерологию
но при этом работает (я проверил на листочке).ID поста 451860, сумма цифр 4+5+1+8+6+0=24, среднее между 2 и 4 = 3, Half Life 3 confirmed
> Шутка про нумералогию
оффтоп, но напомнило
оффтоп, но напомнило
Умберто Эко (с) «Маятник Фуко»
«Театральным жестом он распахнул ставни, предложил нам выглянуть и указал невдалеке, на углу между улочкой и бульварами, деревянный цветочный киоск.
— Господа, — сказал он. — Предлагаю вам самим отправиться и измерить эту будку. Вы увидите, что длина прилавка составляет 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, царь Пергама. Годится?»
Умберто Эко (с) «Маятник Фуко»
— Господа, — сказал он. — Предлагаю вам самим отправиться и измерить эту будку. Вы увидите, что длина прилавка составляет 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, царь Пергама. Годится?»
Умберто Эко (с) «Маятник Фуко»
Вся нумерология пропадает если начать записывать формулы.
Допустим, у нас есть два числа, 10a+b и 10c+d. Тогда их произведением будет 100ac + 10(ad+bc) + db.
Заметим, что ad+bc = (a+b)(c+d) — ac — db.
Рекомендую вам изучить алгоритм Винограда для умножения матриц – вот где истинная нумерология. :)
Почему для умножения Карацубы выбраны только примеры, где сложение не даёт переноса? Это слегка нечестно.
Потому что при сложении двух чисел с одинаковым количеством цифр у вас в худшем случае результат будет на одну цифру больше. Так что для действительно больших чисел этот перенос будет незначимым, поскольку будет выполнен всего на один разряд.
Если взять «неудачный» пример, то будет продемонстрировано как раз то, что метод Карацубы не дает приемущества в общем случае для небольших чисел.
Если взять «неудачный» пример, то будет продемонстрировано как раз то, что метод Карацубы не дает приемущества в общем случае для небольших чисел.
Все думают, что метод умножения, который они учили в школе, наилучший, °°°
Но на самом деле нужно изучать в школе fft
А вот и похожая статья тут была несколько лет назад habr.com/ru/post/262705
Как всегда, кликбейтный заголовок с фактическими неточностями, узнается Кванта.
Они придумали максимально быстрый на данный момент, без доказательства его идеальности. «Фундаментальное» ограничение скорости тоже под большим вопросом.
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.
Они придумали максимально быстрый на данный момент, без доказательства его идеальности. «Фундаментальное» ограничение скорости тоже под большим вопросом.
Мне кажется или O(xlog(x)log(logx)) быстрее O(x^1.46) для нового алгоритма при x выше 3300? Так какая у нового алгоритма сложность то?
Кто объяснит, почему на финальном шаге при умножении 2531х1467 2109 стоит там, где оно стоит. А не, к примеру, на разряд правее.
Умножение Карацубы 2531х1467 требует 9 умножений.
У меня у одного получается 12 умножений?
«Сложение в школе проходят на год раньше, потому что это гораздо проще, оно выполняется за линейное время, со скоростью чтения цифр слева направо»,
А кто может мне пояснить, почему слева направо, а не справа налево?
Сколько раз умножал столбиком, я делаю это справа налево, с переносом десятков в столбец слева.
НЛО прилетело и опубликовало эту надпись здесь
Это же не про плавающую точку. Как, например, вы найдёте в логарифмах первые 20 чисел Мерсенна?
тогда проблемы возникнут со сложением и вычитанием
А нейросети нельзя привлечь для поиска более совершенных алгоритмов перемножения/деления?
Нейронные сети плохо справляются с придумыванием алгоритмов кмк
Не придумывать, а «пробутфорсить» на совпадения.
Дать на вход множественные числа и «поле» для разбиения этих чисел так и эдак.
Сравнивать с заранее вычисленными итоговыми результатами на предмет верности того или ного случайного алгоритма. Может найдутся новые варианты и какие-то из них окажутся эффективными в каких-то контекстах
Дать на вход множественные числа и «поле» для разбиения этих чисел так и эдак.
Сравнивать с заранее вычисленными итоговыми результатами на предмет верности того или ного случайного алгоритма. Может найдутся новые варианты и какие-то из них окажутся эффективными в каких-то контекстах
Алгоритм трудно выковырять из нейросети, и он может оказаться быстрым, но неточным и/или неверным за пределами обучающей выборки. Да и в области выборки даже. А так может и найдётся что-нибудь типа 0x5F3759DF.
"Быстрый обратный квадратный корень" — вообще-то частный случай. Так-то можно любые константы рассчитывать для операции степени от -1 до 1 с помощью математических методов и нейросети здесь не нужны.
Может кто объяснить зачем перемножать два числа размером миллиард на миллиард с такой асимптотической сложностью, если цифр все-равно получится n^2 и столько же операций потратится на запись? Да и вообще где хранить результат этого произведения? Ведь понадобится 10^9 гигабайт памяти.
Интересно существует ли такой способ:
1. первое число умножить на 1,2,3,4,...,9
2. потом полученные значения суммировать с добавлением нужного кол-ва нулей?
1. первое число умножить на 1,2,3,4,...,9
2. потом полученные значения суммировать с добавлением нужного кол-ва нулей?
НЛО прилетело и опубликовало эту надпись здесь
Благодаря статье узнал что то, что на развлекательных сайтах называют «японским методом умножения чисел» (ну там где рисуют разноцветные линии и считают переcечения) по сути графическое представление умножения Карацубы.
Карацюба, ШШ, и еще несколько методов умножения целых произвольной точности подробно описаны во втором томе «Получисленные алгоритмы» трехтомника Д. Кнута «Искусство програмирования для ЭВМ».
Там же разжеван алгоритм умножения в RNS, который требует n умножений, где n — количество модулей в RNS-базисе.
Там же разжеван алгоритм умножения в RNS, который требует n умножений, где n — количество модулей в RNS-базисе.
О, я придумал как считерить — надо перейти к системе счисления с большим основанием
В .NET (структура BigInteger), в JDK (класс BigInteger), в V8 (тип BigInt) и в GNU MP (тип mpz_t) используется основание 2^32 (беззнаковое 32-битное целое). Написать arbitrary precision арифметику с большим основанием (напр. 2^64), наверное возможно (придётся использовать промежуточную 128-битную арифметику), но мне кажется, что на существующих процессорах весь выигрыш сожрётся затратами на обслуживание этой 128-битной арифметики. Ну и прощай переносимость, конечно.
Вообще говоря, современные процессоры умеют перемножать два 64-битных числа с получением 128-битного результата, так что арифметика с основанием 264 вполне достижима (и даже будет быстрее стандартной), если писать на ассемблере.
Проблема в том, что в языках программирования такой операции умножения обычно нет...
Это разве не компилятор должен решать?
А что он может решить, когда нужной операции просто нет?
В каком языке нет символа умножения? В каком языке высокого уровня вы руками выбираете конкретную реализацию умножения в зависимости от типа? Или как-то раскройте что ли мысль.
В известных мне языках нет операции, которая бы из двух чисел размера N бит делала их произведение размера 2N бит.
Вообще-то, любое умножение дает сложение числа разрядов. Что вам мешает написать (uint16)=(uint8)*(uint8)? Как это обрабатывается процессором, зависит от целевой архитектуры и компилятора.
Мешают три вещи.
Во-первых, (uint64)*(uint64) дает на выходе uint64, которую бесполезно расширять далее до uint128.
Во-вторых, если предварительно привести операнды к более широкому типу, вылезет вторая проблема: полное умножение uint128 * uint128 — это вовсе не одна инструкция процессора, а компилятор не всегда замечает что старшая часть операндов — нулевая, и умножение можно сделать по короткой схеме. В итоге получается выгоднее использовать базу половинной разрядности.
В-третьих, типа данных удвоенной разрядности (uint128) зачастую не существует.
Во-первых, (uint64)*(uint64) дает на выходе uint64, которую бесполезно расширять далее до uint128.
Во-вторых, если предварительно привести операнды к более широкому типу, вылезет вторая проблема: полное умножение uint128 * uint128 — это вовсе не одна инструкция процессора, а компилятор не всегда замечает что старшая часть операндов — нулевая, и умножение можно сделать по короткой схеме. В итоге получается выгоднее использовать базу половинной разрядности.
В-третьих, типа данных удвоенной разрядности (uint128) зачастую не существует.
Так этим компилятор занимается, а не программист. Ну и на вопрос я вам ответил.
Занимается чем?
Длинную арифметику, почти во всех известных мне языках, пишут всё-таки программисты.
Длинную арифметику, почти во всех известных мне языках, пишут всё-таки программисты.
Выбором того, каким ассемблерным кодоом реализовать выш код.
Длинная арифметика — условное понятие. Для 8 битных AVR uint32 это длинная арифметика, но никто не пишет ее руками. Деления там вообще нет, но писать в коде "/" никто не запрещает, и компилятор может раскрыть это по-разному.
Вопрос у вас был без такой:
Длинная арифметика — условное понятие. Для 8 битных AVR uint32 это длинная арифметика, но никто не пишет ее руками. Деления там вообще нет, но писать в коде "/" никто не запрещает, и компилятор может раскрыть это по-разному.
Вопрос у вас был без такой:
нет операции, которая бы из двух чисел размера N бит делала их произведение размера 2N бит.Я вам привел вполне релевантный пример. Вы же мне пример языка, где бы программист указывал, какую инструкцию процессора использовать, так и не показали.
Выбором того, каким ассемблерным кодоом реализовать выш код.
Да, этим должен заниматься компилятор. Но это не помогает решить задачу получения оптимального кода.
Длинная арифметика — условное понятие.
Пожалуйста, вспомните в контекста какого поста она тут обсуждается.
Я вам привел вполне релевантный пример.
Ваш пример работает только в том случае, если в выбранном ЯП тип uint8 расширяется до более крупного перед умножением. А это не обязательно так. В каком-нибудь Си для 8-битных AVR запросто может быть int=short=char=int8.
Вы же мне пример языка, где бы программист указывал, какую инструкцию процессора использовать, так и не показали.
Такой язык программирования был назван в первом же комментарии: язык ассемблера. Языков высокого уровня с этим свойством, конечно же, нет, по определению языка высокого уровня. Не понимаю почему вы ожидаете какого-то другого ответа и как это вообще связано с использованием базы половинной разрядности.
В каком-нибудь Си для 8-битных AVR запросто может быть int=short=char=int8.Нет. Там int это uint16, как и в моем примере (собственно, откуда я его и взял). Даже для Attiny13, где вообще нет умножителя.
язык ассемблера.Высокоуровневый?
Языков высокого уровня с этим свойством, конечно же, нет, по определению языка высокого уровня. Не понимаю почему вы ожидаете какого-то другого ответа и как это вообще связано с использованием базы половинной разрядности.Потому, что вы просите какую-то отдельную операцию вместо обычного символа умножения. вместо того чтобы написать код
uint64 a, b;
uint128 c;
....
c=a*b;
Можно так написать? Что-то мне подсказывает, что да.Написать-то можно что угодно, только не забывайте что получится, а? Сходите, полюбуйтесь.
Почему в этой программе:
const int64_t a = 0x1000000000000000;
const int64_t b = 0x1000000000000000;
const __int128 c = a * b;
c равна нулю — нужно объяснять?То есть, вы мне на слова «это вопрос к компилятору, а не командам языка» говорите свое везкое «нет», а в качестве пруфа приводите выдачу конкретного компилятора. Серьезно?
При этом вы почему-то забыли сказать, что компилятор знает о проблеме и вас предупреждает:
При этом вы почему-то забыли сказать, что компилятор знает о проблеме и вас предупреждает:
/example.cpp:9:22: warning: integer overflow in expression of type 'long int' results in '0'При этом я вам не говорил, что мой пример нормально отрабоатет в си. Я сказал, что в языке есть все средства для записи. Вы же хотите какую-то отдельную команду. Вы можете нормально сказать, что конкретно вы хотите? Второй символ умножения или что?
То есть, вы мне на слова «это вопрос к компилятору, а не командам языка» говорите свое везкое «нет», а в качестве пруфа приводите выдачу конкретного компилятора. Серьезно?Абсолютно. Если вы считаете, что этот компилятор не годится — можете найти другой. Их там много. Но не получится. Потому что не в компиляторах дело.
При этом я вам не говорил, что мой пример нормально отрабоатет в си. Я сказал, что в языке есть все средства для записи.Это вообще что? У вас первое предложение противоречит второму, извините.
Второй символ умножения или что?Как вариант. В Forth есть операция
M* — она как раз делает то, что требуется. Но в распространённых языках такой операции нет. Записать операцию «пермножить два 64-битных числа с получением 128-битного результата» там нельзя. В Forth — можно, а в C, Java, Pascal, да и вообще почти во всех распространённых языках — нельзя. Вот вообще нельзя. Никак.При этом вы почему-то забыли сказать, что компилятор знает о проблеме и вас предупреждаетХех. Вопрос «почему там предупреждение и почему оно исчезает если в примере
int64_t на uint64_t заменить (хотя результат всё равно остаётся нулевым)» — это хороший вопрос на знание C, но он всё равно не помогает нам решить поставленную задачу… вы, кстати, знаете, почему замена int64_t на uint64_t убирает предупреждение? Или нет? Если нет — тогда вообще неясно о чём мы тут говорим…Никак.
А если оператор перегрузить?
Нельзя перегрузить оператор для стандартных типов. C++ расширяем, но не изменяем.
Кроме того, непонятно чем перегрузка оператора поможет: если в языке не было конструкции, выражающейся через соответствующую инструкцию процессора — то откуда она в перегруженном операторе возьмётся?
Можно написать
В принципе с этим можно жить (если не забывать про -Og), но это всё равно — хождение по минному полю…
Кроме того, непонятно чем перегрузка оператора поможет: если в языке не было конструкции, выражающейся через соответствующую инструкцию процессора — то откуда она в перегруженном операторе возьмётся?
Можно написать
c = (unsigned __int128)a * b; — но вот уже тут вы опираетесь на свойства конкретного компилятора и на тот факт, что он может понять, что в данном случае использование одиночного mulq — безопасная оптимизация. Clang, скажем, «просекает фишку» всегда, а вот GCC — не всегда. Сравните (и посчитайте количество mulqов и imulqов в сгенерированном коде).В принципе с этим можно жить (если не забывать про -Og), но это всё равно — хождение по минному полю…
Потому что не в компиляторах дело.Тогда каким образом вывод компилятора что-то доказывает? Впрочем, я вполне допускаю, что могу тупить, но тогда почему бы вам нормально не написать ваше видние?!
Впрочем, я вполне допускаю, что могу тупить, но тогда почему бы вам нормально не написать ваше видние?!Потому что любая дискуссия предполагает некоторый уровень владения предметом. Если мне сейчас придётся вам объяснять всё, что программисты проходят за пару лет обучения в ВУЗе — то наша дискуссия никогда не дойдёт до сути вопроса.
Моя отсылка — была простым тестом на понимание вами языка C и ассмеблера.
Тогда каким образом вывод компилятора что-то доказывает?Подумайте. Подсказка: мной был специльно написано пример, дающий ноль байтов кода на выходе. Для того, чтобы исключить из обсуждения вопросы кодогенерации и прочих, не очень важных тут, вещей. А также заложена маленькая «пасхалочка» — вот с тем самым предупреждением о возможной ошибке.
Вы за неё уцепились, чем показали, что вы не понимаете не только как устроен компилятор C, но также и как устроен собственно язык С… а какой смысл обсуждать свойства языка C с человеком, который его не знает?
С тем же успехом мы могли бы обсуждать тонкости клингонского языка, к примеру.
Вот, для сравнения, пример на Forth, показывающий что там нужная нам операция есть:
Вместо ссылки на godbolt я мог бы показать вам это… если бы был хоть какой-то шанс того, что вы бы поняли этот пример.
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 я мог бы показать вам это… если бы был хоть какой-то шанс того, что вы бы поняли этот пример.
В общем, вы правы. Но я не вижу проблемы указать из какой конкретно особенности «устройства языка» следует, что это должно так работать.
Это следуют просто-напросто из того факта, что у выражения
А дальше — можно это значение засовывать уже куда угодно, хоть в 128-битную переменную, хоть в 256-битную, это уже ничего не изменит…
a*b есть значение — и оно имеет тот же тип, что a или b, и, внезапно, int (в зависимости от того, какой трёх типов «шире»).А дальше — можно это значение засовывать уже куда угодно, хоть в 128-битную переменную, хоть в 256-битную, это уже ничего не изменит…
Кстати, насчет специальных команд. Есть, вроде интринсики типа _mul128 или что-то такое (как вы правильно поняли, в норме я не имею дела с такими вещами, и на большинстве моих девайсов вся математика слишком толстая, и выход за пределы uchar является событием).
Объясните, на каком основании у выражения a*b должно быть значение того же типа, что и у a и b? Почему языки устроены таким странным образом?
В нашей повседневной реальности я умножаю метр на метр и получаю квадратный метр. В любых расчётах тип сохраняется только при сложении и вычитании, а при других действиях — получается другой тип. А в языках программирования внезапно, ладно что иначе по умолчанию, но и в порядок привести нельзя.
В нашей повседневной реальности я умножаю метр на метр и получаю квадратный метр. В любых расчётах тип сохраняется только при сложении и вычитании, а при других действиях — получается другой тип. А в языках программирования внезапно, ладно что иначе по умолчанию, но и в порядок привести нельзя.
Ну это вам в историю математики стоит углубиться.
Собственно соображения, подобные высказанным вами, и не позволили древним грекам и римлянам как следует развить баллистику. Ибо без квадратных уравнений в баллистике никак — а как вы его запишите без того, чтобы
Но в сегодняшнем мире люди, всё-таки, проходят квадратные уравнения в седьмом классе, так что, казалось бы, к моменту, когда человек добирается до Хабра для него это уже не должно быть проблемой…
В нашей повседневной реальности я умножаю метр на метр и получаю квадратный метр.И про квадратные уравнения вы, конечно, ничего не слышали?
В любых расчётах тип сохраняется только при сложении и вычитании, а при других действиях — получается другой тип.Ну это, всё-таки, не совсем так. Длина окружности и её радиус имеют одинаковый тип, что не мешает им быть связанными соотношениями L = 2πr.
Собственно соображения, подобные высказанным вами, и не позволили древним грекам и римлянам как следует развить баллистику. Ибо без квадратных уравнений в баллистике никак — а как вы его запишите без того, чтобы
x² сложить с x?Но в сегодняшнем мире люди, всё-таки, проходят квадратные уравнения в седьмом классе, так что, казалось бы, к моменту, когда человек добирается до Хабра для него это уже не должно быть проблемой…
Почему языки устроены таким странным образом?Не только языки. Процессоры тоже. Да, у процессора, в отличие от языка C, есть инструкция, возвращающая «удвоенный» результат (8but * 8bit ⇒ 16bit, 16bit * 16bit ⇒ 32bit, 32bit * 32bit ⇒ 64bit), в отличие от C, однако операция, сохраняющая размер — у него тоже есть… и она, в большинстве случаев, работает быстрее.
Если Х не безразмерный, то и константы не безразмерные (в отличие от числа пи). В физике всегда сохраняется размерность во всех уравнениях (есть даже техники поиска решений методом подгонки размерностей).В нашей повседневной реальности я умножаю метр на метр и получаю квадратный метр.И про квадратные уравнения вы, конечно, ничего не слышали?
В физике всегда сохраняется размерность во всех уравнениях (есть даже техники поиска решений методом подгонки размерностей).Тем не менее даже в этих случаях могут быть много тонкостей, так как в физике полно размерных констант.
Тот факт, что в большинсво языков программирования всё это богатство не отражается — несколько прискорбен, но к выбору
float double или там uint8_t uint64_t это всё не имеет отношения.Ситуация, когда вам хочется сменить базовый тип на практике, всё-таки, случаётся реже, чем когда у вас появляется другая размерность.
Тем не менее даже в этих случаях могут быть много тонкостей, так как в физике полно размерных констант.
Никаких тонкостей нет ИМЕННО благодаря размерным константам. Если не верите — приведите хоть один пример.
А если мне приходится складывать x + x^2 — это достаточная причина, что искать ошибку где-то в выводе формулы.
Да боже ж ты мой. Скорость удаления двух частиц, разлетающихся в разные стороны. Простейший пример, в школе изучают.
Там все размерности сходятся. Если размерность не сходится, то формула не имеет физического смысла.
Впрочем, вы правы, что к размеру переменных это имеет мало отношения, если имеет вообще.
Впрочем, вы правы, что к размеру переменных это имеет мало отношения, если имеет вообще.
К размеру переменных — не имеет.
Но противоречит утверждению khim о том, что у результата умножения концептуально должен быть тот же тип, что и у операндов.
Но противоречит утверждению khim о том, что у результата умножения концептуально должен быть тот же тип, что и у операндов.
Не надо тянуть сову на глобус, пожалуйста. Ей больно.
Типы в понятии современных языков программирования — это не физические размерности, а, скорее, вот эти вот ℕ, ℚ, ℝ и прочие ℤ4294967296.
Все математические операции, если не сказано иного — в математике производятся в рамках одного подобного типа. И умножение и деление тоже.
А то, что «физические» типы в современных языках почти никак не представлены — это неприятно, но к обсуждаемому вопросу отношения не имеет. Эти типы всё равно, скорее всего, существовали бы только в исходниках, но не в скомпилированной программе.
Типы в понятии современных языков программирования — это не физические размерности, а, скорее, вот эти вот ℕ, ℚ, ℝ и прочие ℤ4294967296.
Все математические операции, если не сказано иного — в математике производятся в рамках одного подобного типа. И умножение и деление тоже.
А то, что «физические» типы в современных языках почти никак не представлены — это неприятно, но к обсуждаемому вопросу отношения не имеет. Эти типы всё равно, скорее всего, существовали бы только в исходниках, но не в скомпилированной программе.
НЛО прилетело и опубликовало эту надпись здесь
Кстати, если дело в этом, то почему uint16_t=uint8_t*uint8_t работает (в том числе для AVR, откуда я исходно взял свой пример) так, как этого описал я?
Потому что uin16_t имеет размер меньше, чем int, однако.
Как это согласуется с утверждением выше?
у выражения a*b есть значение — и оно имеет тот же тип, что a или bНу а размер int архитектурно зависим.
А доцитировать до конца?Как это согласуется с утверждением выше?у выражения 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хбитный), согласитесь?если типы меньше, чем int — то они приводятся в int, перед тем, как что-то считатьДаже если int больше размера регистров АЛУ (да и других, впрочем)?
Ну и смотрите, выше вы говорили, что это нечто принципиальное, а оказывается, просто наследие.
Даже если int больше размера регистров АЛУ (да и других, впрочем)?Разумеется. Разработчик компилятора вправе сам решать — что там у него за
int. Но если назвался — то всё должно считаться в int. Никаких АЛУ в стандарте нет.Ну и смотрите, выше вы говорили, что это нечто принципиальное, а оказывается, просто наследие.Где я говорил, что это фундаментальный закон физики?
Да, оно — «просто наследие». В той же степени, в какой вся наша цивилизация — это наследние людй, которые когда-то изобрели колесо. И теперь мы вынуждены строить дороги, мосты, тоннели и многое другое.
В какой-то другой цивилизации — могли бы, вместо этого, приручить гигантстких летучих мышей… и у них много чего могло бы быть по-другому. Но у нас нет гигантских летучих мышей — потому приходится общаться с тем, что есть.
Я уже приводил пример языка, где оператор умножения с порождением результата двойного размера имеется. Если бы наша современная IT-индустрия бы развивалась на его базе, а не на базе C — у нас много чего было бы по-другому. Но поскольку C оказался в основе всего, с чем мы работаем — то и Pascal и C++ и Java и многое-многое другое — работают так же…
Разработчик компилятора вправе сам решать — что там у него за int.То есть, в итоге дело таки в компиляторе? Что принципиально мешает добавить какой-нибудь флаг типа -use128int (и собирать все тяжелые мат модули с ним)? Разве это противоречит стандарту?
Никаких АЛУ в стандарте нет.В получаемом ассемблере-то есть. Как мы получим (а мы ее получаем) оптимальную 8-битную математику с 16 битным int?
Разве это противоречит стандарту?Противоречит. Вы можете иметь в программе какой угодно
int, но он должен быть един для всей программы. Никаких модулей стандарты C и C++ не предусматривают (С++20, возможно, предусмотрит, но вряд ли там будет разрешено иметь в разных модулях разные intы).И вы тут, опять-таки, «никуда не соскочите»: если вы сделаете такой финт ушами, то у вас все вычисления станут int128⇒int128. Даже если когда вы байт на байт будете умножать — они будут сначала превращаться в int128, а потом уже перемножаться.
То есть, в итоге дело таки в компиляторе?Конкретный размер — зависит от компилятора. Тот факт, что умножения, перемножающего два значения разных типов и возвращающих результат другого, более широкого типа — от компилятора не зависит.
От компилятора зависит только где проходит граница между «слишком маленькими» типами, использующимися только для экономии память и «большими» типами, которые могут участвовать в вычислениях. И всё.
Как мы получим (а мы ее получаем)Это вы с -O0 её получаете? Не надо сказок, пожалуйста: если вы умножаете 8-битное число на 8-битное — то они сначала расширяются до 32-бит, потом обрезаются обратно в 8.
оптимальную 8-битную математику с 16 битным int?За счёт того, что большинство существующих компиляторов — оптимизирующие. И некоторые оптимизации вообще неотключаемые. Но гарантий никаких нет — см. пример выше.
Разве я не могу собрать разные исходные файлы, используя разный int, а потом слинковать все вместе? С чужими же elf'ами могу.
Не надо сказок, пожалуйста: если вы умножаете 8-битное число на 8-битное — то они сначала расширяются до 32-бит, потом обрезаются обратно в 8.Это на х86-64. На Avr ничего такого не происходит, при этом дефолтный размер int там 16 бит, если не указать руками иное.
Разве я не могу собрать разные исходные файлы, используя разный int, а потом слинковать все вместе? С чужими же elf'ами могу.Собрать-то вы можете… а вот будет ли подобный франкенштейн работать — это уже большой вопрос, на который ни разработчики стандарта C, ни разработчики компилятора вам не ответят. Вряд ли можно рекомендовать использовать, без самой крайней нужды, что-то, работоспособность чего зависит от цены на папайю в Гонолулу.
На Avr ничего такого не происходит, при этом дефолтный размер int там 16 бит, если не указать руками иное.Ну значит вам везёт и компилятор, которым вы пользуетесь не умеет эту оптимизацию отключать. Завтра может выйти другая версия — и она вполне может начать всё это делать неоптимально.
Мы ведь тут обсуждаем не конкретный компилятор, а язык, так что того факта, что так себя ведёт компилятор на x86-64 — вполне достаточно для иллюстрации.
Почему? В пределах каждой конкретной функции все будет единообразно. В чем вы видите проблему? Разве есть гарантия, что, например, все используемые библиотеки собраны с одинаковым значением int?
Еще раз. Я согласен, что не блещу знаниями стандарта, но я привел пример рабочего платформоспецифичного кода. Выш запрос на int128=int64*int64 в одну инструкцию тоже платформоспецифичен. Так вот, почему бы компилятору бы аналогичным образом его не решить, м?
Ну значит вам везёт и компилятор, которым вы пользуетесьОбычный avr-gcc. Он там есть на godbolt. И я думаю, что все avr компиляторы должны так работать. Иначе просто нет смысла. Вот у вас есть килобайт флэша и 64 байта оперативной памяти, а компилятор такой раз и все удвоил, дополнив нулями.
Мы ведь тут обсуждаем не конкретный компилятор, а языкНу мой изначальный пойнт был в том, что почему бы компилятору это не делать, и что я как минимум знаю случаи, когда (2N) = (N)*(N) работает. В ответ на что вы меня зачморили, закидав примерами, о работоспособности которых я ничего не утверждал.
Еще раз. Я согласен, что не блещу знаниями стандарта, но я привел пример рабочего платформоспецифичного кода. Выш запрос на int128=int64*int64 в одну инструкцию тоже платформоспецифичен. Так вот, почему бы компилятору бы аналогичным образом его не решить, м?
Разве есть гарантия, что, например, все используемые библиотеки собраны с одинаковым значением 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.
Вот только в вашем случае было не (2N) = (N)*(N). У вас было (2N) = (2N)*(2N). Которые компилятор смоге превратить, в конкретном случае, в (2N) = (N)*(N). За что ему, конечно, честь и хвала — вот только эта оптимизация не гарантируется.
Потому что 128-битный int — это, во-первых, неудобно, а во-вторых — это всё равно не даёт вам вожделённой инструкции int128=int64*int64.В примере выше дает. Просто размеры другие. Вы сами сказали, что это на совисти компилятора, как
В примере выше дает. Просто размеры другие.Нигде не даёт. Там везде одинаковые размеры у всех величин (но не всех переменных)
Вы сами сказали, что это на совисти компилятора, какНа совести компилятора — возможность иногда разглядеть, что старшая половина числа — нулевая. И сделать соотвествующую оптимизацию. Он это делает не всегда, а тогда, когда ему это хочется.
Посмотрите на то, с чего мы начали:
В известных мне языках нет операции, которая бы из двух чисел размера N бит делала их произведение размера 2N бит.В ваших примерах — её тоже нет.
Про то, что можно свести явно задачу к умножению 128-битных чисел и помолиться на то, чтобы компилятор не передумал — я писал давным-давно.
Вот только «помолиться на то, чтобы компилятор не передумал» — это проблема. А вдруг передумает? Имеет право.
Да и вообще — священник, который молится богу компиляторов — это явно не тот специалист, которого я хотел бы видеть в штате.
Он это делает не всегда, а тогда, когда ему это хочется.AVR-GCC всегда. Ну либо пруф обратного в студию.
В ваших примерах — её тоже нет.А что это тогда по-вашему?
священник, который молится богу компиляторовМы же не незадокументированные хаки обсуждаем.
Мы же не незадокументированные хаки обсуждаем.Принято.
AVR-GCC всегда. Ну либо пруф обратного в студию.Нет-нет-нет. Пруф обратного требовался бы если бы мы обсуждали незадокументрованные хаки.
А поскольку вы сказали, что их мы обсуждать не будем — то, пожалуйста, документацию, гарантирующую что AVR-GCC так будет вести себя всегда — в студию.
А что это тогда по-вашему?Незадокументированный хак, однако. Да — оно так работает, но нигде нет никакий документации, которая бы обещала нам, что оно всегда будет работать так — и в будущих версиях GCC и на других компилятора — тоже.
Дело в том, что компилятор, ведущий себя иначе, бесполезен. 16-битные операции на 8-битном АЛУ приведут к радикальному росту обьемов кода и расходу памяти, что немыслимо в условиях существующих ограничений.
Думаю, на текущий момент мы более/менее поняли друг друга, и я считаю дальнейшее углубление в вопрос не стоящим трудозатрат. Меня устроит, что я не прав, если хотите.
Думаю, на текущий момент мы более/менее поняли друг друга, и я считаю дальнейшее углубление в вопрос не стоящим трудозатрат. Меня устроит, что я не прав, если хотите.
НЛО прилетело и опубликовало эту надпись здесь
С точки зрения стандарта компиляция с разными размерами int'ов — это просто разные реализации.Нет.
Вы же не говорите, что существование разных компиляторов С с разными размерами интов чему-то там противоречит?Пока вы не пытаетесь слинковать объектники, ими собранные в одной программе — нет. Если пытаетесь — ССЗБ. Потому что это нарушение ODR и ничем хорошим это не кончается.
На самом деле меня удивляет, что вы про компиляторы под DOS/Win16 не вспомнили. Вот там, как раз, есть пример компиляторов, у которых может размер указателя меняться. Но линковать модули, написанные на языке C и собранные в разных режимах запрещено. Для «продвинутых» есть расшиения (вот все эти far> и near) — но это уже не C: если расширять язык, так можно и какой-ниубудь оператор расширяющего умножения ввести. Зачем эти сложности с разными модулями и прочим?
НЛО прилетело и опубликовало эту надпись здесь
Да, потому что реализация в том числе определяет размер подобных типов данных. А дальше искомое утверждение следует тупо согласно формальной логике.Как оно следует? Исходное утверждение — вот оно:
Что принципиально мешает добавить какой-нибудь флаг типа -use128int (и собирать все тяжелые мат модули с ним)?Или вы имеет в виду, что мы можем собирать тяжёлые матмодули таким образом — только не сможем линковать их с лёгкими? Я боюсь, что это слишком тонкое расщепление волос для человека, который искренне считаете, что стандарт — это такая туалетная бумага, только жёсткая и с закорючками, а смотреть нужно только на тот код, который делает компилятор.
Он ведь слинкует — а потом, когда «hello world» — заработает, а большая программа — нет, начнёт ещё и на разработчиков «баллоны катить».
Потому, что вы просите какую-то отдельную операцию вместо обычного символа умножения. вместо того чтобы написать кодУ меня есть ощущение, что вы действительно не понимаете насколько глубока кроличья нора. Давайте я ваш пример доведу до полной, компилирующейся, программы:
Можно так написать? Что-то мне подсказывает, что да.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 просто не получится…del
НЛО прилетело и опубликовало эту надпись здесь
Скажу коротко: это уже не C.
Да, расширить можно любой язык — тут я не спорю. И даже библиотекой то же самое можно. Но это будет уже непереносимая программа, заточенная под конкретный компилятор.
Собственно вся наша длинная дискуссия родилась из того, что есть достаточно много людей, не осознающих, что язык и компилятор — это, всё-таки, разные вещи…
P.S. И кстати, то, что вы не можете отобразить «в нативном C» константу типа __int128, потому что в C и такого типа-то нет! Это, строго говоря, расширение компилятора. Впрочем обсуждаемый вопрос интересен и в 32-битном виде, а типы uint32_t и uint64_t — стандартные, так что на этом я внимание на заострял…
Да, расширить можно любой язык — тут я не спорю. И даже библиотекой то же самое можно. Но это будет уже непереносимая программа, заточенная под конкретный компилятор.
Собственно вся наша длинная дискуссия родилась из того, что есть достаточно много людей, не осознающих, что язык и компилятор — это, всё-таки, разные вещи…
P.S. И кстати, то, что вы не можете отобразить «в нативном C» константу типа __int128, потому что в C и такого типа-то нет! Это, строго говоря, расширение компилятора. Впрочем обсуждаемый вопрос интересен и в 32-битном виде, а типы uint32_t и uint64_t — стандартные, так что на этом я внимание на заострял…
Но вы же согласны, что взаимодействие кода снюансами процессорной архитектура это таки дело компилятора? А раз всякие там gcc-extentions у нас уже есть. то почему бы и нет?) Ну то есть не понятно, почему вы требуете для этого отдельный язык, или что вы там хотели в начале ветки.
Напомню начало этой ветки:
Ну и дальше пошло усиленное натягивание совы на глобус.
Но это не сделает обычный C языком, на котором такое возможно записать «символом умножения» — на что вы, как бы, весьма таки сильно упирали поначалу. Заметьте, кстати, что вы получили и ответ на свой второй вопрос тоже: да, в GNU C 5+ (но не GCC 3.x или GCC 4.x) вы можете выбрать руками конкретную реализацию умножения, в том числе ту, о которой мы говорим.
В тех случаях, когда компилятор как-то может доказать, что переполнения не будет — компилятор Go может произвести оптимизацию, но, опять-таки — не обязан. Как и компилятор C не обязан превращать
mayorovp: Вообще говоря, современные процессоры умеют перемножать два 64-битных числа с получением 128-битного результата, так что арифметика с основанием 264 вполне достижима (и даже будет быстрее стандартной), если писать на ассемблере.
Проблема в том, что в языках программирования такой операции умножения обычно нет…
BigBeaver: Это разве не компилятор должен решать?
mayorovp: А что он может решить, когда нужной операции просто нет?
BigBeaver: В каком языке нет символа умножения? В каком языке высокого уровня вы руками выбираете конкретную реализацию умножения в зависимости от типа? Или как-то раскройте что ли мысль.
…
Ну и дальше пошло усиленное натягивание совы на глобус.
А раз всякие там gcc-extentions у нас уже есть. то почему бы и нет?)Потому что это уже не будет программой на языке C, очевидно. Речь-то шла о программах на распространённых языках (C, C#, Go, Java, Pascal и так далее). В редких, экзотических языках (типа Форта) подобные конструкции есть. Также возможны расширения языка, позволяющие записать подобные вычисления (про
__builtin_mul_overflow я, кстати, знал, но не подумал, что её можно и для этой цели применить — красивый хак, на самом деле).Но это не сделает обычный C языком, на котором такое возможно записать «символом умножения» — на что вы, как бы, весьма таки сильно упирали поначалу. Заметьте, кстати, что вы получили и ответ на свой второй вопрос тоже: да, в GNU C 5+ (но не GCC 3.x или GCC 4.x) вы можете выбрать руками конкретную реализацию умножения, в том числе ту, о которой мы говорим.
Но вы же согласны, что взаимодействие кода снюансами процессорной архитектура это таки дело компилятора?До некоторой степени. Компилятор в любом случае остаётся в рамках языка. Он может сделать хуже, чем позволяет спецификация и математика, но никак не лучше. Скажем, компилятор C может опустить выражение «x = y << z;» до одной ассемблерной инструкции, а компилятор Go, в общем случае, не может — потому что тогда сдвиг на 257 будет неправильно обрабатываться.
В тех случаях, когда компилятор как-то может доказать, что переполнения не будет — компилятор Go может произвести оптимизацию, но, опять-таки — не обязан. Как и компилятор C не обязан превращать
c = (unsigned __int128)a * b;. А вот уже описанный вызов __builtin_mul_overflow позволяет всё описать точно — но это уже не C, это его расширение.Ну то есть не понятно, почему вы требуете для этого отдельный язык, или что вы там хотели в начале ветки.Потому что пользоваться расширениями — это такое… напишите вы программу нашпигованную
__builtin_mul_overflow, а потом вам скажут быстренько скомпилировать её под Windows (она ж у вас на C, в чём проблема) и… что дальше?Ну вот странно, что сравнивают с методом Карацубы, а не Тоома-Кука.
Последний требует O(n^(1+ε)), и это ε можно уменьшать как угодно (ценой роста коэффициента), и по сравнению с O(n*log(n)) это по-прежнему несравнимо. Хотя на практике переходят к Ш-Ш на числах от нескольких десятков килобит…
Последний требует O(n^(1+ε)), и это ε можно уменьшать как угодно (ценой роста коэффициента), и по сравнению с O(n*log(n)) это по-прежнему несравнимо. Хотя на практике переходят к Ш-Ш на числах от нескольких десятков килобит…
Этот метод (а также методы Шенхаге-Штрассена и Фюрера) работает с двоичными кодом. Поэтому на практике эти методы не дают практически никакого выигрыша в скорости.
Мы же все работаем в десятичной системе, это компьютер работает с двоичным кодом. Если мы вводим какие-нибудь 2 числа, например 1,000,000 и 35,000,000, и хотим их перемножить, то сначала их необходимо преобразовать в двоичный код (многократно разделив на 256 и сохранив остатки как char(byte), что увеличить память). Далее из каждого байта Вам необходимо вытаскивать биты, что оказывается не такой уж быстрой операцией. И только после этого возможно применение данных методов. Где выигрыш? Кстати далеко не во всех языках программирования возможны операции с битами. Можно, конечно, попробовать брать байты непосредственно из памяти, но…. Эти точки обозначают и вопросы, и проблемы, и многое другое.
HabrArkady
Мы же все работаем в десятичной системе, это компьютер работает с двоичным кодом. Если мы вводим какие-нибудь 2 числа, например 1,000,000 и 35,000,000, и хотим их перемножить, то сначала их необходимо преобразовать в двоичный код (многократно разделив на 256 и сохранив остатки как char(byte), что увеличить память). Далее из каждого байта Вам необходимо вытаскивать биты, что оказывается не такой уж быстрой операцией. И только после этого возможно применение данных методов. Где выигрыш? Кстати далеко не во всех языках программирования возможны операции с битами. Можно, конечно, попробовать брать байты непосредственно из памяти, но…. Эти точки обозначают и вопросы, и проблемы, и многое другое.
HabrArkady
Во-первых, эти методы работают в любой системе счисления, а не только в двоичной.
Во-вторых, зачем вообще вытаскивать отдельные биты из байтов?
Вообще, есть алгоритм умножения для чисел длинной от 131 до 1200 бит, который использует свойства необычной системы счисления. Для меньших чисел быстрее обычное умножение, а для бо́льших — умножение Карацубы.
Работают. Для алгоритмов Карацубы и Тоома-Кука все равно какая система исчисления. А для этого алгоритма желательна двоичная. Этот метод и методы Шенхаге-Штрассена и Фюрера являются частными случаями быстрого преобразования Фурье. А в нем желательно выбирать основания — 2**n+1. Желательно, но не обязательно. Выбрав такое основание можно умножение заменить сдвигом. Возможно выбрать другое основание, например 10, тогда придется или действительно умножать, или заменить множеством сдвигов и их сумм.
Сложность O(N log(N)), ради чего все это и делается, — она для бинарной системы, для других систем — сложность другая.
Сложность O(N log(N)), ради чего все это и делается, — она для бинарной системы, для других систем — сложность другая.
Поясните, пожалуйста, о каком основании в быстром преобразовании Фурье идёт речь и откуда взялось 2**n+1. Потому что если речь о длине вектора, то наиболее предпочтительными в плане скорости являются всё-таки 2n и 4n.
Быстрое преобразование Фурье точно так же работает в любых системах счисления.
Кстати, чистая двоичная система счисления вообще никогда в алгоритмах длинной арифметики не используется. Используются основания 216, 232, 264, 105, 109 и 1019
Да, Вы правы. Быстрое преобразование Фурье точно так же работает в системах счисления, перечисленных Вами. Насчет двоичной системы, я не имел ввиду основание 2. Я неправильно сформулировал.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Публикации
Математики обнаружили идеальный способ перемножения чисел