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





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Я в свое время так и не нашел ничего подходящего. Может... 15.12.04 17:14  Число просмотров: 6847
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
<"чистая" ссылка>
> А чего тут помогать то? Собственно
> http://www.google.com/search?q=multi+precision+library&sour
> ceid=opera&num=0&ie=utf-8&oe=utf-8

Я в свое время так и не нашел ничего подходящего. Может потому, что мне требовалось возможность работы с числами неограниченной размерности. Ну ограниченной размерами оперативной памяти.

> Про тестирование на малых числах - согласен.
>
> > Ассемблер совсем не нужен. "С" и так
> Ассемблер нужен ОБЯЗАТЕЛЬНО.
>
> Как минимум если реализовать библиотеку работы с числами
> произвольной длины на C, то невозможно без трудностей
> добиться работы с 32-битным лимбом (так как флаг
> переполнения в C недоступен).

Я без проблем реализовывал и без бита переноса, только это было раза в два-три медленнее. Просто обрабатывал 16 битные значения, преобразовав к 32 дополняя нулями. После сложения 32 битных младшая часть - результат, старшая - перенос. При сложении обычно 0 или 1, при умножении - что угодно.

> > медленнее, чем с обычными. Причем сложение/вычитание в
> > столько раз медленнее, во сколько разрядность будет
> Сложение/вычитание имееют линейную сложность: O(N). То есть
> их скорость прямопропорциональна длине складываемых чисел.

А я разве не о том же самом.

> > порядка в n^2 раз медленнее. Использование ассемблера
> даст
> Есть алгоритмы умножения со сложностью
> O(N1.5) и меньше. Бери тот же gmp и
> не мучайся.

Ну не вдовался я в подробности. Хотя что-то в этом духе на самом деле и получается.

> > максимум несколько процентов выигрыша.
> Использование ассемблера в моем случае дало примерно 1000%
> выигрыша только на сложении/вычитании.

Как так можно??? В 10 раз быстрее??? Уууу!

> > Если уж нужна будет библиотечка - нет проблем, только
> > свисните.
> Зачем свистеть, если есть гугль? :-)

Ну да, кого-то (скорее всего большинство) устроит и то, что есть в сети.
<programming>
Вопросы по динамичным переменным в С++ 16.10.04 22:29  
Автор: hotice Статус: Незарегистрированный пользователь
<"чистая" ссылка>
Плз... скажите может кто знает как мне:
1. создать переменную в которую я смог бы записать целое число любой длинны.
2. создать подобие массива с неизвестной длинной и потом обрасчатся к его элементам по индексам.

Спасибо...
Нафиг нужно целое число любой длины?? ))) По поводу... 11.12.04 21:13  
Автор: sfly Статус: Незарегистрированный пользователь
<"чистая" ссылка>
> Плз... скажите может кто знает как мне:
> 1. создать переменную в которую я смог бы записать целое
> число любой длинны.
> 2. создать подобие массива с неизвестной длинной и потом
> обрасчатся к его элементам по индексам.
>
> Спасибо...
Нафиг нужно целое число любой длины?? ))) По поводу массива...., юзай STL ..
#include <vector.h>
vector<int> v;
for(int i = 0; i<100; ++i) v.push_back(i);
for(int i = 0; i<v.size; ++i) printf("Number %d = %d ", i, v[i]); Примерно так ...
Массив любой длины нужен: 12.12.04 08:30  
Автор: Heller <Heller> Статус: Elderman
<"чистая" ссылка>
Массив любой длины нужен:
а) "Считать звёзды"
б) Считать физические характеристики при столкновении атомов/атомных ядер
в) В целях криптологии. В RSA, например, используются числа длиной более 1024 бит.
г) При интегрировании, если требуются точные значения
д) Много где
Массив или разрядность его величин??? 14.12.04 11:47  
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 14.12.04 11:47  Количество правок: 1
<"чистая" ссылка>
> Массив любой длины нужен:
> а) "Считать звёзды"
> б) Считать физические характеристики при столкновении
> атомов/атомных ядер
> в) В целях криптологии. В RSA, например, используются числа
> длиной более 1024 бит.
> г) При интегрировании, если требуются точные значения
> д) Много где
Массив или разрядность его величин???
Пальчиками все делается. Ну писал я библиотечку/класс для работы с числами неограниченной размерности. Точенее ограниченной только фантазией и размерами ОЗУ.
Массивчие таких переменных тоже организовать не сложно. Завели указатель на указатели и размерность. Если надо увеличить массив - то realloc на new_size*sizeof(*class).
Вот только зачем нужно неограниченность. Обычно программер выбирает размерность переменной по максимальному значению, которая она может содержать. В ясную ночь мы может видеть около 6000 звезд. В RSA ключем, длинной более 2048 пока никто не пользуется. В 128 разрядов можно "впихнуть" количество атомов в нашей вселенной или рассояние до звезд в милиметрах. В физике целыми значениями не ограничиться.
Не могу согласиться 16.12.04 19:39  
Автор: Heller <Heller> Статус: Elderman
<"чистая" ссылка>
В случае дробных чисел как раз таки очень могут помочь целые динамического размера. Если представить число в виде целой и дробной части, то целой части можно выделить целую переменную фиксированного размера. Но тогда, если представить дробную часть в экспоненциальной форме, для её предтавления вполне достаточно одного целого числа динамического размера - показателем степени при этом будет длина этого числа со знаком минус и, соответственно, хранить степень необязательно.

