информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Атака на InternetSpanning Tree Protocol: недокументированное применениеСетевые кракеры и правда о деле Левина
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Некоторые пароли от G Suite хранились... 
 Microsoft выпустила Windows Sandbox 
 Microsoft выпустила исправление... 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / programming
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Если нужно u64 /= u32 25.12.03 18:20  Число просмотров: 1609
Автор: 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;
<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-2019 Dmitry Leonov   Page build time: 1 s   Design: Vadim Derkach