2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Нахождение простых чисел без деления
Сообщение03.07.2009, 00:22 
Заслуженный участник


04/05/09
4582
Какая разница как оно называется. В чём отличие кроме названия и скорости?
Кстати, решето - тоже сепаратор. :)

 Профиль  
                  
 
 Re: Нахождение простых чисел без деления
Сообщение03.07.2009, 08:48 
Заблокирован
Аватара пользователя


03/05/09

288
Gomel BY
Этот алгоритм по сути проверка на делимость, здесь также можно выбирать только нечетные или 6*к+-1, ограничиваться до корня и т.д., зато нет деления.
Если кто-то хочет называть решетом- нехай себе, абы не в печку.

 Профиль  
                  
 
 Re: Нахождение простых чисел без деления
Сообщение14.07.2009, 21:42 
Заблокирован
Аватара пользователя


03/05/09

288
Gomel BY
Прошу еще раз обратить внимание на небольшое редактирование темы в начале, если кто не понял.

 Профиль  
                  
 
 Re: Нахождение простых чисел без деления
Сообщение14.07.2009, 23:09 
Заслуженный участник


04/05/09
4582
Прошу ещё раз обратить внимание на то, что приведённый алгоритм медленнее даже тривиального деления на все простые числа (типа тех, что приведёны на Википедии), не говоря уж о более эффективном решете Эратосфена.
А тривиальное деление быстрее потому, что делим только до первого нуля, а у вас приходится считать все остатки до конца.

 Профиль  
                  
 
 Re: Нахождение простых чисел без деления
Сообщение18.07.2009, 21:05 
Заблокирован
Аватара пользователя


03/05/09

288
Gomel BY
venco в сообщении #228867 писал(а):
Прошу ещё раз обратить внимание на то, что приведённый алгоритм медленнее даже тривиального деления на все простые числа (типа тех, что приведёны на Википедии), не говоря уж о более эффективном решете Эратосфена.
А тривиальное деление быстрее потому, что делим только до первого нуля, а у вас приходится считать все остатки до конца.


Опять вы о скорости, предлагаю на Паскале посоревноваться конкрентно до 100 000 или более и сравнить. Ваша привязанность к предварительным оценкам понятна, но я предлагаю на практике убедиться. Паскаль, без вставок Ассемблера я выбираю потому как почти за 20 лет привык, правда, последнее время Маткад устраивает - в пределах моей точности и скорости.
В общем, если не против, я согласен на публичную дуэль, чтобы определить рамки эффективности.
В общем, предлагаю найти Н=1000,..1000000 простое число по договоренности.
При этом предъявлять прогу на Паскале с комментариями пжлт, без фокусов, чтобы оба поняли и у себя на компе и у других выполнили и сравнили. Версию паскаля указать, у меня все есть даже фри, но делфу не ставил, так что давай попроще.

 Профиль  
                  
 
 Re: Нахождение простых чисел без деления
Сообщение19.07.2009, 01:21 
Заслуженный участник


04/05/09
4582
У меня вообще паскаля нет. Если получится gcp поставить, попробую.

 Профиль  
                  
 
 Re: Нахождение простых чисел без деления
Сообщение19.07.2009, 07:17 
Заблокирован
Аватара пользователя


03/05/09

288
Gomel BY
Могу прислать ТП7 - 1мБ, сам тоже на нем буду.

 Профиль  
                  
 
 Re: Нахождение простых чисел без деления
Сообщение19.07.2009, 07:44 
Заслуженный участник


04/05/09
4582
Сделал на GNU Pascal.
код: [ скачать ] [ спрятать ]
Используется синтаксис Pascal
Program primes;

{
 Get current time as precise as possible.
 You can replace this function with anything suitable on your compiler.
 This version reads CPU clock counter with RDTSC instruction.
 It's then divided by the clock frequency - replace it with frequency of your CPU.
 I have 2.4 GHz Intel Core 2 processor.
 }

Function FineTime : Real;
Var
   frequency : Real = 2.4e9; { CPU frequency }
   clock     : Cardinal attribute (Size = 64);
begin
   asm volatile("rdtsc" : "=A" (clock));
   FineTime := clock / frequency;
end;

{ Count number of primes up to n using simple sieve of Eratosthenes. }
Function prime_count1(n : Integer) : Integer;
Type
   TSieve = Array[0..999999999] of Boolean;
   PSieve = ^TSieve;
Var      
   i           : Integer;
   j           : Integer;
   prime_count : Integer;
   prime       : PSieve; { dynamically allocated array for the sieve }
