¿La forma más rápida de calcular números primos en C#?

Question

De hecho, tengo una respuesta a mi pregunta pero no está paralelizada, así que estoy interesado en formas de mejorar el algoritmo. De todos modos, podría ser útil como es para algunas personas.

int Until = 20000000; 
BitArray PrimeBits = new BitArray(Until, true); 

/* 
* Sieve of Eratosthenes 
* PrimeBits is a simple BitArray where all bit is an integer 
* and we mark composite numbers as false 
*/ 

PrimeBits.Set(0, false); // You don't actually need this, just 
PrimeBits.Set(1, false); // remindig you that 2 is the smallest prime 

for (int P = 2; P < (int)Math.Sqrt(Until) + 1; P++) 
    if (PrimeBits.Get(P)) 
     // These are going to be the multiples of P if it is a prime 
     for (int PMultiply = P * 2; PMultiply < Until; PMultiply += P) 
      PrimeBits.Set(PMultiply, false); 

// We use this to store the actual prime numbers 
List<int> Primes = new List<int>(); 

for (int i = 2; i < Until; i++) 
    if (PrimeBits.Get(i)) 
     Primes.Add(i); 

Tal vez podría utilizar múltiples BitArray s y BitArray.And() juntos?

Answer 1

Puede ahorrar algo de tiempo haciendo una referencia cruzada de su matriz de bits con una lista doblemente enlazada, para que pueda avanzar más rápidamente al siguiente primo.

Además, al eliminar compuestos posteriores una vez que golpea una nueva prima p por primera vez, el primer múltiplo compuesto de p restante será p * p, ya que todo lo anterior se eliminó. De hecho, solo necesita multiplicar p por todos los primos potenciales restantes que quedan después en la lista, deteniéndose tan pronto como el producto esté fuera de rango (mayor que Hasta).

También hay algunos buenos algoritmos probabilísticos, como la prueba Miller-Rabin. The wikipedia page es una buena introducción.

Answer 2

Paralelización aparte, no querrá calcular sqrt (Until) en cada iteración. También puede suponer múltiplos de 2, 3 y 5 y solo calcular para N% 6 en {1,5} o N% 30 en {1,7,11,13,17,19,23,29}.

Debe ser capaz de paralelizar el algoritmo de factoraje con bastante facilidad, ya que la etapa Nth solo depende del resultado sqrt (n) th, por lo que después de un tiempo no habrá ningún conflicto. Pero ese no es un buen algoritmo, ya que requiere mucha división.

También debe ser capaz de paralelizar los algoritmos de tamizado, si tiene paquetes de trabajo de escritorios que se garantiza que se completarán antes de una lectura. En su mayoría, los escritores no deberían entrar en conflicto con el lector; al menos una vez que haya realizado algunas entradas, debería funcionar al menos N sobre el lector, por lo que solo necesita una lectura sincronizada con cierta frecuencia (cuando N supera la última lectura sincronizada valor). No debería necesitar sincronizar la matriz bool en cualquier número de subprocesos de escritor, ya que no surgen conflictos de escritura (en el peor de los casos, más de un subproceso escribirá un verdadero en el mismo lugar).

El problema principal sería asegurarse de que cualquier trabajador que se espera para escribir ha finalizado. En C++ usaría un compare-and-set para cambiar al trabajador que se espera en cualquier momento. No soy un experto en C#, así que no sé cómo hacerlo en ese idioma, pero la función Winlock InterlockedCompareExchange debería estar disponible.

También puede probar un enfoque basado en actores, ya que de esa manera puede programar los actores que trabajan con los valores más bajos, lo que puede ser más fácil garantizar que está leyendo partes válidas del tamiz sin tener que bloquear el bus en cada incremento de N.

De cualquier manera, debe asegurarse de que todos los trabajadores hayan superado la entrada N antes de leerla, y el costo de hacer eso es cuando se realiza la compensación entre paralelo y serie.

Answer 3

@DrPizza La elaboración de perfiles solo realmente ayuda a mejorar una implementación, no revela oportunidades para la ejecución paralela, o sugiere mejores algoritmos (a menos que tenga experiencia de lo contrario, en cuyo caso me gustaría ver su perfilador))

He únicas máquinas de un solo núcleo en el hogar, pero se encontró con un equivalente Java del tamiz BitArray, y una sola versión roscada de la inversión de la criba - la celebración de los números primos marcado en una matriz, y usando un wheel para reducir el espacio de búsqueda por un factor de cinco, luego marcar una matriz de bits en incrementos de la rueda usando cada marca de cebado. También reduce el almacenamiento a O (sqrt (N)) en lugar de O (N), lo que ayuda a ambos en términos de mayor N, paginación y ancho de banda.

Para valores medios de N (1e8 a 1e12), los números primos hasta sqrt (N) se pueden encontrar bastante rápido, y después de eso, podrá paralelizar la búsqueda posterior en la CPU con bastante facilidad. En mi máquina de un solo núcleo, el acercamiento de la rueda encuentra primos de hasta 1e9 en 28s, mientras que su tamiz (después de mover el sqrt fuera del ciclo) toma 86s; la mejora se debe a la rueda; la inversión significa que puede manejar N más grande que 2^32 pero lo hace más lento. El código se puede encontrar here. Puede paralelizar la salida de los resultados del tamiz ingenuo después de pasar el sqrt (N) también, ya que la matriz de bits no se modifica después de ese punto; pero una vez que se trata de N lo suficientemente grande como para que importe, el tamaño de la matriz es demasiado grande para los enteros.

Answer 4

Sin perfiles no podemos decir qué parte del programa necesita optimización.

Si estuviera en un sistema grande, entonces uno usaría un generador de perfiles para encontrar que el generador de números primos es la parte que necesita ser optimizado.

Hacer perfiles de un bucle con una docena de instrucciones no suele valer la pena - la sobrecarga del generador de perfiles es significativa en comparación con el cuerpo del bucle, y sobre las únicas formas de mejorar un bucle tan pequeño es cambiar el algoritmo hacer menos iteraciones Entonces, IME, una vez que haya eliminado cualquier función costosa y tenga un objetivo conocido de unas pocas líneas de código simple, es mejor cambiar el algoritmo y cronometrar una ejecución de extremo a extremo que tratar de mejorar el código por nivel de instrucción perfilado

Answer 5

También debe considerar un posible cambio de algorithms.

Considere que puede ser más económico simplemente agregar los elementos a su lista, tal como los encuentra.

Quizás el espacio preasignado para su lista haga que sea más barato construir/poblar.

Answer 6

¿Está tratando de encontrar nuevos números primos? Esto puede sonar estúpido, pero es posible que pueda cargar algún tipo de estructura de datos con números primos conocidos. Estoy seguro de que alguien tiene una lista. Puede ser un problema mucho más fácil encontrar números existentes que calculen nuevos.

También puede consultar Microsofts Parallel FX Library para hacer que su código existente tenga múltiples subprocesos para aprovechar los sistemas multi-core. Con cambios mínimos de código, puede crear bucles de subprocesos múltiples.

Answer 7

Hay un muy buen artículo sobre la criba de Eratóstenes: The Genuine Sieve of Eratosthenes

Está en un entorno funcional, pero la mayor parte del opimization también se aplican a una aplicación de procedimiento en C#.

Las dos optimizaciones más importantes son comenzar a tachar en P^2 en lugar de 2 * P y usar una rueda para los siguientes números primos.

Para concurrencia, puede procesar todos los números hasta P^2 en paralelo a P sin realizar ningún trabajo innecesario.

Answer 8

void PrimeNumber(long number) 
    { 
     bool IsprimeNumber = true; 
     long value = Convert.ToInt32(Math.Sqrt(number)); 
     if (number % 2 == 0) 
     { 
      IsprimeNumber = false; 
      MessageBox.Show("No It is not a Prime NUmber"); 
      return; 
     } 
     for (long i = 3; i <= value; i=i+2) 
     {    
      if (number % i == 0) 
      { 

       MessageBox.Show("It is divisible by" + i); 
       IsprimeNumber = false; 
       break; 
      } 

     } 
     if (IsprimeNumber) 
     { 
      MessageBox.Show("Yes Prime NUmber"); 
     } 
     else 
     { 
      MessageBox.Show("No It is not a Prime NUmber"); 
     } 
    }