10.12.2003 21:41
Membrana
Есть что нибудь быстрее решета Эратосфена?
Хотелось бы узнать - есть ли точный метод последовательного поиска простых чисел
более быстрый чем решето Эратосфена?
27.12.2003 01:48
hd
насчет быстрее - не знаю...
но коечто есть:

#!/usr/bin/perl -sw

use Quantum::Superpositions;

sub is_prime { return $_[0]==2 || $_[0] % all(2..sqrt($_[0])+1) != 0 }

do{print "$_ - простое число\n" if is_prime($_)} for map {2*$_+1} 1..1000;
29.12.2003 12:38
F1
и в чем fun?
Это обыкновенный полный перебор делителей от 2 до sqrt(n)+1, работает значительно медленнее решета, соответственно. Подставьте вместо 1000 100000, и можете смело идти оформлять пенсию. :-)
29.12.2003 20:13
hd
fun, как ни странно, в скорости
у меня AthlonXP2100+ (640 Mb RAM) с установленным ASPLinux, ядро 2.4.22, perl 5.8.0 и соответственно такие данные для измерения скорости:

для первого примера на интервале 1000000000 - 1000000050:

[vilfred@mobile100 vilfred]$ time ./yy.pl
1000000007 - простое число
1000000009 - простое число
1000000021 - простое число
1000000033 - простое число

real 0m16.285s
user 0m16.250s
sys 0m0.030s
[vilfred@mobile100 vilfred]$

а для этого примера реализации решета Эратосфена (может и както по иному можно написать - не знаю), машина ругается на большие значения (по моему выедается вся оперативная память):

#!/usr/bin/perl
$N = 1000000050;
@L = (1) x $N;
$L[0] = 0; $L[1] = 0;
$start = 2;
$t0 = time;
while($start<$N) {
if($L[$start]==0) { $start++; next; }
for($i=$start*2;$i<$N;$i+=$start) { $L[$i] = 0; }
$start++;
}
print "time: ".(time-$t0)."\n";

for($i=0;$i<$N;$i++) {
# print $i." " if($L[$i]==1);
}

[vilfred@mobile100 vilfred]$ ./eratos.pl
panic: malloc at ./eratos.pl line 3.
[vilfred@mobile100 vilfred]$

для $N = 100000050;
[vilfred@mobile100 vilfred]$ time ./eratos.pl
Out of memory!

real 0m1.752s
user 0m1.330s
sys 0m0.420s
[vilfred@mobile100 vilfred]$

для $N = 10000050;
[vilfred@mobile100 vilfred]$ time ./eratos.pl
time: 34

real 0m38.773s
user 0m38.170s
sys 0m0.400s
[vilfred@mobile100 vilfred]$

А в первом случае через интервалы могу хоть както за _конечное_ время получить простые числа без дополнительных библиотек для работы с очень большими числами (которых на www.cpan.org некоторое количество есть)

первый пример можно запустить в фон: nohup ./yy.pl 1>stdout 2stderror &
и забыть о нем на год (если машину не перегружать)... он потихоньку да и досчитает.

А с приведенной реализацией решета Эратосфена (по другому просто не знаю как писать, может и можно) приходится в памяти строить массив данных... и тут для работы критичны возможности машины.
30.12.2003 14:26
F1
ты просто решаешь совершенно другую задачу
Если искать решения на интервале от 1000000 до 1000000050, тогда конечно. Ты попробуй от 2 до 1000000050 поискать! Решето Эратосфена эффективно только при такой постановке задачи, если искать на маленьком интвервале, преимущество фактически незаметно будет по очевидным причинам.
Что касается паники malloc'а, то решето достаточно строить по нечетным числам, и достаточно хранить 1 бит на число. Это экономит память в 16 раз, так что твой миллиард в машину влезет запросто. Во-вторых, если в оперативку уже не лезет, надо оптимизировать по swapу - группировать обращения к блокам памяти. В третьих, спрашивалось, какой метод быстрее, а не "какой требует меньше памяти". :-)
30.12.2003 14:35
hd
я пытаюсь её решить в общем виде...
По поводу нечетности, дык это, если число четно, то оно заведомо непростое, разве нет? (иными словами это не учитывается)...

вообще, конструкции 0 .. 1000000000 (которые передаются подпрограммам) это массивы с 1000000000-1 значениями. Там в интервале 1000000000 .. 1000000050, насколько я понял, идет сравнение с полным числовым рядом (и какова скорость?). Т.е. с миллиардом. то что там интервал в 50 стоит - ничего не значит... там не по 50 сравнение вовсе идет.

p.s. работать с inodes под linux я не умею...

