> Интересно, как они это реализовали? Явно что-то GNU-шное > использовали ;-) Дело то не хитрое. Хотел тоже переменный размер реализовать, только медленно это будет. Может для малых значений то и быстрее получится - меньше "пустоты" обрабатывать придется. Беда в том, что функции динамического распределения памяти надо будет дергать, а они медленные. Все за каждый такт борятся. Так что этот плюс (работа с числами любой длины) невелируется с потерей скорости (в шифровалках то заведомо оговорена длина ключа, и скорость очень важна).
Рассмотрим пока обработку 64 битных данных на 32 битном АЛУ.
Про сkожение с переносом и вычитание с заёмом все понятно, написал функцию/метод_класса. Компилирую SymantecC 7.1 (он 64 битные данные тоже поддерживает). Сравниваю время обработки. Получается дольше. Понятно почему - он ADD+ADC прям в код вставляет, а у меня вызов функций с передачей параметров.
Про умножение тоже все понятно - столбиком. В обоих случаях вызываются функции с передачей параметров (встроенная через регистры, у меня указатели через стэк). У меня, почему-то работает быстрее немножко. Странно.
Накатал тупое деление столбиком. У меня значительно медленнее. Правда чуть другой "столбик", чем при умножении использовался. Думаю, что соптимизировав смогу добиться аналогичной производительности.
Вопрос в том, может есть какой-то другой метод деления, не "столбиком"? У меня - сдвиг, сравнение, если меньше - вычитание и установка соответствующего знакового разряда в результат.
А как такой вариант?29.12.03 14:57 Автор: whiletrue <Роман> Статус: Elderman
Там несколько алгоритмов (и в доках описаны) и для умножения и для деления. Правда эта библиотека для действительно больших чисел, но может тебе что-нибудь там пригодится
> Там несколько алгоритмов (и в доках описаны) и для > умножения и для деления. Правда эта библиотека для > действительно больших чисел, но может тебе что-нибудь там > пригодится если уж это все, до чего научная мысль дошла...
Методов достаточно. Про таблицу умножения мы знаем с первого класса, только она не подходит для больших чисел. Я, похоже, Каратсубой попользовался (столбиком). Только ограничился тремя умножениями (по "таблице умножения":) и двумя сложениями, поскольку увеличения разрядности в два раза не требовалось.
С делением - тоже мало веселенького, если исключить табличные методы, метод отброса младших разрядов при делении на основание системы счисление в степени и метод последовательного вычитания с инкрементированием счетчика-результата, то остается, собственно "столбиком". Оперировать не в двоичной системе тяжело из-за множества умножений, а в двоичной тяжело из-за большого количества итераций и сложных сдвигов. "Библиотечное" деление то работает почти со скоростью умножения.
Если нужно u64 /= u3225.12.03 18:20 Автор: leo <Леонид Юрьев> Статус: Elderman
Круто!
Еслиб просто требовалось производить операции над 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
В виндах 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.
Удачи!