У кнута во 2-м томе целый раздел (4.3) про вычисления с произвольной точностью17.08.04 13:12 Число просмотров: 1443 Автор: amirul <Serge> Статус: The Elderman
Обработка больших значений. Часть вторая.16.08.04 19:55 Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman Отредактировано 16.08.04 19:59 Количество правок: 3
Писал когда-то в первой части недавно (25-DEC-03 "http://bugtraq.ru/cgi-bin/forum.mcgi?type=sb&b=2&m=96056"), что деление медленное получилось. Тред не редактируется, ничего не добавляется. Тогда я "игрался" с 64 битными числами. Подкрутил библиотечку до бесконечно больших чисел (ограничено памятью писюка). Деление какое-то получается не просто медленное, а полная %опа. 256-ти килобитное число секунду делится на 32-х битное, а сколько будет делиться гигабитное - не дождешься. При увеличении разрядности в два раза скорость падает в четыре раза. Умножение происходит примерно в 10000-100000 раз быстрее. Ну ладно бы раз в десять разница была - в тысячу раз быстрее деление сделать. Ну знаю как ускорить в 2-3 раза, а в тысячу - нужно что-то с алгоритмом делать.
Спасибо leo за ссылочку "http://leo.yuriev.ru/files/simple-rsa.rar". Пеимущества этой библиотечки в том, что без ассемблера. Умножение там действительно быстрое (хотя реализация - полная задница), но у меня значительно быстрее. Деление такое же, только медленнее - я быстрее вычисляю позицию старшего разряда результата. Короче так же умножение "столбиком", деление уголком. Я умножаю 32-х битные числа, используя MUL (всего несколько тактов), количество итераций = произведение количества 32-х битных слов во множителях, каждая итерация - умножение, пару сложений и несколько MOV. Делю "уголком": сначала двигается делитель до совпадения старших разрядов с делимым влево (количество бит сдвига вычисляется и без сдвига, сдвиг быстрый), потом сравнение, если меньше - вычитание и установка разряда в результат, сдвиг делителя на 1 разряд обратно, и таких итераций столько, на сколько делитель двигался влево. Похоже тормоза из-за побиттовых сдвигов больших значений. Кто-то тут на форуме предлагал делить "большими кусками". Да, можно обойтись без побиттового сдвига, но тогда вспомним деление "уголком" - потребуется вычислять "разряд", мысленно на него умножать, сравнивать, если ошиблись уменьшать разряд..., короче гемор, дополнительная память и, как результат, медленнее. Там же предлагалось строить таблицу (как в том посте было написано "для константного делителя"), построение таблицы для 256 больших значений отожрет немерено памяти и времени, хотя само деление потом будет быстрее. Деление почти равных чисел может свестись к одному-нескольким сравнениям/вычитаниям без умножений, а тут по алгоритму 256 минимум надо выложить, а то и 2^32. Выгодность побиттовых сдвигов при делении уголком в том, что подбирать множитель и умножать не надо - либо вычитать (на 1 умножать не надо) либо нет (на 0 умножать тоже не надо).
Читал "http://www.gnu.org/software/gmp/manual/html_mono/gmp.html#Algorithms", частично не понял, то что понял - не катит. Че делать, наверняка где-то есть на простом русском языке описание что и как, конкретно, понятно и гарантированно быстро, по сравнению с "уголком".
У кнута во 2-м томе целый раздел (4.3) про вычисления с произвольной точностью17.08.04 13:12 Автор: amirul <Serge> Статус: The Elderman
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