Да и вообще во многих задачах размер данных заранее неизвестен даже примерно. Может быть он считает числа Фибоначе, удаляясь в бесконечнось? Существует такая задача - кто-то где-то этим вроде как даже занимается. Хотя целесообразность этого и сомнительна.
А если учесть еще и возможности телескопов, то несколько... 14.12.04 12:48  
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка>
> которая она может содержать. В ясную ночь мы может видеть
> около 6000 звезд. В RSA ключем, длинной более 2048 пока
А если учесть еще и возможности телескопов, то несколько миллиардов: индекс поместится в одном dword-е, а массив с самими параметрами вряд ли нужно динамически перераспределять (да и вообще сильно сомневаюсь, что в этом случае используется плейн массив - скорее sql-база). Ну а RSA на самом деле сейчас самые стойкие ключи, которые используются 4096 бит, но это тоже не требует уж больно динамических переменных

> никто не пользуется. В 128 разрядов можно "впихнуть"
> количество атомов в нашей вселенной или рассояние до звезд
> в милиметрах. В физике целыми значениями не ограничиться.

ЗЫ: Кста, в gmp есть C++шные врапперы.
Нет вообщето звёзды мне считать не надо... а вот RSA, ну или... 14.12.04 22:35  
Автор: hotice Статус: Незарегистрированный пользователь
<"чистая" ссылка>
Нет вообщето звёзды мне считать не надо... а вот RSA, ну или что то подобное надо... мне нужны элементарные операции типа + - / * и все они должны производится на числами свыше 512 бит и очень, очень быстро... знаю что асм это круто, но с ним не очень дружу, и вообще хочется на Си всё сделать. А массив мне нужен для факторизации числа...)))
Ааа, ну теперь все понятно! 15.12.04 14:08  
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 15.12.04 14:14  Количество правок: 1
<"чистая" ссылка>
> Нет вообщето звёзды мне считать не надо... а вот RSA, ну
> или что то подобное надо... мне нужны элементарные операции
> типа + - / * и все они должны производится на числами свыше
> 512 бит и очень, очень быстро... знаю что асм это круто, но
> с ним не очень дружу, и вообще хочется на Си всё сделать. А
> массив мне нужен для факторизации числа...)))

