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

Требуется быстро перемножать 32-разрядные двоичные полиномы.
Они перемножаются как обычные двоичные числа в столбик, только вместо сложения там XOR. Блин, держу в руках кремень PIV 3000,
а чем он лучше проца Z80 из раздолбанного АОНа? Такой же кусок окаменелого дерьма, умножать НЕ УМЕЕТ!!! =(((

А че спрашиваю, нет ли там у процов семейства Intel каких-нить недокументированных возможностей или префиксов перед обычными командами беззнакового умножения, чтобы полиномы умножать?

 

del

 

А чем это лучше, чем крутить ручку арифмометра?
По сравнению с Z80 есть такое преимущество, что таблицу умножения для 8-битных полиномов можно хранить в памяти на 128 кило и извлекать за одну ссылку по памяти. Но хочется что-то посерьезнее изобразить на 32-разрядном компе. Перемножить не проблема, проблема бысто перемножить, со временем, сравнимым со встроенным умножением обычных чисел. А иначе смысла нет, тормозить будет.

 

скорость "умножения обычных чисел" http://wasm.ru/forum/viewtopic.php?id=21543.

 

persicum тебе надо перемножение полиномов или их перемножение по модулю как в CRC? В принципе это достаточно легко ускорить через таблицу умножения из 256 или 65536 элементов. По скорости это будет сравнимо с арифметическим умножением - всего 4-8 поисков по таблице в сache. По-другому - никак. Это редкая операция, поэтому её нет ни в одном процессоре.

 

Тем что для достижения подобной скорости ручку нужно крутить со сверхзвуковой скоростью

 

Может я не прав но возможно имеет смысл смотреть в сторону MMX, SSE2, SSE3 ...

К примеру есть такая замечательная команда:

XORPS xmm, xmm/m

XORит за раз число длинной в 128 бит

 

В принципе нужно перемножать по модулю, но не столь важно, главное как быстрее, модуль можно будет потом взять от результата скалярного произведения векторов полиномов. Вот сижу, думаю, и в упор не вижу, как CRC-шные таблицы могут тут помочь. Это что - остатки от чисел вида XX00000000. Вот прикидываю - двоичное умножение требует 32 оборота, умножение байтами в столбик требует целых 16 оборотов.
А вот 16-битные полиномы можно перемножать за одну или три ссылки по памяти через дискретные логарифмы. Берем логарифмы, складываем, берем антилогарифм суммы, и все, как на логарифмической линейке. Но для 32-битных такая таблица логарифмов будет весить 4Гига*4байта.

А зря! Что стоило заменить сложение на XOR в обычном умножении? Это далось бы разработчикам абсолютно даром, и совершенно не понятно, почему такой простой фичи нигде нет в железе.

 

Потому что 99.9999% программ не перемножают полиномы (и уж тем более в критических по времени частях), но перемножают числа.

 

Для криптографии, помехоустойчивых кодов и генераторов случайных чисел пригодилось бы...

 

Кстати z80 выполнял вычисление тригонометрии с помощью разложения функции в ряд Тейлора

 

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

 

В математике я не силён, но Calculator спектрум вычислял SIN(x) именно так.

 

Читайте главу 38 в Algorithms for programmers.

 

И здесь тоже можно отослать к книжке "Алгебраические и алгоритмические основы: Элементарное введение в эллиптическую криптографию":

 

Удивительно, но я как раз читаю именно эту книжку и эту главу!
В принципе, как я понял, умножение многочленов по мет.Карацубы реализовать не просто (если не использовать готовые исходники), а вот написать собственный модифицированный классический алгоритм перемножения с помощью таблиц - вполне реально, особенно если это кольцо GF(2)[X]

 

profile003
Может, я чего-то не понимаю, но алгоритм Карацубы весьма прост.
Вот как я его реализовывал (конечно, догадываюсь, что это не самая лучшая реализация... )

Код (Text):

1.     void xmultiply_karatsuba (const lnum & right, lnum & result) const
2.     {
3.         size_t l = std::max (length(), right.length()) / 2;
4.         lnum
5.             a1 = *this >> l,
6.             b1 = right >> l,
7.             a2 = this->last_digits (l),
8.             b2 = right.last_digits (l),
9.             r1 = a1 * b1,
10.             r2 = (a1 - a2) * (b2 - b1),
11.             r3 = a2 * b2;
12.         result = (r1 << 2*l) + (r1 << l) + (r2 << l) + (r3 << l) + r3;
13.     }

где operator* сводится к функции:

Код (Text):

1.     void xmultiply (const lnum & right, lnum & result) const
2.     {
3.         if (std::max (length(), right.length()) > 100)
4.             xmultiply_karatsuba (right, result);
5.         else
6.             xmultiply_comba (right, result);
7.     }

 

Вообщем это решение "в лоб" идеи алгоритма умножения, а в книжке написано про эффективное перемножение, которое сводится к декомпозиции перемножаемых полиномов в элементарные полиномы и рекурсивное применение алгоритма Карацубы .... но я пока это еще читаю

 

Какой же это "умножение в лоб", если тут оба полинома делятся пополам, получившиеся 4 части перемножаются между собой рекурсивно, и всё объединяется?

 

это базовая схема умножения алгоритмом Карацубы

позволяет распараллелить алгоритм на несколько процессоров