Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Поправки 26.03.04 18:49 Число просмотров: 4075
Автор: Xelator Статус: Незарегистрированный пользователь
|
К сожалению нет у меня уже исходников - ну ооочень давно было дело.
Попробуем еще раз на словах.
1) простое деление столбиком, которое используете вы содержит
- сравнение старшего бита делимого с делителем.
в первый раз они всегда равны, затем после первого вычитания следующие страшие биты делимого могут быть нулями.
- сдвиг делителя, чтобы его старший бит стоял там же где и текущий старший бит делимого
- вычитания делителя из делимого
И так по кругу. Если у вас делитель 256-битный, а делимое 512-битное (после умножения двух 256-битных чисел например), то потратим 256 сравнений, и в худшем случае 256 сдвигов 256-битного делителя и 256 вычитаний делителя из делимого. Если предположить что у нас поровну нулей и единиц в делимом (это ведь криптография и должно быть равномерное распределение?), то в среднем 128 сдвигов и вычитаний делителя.
2) блочное деление, которое я описывал дляфиксированногоделителя. если делитель нефиксированный, то ко времени работы алгоритма надо добавить время построения таблицы.
в нашем случае в роли делителя должен выступать порождающий элемент, т.е. величина фиксированная.
предварительные действия - они же генерация таблицы:
- выбрать размер таблицы , он же ширина блока. Возьмем 8 бит, размер таблицы тогда 256 ячеек.
- получить все числа такие, что они при умножении на делитель генерируют результат, у которого старшие 8 бит принимают всевозможные значения. Таковых должно быть 256 в нашем случае.
Получив таковые числа, построить таблицу, в которой каждый элемент равен результату умножения делителя на одно из чисел. Отсортировать эту таблицу по значению старших 8 бит результата.
Слов много, а на самом деле делов на полкопейки - например, берете полином у которого старшие биты поочередно заполняете 256 возможными значениями и делите обычным алгоритмом. Получается то, что нужно само собой.
Теперь блочный алгоритм деления.
- прочитать старший 8-битный блок 512-битного делимого
- по его значению выбрать элемент из таблицы (помните, мы ее сортировали так, чтобы само значение могло быть одновременно и индексом)
- вычесть 256-битное табличное значение из делимого
Итого сложность в операциях = 256/8 = 32 блока => 32 раза прочитать 8-битный блок из делимого, по этому индексу 32 раза прочитать 256-битное табличное значение и 32 вычесть это табличное значение.
У первого алгоритма = 256 сравнений, 128 сдвигов и 128 вычитаний
У второго = 32 чтения из делимого, 32 чтения из таблицы, 32 вычитания.
Надо понимать, что чтения здесь не стоят ничего - это просто адреса для вычитания.
Итого в 8 раз меньше вычитаний, нет вообще 128 сдвигов и 256 сравнений.
Прокатывает объяснение? Если да, то продолжим для трехчленов и пятичленов.
|
|
|