Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Не, быстрая не нужна, нужна не медленная. 15.12.08 18:17 Число просмотров: 4595
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman Отредактировано 15.12.08 18:19 Количество правок: 2
|
> Для чего тебе быстрая генерация простых > чисел? Реально рабин-миллер дает приемлемый (и по скорости > и по вероятности) результат на практически применимых > длинах чисел.
Сейчас уж не вспомню, то ли полкило, то ли килобит за минуту - обидно, понимаешь, умеючи и за 1-10 сек двухкилобитный генерится. Причем у меня скорость падает примерно как квадрат от разрядности. В смысле в два раза больше разраядность, в четыре (а то и больше) раза дольше генерится.
> Натуральному. Я уже давал ссылку на распределение простых > чисел. Расстояние между ними растет логарифмически > (натурально логарифмически :-) )
Ну это приятнее - раза в полтора будет быстрее.
> > тысячу раз медленнее. Кроме того рекомендовалось > зачем-то > > первоначально проверить делимость на маленькие простые > > числа. > Не знаю, по моему в случае рабина миллера это бессмысленно. > Один gcd - это как минимум десяток делений. При этом число > уменьшится незначительно и не слишком повлияет на скорость > дальнейшей проверки.
Меня это смутило. Причина моих сомнений проста - получается, что Миллера-Рабина без такой проверки полный бред выдаст, ошибится сможет, особенно, если делители маленькие. Потом решил, что это рекомендовалось сделать, чтоб отсеить заведомо составные (кратные 2, 3, 5, ...). В принципе тест М-Р может быть достаточно сложным, длинным и долгим, если "отлуп" наступит на одном из последних раундов. Если же взять произведение десятка-другого маленьких простых и найти с ним НОД, то после первого же деления (по Евклиду) получаем уже достаточно небольшое число. Поэтому не десяток, а несколько делений вместо немалого количества умножений может быть оправдано.
> Категорически не согласен. Если выбирать между примитивной > реализацией и фундаментальными сведениями - то лучше пусть > будет фундамент, а реализацию я как нибудь сам. С другой > стороны лучше чтобы было и то и то.
Пусть будет и то и то. Порой бывает надо быстро реализовать, а тут попадается теория, да еще оборваная на полуслове, типа додумай сам, для повышения соображалки.
> А при чем здесь gcc? gmp под цигвином/мингвом можно
А это разве не надстройки над gcc?
> собирать и без всяких дополнительных телодвижений. То что я > дал - это gmp для visual studio.
Да, видел, 6 версии достаточно.
> Ну и vc и gcc умеют 32/64. Я кстати, используя > вышеприведенный линк собирал 64-битный gmp для вычисления > 9^(9^9) > Прирост в скорости от перехода 32->64 не очень большой, > но процентов 10-15 есть.
Странно, должно быть раза в четыре. Я для совместимости реализовывал на 16 битах - отсюда думаю и тормоза. 32 уже, полагаю хватило бы, если в четыре раза скорость бы поднялась. Жалко бросать, делал для себя, на с++ класс с перегрузкой операций, удобнее, чем структуры в функции передавать.
> > Благо не за сам линукс. > Жаль :-)
Как много в этом мире добрых людей!
|
|
|