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

numeros primos c# windows form

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 usar múltiples BitArray sy BitArray. ¿Y () ellos juntos?

Answer 1

Dejando a un lado la paralelización, no querrás 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}.

Debería ser capaz de paralelizar el algoritmo de factorización 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 debería poder 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 garantizar que cualquier trabajador que se espera para escribir haya 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 para garantizar que está leyendo partes válidas del tamiz sin tener que bloquear el bus en cada incremento de NORTE.

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

Answer 2

Puede ahorrar algo de tiempo al hacer referencias cruzadas 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 composites posteriores una vez que tocas una nueva prima p por primera vez, el primer múltiplo compuesto de p restante será p * p, ya que todo antes de eso ya ha sido eliminado. 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 de Miller-Rabin. La página de wikipedia es una buena introducción.

Answer 3

@DrPizza La creació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 con lo contrario, en cuyo caso me gustaría ver su generador de perfiles).

Solo tengo máquinas de un solo núcleo en casa, pero ejecuté un equivalente Java de su tamiz BitArray, y una versión de rosca única de la inversión del tamiz, manteniendo los números primos de marcado en una matriz y usando una rueda para reducir el espacio de búsqueda 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 N, paginación y ancho de banda más grandes.

Para valores medios de N (1e8 a 1e12), los números primos hasta sqrt (N) se pueden encontrar con bastante rapidez, 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 aquí . 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 un perfil, 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 optimizar.

En general, no vale la pena perfilar un bucle con una docena de instrucciones: 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 para 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

¿Estás 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 se multiplique para aprovechar los sistemas multi-core. Con cambios mínimos de código, puede crear bucles de subprocesos múltiples.

Answer 6

Hay un artículo muy bueno sobre el Tamiz de Eratóstenes: El Tamiz Genuino de Eratóstenes

Está en un entorno funcional, pero la mayor parte de la opimización también se aplica a una implementació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 hacer ningún trabajo innecesario.

Answer 7

También debería considerar un posible cambio de algoritmos .

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

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

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");
}
}