|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Doroshev 2:5020/400 27 Mar 2002 18:21:31
To : Roman Miroshnichenko
Subject : Re: Пpостые числа... - fido7.ru.algorithms
--------------------------------------------------------------------------------
Roman Miroshnichenko wrote:
>
> > О том и речь, что разумный предел - 2*3*5
> >
> > 2 50% 1/2
> > 3 33,(3)% 1/2-1/(2*3)=1/3
> > 5 30% 1/3-1/(2*3*5)=3/10
> > 7 29,52% 3/10-1/(2*3*5*7)=31/105
> > 11 29,48% 31/105-1/(2*3*5*7*11)=227/770
> >
> Осмелюсь заметить, что вы где-то ошиблись в расчетах:
> 2 - 50% 1/2 - бзусловно
> 3 = 1/2*2/3 = 1/3 - совпало
> 5 = (2-1)/2*(3-1)/3*(5-1)/5 = 4/15 = 26.7% - это уже что-то
> (почему не 3/10 = 9/30, а 8/30 ? Да хотя бы потому, что после 5
> в интервале 30 ровно 8 простых чисел (7,11,13,17,19,23,29,31)
> 7 = 4/15*6/7=24/105 = 8/35 = 22.9% - это еще не предел
> ..
> 13 = 8/35*10/11*12/13 = 192/1001 = 19.1% можно разумно
> тормозить, так как 2*3*5*7*11*13 уже всего лишь 30030
>
> ЗЫ: кстати, благодаря такому отсеиванию и тесту Рабина-Миллера,
> я сравнительно быстренько построил все 32-х битные простые числа ,
> а оказалось их ровно ровно 203_280_221 штуки, и после определенных
> извратов поместилось 220 МБ!
Время + парметры машины, если можно. А то что-то больно мне решето понравилось.
Правда, кто-то говорил про 10 секунд и 2^32, но там оказалась совсем другая
программа.
Да, с процентами действительно неверный ответ. А верный - вот он:
Prime простое
% доля кандидатов в простые
Size размер массива для хранения всех простых < 2^32, Mb,
где одному кандидату в простые соответствует 1 бит
T произведение всех ранее встреченных простых или Период
L количество кандидатов в простые в одном периоде
Prime % Size T L
1 1,0000 512,00 1 1
2 0,5000 256,00 2 1
3 0,3333 170,67 6 2
5 0,2667 136,53 30 8
7 0,2286 117,03 210 48
11 0,2078 106,39 2310 480
13 0,1918 98,21 30030 5760
17 0,1805 92,43 510510 92160
19 0,1710 87,56 9699690 1658880
61 0,1316 67,37 1,2E+23 1,5E+22
127 0,1139 58,30 4,0E+48 4,6E+47
251 0,1004 51,38 6,4E+100 6,4E+99
509 0,0893 45,70 3,2E+211 2,9E+210
1021 0,0806 41,29
2039 0,0735 37,61
4093 0,0674 34,49
В выходном файле данные должны храниться блоками по L битов, где каждый из битов
представляет число вида
T*n+{1,07,11,13,17,19,23,29,....a[i]...}
n - номер блока
T - период
a[i] - 0<=i<L
Видно, что предел уменьшения размера файла с простыми где-то около 34Mb, правда
таблицу a[i] для такого в памяти не разместишь - float оказался коротковат, и
каждый бит из решета(=кандидат в простые) перед тем как записывать в файл надо
будет проверять, не делится ли он на несколько первых тысяч простых чисел. Такую
же процедуру придется проводить и при чтении из файла.
Кстати, смысла использовать Рабина-Миллера для генерации всех подряд простых до
2^32 я не вижу. он должен быть полезен для генерации небольшого количества
простых большой длины. Для решета надо по массиву битов размером n/2 пробежаться
n^(1/2)/ln(n^(1/2)) раз - это количество простых, не превосходящих корень из n.
затраты времени ~n^(3/2)/ln(n) - наверное даже меньше, потому что установить в 0
каждый третий бит дольше, чем каждый тысячный.
А затраты времени на Рабина с Миллером пропорциональны ln(n), может быть в
небольшой степени, из-за увеличения количества знаков в числах, и
пропорциональны количеству раундов.
Асимптотически Миллер намного лучше решета, но вот только первых 2^32 чисел
слишком мало, коротки больно числа.
Кроме того тест Миллера - вероятностный, и каждый раунд составное число проходит
с вероятностью 1/4.
20 раундов для поиска 2^28 простых маловато. Вероятность ошибки - 1/2^12.
Раундов 40 надо брать.
Andrew Doroshev
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
