Требуется быстро перемножать 32-разрядные двоичные полиномы. Они перемножаются как обычные двоичные числа в столбик, только вместо сложения там XOR. Блин, держу в руках кремень PIV 3000, а чем он лучше проца Z80 из раздолбанного АОНа? Такой же кусок окаменелого дерьма, умножать НЕ УМЕЕТ!!! =((( А че спрашиваю, нет ли там у процов семейства Intel каких-нить недокументированных возможностей или префиксов перед обычными командами беззнакового умножения, чтобы полиномы умножать?
А чем это лучше, чем крутить ручку арифмометра? По сравнению с Z80 есть такое преимущество, что таблицу умножения для 8-битных полиномов можно хранить в памяти на 128 кило и извлекать за одну ссылку по памяти. Но хочется что-то посерьезнее изобразить на 32-разрядном компе. Перемножить не проблема, проблема бысто перемножить, со временем, сравнимым со встроенным умножением обычных чисел. А иначе смысла нет, тормозить будет.
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% программ не перемножают полиномы (и уж тем более в критических по времени частях), но перемножают числа.
Да не гони! Там были многочлены Чебышева, у них экстремально-хорошие свойства, а не просто сходимость, как у Тейлора.
И здесь тоже можно отослать к книжке "Алгебраические и алгоритмические основы: Элементарное введение в эллиптическую криптографию":
Удивительно, но я как раз читаю именно эту книжку и эту главу! В принципе, как я понял, умножение многочленов по мет.Карацубы реализовать не просто (если не использовать готовые исходники), а вот написать собственный модифицированный классический алгоритм перемножения с помощью таблиц - вполне реально, особенно если это кольцо GF(2)[X]
profile003 Может, я чего-то не понимаю, но алгоритм Карацубы весьма прост. Вот как я его реализовывал (конечно, догадываюсь, что это не самая лучшая реализация... ) Код (Text): void xmultiply_karatsuba (const lnum & right, lnum & result) const { size_t l = std::max (length(), right.length()) / 2; lnum a1 = *this >> l, b1 = right >> l, a2 = this->last_digits (l), b2 = right.last_digits (l), r1 = a1 * b1, r2 = (a1 - a2) * (b2 - b1), r3 = a2 * b2; result = (r1 << 2*l) + (r1 << l) + (r2 << l) + (r3 << l) + r3; } где operator* сводится к функции: Код (Text): void xmultiply (const lnum & right, lnum & result) const { if (std::max (length(), right.length()) > 100) xmultiply_karatsuba (right, result); else xmultiply_comba (right, result); }
Вообщем это решение "в лоб" идеи алгоритма умножения, а в книжке написано про эффективное перемножение, которое сводится к декомпозиции перемножаемых полиномов в элементарные полиномы и рекурсивное применение алгоритма Карацубы .... но я пока это еще читаю
Какой же это "умножение в лоб", если тут оба полинома делятся пополам, получившиеся 4 части перемножаются между собой рекурсивно, и всё объединяется?
это базовая схема умножения алгоритмом Карацубы позволяет распараллелить алгоритм на несколько процессоров