Ааа, ну теперь все понятно!
Могу помочь и библиотечкой работы с большими значениями, но для начала помогу дельным советом.
Я сам в качестве хобби увлекаюсь подобным безобразием. Так вот совсем не за чем сразу начинать работать с очень большими числами при "изобретательстве" алгоритма быстрой факторизации. Попробуйте, как и я в свое время, начать с 16-32 битных чисел. Мало - попробуйте с 64 разрядными - подавляющее большинство компиляторов прекрасно умеют эмулировать 64 разрядность на 32 разрядном процессоре. Просто это удобно, и для того, чтоб убедиться на 0.999 что алгоритм сработает или заведомо не сработает вполне достаточно. С ними (обычными переменными) проще работать, да и однозначно быстрее. В процессе экспериментов часто придется перекомпилировать и производить вычисления - ну зачем тратить драгоценное время на эксперименты, результат которых можно получить и в более короткое время. Если, вдруг, улыбнется удача и после того как все многочисленные эксперименты завершатся успешно - можно поработать с многоразрядными значениями.
Ассемблер совсем не нужен. "С" и так ассемблерно-ориентированный очень быстрый язык с очень компактным кодом. Работа с большими числами будет все-равно медленнее, чем с обычными. Причем сложение/вычитание в столько раз медленнее, во сколько разрядность будет превышать разрядность регистров. Умнодение будет медленнее порядка в n^2 раз медленнее. Использование ассемблера даст максимум несколько процентов выигрыша.
Если уж нужна будет библиотечка - нет проблем, только свисните.
Позволю не согласиться 15.12.04 15:35  
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка>
> Ааа, ну теперь все понятно!
> Могу помочь и библиотечкой работы с большими значениями, но
А чего тут помогать то? Собственно
http://www.google.com/search?q=multi+precision+library&sourceid=opera&num=0&ie=utf-8&oe=utf-8

Про тестирование на малых числах - согласен.

> Ассемблер совсем не нужен. "С" и так
Ассемблер нужен ОБЯЗАТЕЛЬНО.

Как минимум если реализовать библиотеку работы с числами произвольной длины на C, то невозможно без трудностей добиться работы с 32-битным лимбом (так как флаг переполнения в C недоступен).

> медленнее, чем с обычными. Причем сложение/вычитание в
> столько раз медленнее, во сколько разрядность будет
Сложение/вычитание имееют линейную сложность: O(N). То есть их скорость прямопропорциональна длине складываемых чисел.

> порядка в n^2 раз медленнее. Использование ассемблера даст
Есть алгоритмы умножения со сложностью O(N1.5) и меньше. Бери тот же gmp и не мучайся.

> максимум несколько процентов выигрыша.
Использование ассемблера в моем случае дало примерно 1000% выигрыша только на сложении/вычитании.

> Если уж нужна будет библиотечка - нет проблем, только
> свисните.
Зачем свистеть, если есть гугль? :-)
Я в свое время так и не нашел ничего подходящего. Может... 15.12.04 17:14  
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
<"чистая" ссылка>
> А чего тут помогать то? Собственно
> http://www.google.com/search?q=multi+precision+library&sour
> ceid=opera&num=0&ie=utf-8&oe=utf-8

Я в свое время так и не нашел ничего подходящего. Может потому, что мне требовалось возможность работы с числами неограниченной размерности. Ну ограниченной размерами оперативной памяти.

> Про тестирование на малых числах - согласен.
>
> > Ассемблер совсем не нужен. "С" и так
> Ассемблер нужен ОБЯЗАТЕЛЬНО.
>
> Как минимум если реализовать библиотеку работы с числами
> произвольной длины на C, то невозможно без трудностей
> добиться работы с 32-битным лимбом (так как флаг
> переполнения в C недоступен).

Я без проблем реализовывал и без бита переноса, только это было раза в два-три медленнее. Просто обрабатывал 16 битные значения, преобразовав к 32 дополняя нулями. После сложения 32 битных младшая часть - результат, старшая - перенос. При сложении обычно 0 или 1, при умножении - что угодно.

> > медленнее, чем с обычными. Причем сложение/вычитание в
> > столько раз медленнее, во сколько разрядность будет
> Сложение/вычитание имееют линейную сложность: O(N). То есть
> их скорость прямопропорциональна длине складываемых чисел.

А я разве не о том же самом.

