Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| |
Ндаа... 25.12.03 17:23 Число просмотров: 2438
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 25.12.03 17:24 Количество правок: 2
|
> Там несколько алгоритмов (и в доках описаны) и для
> умножения и для деления. Правда эта библиотека для
> действительно больших чисел, но может тебе что-нибудь там
> пригодится
если уж это все, до чего научная мысль дошла...
Методов достаточно. Про таблицу умножения мы знаем с первого класса, только она не подходит для больших чисел. Я, похоже, Каратсубой попользовался (столбиком). Только ограничился тремя умножениями (по "таблице умножения":) и двумя сложениями, поскольку увеличения разрядности в два раза не требовалось.
С делением - тоже мало веселенького, если исключить табличные методы, метод отброса младших разрядов при делении на основание системы счисление в степени и метод последовательного вычитания с инкрементированием счетчика-результата, то остается, собственно "столбиком". Оперировать не в двоичной системе тяжело из-за множества умножений, а в двоичной тяжело из-за большого количества итераций и сложных сдвигов. "Библиотечное" деление то работает почти со скоростью умножения.
|
|
<programming>
|
Обработка больших значений. 25.12.03 15:14
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 25.12.03 15:15 Количество правок: 1
|
Рассмотрим пока обработку 64 битных данных на 32 битном АЛУ.
Про сkожение с переносом и вычитание с заёмом все понятно, написал функцию/метод_класса. Компилирую SymantecC 7.1 (он 64 битные данные тоже поддерживает). Сравниваю время обработки. Получается дольше. Понятно почему - он ADD+ADC прям в код вставляет, а у меня вызов функций с передачей параметров.
Про умножение тоже все понятно - столбиком. В обоих случаях вызываются функции с передачей параметров (встроенная через регистры, у меня указатели через стэк). У меня, почему-то работает быстрее немножко. Странно.
Накатал тупое деление столбиком. У меня значительно медленнее. Правда чуть другой "столбик", чем при умножении использовался. Думаю, что соптимизировав смогу добиться аналогичной производительности.
Вопрос в том, может есть какой-то другой метод деления, не "столбиком"? У меня - сдвиг, сравнение, если меньше - вычитание и установка соответствующего знакового разряда в результат.
|
| |
Ндаа... 25.12.03 17:23
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 25.12.03 17:24 Количество правок: 2
|
> Там несколько алгоритмов (и в доках описаны) и для
> умножения и для деления. Правда эта библиотека для
> действительно больших чисел, но может тебе что-нибудь там
> пригодится
если уж это все, до чего научная мысль дошла...
Методов достаточно. Про таблицу умножения мы знаем с первого класса, только она не подходит для больших чисел. Я, похоже, Каратсубой попользовался (столбиком). Только ограничился тремя умножениями (по "таблице умножения":) и двумя сложениями, поскольку увеличения разрядности в два раза не требовалось.
С делением - тоже мало веселенького, если исключить табличные методы, метод отброса младших разрядов при делении на основание системы счисление в степени и метод последовательного вычитания с инкрементированием счетчика-результата, то остается, собственно "столбиком". Оперировать не в двоичной системе тяжело из-за множества умножений, а в двоичной тяжело из-за большого количества итераций и сложных сдвигов. "Библиотечное" деление то работает почти со скоростью умножения.
|
| | |
Если нужно u64 /= u32 25.12.03 18:20
Автор: leo <Леонид Юрьев> Статус: Elderman
|
Если нужно поделить 'unsingned __int64' на 'unsigned __int32', то можно так:
__forceinline unsigned __get_edx()
{
__asm mov eax, edx
}
#define DIVMOD64(HighPart, LowPart, Divisor, Reminder) \
{ \
{ \
__asm mov ecx, Divisor \
__asm mov eax, HighPart \
__asm xor edx, edx \
__asm div ecx \
__asm mov HighPart, eax \
__asm mov eax, LowPart \
__asm div ecx \
__asm mov LowPart, eax \
} \
Reminder = __get_edx(); \
}
---
Смысл такой:
Reminder = (HighPart << 32 + LowPar) % Divisor;
(HighPart, LowPar) = (HighPart << 32 + LowPar) / Divisor;
|
| | | |
Увы... 26.12.03 10:53
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 26.12.03 10:54 Количество правок: 1
|
Круто!
Еслиб просто требовалось производить операции над int64, можно было бы и встроенными возможностями воспользоваться.
А еслиб очень приперло, то можно и Итаниум или Атлон64 прикупить.
Иметтся желание разобраться как это происходит. Точнее как бысто делить.
Тренеруюсь над int64 чтоб проверить правильность реализации алгоритмов. А то потом при работе с килобитными числами ошибки тяжелее выловить.
Вчера посмотрел - блин, пробовал делить методом поиска частного методом деления пополам.
|
| | | | |
А тип сопроцессора comp не проканает? Вот тебе аппаратный Int64 на IA32 ;-) 29.12.03 10:37
Автор: HandleX <Александр М.> Статус: The Elderman
|
|
|
| | | | | |
Еслиб только 64, можно даже встроенными в компилятор средствами пользоваться. А как быть с килобитом... 29.12.03 12:08
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
|
|
|
| | | | | | |
Кстати, в этом плане прикольна эволюция калькулятора Windows… ;-) 09.01.04 07:31
Автор: HandleX <Александр М.> Статус: The Elderman
|
В виндах 3.11 и 95 калькулятор не мог считать значения больше максимального сопроцессорного типа Extended. Сейчас считает неограниченные значения, правда, когда они очень большие, вычисления затягиваются. Калькулятор даже предупреждает о том, что они могут занять длительное время. Ну и видно в диспетчере задач, как он память отжирает при больших значениях.
Интересно, как они это реализовали? Явно что-то GNU-шное использовали ;-)
|
| | | | | | | |
Начиная с NT SP4 и Win98. 09.01.04 10:13
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
|
> Интересно, как они это реализовали? Явно что-то GNU-шное
> использовали ;-)
Дело то не хитрое. Хотел тоже переменный размер реализовать, только медленно это будет. Может для малых значений то и быстрее получится - меньше "пустоты" обрабатывать придется. Беда в том, что функции динамического распределения памяти надо будет дергать, а они медленные. Все за каждый такт борятся. Так что этот плюс (работа с числами любой длины) невелируется с потерей скорости (в шифровалках то заведомо оговорена длина ключа, и скорость очень важна).
|
| | | | | | | | |
Re: Обработка больших значений 09.01.04 14:25
Автор: leo <Леонид Юрьев> Статус: Elderman
|
> > Интересно, как они это реализовали? Явно что-то
> GNU-шное
> > использовали ;-)
Точно нет, M$ сейчас обходит GNU как можно подальше.
Перестраховываются.
> Дело то не хитрое. Хотел тоже переменный размер
> реализовать, только медленно это будет. Может для малых
> значений то и быстрее получится - меньше "пустоты"
> обрабатывать придется. Беда в том, что функции
> динамического распределения памяти надо будет дергать, а
> они медленные. Все за каждый такт борятся. Так что этот
> плюс (работа с числами любой длины) невелируется с потерей
> скорости (в шифровалках то заведомо оговорена длина ключа,
> и скорость очень важна).
При вычислениях почти всегда можно использовать _alloca() вместо malloc(). Кроме этого никто не мешает реализовать свои супер-пупер быстрые функции выделения памяти (см. slab в linux kernel).
Обработка больших чисел переменной длины становить не медленее "фиксированной" арифметики, как только длина чисел превысит 4-5 машинных слова. Поэтому если 128 бит может не хватить - то переменный размер однозначно.
Если реализовывать не на ассемблере, то основное неудобство доставляет отсутствие полноценных функций соответствующих "процессорным" сложению/вычитанию с переносом, умножение с "двойным" результатом и такое же деление.
Если нужно сделать действительно быстро - мой совет: возьми за основу вот это http://leo.yuriev.ru/files/simple-rsa.rar (автор мне не известен, наверное какой-нибудь студент). Используя GNU C++ реализуй на inline-asm функции сложение/вычитание с переносом и правильное умножение/деление, и задействуй их. При правильном подходе вседа можно будет реализовать поддержку любого процессора, меняя только четыре-пять низкоуровневых функций.
Ну и конечно как вариант - всегда можно взять что-нибудь готовое из GNU.
Удачи!
|
|
|
подробно о проекте
Анализ криптографических сетевых...
