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





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Если не будешь читать, что тебе отвечают, то тебе перестанут отвечать 22.10.04 10:44  Число просмотров: 5762
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка>
> Я понял что MSDN это такая справка типа стандартной... )))
> Понял что её можно найти в среде разрадотеки....
>
> А теперь честно ... мне бы хотелось точно знать как решить
> задачи такого рода:
> 1. Умножние двух 100 разрядных числа = 200 разрядов
Здесь http://www.bugtraq.ru/cgi-bin/forum.mcgi?type=sb&b=2&m=113509 тебе уже давали ссылку на алгоритмы сюда: http://algolist.manual.ru/maths/longnum.php
За более быстрыми (и более изощренными и непонятными алгоритмами) тебе уже надо обращаться к серьезным источникам типа того же Кнута (во 2-м томе есть целый раздел посвященный работе с числами произвольной точности) или к библиотекам в исходниках типа того же gmp, но сильно сомневаюсь что начинающему (каким бы гениальным он ни был) это под силу.

> 2. как запомнить все простые числа от 2 до любого 200
> разрядного числа.
Давай немного повычисляем. Раз уж ты взялся за простые числа, то должен знать асимптотическую формулу распределения простых чисел: n = N / ln(N), где n - ПРИМЕРНОЕ количество простых чисел, меньших N, ну а N - любое натуральное число (чем больше N, тем точнее эта формула).

10^200 / ln (10 / 200) ~= 10^200 / 460 ~= 2 * 10^197

Ну а длина среднего простого числа на этом диапазоне будет равна средней длине натурального числа на диапазоне. То есть среднее простое число примерно равно

p == sum(n = 1..N, n * P(n)), если учесть, что P(n) для равномерно распределенных натуральных чисел будет равна P(n) = 1 / N, то p == sum(n = 1..N, n / N) == sum(n = 1..N, n) / N == (N * (N - 1) / 2) / N == (N - 1) / 2
При N == 1 * 10^200, среднее число будет равно 5 * 10^199

То есть для его хранения нужно 199 десятичных знаков, если умножить это число на двоичный логарифм десяти (количество двоичных знаков в одном десятичном), то получим 661 бит (или 83 байта) на каждое число.

Теперь умножаем количество простых чисел, которые необходимо сохранить на длину среднего простого числа:

2 * 10^197 * 83 == 1.66 * 10^199

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

Нужно 10^196 килобайт или 10^193 мегабайт или 10^190 гигабайт. Ну а теперь подумай как ты заработаешь на такое количество памяти
<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