> > порядка в n^2 раз медленнее. Использование ассемблера
> даст
> Есть алгоритмы умножения со сложностью
> O(N1.5) и меньше. Бери тот же gmp и
> не мучайся.

Ну не вдовался я в подробности. Хотя что-то в этом духе на самом деле и получается.

> > максимум несколько процентов выигрыша.
> Использование ассемблера в моем случае дало примерно 1000%
> выигрыша только на сложении/вычитании.

Как так можно??? В 10 раз быстрее??? Уууу!

> > Если уж нужна будет библиотечка - нет проблем, только
> > свисните.
> Зачем свистеть, если есть гугль? :-)

Ну да, кого-то (скорее всего большинство) устроит и то, что есть в сети.
Вторая ссылка по указанному запросу: 15.12.04 17:36  
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка>
> > А чего тут помогать то? Собственно
> >
> http://www.google.com/search?q=multi+precision+library&sour
> > ceid=opera&num=0&ie=utf-8&oe=utf-8
>
> Я в свое время так и не нашел ничего подходящего. Может
> потому, что мне требовалось возможность работы с числами
> неограниченной размерности. Ну ограниченной размерами
> оперативной памяти.
Вторая ссылка по указанному запросу:
https://www.cosic.esat.kuleuven.ac.be/nessie/call/mplibs.html
Кста, gmp - работает с числами НЕОГРАНИЧЕННОЙ разрядности (ограниченной только размерами памяти:-) ). По необходимости она расширяет количество, но для большей эффективности стоит сразу же зарезервировать необходимый размер.

> Я без проблем реализовывал и без бита переноса, только это
> было раза в два-три медленнее. Просто обрабатывал 16 битные
> значения, преобразовав к 32 дополняя нулями. После сложения
> 32 битных младшая часть - результат, старшая - перенос. При
> сложении обычно 0 или 1, при умножении - что угодно.
Ага. Только в этом случае даже при сложении/вычитании возникает огромный оверхед, а уж при умножении и не приведи господь делении - совсем мрачно становится. Кстати, я тоже использовал 16-тибитные лимбы. Сложение вычитание одинаковых по размерности чисел было примерно в 10 раз медленнее, чем в gmp.

> А я разве не о том же самом.
Ну да. Просто я дальше об умножении в терминах O заговорил, и чтобы быть последовательным привел оценку и тут :-)

> Ну не вдовался я в подробности. Хотя что-то в этом духе на
> самом деле и получается.
Просто так (умножение в столбик) не получится. Для снижения сложности умножения там применяются хитрые алгоритмы, некоторые из которых я так и не понял.

> Как так можно??? В 10 раз быстрее??? Уууу!
Вот так вот. Я тоже в свое время писал библиотеку для работы с числами произвольной длины. 16-битные лимбы, отсутсвие оптимизации. 100000 операций сложения уж не помню какой длины (не маленькой) занимали около 17 секунд (как сейчас помню). Ну а gmp сделал то же самое за полторы секунда. Вот был облом. Это одна из вех, на которых я понял, что доверять библиотекам все таки нужно, а девиз: "Этот код плохой, потому как написан не мной" - чаще всего заблуждение. :-)

> Ну да, кого-то (скорее всего большинство) устроит и то, что
> есть в сети.
Я даже больше скажу. Лучше - фиг напишешь :-)
Скачал - буду смотреть и тестировать. 17.12.04 15:01  
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
<"чистая" ссылка>
> Вторая ссылка по указанному запросу:
> https://www.cosic.esat.kuleuven.ac.be/nessie/call/mplibs.ht
> ml
> Кста, gmp - работает с числами НЕОГРАНИЧЕННОЙ разрядности
> (ограниченной только размерами памяти:-) ). По
> необходимости она расширяет количество, но для большей
> эффективности стоит сразу же зарезервировать необходимый
> размер.

Скачал - буду смотреть и тестировать.

> Ага. Только в этом случае даже при сложении/вычитании
> возникает огромный оверхед, а уж при умножении и не приведи
> господь делении - совсем мрачно становится. Кстати, я тоже
> использовал 16-тибитные лимбы. Сложение вычитание
> одинаковых по размерности чисел было примерно в 10 раз
> медленнее, чем в gmp.

