перемножение полиномов

Это вы про что, про перемножение длинных полиномов?
Для 32 разрядных имхо самое быстрое это цикл на 32 оборота с регистрами, в память лазять не надо... А если побайтово в столбик то нужно будет в таблицу умножения лазать 16 раз ну и тоже много-много ксорить...

 

Вот, подкинули ссылочку по сабжу
Fast Galois Field Arithmetic Library in C/C++
http://www.cs.utk.edu/~plank/plank/papers/CS-07-593/

Обещают:
The performance of these procedures has been tuned to be very fast. A multiplication table is employed when w=8. Log and inverse log tables are employed with w=16, and seven multiplication tables are employed when w=32.

 

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

 

Посмотрел библиотеку... Для перемножения 32-битных полиномов по модулю там используются два вложенных цикла на 4 оборота каждый (и того шышнадцать однобайтовых комбинаций) и семь предвычесленных таблиц на 65536 входов каждая. Все это весьма поучительно, познавательно и интересно, но у меня огромные сомнения, что это будет работать быстрее простой асмовской процедуры хотя и на 32 оборота, но зато все данные и редуцирующий полином находятся в регистрах и плюс флаги сами собой устанавливаются. Однозначно на порядок медленнее должно быть у них, но возможно и быстрее аналогичной Си-шной процедуры, которя там используется к примеру для 31-битных полиномов.

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

 

Слава богу, что вы не разрабатываете процессоры.

 

Для перемножения 32-разрядных полиномов у меня получился следующий код, работоспособность не проверял еще:

Код (Text):

1.  xor ebx,ebx //результат
2.  mov ecx,32
3. @lll:
4.  shr edx,1 //второй множитель
5.  jnc @nobit
6.  xor ebx,eax //первый множитель
7. @nobit:
8.  shl eax,1
9.  jnc @noreduct
10.  xor eax,esi //редуцирующий полином
11. @noreduct:
12.  loop @lll

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

 

persicum
И не говори!
Обязательно надо в проц общего назначения добавить еще и разложение фурье одной командой. Очень нужно!
Да и функционал расчета кредитных рисков в командах проца представлен очень бедно - требует срочного расширения.
А мне вот в проце крайне не хватает математики эллиптических кривых в add/mul - надо срочно добавить, уже звоню в Intel.
Иначе лажа а не проц - пользоваться невозможно!

 

SSE3 вроде делает шаги в этом направлении и в направлении комплексных чисел.

 

persicum

Не кури больше этого SSE3 - это всего лишь несчастный десяток команд, которые забыли сделать в SSE2 На SSE даже синус предлагается ручками считать, что выходит быстрее, чем на FPU. Но, в принципе, насчет комплексных чисел можно согласится - горизонтальные операции помогают. Только они пока тормозные Правда может это на моем устаревшем железе ибо на феномах\пенринах еще не смотрел.