p.s.s. а гденнить есть список простых чисел? Эти два алгоритма проверить.
30.12.2003 15:00
hd
вобщем
А какие еще алгоритмы для вычисления простых чисел есть? Может что еще получится сделать...
30.12.2003 15:22
F1
как раз не в общем, а для узких интервалов!
Цитата

По поводу нечетности, дык это, если число четно, то оно заведомо непростое, разве нет?
(иными словами это не учитывается)...

Тогда, простите, за какой же радостью Вы в вашей программе резервируете для этих чисел ячейки в решете?! А потом еще удивляетесь, что malloc в панике!

Цитата

вообще, конструкции 0 .. 1000000000 (которые передаются подпрограммам) это массивы с
1000000000-1 значениями.

Кто ж Вас заставляет передавать 0..1000000000?

Цитата

Там в интервале 1000000000 .. 1000000050, насколько я понял, идет сравнение с полным числовым рядом (и какова скорость?). Т.е. с миллиардом. то что там интервал в 50 стоит - ничего не значит... там не по 50 сравнение вовсе идет.

Нет, Вы поняли совершенно неправильно!
Ваш полный перебор требует порядка C*N*sqrt(M), где C - константа, N - ширина интервала, M - максимльное значение. Правильно написанное решето требует C'*sqrt(M)*log(N) операций.
При этом перебор действительно может отработать быстрее, если C'/C > N/log(N); ну и что с того? Если Вы возьмете ширину интервала не 50, а 50000, Ваш перебор отработает в 1000 раз медленнее, а решето замедлится менее чем в 7 раз. А можно взять не 50000, а весь миллиард. Поэтому Ваше решение как раз ни в какой мере не является общим - оно годится только для узких интервалов. И вообще, подобным образом доказывать, что перебор до корня работае быстрее решета - все равно, что утверждать, что велосипед быстрее самолета, мотивируя это тем, что на велосипеде рано или поздно можно приехать на дачу, а самолет там попросту завязнет в навозе при посадке! :-)

Цитата

p.s. работать с inodes под linux я не умею...

Для того, чтобы соптимизировать под swap, это не требуется. Для этого поступают так:
1. Массив разбивают на блоки (размер блока выбирается так, чтобы два блока гарантированно
помещался в физическую память).
2. Вместо того, чтобы для каждого простого числа заполнять решето его делимыми до конца,
вначале полностью заполняется первый блок, затем - второй и т.д.
Устроено просто, работает эффективно, только C' возрастает (применял в поиске совершенных чисел - не хватало оперативки для вычисления пятого "решетом", а перебор делителей в этой задаче просто не котируется - тогда я еще не знал, что все четные описываются простой формулой, а нечетных еще в глаза никто не видел и не исключено, что их нет - во всяком случае, доказано, что гипотетическое нечетное совершенное неразложимо в произведение восьми или менее простых).

Цитата

p.s.s. а гденнить есть список простых чисел? Эти два алгоритма проверить.

В интернете точно есть, и не один вариант. На работе ребята как-то скачивали для тестирования. :-)
30.12.2003 15:54
hd
параллельные вычисления
Цитата

Тогда, простите, за какой же радостью Вы в вашей программе резервируете для этих чисел ячейки в решете?! А потом еще удивляетесь, что malloc в панике!

Ну, будет в два раза больше если переписать, ладно, хорошо.

Цитата

Кто ж Вас заставляет передавать 0..1000000000?

ну, как бы это, есть некий fun в perl'e чем короче прога, тем креативней писатель :) (щас на меня выльют тонны грязи)...

Цитата

И вообще, подобным образом доказывать, что перебор до корня работае быстрее решета - все равно, что утверждать, что велосипед быстрее самолета, мотивируя это тем, что на велосипеде рано или поздно можно приехать на дачу, а самолет там попросту завязнет в навозе при посадке!

Ну так нам же не в Урюпинск надо. Я параллелю задачу и мне жить дешевле, форкнулся на 200 прцессов на p100, сиди и жди.

Цитата

Ваш полный перебор требует порядка C*N*sqrt(M), где C - константа, N - ширина интервала, M - максимльное значение. Правильно написанное решето требует C'*sqrt(M)*log(N) операций. При этом перебор действительно может отработать быстрее, если C'/C > N/log(N); ну и что с того?

Да, то все верно сказано, но вы говоритео _последовательных_вычислениях_. А функция all создает суперпозицию состояний, которая(я кста не понял как она еще до конца работает, т.к. процессор всетки выполняет последовательно вычисления) может по некоторым данным ускорить в сотни раз вычисления, и просто так к этой суперпозиции состояний обратиться как к массиву нельзя, его надо "опредметить" чтоли...

первый приведенный код не просто так был приведен, я когда увидел анонс этих двух модулей, то 24 часа наверное сидел переводил, настолько это важным показалось (мне лично конечно)... потом дал в новость на www.linux.org.ru