По идее должно быть только в 2 (чуть более) раза при использовании Ассемблера. 10 получить можно при использовании слабооптимизирующего компилятора.

> Просто так (умножение в столбик) не получится. Для снижения
> сложности умножения там применяются хитрые алгоритмы,
> некоторые из которых я так и не понял.

А что же мы все "столбиком" на бумаге считаем?

> Вот так вот. Я тоже в свое время писал библиотеку для
> работы с числами произвольной длины. 16-битные лимбы,
> отсутсвие оптимизации. 100000 операций сложения уж не помню
> какой длины (не маленькой) занимали около 17 секунд (как
> сейчас помню). Ну а gmp сделал то же самое за полторы
> секунда. Вот был облом. Это одна из вех, на которых я
> понял, что доверять библиотекам все таки нужно, а девиз:
> "Этот код плохой, потому как написан не мной" - чаще всего
> заблуждение. :-)

При случае напишу про свои тесты.

> Я даже больше скажу. Лучше - фиг напишешь :-)

Зависит от критериев оценки. Быстрее - может быть, хотя не факт. Удобнее - вполне возможно.

И в довесок. 10 раз быстрее, 100, 1000. Если факторизация будет сложности log(n), то быстродействие не будет играть большого значения, если оно не будет уж настолько тупым/тормозным. Какая разница - будет ли думать компьютер микросекунду или милисекунду над задачей разложения килобитного числа. А для n/ln(n) любого быстродействия будет мало, чего уж там говорить об одном или двух десятичных порядках.
Нет, компилятор был VC6. Лимбы в два раза меньше - проходов... 17.12.04 16:45  
Автор: 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 раз это для СЛОЖЕНИЯ. Никакого более эффективного алгоритма для сложения придумать нельзя. Можно только оптимизировать реализацию. А вот для других операций - используются самые эффективные из известных на сегодня алгоритмов
Приведу примерчик. 17.12.04 23:11  
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 17.12.04 23:12  Количество правок: 1
<"чистая" ссылка>
> Нет, компилятор был VC6. Лимбы в два раза меньше - проходов
> по циклу - в 2 раза больше (производительность ровно в 2
> раза меньше). Это раз. Проверять переполнение в случае
> ассемблерной реализайии не нужно - можно сразу использовать
> команду сложения с переполнением, в случае с C-шной
> реализацией (уменьшенный лимб) вместо одной команды на
> каждый лимб используется минимум 3-4 (сложение-проверка
> переполнения-ветвление-прибавление переполненного разряда)
> итого внутренний цикл в 4 раза длиннее, кроме того,
> ветвления очень плохо влияют на конвейер (тем более в
> случае с числами предсказания ветвлений работать не будут).
> В общем всего набирается примерно на 1000 процентов только
> на сложении/вычитании.

unsigned16 a[ N ], b[ N ];
unsigned32 x = 0;
for( i = 0; i < N; i += 1 ){
    x += a[ i ];
    x += b[ i ];
    a[ i ] = x;
    x >>= 16;
}

---
Какие тут проверки и разрушения конвеера? И это не смотря на то, что современные процессоры точно могут предсказать ветвления.
Если Х - аккумуляторный регистр, то два(!) сложения, одна пересылка, один сдвиг (жаль нельзя присвоить старшую часть/перенос младшей). И ни каких сравнений.

> > > Просто так (умножение в столбик) не получится.
> Для
> > снижения
> > > сложности умножения там применяются хитрые
> алгоритмы,
> > > некоторые из которых я так и не понял.
> >
> > А что же мы все "столбиком" на бумаге считаем?
> Контекст потерян. 3 сообщения назад я упомянул эффективные
> методы умножения со сложностью O(N1.5) и
> меньше. Вы сказали, что "не вдавались в подробности, может
> что то в этом роде и получается". Именно к этой фразе
> относится мое замечание о том, что в случае с умножением в
> столбик ничего не получится. То есть при умножении в
> столбик о такой сложности приходится только мечтать.
> А считаем мы в столбик потому, что довольно трудно на
> листике сделать быстрое преобразование фурье и не ошибиться
> при этом.

