Необходимо перемножить 2 64-хбайтных числа с наименьшими временными затратами. Думаю делать так: a0b0, b0a1 + b1a0, b0a2+b1a1+b2a0 и т.д., и по ходу дела суммировать их в результирующем буфере, учитывая перенос (команда adc). Значения индексов для a и b буду брать из регистров SSE2, куда перед вызовом функции буду их загонять из буфера в памяти (все значения вычислены заранее). Может быть, в дальнейшем написать макрос, продублировать его тело 256 раз, развернув тем самым цикл. А может, перемножать числа парами (есть там такая команда, название не помню). Кто занималься этим, подскажите плз.
64 байта??? Ты загнул. Может бита? Можно с помощью FPU, можно так (взято в книге Зубкова): Код (Text): ; беззнаковое умножение двух 64-битных чисел (X и Y) и сохранение ; результата в 128-битное число Z mov eax,dword ptr X mov ebx,eax mul dword ptr Y ; перемножить младшие двойные слова mov dword ptr Z,eax ; сохранить младшее слово произведения mov ecx,edx ; сохранить старшее двойное слово mov eax,ebx ; младшее слово "X" в еах mul dword ptr Y[4] ; умножить младшее слово на старшее add еах,есх adc edx,0 ; добавить перенос mov ebx,eax ; сохранить частичное произведение mov ecx,edx mov eax,dword ptr X[4] mul dword ptr Y ; умножить старшее слово на младшее add eax,ebx ; сложить с частичным произведением mov dword ptr Z[4],eax adc ecx,edx mov eax,dword ptr X[4] mul dword ptr Y[4] ; умножить старшие слова add eax,ecx ; сложить с частичным произведением adc edx,0 ; и добавить перенос mov word ptr Z[8],eax mov word ptr Z[12],edx Чтобы выполнить умножение со знаком, потребуется сначала определить знаки множителей, изменить знаки отрицательных множителей, выполнить обычное умножение и изменить знак результата, если знаки множителей были разными.
Нее, именно байта. У меня операции в группе точек эллиптической кривой, там числа - офигеть какие здоровые. А то, что ты написал у меня по идее в цикле должно крутиться несколько раз.
1. можно использовать умножение столбиком (как в школе ) -- это, видимо, то что ты и предлагаешь. 2. можно сделать быстрее: умножение 512x512 бит представляешь как 4 умножения 256x256 бит, каждое из которых как 4 128x128 и т.д. до 32x32. Умноженией 32x32 тогда потребуется 256 штук. Вообще рекомендую глянуть как подобные вещи реализованы в GMP (www.swox.com/gmp), OpenSSL или в любой другой более-менее серьезной библиотеке.
flankerx Хм, а в случае "школьного" умножения сколько? Вроде те же самые 256 и будут.. В принципе для (не очень) длинных чисел используется Karatsuba, в том числе по-моему и в GMP.
Упс. Ошибся немного ( Метод Карацубы немного иначе выглядит. В нем для умножения двух 512-битных чисел нужно вполнить ТРИ умножения 256x256: A=a1 | a2, B=b1 | b2 (a1 -- старшие разряды, a2 -- младшие). Тогда AB = a1b1 | (a1-a2)(b2-b1) | a2b2 Тогда для умножения 512x512 нужно 81 умножение 32x32. Теоретическая оценка "школьного" метода -- n^2, Карацубы -- n^lg3. В GMP используется несколько алгоритмов умножения: сначала "обычный", потом Карацуба, потом еще Тоома-Кука, а для очень больших чисел -- FFT.
Метод Карацубы имхо не оправдан на 64-хбайтных числах, хотя я могу ошибаться. З.Ы. А что за метод Тоома-Кука?
serious См. во втором томе Кнута, например. Но это метод для еще бОльших (чем Карацуба) чисел применяется.
Где-то видел, что метод Карацубы применяется в основном на 512-1024-хбайтных числах. З.Ы. Так всетаки, получается в данной ситуации лучше умножать "столбиком"?
serious ну почему? если столюиком -- 256 умножений, если карацубой -- 81. вот посмотрел в GMP -- там такая строка есть в конфигурационом файле #define MUL_KARATSUBA_THRESHOLD 18 я уж не знаю 18 чего (скоре всего лимбов, т.е. машинных слов), но 18*4 = 72 по-любому меньше 512 )
Сделал умножение таким образом: Код (Text): __asm { xor ecx, ecx // счетчик цикла up: // TODO: Проверка операндов на 0. movdqa xmm0, [multi_1 + ecx] // загрузка 2-х пар множителей pshufd xmm1, xmm0, 00010000b // Ai, Ai+1 (A0 | A1 | A0 | A0) movdqa xmm2, [multi_2 + ecx] // загрузка 2-х пар множителей pshufd xmm3, xmm2, 00010000b // Bi, Bi+1 (B0 | B1 | B0 | B0) pmuludq xmm3, xmm1 // пакетное умножение первых 2-х пар // xmm3 = (A1*B1) | (A0*B0) pshufd xmm4, xmm2, 00000001b // Bi, Bi+1 (B0 | B1 | B0 | B1) pmuludq xmm4, xmm1 // пакетное умножение оставшихся 2-х пар // xmm4 = (B0*A1) | (A0*B1) add ecx, 16 // смещение на 128 бит cmp ecx, 256 jnz up } Теперь вот непонятно, каким образом это все складывать, учитывая перенос. Если вытаскивать из xmm регистров дворды и потом их складывать при помощи adc, получается как-то гемморойно. Может, есть какой-нибудь другой способ?
