VBNet.Su - Visual Basic .NET. ASP .NET. Framework .NET.
Список форумов
Общий форум

Скорость алгоритма: "Доктор, что я не так делаю?"

Быстрый переход:
Общий форум / C# (Framework 1.x/2.x/3.x) (ссылка)04 января 2009 / 20:54
ostgals
Пользователь
ку 2.857421875+

вопросов: 1
советов: 0
ответов: 0
комментариев: 2


Возникла необходимость сгенерировать кучу простых чисел. Изучив вопрос, реализовал два класса-генератора, основанных на решете Эратосфена и решете Аткина саатвесна..

По теории, решето Аткина намного быстрее, чем решето Эратосфена. Однако, практическое использование моих классов доказывает обратное: Эратосфен опережае Аткина в 2 с лишним раза...

Очень подозреваю, что ошибся где-то в реализации, но не могу найти где.

PrimesEratosthenes.cs:
  1.  
  2.     public class PrimesEratosthenes
  3.     {
  4.         private byte[] primes;
  5.  
  6.         public PrimesEratosthenes(long MaxLimit)
  7.         {
  8.             Generate(MaxLimit);
  9.         }
  10.  
  11.         protected void Generate(long MaxLimit)
  12.         {
  13.             primes = new byte[MaxLimit];
  14.             Array.Clear(primes, 0, primes.Length);
  15.  
  16.             for (long n = 2; n < MaxLimit; n++)
  17.                 if (primes[n] == 0)
  18.                     for (long i = n * 2; i < MaxLimit; i += n) primes<em> = 1;
  19.         }
  20.     }
  21.  


PrimesAtkin.cs:
  1.  
  2.     public class PrimesAtkin
  3.     {
  4.         private byte[] primes;
  5.  
  6.         public PrimesAtkin(long MaxLimit)
  7.         {
  8.             Generate(MaxLimit);
  9.         }
  10.  
  11.         protected void Generate(long MaxLimit)
  12.         {
  13.             primes = new byte[MaxLimit];
  14.             Array.Clear(primes, 0, primes.Length);
  15.  
  16.             primes[2] = 1;
  17.             primes[3] = 1;
  18.  
  19.             long sqr_lim = (long)(Math.Sqrt((double)MaxLimit));
  20.             long x, y, n;
  21.            
  22.             for (x = 1; x < sqr_lim; x++)
  23.                 for (y = 1; y < sqr_lim; y++)
  24.                 {
  25.                     n = (4 * x * x) + (y * y);
  26.                     if (n <= MaxLimit && (n % 12 == 1 || n % 12 == 5)) primes[n] = (byte)(primes[n] == 0 ? 1 : 0);
  27.  
  28.                     n = (3 * x * x) + (y * y);
  29.                     if (n <= MaxLimit && n % 12 == 7) primes[n] = (byte)(primes[n] == 0 ? 1 : 0);
  30.  
  31.                     if (x > y)
  32.                     {
  33.                         n = (3 * x * x) - (y * y);
  34.                         if (n <= MaxLimit && n % 12 == 11) primes[n] = (byte)(primes[n] == 0 ? 1 : 0);
  35.                     }
  36.                 }
  37.  
  38.             for (x = 5; x < sqr_lim; x++)
  39.                 if (primes[x] == 1)
  40.                 {
  41.                     n = x * x;
  42.                     for (y = 2 * n; y < MaxLimit; y += n) primes[y] = 0;
  43.                 }
  44.         }
  45.     }
  46.  




Комментарий #1 (ссылка)05 января 2009 / 02:02
Skywalker
Пользователь
ку 2.904296875+