Не ужели для умножения нужно быстрое преобразование Фурье. Разве оно не сложнее, чем простое умножение столбиком :-(.

> > И в довесок. 10 раз быстрее, 100, 1000. Если
> факторизация
> > будет сложности log(n), то быстродействие не будет
> играть
> > большого значения, если оно не будет уж настолько
> > тупым/тормозным. Какая разница - будет ли думать
> компьютер
> > микросекунду или милисекунду над задачей разложения
> > килобитного числа. А для n/ln(n) любого быстродействия
> > будет мало, чего уж там говорить об одном или двух
> > десятичных порядках.
> Дык опять повторюсь 10 раз это для СЛОЖЕНИЯ. Никакого более
> эффективного алгоритма для сложения придумать нельзя. Можно
> только оптимизировать реализацию. А вот для других операций
> - используются самые эффективные из известных на сегодня
> алгоритмов

Я здесь как раз о том, чтоб не над эффективностью алгоритма работы с длинными числами работать, а над самим алгоритмом факторизации.
Да, от ветвления избавились. Я бы тоже избавился, если б... (upd) 20.12.04 12:18  
Автор: amirul <Serge> Статус: The Elderman
Отредактировано 20.12.04 12:23  Количество правок: 1
<"чистая" ссылка>
>
> unsigned16 a[ N ], b[ N ];
> unsigned32 x = 0;
> for( i = 0; i < N; i += 1 ){
>     x += a[ i ];
>     x += b[ i ];
>     a[ i ] = x;
>     x >>= 16;
> }
> 

---

> Какие тут проверки и разрушения конвеера? И это не смотря
Да, от ветвления избавились. Я бы тоже избавился, если б догадался. Писал я свою библиотеку ОЧЕНЬ давно.

> на то, что современные процессоры точно могут предсказать
> ветвления.
Предсказание ветвлений в данном случае не срабатывает. Оно предназначено для предсказания ветвлений, образующих циклы, то есть если вероятность срабатывания условия не равна 0.5 (и чем дальше от 0.5 тем лучше работает предсказатель). Ну а в данном случае вероятность того, что будет перенос в общем случае равна ровно 0.5, и предсказатель будет обламываться. Хотя в целом, хоть конвейер и не разрушается - используется гораздо больше одной операции на один лимб и ровно вдвое больше лимбов. Так что работать оно будет минимум раз в 5 медленнее, чем ассемблерная реализация с adc.

> Не ужели для умножения нужно быстрое преобразование Фурье.
> Разве оно не сложнее, чем простое умножение столбиком :-(.
Гы. Это как раз один из алгоритмов, которые я не понял
http://www.swox.com/gmp/manual/Multiplication-Algorithms.html#Multiplication%20Algorithms
http://www.swox.com/gmp/manual/FFT-Multiplication.html#FFT%20Multiplication

В частности это САМЫЙ эффективный алгоритм при умножении очень больших чисел.

> Я здесь как раз о том, чтоб не над эффективностью алгоритма
> работы с длинными числами работать, а над самим алгоритмом
> факторизации.
Тут согласен. Но в любом случае лучше работать над эффективным НОВЫМ алгоритмом при этом используя уже изобретенный эффективный инструментарий, чем изобретать свои велосипеды, затрачивая время на их оптимизацию
-----

Кстати, эффективность FFT-метода при умножении O(Nk/(k - 1)), где k - насколько я понял - разрядность FFT преобразования. В пределе это O(N), в то время как умножение в столбик - O(N2)
[C++] я скачал... 17.12.04 23:25  
Автор: hotice Статус: Незарегистрированный пользователь
<"чистая" ссылка>
А дальше что делать ведь я то программирую под Виндой...
[C++] Они перестали поддерживать gmp под винду (раньше поддерживали) 20.12.04 12:06  
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка>
> А дальше что делать ведь я то программирую под Виндой...
Советую скачать уже портированную
Идем в гугль:
http://www.google.com/search?q=gmp+windows&sourceid=opera&num=0&ie=utf-8&oe=utf-8
Идем по первой ссылке:
http://www.cs.nyu.edu/exact/core/gmp/
Это какая то либа под винду, юзающая gmp. И портированный gmp лежит прямо на этой странице. Причем как бинарники, так и патчи (которые с большой вероятностью подойдут и к более поздним версиям).
Эта либа просит еще какую-то "libc.lib". 08.01.09 00:17  
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 08.01.09 00:36  Количество правок: 1
<"чистая" ссылка>
> Советую скачать уже портированную
> Идем в гугль:
> http://www.google.com/search?q=gmp+windows&sourceid=opera&n
> um=0&ie=utf-8&oe=utf-8
> Идем по первой ссылке:
> http://www.cs.nyu.edu/exact/core/gmp/

Эта либа просит еще какую-то "libc.lib". LINK : fatal error LNK1104: cannot open file 'LIBC.lib'
Какой гемор. Портировать надо - гемор. Зачем писали так, надо было бы на одном из стандартных С.
Другую операционку что-ли ставить для этого.

> Это какая то либа под винду, юзающая gmp. И портированный
> gmp лежит прямо на этой странице. Причем как бинарники, так
> и патчи (которые с большой вероятностью подойдут и к более
> поздним версиям).

Что-то еще в венде патчить надо или в компиллере?
Это ж 4 года назад было. Сейчас проще 08.01.09 03:21  
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка>
libc.lib - это собственно C Runtime (статически линкуемый). Причем single threaded, которых в современных вижуал сях уже и нет.

В общем сабж, но вот здесь http://bugtraq.ru/cgi-bin/forum.mcgi?type=sb&b=15&m=152903 я тебе давал линк на более новый gmp для VC++

> Эта либа просит еще какую-то "libc.lib". LINK : fatal error
> LNK1104: cannot open file 'LIBC.lib'
> Какой гемор. Портировать надо - гемор. Зачем писали так,
> надо было бы на одном из стандартных С.
Ну недолюбливают в GNU винду. Что ж поделать :-)

> Другую операционку что-ли ставить для этого.
Не надо.

> > и патчи (которые с большой вероятностью подойдут и к
> более
> > поздним версиям).
> Что-то еще в венде патчить надо или в компиллере?

Патчить в исходниках gmp. Но, как я уже сказал, это неактуально.
Не осилю я эту gmp. Взял gmp-4.2.1.vc9, взял yasm, взял... 12.01.09 01:47  
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 12.01.09 01:49  Количество правок: 1
<"чистая" ссылка>
> libc.lib - это собственно C Runtime (статически линкуемый).
> Причем single threaded, которых в современных вижуал сях
> уже и нет.
>
> В общем сабж, но вот здесь
> http://bugtraq.ru/cgi-bin/forum.mcgi?type=sb&b=15&m
> =152903 я тебе давал линк на более новый gmp для VC++

Не осилю я эту gmp. Взял gmp-4.2.1.vc9, взял yasm, взял Питон, который не смог обработать скрипт по модификации проекта, ругаясь, что должен быть запущен из определенной директории. Что самое прикольное (проверил посимвольно неоднократно) она так и называлась. Ну, ничего, вместо Питона я могу и вручную поменять номера версии. Потом при пересборке компилер ругался на недостающие файлы, которых действительно в скаченном зипе не было. Нашел я где-то gmp-4.1.tar.gz и подсунул что было. Например файл mp_set_fns.c уже стал находится, но где я возьму файл mp_get_fns.c При пересборке (как написано в ридми) gen-* (которые должны пересобираться после gen-gmp) возникала ошибка не найден инклюд dumbmp.c, при чем он действительно инклюдится, и его нигде нет.
Не знаю чем все закончится. Или найду что-нибудь, из чего библиотека соберется. Или найду готовую (?). Или придется самому писать.
1  |  2  |  3  |  4 >>  »  




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


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