информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Где водятся OGRыПортрет посетителяЗа кого нас держат?
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
 С наступающим 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
все доски
FAQ
IRC
новые сообщения
site updates
guestbook
beginners
sysadmin
programming
operating systems
theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Тут наверное недопонимание какое-то... 25.03.04 16:07  Число просмотров: 4057
Автор: Xelator Статус: Незарегистрированный пользователь
<"чистая" ссылка>
> А при "делении столбиком" потребуется 256 сравнений, может
> быть, (в зависимости от результата сравнения) вычитаний
> плюс установления бита в соответствующий разряд результата
> и сдвигов в худшем случае.

Тут наверное недопонимание какое-то...
Указанная мной оценка была для операция инверсии x через x^(p-2).

Что же касатеся Ваших 256 сравнений и вычитаний, то это для деления.
Для деления же я предлагал как бы то же самое, но основанное на блочном принципе.
Т.е. вы сравниваете не бит, а блок битов. Если у вас фиксированный делитель, т.е. порождающий полином, то вы для него всегда можете заготовить все варианты чисел на которые его надо умножить, чтобы получить все значения блока. Точнее заготавливать надо варианты умноженного делителя.
Тогда можно вычитать сразу блок за один раз, а не один бит. И сравнение делать блока, а не одного бита. Скажем если побить на 8-битные блоки, то вместо 256 сравнений и возможных вычитаний будет 32, в то время как операция на 32-битной машине как для бита так и для 8-битного слова одинаковые.
Итого накладные расходы - это 256 значений делителя в таблице.

На самом же деле, если учесть что у нас трехчлены и пятичлены используются в качестве делителя, то таблица усыхает - ненулевых битов всего 3 или 5, => нужно хранить максимум два 8-битных слова и надо вычислять откуда их вычислять. Далее, на самом деле по скольку значение умноженного старшего бита будет всегда давать сравниваемый блок, то он будет зануляться, поэтому его можно занулять сразу, а не вычитать. Итого получается 2 или 4 элемента для каждого значения 8-битного блока.

Кроме того, значение блока можно очевидно использовать как индекс в этой таблицы, тогда алгоритм деления будет выглядеть примерно так для трехчлена:

// x - делимое
// y - делитель
// r - результат
r = x
for i=n/8 ; i>=0 ; i--
index = r[n];
r[n] = 0;
r[index1] ^= t1[index];
r[index2] ^= t2[index]

Здесь index1 и index2 зависят от выбранного фиксированного делителя. Ну если например он = 2^n + 2^k +1, то index1 - это расстояние от n до k а index2 - от k до 1.

Еще будет друггой эффект - некоторые блоки не удастся вот так вот просто поксорить, потому что в вышеуказанном примере ксорка происходит по выравненному на 8бит адресу, а может понадобиться поксорить например начиная с 33 бита, тогда надо иметь в таблице ни один элемент, а два, которые заранее сдвинуты, чтобы учесть такое безобразие. Это опять можно сделать заранее если полином фиксированный.

И наконец, даже если он не фиксированный перепостроение такой таблицы каждый раз может давать эффект. Это зависит от того, насколько делимое больше по порядку чем делитель. Если вы следите за такими вещами и приводите результаты вычислений всякий раз когда они могут стать больше чем степень порождающего элемента, тогда делимое может быть максимум вдвое шире делителя.
Но даже в этом случае, вроде бы можно перестраивать таблицу на ходу.
У меня это было давно, во времена Пентиума 1. Может раскладка затрат и поменялась.
<theory> Поиск 






Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach