Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Нет, компилятор был VC6. Лимбы в два раза меньше - проходов... 17.12.04 16:45 Число просмотров: 5962
Автор: amirul <Serge> Статус: The Elderman
|
> По идее должно быть только в 2 (чуть более) раза при
> использовании Ассемблера. 10 получить можно при
> использовании слабооптимизирующего компилятора.
Нет, компилятор был VC6. Лимбы в два раза меньше - проходов по циклу - в 2 раза больше (производительность ровно в 2 раза меньше). Это раз. Проверять переполнение в случае ассемблерной реализайии не нужно - можно сразу использовать команду сложения с переполнением, в случае с C-шной реализацией (уменьшенный лимб) вместо одной команды на каждый лимб используется минимум 3-4 (сложение-проверка переполнения-ветвление-прибавление переполненного разряда) итого внутренний цикл в 4 раза длиннее, кроме того, ветвления очень плохо влияют на конвейер (тем более в случае с числами предсказания ветвлений работать не будут). В общем всего набирается примерно на 1000 процентов только на сложении/вычитании.
> > Просто так (умножение в столбик) не получится. Для
> снижения
> > сложности умножения там применяются хитрые алгоритмы,
> > некоторые из которых я так и не понял.
>
> А что же мы все "столбиком" на бумаге считаем?
Контекст потерян. 3 сообщения назад я упомянул эффективные методы умножения со сложностью O(N1.5</sup) и меньше. Вы сказали, что "не вдавались в подробности, может что то в этом роде и получается". Именно к этой фразе относится мое замечание о том, что в случае с умножением в столбик ничего не получится. То есть при умножении в столбик о такой сложности приходится только мечтать.
А считаем мы в столбик потому, что довольно трудно на листике сделать быстрое преобразование фурье и не ошибиться при этом.
> При случае напишу про свои тесты.
Жду
> Зависит от критериев оценки. Быстрее - может быть, хотя не
> факт. Удобнее - вполне возможно.
Куда уж удобнее. Кроме C-шных вызовов есть еще C++-сная обертка для них.
> И в довесок. 10 раз быстрее, 100, 1000. Если факторизация
> будет сложности log(n), то быстродействие не будет играть
> большого значения, если оно не будет уж настолько
> тупым/тормозным. Какая разница - будет ли думать компьютер
> микросекунду или милисекунду над задачей разложения
> килобитного числа. А для n/ln(n) любого быстродействия
> будет мало, чего уж там говорить об одном или двух
> десятичных порядках.
Дык опять повторюсь 10 раз это для СЛОЖЕНИЯ. Никакого более эффективного алгоритма для сложения придумать нельзя. Можно только оптимизировать реализацию. А вот для других операций - используются самые эффективные из известных на сегодня алгоритмов
|
|
|
подробно о проекте
Анализ криптографических сетевых...