begin
   GetMem(prime, (n+1)*sizeof(Boolean)); { allocate the sieve array }
   FillChar(prime^, (n+1)*sizeof(Boolean), True); { fill it with ones }
   prime_count := 0;
   for i := 2 to n do
   begin
      if prime^[i] then { next prime found }
      begin
         Inc(prime_count);
         { mark all multiplies as non-primes: }
         j := i*2;
         while j <= n do
         begin
            prime^[j] := False;
            Inc(j, i);
         end;
      end;
   end;
   FreeMem(prime, (n+1)*sizeof(Boolean)); { free sieve array }
   prime_count1 := prime_count;
end;

{ run prime counting function and determine its runtime }
Procedure test1(n : Integer);
Var
   count : Integer;
   time  : Real;
begin
   time := FineTime();
   count := prime_count1(n);
   time := FineTime() - time;
   WriteLn('Number of primes up to ',n,' - ',count,'   time spent: ',time:0:3,' secs');
end;
   
begin
   test1(100000);
   test1(1000000);
   test1(10000000);
   test1(100000000);
end.
 

Команда компиляции: gpc -O3 -o primes2p.exe primes2p.pas
Результаты:
Number of primes up to 100000 - 9592 time spent: 0.001 secs
Number of primes up to 1000000 - 78498 time spent: 0.008 secs
Number of primes up to 10000000 - 664579 time spent: 0.408 secs
Number of primes up to 100000000 - 5761455 time spent: 5.770 secs

Я имплементировал также ваш алгоритм (как я его понял) и вот его результаты для сравнения:
Number of primes up to 100000 - 9592 time spent: 3.002 secs

 Профиль  
                  
 
 Re: Нахождение простых чисел без деления
Сообщение21.07.2009, 22:57 
Заблокирован
Аватара пользователя


03/05/09

288
Gomel BY
Уважаемый оппонент, я решил отказаться от споров.
Мой алгоритм проверяет делимость чисел, при этом при каждом акте проверки делить не надо, а всего лишь добавить единицу!
В остальном ничем не отличается от проверки на делимость и ничего общего не имеет с решетом.
Спасибо за внимание.

 Профиль  
                  
 
 Re: Нахождение простых чисел без деления
Сообщение22.07.2009, 10:38 
Заблокирован
Аватара пользователя


03/05/09

288
Gomel BY
venco в сообщении #228867 писал(а):
А тривиальное деление быстрее потому, что делим только до первого нуля, а у вас приходится считать все остатки до конца.


Можно не считать до конца все остатки - обнаружив 0 перейти к следующему числу, только для вычисления остатков делать коррекцию, добавляя не 1, а больше по модулю.
Примерно так: от последнего простого помним сколько добавить и проверяем, а вот если обнаружится простое, то коррекцию действительно придется ко всем ранее обнаруженным применить.
Это только наброски, конкрентно можно уточнить.
Впрочем, не стоит так изгаляться, проще добавлять по 1 ко всем по ихним модулям.

 Профиль  
                  
 
 Re: Нахождение простых чисел без деления
Сообщение28.07.2009, 21:08 
Заблокирован
Аватара пользователя


03/05/09

288
Gomel BY
Цитата:
Const Rmax = 9;
Var
P:array [1..Rmax] of integer;{Prime numbers}
R:array [1..Rmax] of integer;{Rests}
Num,Nmax,N :integer;
Pyes :boolean;
begin
writeln('Prime numbers search by garskov@yandex.ru Ver 13.09.2009');
Num:=2;P[1]:=2;Nmax:=1;R[1]:=0;
repeat
inc(Num); Pyes:=true;
write(Num:6);
for N:=1 to Nmax do
begin
inc(R[N]);
if R[N] = P[N] then begin R[N]:=0; Pyes:=False; end;
Write(R[N]:4);
end;
if Pyes then begin inc(Nmax);P[Nmax]:=Num;R[Nmax]:=0;write(Num:4,'!');end;
writeln;
until Nmax = Rmax;
write('Enter for exit');Readln;End.

 Профиль  
                  
 
 Re: Нахождение простых чисел без деления
Сообщение14.09.2009, 18:43 
Заблокирован
Аватара пользователя


03/05/09

288
Gomel BY
Комментарий, по русски пояснение:
Деление заменяется добавлением единицы по модулю - самый примитивный вариант, но интересно, как этот алгоритм себя проявит в скорости типа найти все первые миллион или меньше миллиона.
Я полагаю, используя ассемблер в критических вставках, можно посоревноваться.
Эта программа демонстрационная, никаких приемов эффективности,
только чтобы алгоритм показать понятней.
Послал на сайт который взял на себя простые числы во всем мире
http://primes.utm.edu/
оне мудаки не ответили, хотя на моем инглише вроде ясно пояснил; ну и хрен с ними , потом сами пожалеют.
Учите русский. Это в перспективе будет второй язык после китайского

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 27 ]  На страницу Пред.  1, 2

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group