вопросов: 0
советов: 0
ответов: 0
комментариев: 5


  1. using System;
  2. using System.Diagnostics;
  3.  
  4. namespace PrimeFinder
  5. {
  6.     class Program
  7.     {
  8.         static void Main(string[] args)
  9.         {
  10.             System.Diagnostics.Stopwatch sw = new Stopwatch();
  11.             sw.Start();
  12.             PrimesEratosthenes prEra = new PrimesEratosthenes(50000000);
  13.             sw.Stop();
  14.             Console.WriteLine(sw.ElapsedTicks.ToString());
  15.             sw.Reset();
  16.             sw.Start();
  17.             PrimesAtkin prAtk = new PrimesAtkin(50000000);
  18.             sw.Stop();
  19.             Console.WriteLine(sw.ElapsedTicks.ToString());
  20.             Console.ReadLine();
  21.         }
  22.     }
  23.  
  24.     public class PrimesEratosthenes
  25.     {
  26.         private bool[] primes;
  27.  
  28.         public PrimesEratosthenes(long MaxLimit)
  29.         {
  30.             Generate(MaxLimit);
  31.         }
  32.  
  33.         protected void Generate(long MaxLimit)
  34.         {
  35.             primes = new bool[MaxLimit+1];
  36.  
  37.             for (long n = 2; n <= MaxLimit; n++)
  38.                 if (!primes[n])
  39.                     for (long i = n * 2; i <= MaxLimit; i += n) primes<em> = true;
  40.         }
  41.     }
  42.  
  43.     public class PrimesAtkin
  44.     {
  45.         private bool[] primes;
  46.  
  47.         public PrimesAtkin(long MaxLimit)
  48.         {
  49.             Generate(MaxLimit);
  50.         }
  51.  
  52.         protected void Generate(long MaxLimit)
  53.         {
  54.             primes = new bool[MaxLimit+1];
  55.  
  56.             primes[2] = true;
  57.             primes[3] = true;
  58.  
  59.             long sqr_lim = (long)(Math.Sqrt((double)MaxLimit));
  60.             long x2, y2, i, j, n;
  61.  
  62.             x2 = 0;
  63.             for (i = 1; i <= sqr_lim; i++)
  64.             {
  65.                 x2 += 2 * i - 1;
  66.                 y2 = 0;
  67.                 for (j = 1; j <= sqr_lim; j++)
  68.                 {
  69.                     y2 += 2 * j - 1;
  70.                     n = 4 * x2 + y2;
  71.                     if (n <= MaxLimit && (n % 12 == 1 || n % 12 == 5)) primes[n] = !primes[n];
  72.  
  73.                     n -= x2;
  74.                     if (n <= MaxLimit && n % 12 == 7) primes[n] = !primes[n];
  75.  
  76.                     n -= 2 * y2;
  77.                     if (i > j && n <= MaxLimit && n % 12 == 11) primes[n] = !primes[n];
  78.                 }
  79.             }
  80.  
  81.             for (i = 5; i <= sqr_lim; i++)
  82.                 if (primes<em>)
  83.                 {
  84.                     n = i * i;
  85.                     for (j = n; j <= MaxLimit; j += n) primes[j] = false;
  86.                 }
  87.         }
  88.     }
  89. }



результат:
эрато: 26902581
аткин: 21265767

но все равно чот медленно, если найдешь в чом дело, напиши, а то аж интересно стало...
..и было сказано:
Спасибо: VB .NET Programmer
Комментарий #2 (ссылка)05 января 2009 / 18:51
ostgals
Пользователь
ку 2.857421875+

вопросов: 1
советов: 0
ответов: 0
комментариев: 2


Это оптимизированный вариант. Ога, я его видел, но реализовал только классический.

Как я понял, что на самом деле алгоритм Аткина будет быстрее Эратосфена только для интервалов 10^10 и более. Мне для моих целей достаточно 10^7, так что я смело юзаю доброго старого Эратика :)

For intervals larger about 10^9, surely for those > 10^10, the Sieve of Eratosthenes is outperformed by the Sieve of Atkins and Bernstein which uses irreducible binary quadratic forms.


Комментарий #3 (ссылка)05 января 2009 / 19:02
Skywalker
Пользователь
ку 2.904296875+

вопросов: 0
советов: 0
ответов: 0
комментариев: 5


я видел в инете скриншот, чувак прогу написал, и лимит был где-то 1000000, аткин был быстрее раза в 3. так что странно все-таки)
Комментарий #4 (ссылка)05 января 2009 / 19:04
Skywalker
Пользователь
ку 2.904296875+

вопросов: 0
советов: 0
ответов: 0
комментариев: 5


нет, я ошибся, аткин у него медленнее)

http://adwcom.ru/wp-content/uploads/2008/07/image8.png
Страницы:    < назад    ·    вперед >
1
Зарегистрируйтесь, чтобы иметь возможность участвовать в жизни форума.