# #c #assembly #x86 #twos-complement #bigint
Вопрос:
Итак, у меня есть следующее определение структуры для моего 1024-разрядного числа (я хочу использовать здесь представление дополнения 2, и я нахожусь в 32-разрядной системе).:
typedef struct int1024
{
int32_t num[32]; //should I use uint32_t?
} int1024;
В основном массив, содержащий сегменты числа.
Для добавления с тех пор подписанное и неподписанное добавление-это одно и то же. Я могу просто воспользоваться инструкциями add и adc выполнить расширенную операцию для моего большего массива.
Теперь перейдем к умножению. Я смог заставить умножение без знака работать, используя комбинацию imul (используя верхний и нижний результаты) и adc используя классический O(n^2) алгоритм умножения. Однако для моих результатов мне нужно знаковое умножение. Я знаю, что люди говорят просто использовать версию со знаком величины. т. Е. возьмите дополнение 2, когда оно отрицательное, и в конце примените дополнение 2, если это необходимо. Но все дополнительные примечания и добавление 1 будут очень дорогими, так как мне нужно сделать много умножений. Существует ли техника для выполнения большого умножения со знаком для представлений чисел, подобных этому. (Я действительно не хочу никаких ветвящихся или рекурсивных вызовов здесь). Я думаю, что одна из моих главных проблем заключается в том, как справиться с переносом и высокой частью умножения отрицательных чисел. (просто идея, может быть, я мог бы использовать комбинацию умножения со знаком и без знака, но я не знаю, с чего начать). Если у вас нет времени на 1024 бита, будет достаточно 128-битного ответа (я просто обобщу его).
Комментарии:
1. Вы хотели бы использовать целочисленный тип без знака для элементов массива. Обратите внимание, что при умножении NxN->N целых чисел (ширина аргумента = ширина результата) не имеет значения, является ли умножение операцией со знаком или без знака: наименее значимые N битов результата одинаковы. Является ли умножение подписанным или беззнаковым, имеет значение для наиболее значимых N битов широкого (NxN->2N) умножения или эквивалентной операции умножения. В этом случае наиболее значимые биты результата умножения со знаком могут быть легко сгенерированы из наиболее значимых битов беззнакового умножения.
2. Вы делаете это в качестве упражнения?
GMPБиблиотека делает это и многое другое. См.: gmplib.org кстати, то, что вы называетеnumих использованиеunsigned long longПО (если машина изначально 64 бит) и каждый подсчитывает количество клеток, так что они обрабатывают переменной длины, числа и увеличиваться по мере необходимости [который может все ускорить, так как это медленно, чтобы сделать 32 умножает если (например) каждое число используется только небольшое число битов]3. Отрицание относительно дешево по сравнению с умножением «от руки». Мой метод большой арифметики заключается в работе с 32-разрядными массивами и 64-разрядными промежуточными значениями.
4. @Флюгер На РУКЕ Я использовал UMLAL (Умножение без знака и накопление длинных), который делает 32×32 32 -> 64, очень удобно для распространения переноса. Есть ли что-нибудь подобное в x86 ISA?
5. @tum_: x86 всегда имел расширяющееся умножение, но все еще не имеет накопления. ( felixcloutier.com/x86/mul , до 64×64 => 128-разрядный в коде x86-64.) Intel имеет официальный документ, при сравнении с BMI2 MULX (расширение мул, что не касается флагов, поэтому оно не мешает АЦП звенят цепями, и меньше неявных операндов, только гексоген ввода), и против MULX Adox по/ADCX (Бродуэлла) допускать 2 независимых звенят цепями (в МВ и в): intel.com/content/dam/www/public/us/en/documents/white-papers/… для 512×64-битных или 512×512
Ответ №1:
Обратите внимание, что в 1024-разрядном целочисленном числе только самый верхний бит, бит 1023, является битом знака и имеет значение места -(2**1023) . Все остальные биты имеют нормальное (2**pos) значение места. т. е. все нижние «конечности» должны рассматриваться как беззнаковые, когда вы выполняете умножение на них.
У вас есть один знаковый бит и 1023 младших бита. Ни одного знака на конечность.
Кроме того, разница между умножением со знаком и без знака заключается только в верхней половине расширяющегося умножения (N x N => 2N бит). Вот почему x86 имеет отдельные инструкции для imul r/m64 и mul r/m64 для выполнения полного умножения в RDX:RAX (https://www.felixcloutier.com/x86/imul против https://www.felixcloutier.com/x86/mul). Но для нерасширения есть только imul r, r/m и imul r, r/m, imm которые компиляторы используют как для неподписанных, так и для подписанных (и так должны поступать люди).
Поскольку вам нужен 1024×1024 => 1024-битный продукт, который отбрасывает верхние 1024 бита, вы можете и должны просто сделать все это без подписи.
Когда вы пишете в asm, вы можете использовать любой размер блока, например 64-разрядный в 64-разрядном режиме, не ограничиваясь размером блока C.
Видишь https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/ia-large-integer-arithmetic-paper.pdf для того, как использовать BMI2 mulx (оставляет ФЛАГИ нетронутыми, чтобы не нарушать adc цепочки, и имеет только RDX в качестве неявного ввода, при этом другой источник и оба вывода являются явными, экономя на инструкциях MOV). И, при необходимости, также Broadwell ADOX / ADCX для параллельного запуска двух цепочек dep, чтобы получить больше ILP для данных BigInteger среднего размера, таких как 512×512-бит или 512×64-бит (которые они используют в качестве примера).