Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Тут наверное недопонимание какое-то... 25.03.04 16:36 Число просмотров: 4056
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
|
> Тут наверное недопонимание какое-то...
Естесственно, поэтому и хочется поподробнее разобраться, наверняка тут на форуме не я один всего этого непонял.
Ковыряюсь тут над библиотечкой, работающей с большими числами, так вот у меня деление пока получается в 50 раз медленнее умножения. Хотелось бы достичь эквивалентной скорости.
> Указанная мной оценка была для операция инверсии x через > x^(p-2). > > Что же касатеся Ваших 256 сравнений и вычитаний, то это для > деления. > Для деления же я предлагал как бы то же самое, но > основанное на блочном принципе.
Вот это и интересно, может поэтому и умножение у меня быстрее, что я его по-другому от деления реализовал, "по блочному принципу". Пока не догадался как это с делением сделать.
> Т.е. вы сравниваете не бит, а блок битов. Если у вас
Естественно, когда я сравниваю делимое и делитель, я сравниваю поблочно - кусками по 32 бит в соответствии с ИА32 архитектурой.
> фиксированный делитель, т.е. порождающий полином, то вы для > него всегда можете заготовить все варианты чисел на которые > его надо умножить, чтобы получить все значения блока. > Точнее заготавливать надо варианты умноженного делителя. > Тогда можно вычитать сразу блок за один раз, а не один бит. > И сравнение делать блока, а не одного бита. Скажем если > побить на 8-битные блоки, то вместо 256 сравнений и
Если бы деление можно было реализовать еще проще/быстрее чем "столбиком", как учат в начальной школе, то, наверное, и учили бы по-другому.
> возможных вычитаний будет 32, в то время как операция на > 32-битной машине как для бита так и для 8-битного слова > одинаковые. > Итого накладные расходы - это 256 значений делителя в > таблице. Дык у меня 8 вычитаний 32битных блоков и получается.
В двоичной системе легче делить, чем в десятиричной, там умножать не надо, поскольку умножение на 0 дает 0, а умножение на 1 дает само число.
Естественно, если делитель больше делимого, то результат 0 и делить ничего не надо.
Двигаем делитель, пока старшие биты не займут одинаковые позиции, далее цикл если делимое больше делителя (сдвинутого), то вычитаем одно из другого и ставим 1 в соответствующий разряд результата, двигаем вправо делитель. Деление столбиком напоминает, без умножения, естественно?
Фрагмент функции представить для общего обозрения?
Если не трудно (имеется в наличии) - представте вашу идею на алгоритмическом языке...
|
|
|