Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Приведу примерчик. 17.12.04 23:11 Число просмотров: 6677
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 17.12.04 23:12 Количество правок: 1
|
> Нет, компилятор был VC6. Лимбы в два раза меньше - проходов
> по циклу - в 2 раза больше (производительность ровно в 2
> раза меньше). Это раз. Проверять переполнение в случае
> ассемблерной реализайии не нужно - можно сразу использовать
> команду сложения с переполнением, в случае с C-шной
> реализацией (уменьшенный лимб) вместо одной команды на
> каждый лимб используется минимум 3-4 (сложение-проверка
> переполнения-ветвление-прибавление переполненного разряда)
> итого внутренний цикл в 4 раза длиннее, кроме того,
> ветвления очень плохо влияют на конвейер (тем более в
> случае с числами предсказания ветвлений работать не будут).
> В общем всего набирается примерно на 1000 процентов только
> на сложении/вычитании.
unsigned16 a[ N ], b[ N ];
unsigned32 x = 0;
for( i = 0; i < N; i += 1 ){
x += a[ i ];
x += b[ i ];
a[ i ] = x;
x >>= 16;
}
---
Какие тут проверки и разрушения конвеера? И это не смотря на то, что современные процессоры точно могут предсказать ветвления.
Если Х - аккумуляторный регистр, то два(!) сложения, одна пересылка, один сдвиг (жаль нельзя присвоить старшую часть/перенос младшей). И ни каких сравнений.
> > > Просто так (умножение в столбик) не получится.
> Для
> > снижения
> > > сложности умножения там применяются хитрые
> алгоритмы,
> > > некоторые из которых я так и не понял.
> >
> > А что же мы все "столбиком" на бумаге считаем?
> Контекст потерян. 3 сообщения назад я упомянул эффективные
> методы умножения со сложностью O(N1.5) и
> меньше. Вы сказали, что "не вдавались в подробности, может
> что то в этом роде и получается". Именно к этой фразе
> относится мое замечание о том, что в случае с умножением в
> столбик ничего не получится. То есть при умножении в
> столбик о такой сложности приходится только мечтать.
> А считаем мы в столбик потому, что довольно трудно на
> листике сделать быстрое преобразование фурье и не ошибиться
> при этом.
Не ужели для умножения нужно быстрое преобразование Фурье. Разве оно не сложнее, чем простое умножение столбиком :-(.
> > И в довесок. 10 раз быстрее, 100, 1000. Если
> факторизация
> > будет сложности log(n), то быстродействие не будет
> играть
> > большого значения, если оно не будет уж настолько
> > тупым/тормозным. Какая разница - будет ли думать
> компьютер
> > микросекунду или милисекунду над задачей разложения
> > килобитного числа. А для n/ln(n) любого быстродействия
> > будет мало, чего уж там говорить об одном или двух
> > десятичных порядках.
> Дык опять повторюсь 10 раз это для СЛОЖЕНИЯ. Никакого более
> эффективного алгоритма для сложения придумать нельзя. Можно
> только оптимизировать реализацию. А вот для других операций
> - используются самые эффективные из известных на сегодня
> алгоритмов
Я здесь как раз о том, чтоб не над эффективностью алгоритма работы с длинными числами работать, а над самим алгоритмом факторизации.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
