информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Портрет посетителяАтака на InternetВсе любят мед
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Три миллиона электронных замков... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / programming
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Ндаа... 25.12.03 17:23  Число просмотров: 2156
Автор: 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 прям в код вставляет, а у меня вызов функций с передачей параметров.
Про умножение тоже все понятно - столбиком. В обоих случаях вызываются функции с передачей параметров (встроенная через регистры, у меня указатели через стэк). У меня, почему-то работает быстрее немножко. Странно.
Накатал тупое деление столбиком. У меня значительно медленнее. Правда чуть другой "столбик", чем при умножении использовался. Думаю, что соптимизировав смогу добиться аналогичной производительности.
Вопрос в том, может есть какой-то другой метод деления, не "столбиком"? У меня - сдвиг, сравнение, если меньше - вычитание и установка соответствующего знакового разряда в результат.
А как такой вариант? 29.12.03 14:57  
Автор: whiletrue <Роман> Статус: Elderman
<"чистая" ссылка>


Методом Ньютона для нахождения обратного
Gnu multi precision 25.12.03 15:54  
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка>
Там несколько алгоритмов (и в доках описаны) и для умножения и для деления. Правда эта библиотека для действительно больших чисел, но может тебе что-нибудь там пригодится

http://www.gnu.org/software/gmp/manual/html_mono/gmp.html#Algorithms
Ндаа... 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.
Удачи!
1




Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach