Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| | | |
Если не будешь читать, что тебе отвечают, то тебе перестанут отвечать 22.10.04 10:44 Число просмотров: 5890
Автор: 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 Статус: Незарегистрированный пользователь
|
|
А дальше что делать ведь я то программирую под Виндой...
|
| | | | | | | | | | | | | | |
Эта либа просит еще какую-то "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, при чем он действительно инклюдится, и его нигде нет.
Не знаю чем все закончится. Или найду что-нибудь, из чего библиотека соберется. Или найду готовую (?). Или придется самому писать.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
