Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
А это смотря для каких задач. Если надо одно большое... 29.03.05 16:24 Число просмотров: 4055
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
|
> Даже по решету эратосфена придется "пройтись" простыми до
> корня из N. т.е. если N~10^70,
> то пройтись придется простыми до 10^35. (Если я правильно
> знаю решето)
А это смотря для каких задач. Если надо одно большое простое, то нужно их поискать в окресности перебором. Если надо много/все на интервале, то решетом. В любом случае это будет быстрее, чем пытаться делить каждое на простые и проверять остаток. Причем разница колосальна.
> Тогда что остается неприменимого в формуле Стирлинга?
> Только точность.
Естественно! 4 знака очень мало, когда речь идет о сотне.
> Интересно, как получить остальные члены в полиноме для
> увеличения точности.
Вариант - эмпирически. Подбираем коэффициенты, оценивая сренеквадратичное отклонение. Другой метод будет более сложен.
> И еще, какая понадобится точность для N=10^k, k знаков, или
> больше чем 10^k? :)
n-k. Хотим +/-10 - надо -(к-1), хотим +/-100 - надо -(к-2).
> Это если будет, а если нет? И еще, если рассматривать
> только половинку (верхнюю) интервала,
> то относительное изменение чисел (отношение максимального
> члена к минимальному) будет максимум в 2 раза, что может
> снизить неточность, по сравнению
> с нижней половиной, где относительное изменение чисел будет
> 10^35 (Если N 10^70).
Экстенсивные методы бессмысленно рассматривать, это все равно что на ассемблере вылизывать код, чтоб добиться десятикратного ускорения. С одной стороны это не плохо. С другой стороны если речь идет о времени вычислений 10^600 лет, то от того что время сократится до 10^599 лет легче не станет.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