...

30.12.2003 16:44
Эратосфена тоже можно "распараллелить"
только я не знаю как на perl'e это написать :)
Идея в следующем. Есть некий прцесс, читающий из stream'a числа и выдающий новый stream по следующему правилу: первое число входного stream'a объявляется простым, а на выход подаются все числа из входного потока не кратные первому. Если построить pipeline таких процессов и на вход первому дать 2..N, то в результате получишь что надо. Правда, для этого решения - чем больше процессоров тем лучше, но память не так вожна.

30.12.2003 17:11
F1
все-таки, боюсь, Вы не поняли
Цитата

> Кто ж Вас заставляет передавать 0..1000000000?
ну, как бы это, есть некий fun в perl'e чем короче прога, тем креативней писатель :)
(щас на меня выльют тонны грязи)...

Да никто не будет грязью поливать, просто, когда речь идет о сравнении скоростей алгоритмов, сравнивать их таким образом неприлично. Иначе бы сортировку все выполняли исключительно пузырьком. :-)
А вообще, с точки зрения лаконичности, Perl - не лучший язык для реализации математических алгоритмов. Лично меня в этой области Haskell очень впечатлил.

Цитата

Ну так нам же не в Урюпинск надо. Я параллелю задачу и мне жить дешевле, форкнулся на
200 прцессов на p100, сиди и жди.
...
Да, то все верно сказано, но вы говоритео _последовательных_вычислениях_. А функция
all создает суперпозицию состояний, которая(я кста не понял как она еще до конца
работает, т.к. процессор всетки выполняет последовательно вычисления) может по
некоторым данным ускорить в сотни раз вычисления, и просто так к этой суперпозиции
состояний обратиться как к массиву нельзя, его надо "опредметить" чтоли...

А вот для параллельных вычислений рассматриваемая задача - вовсе не лучший пример.
Параллелить алгоритм, скорость работы которого линейно пропорциональна ширине интервала, бессмысленно при сущестововании логарифмического алгоритма. Параллельные вычисления лишь уменьшают C в пропорциональное количество раз. Пусть у Вас 200 процессоров и Вы проверяете интервал в 1000 чисел за то же время, за которое один процессор проверяет 50; но на интервале в 50000 все ваши 200 процессоров опять проиграют одному-единственнному процессору с решетом.
Вот если бы стояла задача проверить на простоту одно-единственное произвольное число, тогда все верно - быстрее перебора до корня, наверное, сложно что-нибудь придумать, и параллельные вычисления дают реальный выигрыш.
"Решето", кстати, тоже можно параллелить, просто прирост эффективности будет хуже линейного... или это мне слабо навскидку придумать, как его распараллелить так, чтобы прирост был линейным. :-)
30.12.2003 17:22
Вы считаете себя слишком занятым для правильного цитирования?
Вы считаете себя слишком занятым для правильного цитирования? И полагаете, что модераторы должны заниматься этим вместо вас?
30.12.2003 17:29
Сергей Михайлов
проверка одного числа - совсем другая задача
Цитата

F1 писал:
Вот если бы стояла задача проверить на простоту одно-единственное произвольное число, тогда все верно - быстрее перебора до корня, наверное, сложно что-нибудь придумать, и параллельные вычисления дают реальный выигрыш.

Существует полиномиальный алгоритм проверки данного числа на простоту (правда я не утверждаю, что он быстро считает :), константы большие, понимаете ли). Но, кроме того, существует алгоритм (оценка сложности неизвестна), который числа порядка 10^100 проверяет за несколько минут (а, возможно, уже и секунд, учитывая рост производительности процессоров)
30.12.2003 18:46
hd
хорошо, учту это пожелание
гм, просто скопировать текст выделением в мозилловский почтовик, где оно автоматом расставит квотирование быстрее, чем руками вбить
Цитата

some text
. 12 символов против трех кликов мышкой.
30.12.2003 18:59
hd
вах, а тут окзывается все есть :)
просто как то не замечал... хыммм.
30.12.2003 19:00
hd
гм, если много процессоров то это другое
я про один проценссор говорил. ну да ладно. а perl - да ,он в 10 раз медленнее чем c/c++
30.12.2003 19:04
hd
гм...
ну, доводы веские, а мне чтобы что то доказать, писать надо, но это после нового года, а сейчас пора идти закупаться...

p.s. всех с новым годом.
31.12.2003 05:10
Клюкс
Ну не совсем
Цитата

Я параллелю задачу и мне жить дешевле, форкнулся на 200 прцессов на p100, сиди и жди.
Ну и получил 200 независимых процессов. Вот для этого количество процессоров еще более критично, чем для моего алгоритма.

Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти