Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| | | | | | | | | | | | | | | | | | | | | | | | | | | | |
Ну не знаю на сколько нестандартный. Ну нет у меня под рукой... 20.01.09 11:37 Число просмотров: 5165
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 20.01.09 11:46 Количество правок: 2
|
> Ты чем конпелируешь? iostream.h - это НЕстандартный хедер.
> Он может быть в твоей среде компиляции, но в стандарте он
> однозначно отсутствует.
Ну не знаю на сколько нестандартный. Ну нет у меня под рукой учебника по С++. Стандарт то должен быть один, иначе какой же он стандарт. Может это по микрософтовски не стандарт. Посмотрел сейчас в БорландС версии 3.1, посмотрел в билдере 5 версии, насколько помню в СимантекС версии 7.2 (нет сейчас под рукой) ".h" присутствовало. Я понимаю, что есть еще другие извращения типа ".hpp" для своих ++ хедеров, хотя старый БорландС распознавал именно "++" по типу компилироваемого файла как ".cpp", в отличии от микрософтовского ".cc".
Но это все не самое главное. Глаза разуты, все вижу. Понимаю, у каждого софта есть свои фичи.
> > нет. Все по Страустрапу. Что за кусок дерьма, который
> это
> По КАКОМУ страуструпу? Второе издание? Которому уже лет 15?
Получается что, на Ричи и Кернигановском С уже писать нельзя, потому что ему более 30 лет.
Честно говоря ненавижу эти консольные потоки с самого первого дня за использование этих операторов.
> std::cout << blabla<< std::endl;
---
> ну или на крайний случай (хотя и не рекомендуется для
> продакшн кода):
> using namespace std;
---
Довольно быстро нашел последнее решение, но все равно спасибо, за первое.
> ЗЫ: Может действительно высокоуровневый язык попробуешь? С
> гмп-ой у тебя явно не складывается
Ни в коем случае. Определенное занятие может быть для кого-то противной работой, а для кого-то любимым занятием. Думаете школьникам/студентам приятно решать математические задачи? Но ведь найдутся наверняка люди, которые в свободное время с большим удовольствием погрузятся в математические проблемы. Мне нравится С/С++. Проблема осталась теперь в другом - в свободном времени :-).
|
|
<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, при чем он действительно инклюдится, и его нигде нет.
Не знаю чем все закончится. Или найду что-нибудь, из чего библиотека соберется. Или найду готовую (?). Или придется самому писать.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
