C #: Aplicación del tamiz de Atkin
https://stackoverflow.com/questions/1569127
-
21-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Me preguntaba si alguien aquí tiene una buena aplicación de la criba de Atkin que les gustaría compartir.
Estoy tratando de ponerlo en práctica, pero no puedo envolver mi cabeza alrededor de ella. Aquí es lo que tengo hasta ahora.
public class Atkin : IEnumerable<ulong>
{
private readonly List<ulong> primes;
private readonly ulong limit;
public Atkin(ulong limit)
{
this.limit = limit;
primes = new List<ulong>();
}
private void FindPrimes()
{
var isPrime = new bool[limit + 1];
var sqrt = Math.Sqrt(limit);
for (ulong x = 1; x <= sqrt; x++)
for (ulong y = 1; y <= sqrt; y++)
{
var n = 4*x*x + y*y;
if (n <= limit && (n % 12 == 1 || n % 12 == 5))
isPrime[n] ^= true;
n = 3*x*x + y*y;
if (n <= limit && n % 12 == 7)
isPrime[n] ^= true;
n = 3*x*x - y*y;
if (x > y && n <= limit && n % 12 == 11)
isPrime[n] ^= true;
}
for (ulong n = 5; n <= sqrt; n++)
if (isPrime[n])
for (ulong k = n*n; k <= limit; k *= k)
isPrime[k] = false;
primes.Add(2);
primes.Add(3);
for (ulong n = 5; n <= limit; n++)
if (isPrime[n])
primes.Add(n);
}
public IEnumerator<ulong> GetEnumerator()
{
if (!primes.Any())
FindPrimes();
foreach (var p in primes)
yield return p;
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}
He intentado prácticamente sólo a "traducir" el pseudocódigo que aparece al Wikipedia , pero no está funcionando correctamente. Así que, o he entendido algo o simplemente hecho algo malo. O más probable es tanto ...
Tenga una lista de los 500 primeros números primos que uso como una prueba y mi aplicación falla en el número 40 (o 41?).
valores difieren en el índice [40]
Esperado: 179
Pero fue de: 175
¿Es capaz de encontrar mi error, ¿Tiene una implementación por ahí que se puede compartir, o ambos?
La prueba exacta estoy usando el siguiente aspecto:
public abstract class AtkinTests
{
[Test]
public void GetEnumerator_FirstFiveHundredNumbers_AreCorrect()
{
var sequence = new Atkin(2000000);
var actual = sequence.Take(500).ToArray();
var expected = First500;
CollectionAssert.AreEqual(expected, actual);
}
private static readonly ulong[] First500 = new ulong[]
{
2, 3, 5, 7, 11, 13, 17, ...
};
}
Solución
Este código:
for (ulong k = n*n; k <= limit; k *= k)
isPrime[k] = false;
no parece ser una traducción fiel de este pseudocódigo:
is_prime(k) ← false, k ∈ {n², 2n², 3n², ..., limit}
Su código parece que tendrá una duración de n * n, n ^ 4, n ^ 8, etc. es decir, elevar al cuadrado cada vez en lugar de añadir n-cuadrado cada vez. Prueba esto:
ulong nSquared = n * n;
for (ulong k = nSquared; k <= limit; k += nSquared)
isPrime[k] = false;
Otros consejos
El última respuesta por Aaron Mugatroyd a partir de la fuente de Python traducida de una criba de Atkin (SOA) no es demasiado malo, pero puede ser mejorado en varios aspectos como se echa de menos algunas optimizaciones importantes, de la siguiente manera:
-
Su respuesta no utiliza el módulo completo 60 versión original Atkin y Bernstein de la criba, sino más bien una variación ligeramente mejorada del pseudo código del artículo de Wikipedia lo utiliza en un factor de 0,36 con la de tamiz numérico operaciones de palanca / de desecho combinada; mi código siguiente se utiliza la página de códigos no segmento de seudo razonablemente eficiente según mis comentarios en una respuesta al comentar sobre el tamiz de Atkin que utiliza un factor de aproximadamente 0,26 veces el intervalo numérico para reducir la cantidad de trabajo realizado a aproximadamente un factor de aproximadamente dos séptimos.
-
Su código reduce el tamaño del búfer de sólo tener representaciones de número impar, mientras que mi código adicional bit de paquetes para eliminar cualquier representación de los números divisible por tres y cinco, así como aquellos divisible por dos implicado por "probabilidades de sólo "; esto reduce los requisitos de memoria en un factor adicional de casi la mitad (a 8/15) y ayuda a hacer un mejor uso de los cachés de la CPU para un aumento adicional de la velocidad debido a la reducción del tiempo medio de acceso a la memoria.
-
Mi código cuenta el número de números primos usando una tabla de consulta rápida (LUT) Técnica de recuento pop para tomar casi no hay tiempo para contar en comparación con el segundo aproximadamente un utilizando la técnica de bit por bit que utiliza; sin embargo, en este código de ejemplo incluso ese pequeño tiempo se saca de la porción de temporizado del código.
-
Por último, mi código optimiza las operaciones de manipulación de bits para un mínimo de código por bucle interno. Por ejemplo, no utiliza continuo cambio justo al lado de uno a producir el índice de representación extraño y, de hecho, poco cambio en absoluto escribiendo todos los bucles internos como módulo constante (igual a la posición de bit) operaciones. A su vez, el código traducido de Aaron es bastante ineficaz en las operaciones como por ejemplo en primer sacrificio libre cuadrado se suma al cuadrado de la flor con el índice a continuación, busca un resultado extraño en lugar de limitarse a añadir dos veces el cuadrado de modo que no se requiera la comprobación ; entonces se hace que incluso el redundante cheque desplazando el número correcto por uno (dividiendo por dos) antes de hacer la operación de sacrificio en el bucle interior, tal como lo hace para todos los bucles. Este código ineficiente no hará mucho de una diferencia en tiempo de ejecución para grandes gamas de uso de esta técnica "gran tamiz tampón array", ya que la mayoría de las veces por operación se utiliza en acceso a la memoria RAM (alrededor de 37 ciclos de reloj de la CPU o más para una rango de un mil millones), pero hará que el tiempo de ejecución mucho más lento de lo que debe ser para intervalos más pequeños que encajan en las cachés de CPU; en otras palabras, se establece un límite demasiado alto más bajo en la velocidad de ejecución por operación.
El código es como sigue:
//Sieve of Atkin based on full non page segmented modulo 60 implementation...
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
namespace NonPagedSoA {
//implements the non-paged Sieve of Atkin (full modulo 60 version)...
class SoA : IEnumerable<ulong> {
private ushort[] buf = null;
private long cnt = 0;
private long opcnt = 0;
private static byte[] modPRMS = { 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61 };
private static ushort[] modLUT;
private static byte[] cntLUT;
//initialize the private LUT's...
static SoA() {
modLUT = new ushort[60];
for (int i = 0, m = 0; i < modLUT.Length; ++i) {
if ((i & 1) != 0 || (i + 7) % 3 == 0 || (i + 7) % 5 == 0) modLUT[i] = 0;
else modLUT[i] = (ushort)(1 << (m++));
}
cntLUT = new byte[65536];
for (int i = 0; i < cntLUT.Length; ++i) {
var c = 0;
for (int j = i; j > 0; j >>= 1) c += j & 1;
cntLUT[i] = (byte)c;
}
}
//initialization and all the work producing the prime bit array done in the constructor...
public SoA(ulong range) {
this.opcnt = 0;
if (range < 7) {
if (range > 1) {
cnt = 1;
if (range > 2) this.cnt += (long)(range - 1) / 2;
}
this.buf = new ushort[0];
}
else {
this.cnt = 3;
var nrng = range - 7; var lmtw = nrng / 60;
//initialize sufficient wheels to non-prime
this.buf = new ushort[lmtw + 1];
//Put in candidate primes:
//for the 4 * x ^ 2 + y ^ 2 quadratic solution toggles - all x odd y...
ulong n = 6; // equivalent to 13 - 7 = 6...
for (uint x = 1, y = 3; n <= nrng; n += (x << 3) + 4, ++x, y = 1) {
var cb = n; if (x <= 1) n -= 8; //cancel the effect of skipping the first one...
for (uint i = 0; i < 15 && cb <= range; cb += (y << 2) + 4, y += 2, ++i) {
var cbd = cb / 60; var cm = modLUT[cb % 60];
if (cm != 0)
for (uint c = (uint)cbd, my = y + 15; c < buf.Length; c += my, my += 30) {
buf[c] ^= cm; // ++this.opcnt;
}
}
}
//for the 3 * x ^ 2 + y ^ 2 quadratic solution toggles - x odd y even...
n = 0; // equivalent to 7 - 7 = 0...
for (uint x = 1, y = 2; n <= nrng; n += ((x + x + x) << 2) + 12, x += 2, y = 2) {
var cb = n;
for (var i = 0; i < 15 && cb <= range; cb += (y << 2) + 4, y += 2, ++i) {
var cbd = cb / 60; var cm = modLUT[cb % 60];
if (cm != 0)
for (uint c = (uint)cbd, my = y + 15; c < buf.Length; c += my, my += 30) {
buf[c] ^= cm; // ++this.opcnt;
}
}
}
//for the 3 * x ^ 2 - y ^ 2 quadratic solution toggles all x and opposite y = x - 1...
n = 4; // equivalent to 11 - 7 = 4...
for (uint x = 2, y = x - 1; n <= nrng; n += (ulong)(x << 2) + 4, y = x, ++x) {
var cb = n; int i = 0;
for ( ; y > 1 && i < 15 && cb <= nrng; cb += (ulong)(y << 2) - 4, y -= 2, ++i) {
var cbd = cb / 60; var cm = modLUT[cb % 60];
if (cm != 0) {
uint c = (uint)cbd, my = y;
for ( ; my >= 30 && c < buf.Length; c += my - 15, my -= 30) {
buf[c] ^= cm; // ++this.opcnt;
}
if (my > 0 && c < buf.Length) { buf[c] ^= cm; /* ++this.opcnt; */ }
}
}
if (y == 1 && i < 15) {
var cbd = cb / 60; var cm = modLUT[cb % 60];
if ((cm & 0x4822) != 0 && cbd < (ulong)buf.Length) { buf[cbd] ^= cm; /* ++this.opcnt; */ }
}
}
//Eliminate squares of base primes, only for those on the wheel:
for (uint i = 0, w = 0, pd = 0, pn = 0, msk = 1; w < this.buf.Length ; ++i) {
uint p = pd + modPRMS[pn];
ulong sqr = (ulong)p * (ulong)p; //to handle ranges above UInt32.MaxValue
if (sqr > range) break;
if ((this.buf[w] & msk) != 0) { //found base prime, square free it...
ulong s = sqr - 7;
for (int j = 0; s <= nrng && j < modPRMS.Length; s = sqr * modPRMS[j] - 7, ++j) {
var cd = s / 60; var cm = (ushort)(modLUT[s % 60] ^ 0xFFFF);
//may need ulong loop index for ranges larger than two billion
//but buf length only good to about 2^31 * 60 = 120 million anyway,
//even with large array setting and half that with 32-bit...
for (ulong c = cd; c < (ulong)this.buf.Length; c += sqr) {
this.buf[c] &= cm; // ++this.opcnt;
}
}
}
if (msk >= 0x8000) { msk = 1; pn = 0; ++w; pd += 60; }
else { msk <<= 1; ++pn; }
}
//clear any overflow primes in the excess space in the last wheel/word:
var ndx = nrng % 60; //clear any primes beyond the range
for (; modLUT[ndx] == 0; --ndx) ;
this.buf[lmtw] &= (ushort)((modLUT[ndx] << 1) - 1);
}
}
//uses a fast pop count Look Up Table to return the total number of primes...
public long Count {
get {
long cnt = this.cnt;
for (int i = 0; i < this.buf.Length; ++i) cnt += cntLUT[this.buf[i]];
return cnt;
}
}
//returns the number of toggle/cull operations used to sieve the prime bit array...
public long Ops {
get {
return this.opcnt;
}
}
//generate the enumeration of primes...
public IEnumerator<ulong> GetEnumerator() {
yield return 2; yield return 3; yield return 5;
ulong pd = 0;
for (uint i = 0, w = 0, pn = 0, msk = 1; w < this.buf.Length; ++i) {
if ((this.buf[w] & msk) != 0) //found a prime bit...
yield return pd + modPRMS[pn]; //add it to the list
if (msk >= 0x8000) { msk = 1; pn = 0; ++w; pd += 60; }
else { msk <<= 1; ++pn; }
}
}
//required for the above enumeration...
IEnumerator IEnumerable.GetEnumerator() {
return this.GetEnumerator();
}
}
class Program {
static void Main(string[] args) {
Console.WriteLine("This program calculates primes by a simple full version of the Sieve of Atkin.\r\n");
const ulong n = 1000000000;
var elpsd = -DateTime.Now.Ticks;
var gen = new SoA(n);
elpsd += DateTime.Now.Ticks;
Console.WriteLine("{0} primes found to {1} using {2} operations in {3} milliseconds.", gen.Count, n, gen.Ops, elpsd / 10000);
//Output prime list for testing...
//Console.WriteLine();
//foreach (var p in gen) {
// Console.Write(p + " ");
//}
//Console.WriteLine();
//Test options showing what one can do with the enumeration, although more slowly...
// Console.WriteLine("\r\nThere are {0} primes with the last one {1} and the sum {2}.",gen.Count(),gen.Last(),gen.Sum(x => (long)x));
Console.Write("\r\nPress any key to exit:");
Console.ReadKey(true);
Console.WriteLine();
}
}
}
Este código se ejecuta alrededor de dos veces tan rápido como código de Aaron (alrededor de 2,7 segundos utilizando el modo de 64 bits o de 32 bits en un i7-2700K (3,5 GHz) con el tampón de aproximadamente 16,5 Megabytes y aproximadamente 0258 millones de palanca combinada / cuadrado prime operaciones de desecho libre (que se pueden mostrar descomentando la "++ this.opcnt" estados) para una serie tamiz de mil millones, en comparación con 5.4 / 6.2 segundos (32 bits / 64 bits) para su código sin el recuento tiempo y casi el doble de la utilización de la memoria utilizando aproximadamente 0.359 mil millones de operaciones de palanca / de desecho combinada para tamizado de hasta mil millones.
A pesar de que es más rápido que sus probabilidades de sólo ingenuas más optimizadas de aplicación del tamiz no paginado de Eratóstenes (SOE), que no hacen que el tamiz de Atkin más rápido que la criba de Eratóstenes como si uno aplica técnicas similares tal como se utilizan en la anterior implementación de SOA a la SoE plus utiliza máxima factorización rueda, el SOE sobre ésimoe misma velocidad que esto.
Análisis: Aunque el número de operaciones para el SoE totalmente optimizado son aproximadamente el mismo que el número de operaciones para el SOA para una gama tamiz de mil millones, el cuello de botella principal de estas no paginada implementaciones es acceso a la memoria una vez que el tamaño del búfer de tamiz excede los tamaños de caché CPU (32 kilobytes de memoria caché L1 en un acceso ciclo de reloj, 256 caché Kilobytes L2 en alrededor de cuatro ciclos de reloj de tiempo de acceso y 8 Megabytes de memoria caché L3 en alrededor de 20 ciclos de reloj de tiempo de acceso para mi i7), después de lo cual el acceso a memoria puede exceder de un centenar de ciclos de reloj.
Ahora ambos tienen un factor de aproximadamente ocho mejora en la velocidad de acceso de memoria cuando uno se adapta a los algoritmos de segmentación de la página, así uno puede tamizar rangos que no cabrían lo contrario en la memoria disponible. Sin embargo, el estado del medio ambiente continúa ganando más de la SOA como el rango de tamiz empieza a ser muy grande debido a las dificultades en la aplicación del "primos plaza libre" parte del algoritmo, debido a los grandes avances en el sacrificio de las exploraciones que crecen rápidamente a muchos cientos de veces el tamaño de las memorias intermedias de página. Además, y tal vez más grave, que se llena la memoria y / o procesos informáticos para calcular el nuevo punto de partida para cada valor de 'x' en cuanto al valor de 'y' en la representación más baja de cada búfer de página para un bastante más gran pérdida en la eficiencia del paginado SoA comparaed al estado del medio ambiente como la gama crece.
EDIT_ADD: Las probabilidades sólo para SoE como el usado por Aaron Murgatroyd utiliza alrededor de 1026 millones de operaciones de desecho para un rango tamiz de mil millones de tan cerca de cuatro veces tantas operaciones como la SOA y por lo tanto debe funcionar sobre cuatro veces más lento, pero la SOA incluso tal como se aplica aquí tiene un bucle interior más complejo y, sobre todo debido a una proporción mucho mayor de los odds de sólo sacrificios SoE tienen un paso mucho más corto en las exploraciones de sacrificio que los pasos de la SOA los odds ingenuas -sólo SoE tiene mucho mejores tiempos de acceso de memoria promedio a pesar de la memoria intermedia de tamiz muy superior a los tamaños de caché CPU (mejor uso de asociatividad caché). Esto explica por qué la SOA anterior es sólo alrededor del doble de rápido que las probabilidades sólo para SoE a pesar de lo que parece teóricamente estar haciendo sólo una cuarta parte de la obra.
Si uno fuera a utilizar un algoritmo similar usando constantes bucles internos de módulo como para la SOA anteriores y aplicado el mismo factorización 2/3/5 rueda, el SoE reduciría el número de operaciones de desecho a aproximadamente 0405 millones de operaciones por lo que sólo alrededor 50% más operaciones que el SOA y, teóricamente, ejecutar sólo un poco más lenta que la SOA, pero pueden funcionar aproximadamente a la misma velocidad debido a los avances de desecho sigue siendo un poco menor que la de la SOA en la media para esta gran capacidad de memoria "ingenua" uso buffer. El aumento de la factorización de la rueda a la rueda 2/3/5/7 significa que las operaciones SoE de desecho se reducen a aproximadamente 0,314 para una gama matanza selectiva de un mil millones y pueden hacer que la versión de la SoE plazo sobre la misma velocidad para este algoritmo.
Además uso de factorización de la rueda puede hacerse por pre-sacrificio de la matriz de tamiz (copia en un patrón) para los 2/3/5/7/11/13/17/19 factores primos a casi ningún costo en tiempo de ejecución para reducir el número total de operaciones de desecho a aproximadamente 0251 millones para una gama tamiz de mil millones y el SoE funcionará más rápido o aproximadamente la misma velocidad que incluso esta versión optimizada de la SOA, incluso para estas versiones grandes búfer de memoria, con el SoE sigue teniendo mucho menos la complejidad del código de los anteriores.
Por lo tanto, se puede observar que el número de operaciones para el SoE se puede reducir en gran medida de un incluso probabilidades versión sólo factorización rueda ingenuo o o 2/3/5 de tal manera que el número de operaciones son aproximadamente los mismos que para la SOA, mientras que al mismo tiempo el tiempo por operación en realidad puede ser menor debido a los dos bucles internos de menor complejidad y acceso de memoria más eficiente. END_EDIT_ADD
EDIT_ADD2: Añadirel código de un SoE utilizando una técnica de posición de módulo / bit constante similar para los bucles más interiores como para el SoA anteriormente de acuerdo con el código de pseudo más abajo la respuesta como ligada arriba . El código es un poco menos complejo que la SOA anteriores a pesar de tener alta factorización rueda y pre-sacrificio aplicarse de tal manera que el número total de operaciones de desecho son en realidad menos de las operaciones de palanca / de desecho combinados para la SOA hasta un rang tamizado de alrededor de dos mil millones. El código de la siguiente manera:
EDIT_FINAL código corregido abajo y comentarios relacionados con ella END_EDIT_FINAL
//Sieve of Eratosthenes based on maximum wheel factorization and pre-culling implementation...
using System;
using System.Collections;
using System.Collections.Generic;
namespace NonPagedSoE {
//implements the non-paged Sieve of Eratosthenes (full modulo 210 version with preculling)...
class SoE : IEnumerable<ulong> {
private ushort[] buf = null;
private long cnt = 0;
private long opcnt = 0;
private static byte[] basePRMS = { 2, 3, 5, 7, 11, 13, 17, 19 };
private static byte[] modPRMS = { 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, //positions + 23
97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163,
167, 169, 173, 179, 181 ,187 ,191 ,193, 197, 199, 209, 211, 221, 223, 227, 229 };
private static byte[] gapsPRMS = { 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8,
4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4,
2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 4, 2, 4 };
private static ulong[] modLUT;
private static byte[] cntLUT;
//initialize the private LUT's...
static SoE() {
modLUT = new ulong[210];
for (int i = 0, m = 0; i < modLUT.Length; ++i) {
if ((i & 1) != 0 || (i + 23) % 3 == 0 || (i + 23) % 5 == 0 || (i + 23) % 7 == 0) modLUT[i] = 0;
else modLUT[i] = 1UL << (m++);
}
cntLUT = new byte[65536];
for (int i = 0; i < cntLUT.Length; ++i) {
var c = 0;
for (int j = i ^ 0xFFFF; j > 0; j >>= 1) c += j & 1; //reverse logic; 0 is prime; 1 is composite
cntLUT[i] = (byte)c;
}
}
//initialization and all the work producing the prime bit array done in the constructor...
public SoE(ulong range) {
this.opcnt = 0;
if (range < 23) {
if (range > 1) {
for (int i = 0; i < modPRMS.Length; ++i) if (modPRMS[i] <= range) this.cnt++; else break;
}
this.buf = new ushort[0];
}
else {
this.cnt = 8;
var nrng = range - 23; var lmtw = nrng / 210; var lmtwt3 = lmtw * 3;
//initialize sufficient wheels to prime
this.buf = new ushort[lmtwt3 + 3]; //initial state of all zero's is all potential prime.
//initialize array to account for preculling the primes of 11, 13, 17, and 19;
//(2, 3, 5, and 7 already eliminated by the bit packing to residues).
for (int pn = modPRMS.Length - 4; pn < modPRMS.Length; ++pn) {
uint p = modPRMS[pn] - 210u; ulong pt3 = p * 3;
ulong s = p * p - 23;
ulong xrng = Math.Min(9699709, nrng); // only do for the repeating master pattern size
ulong nwrds = (ulong)Math.Min(138567, this.buf.Length);
for (int j = 0; s <= xrng && j < modPRMS.Length; s += p * gapsPRMS[(pn + j++) % 48]) {
var sm = modLUT[s % 210];
var si = (sm < (1UL << 16)) ? 0UL : ((sm < (1UL << 32)) ? 1UL : 2UL);
var cd = s / 210 * 3 + si; var cm = (ushort)(sm >> (int)(si << 4));
for (ulong c = cd; c < nwrds; c += pt3) { //tight culling loop for size of master pattern
this.buf[c] |= cm; // ++this.opcnt; //reverse logic; mark composites with ones.
}
}
}
//Now copy the master pattern so it repeats across the main buffer, allow for overflow...
for (long i = 138567; i < this.buf.Length; i += 138567)
if (i + 138567 <= this.buf.Length)
Array.Copy(this.buf, 0, this.buf, i, 138567);
else Array.Copy(this.buf, 0, this.buf, i, this.buf.Length - i);
//Eliminate all composites which are factors of base primes, only for those on the wheel:
for (uint i = 0, w = 0, wi = 0, pd = 0, pn = 0, msk = 1; w < this.buf.Length; ++i) {
uint p = pd + modPRMS[pn];
ulong sqr = (ulong)p * (ulong)p;
if (sqr > range) break;
if ((this.buf[w] & msk) == 0) { //found base prime, mark its composites...
ulong s = sqr - 23; ulong pt3 = p * 3;
for (int j = 0; s <= nrng && j < modPRMS.Length; s += p * gapsPRMS[(pn + j++) % 48]) {
var sm = modLUT[s % 210];
var si = (sm < (1UL << 16)) ? 0UL : ((sm < (1UL << 32)) ? 1UL : 2UL);
var cd = s / 210 * 3 + si; var cm = (ushort)(sm >> (int)(si << 4));
for (ulong c = cd; c < (ulong)this.buf.Length; c += pt3) { //tight culling loop
this.buf[c] |= cm; // ++this.opcnt; //reverse logic; mark composites with ones.
}
}
}
++pn;
if (msk >= 0x8000) { msk = 1; ++w; ++wi; if (wi == 3) { wi = 0; pn = 0; pd += 210; } }
else msk <<= 1;
}
//clear any overflow primes in the excess space in the last wheel/word:
var ndx = nrng % 210; //clear any primes beyond the range
for (; modLUT[ndx] == 0; --ndx) ;
var cmsk = (~(modLUT[ndx] - 1)) << 1; //force all bits above to be composite ones.
this.buf[lmtwt3++] |= (ushort)cmsk;
this.buf[lmtwt3++] |= (ushort)(cmsk >> 16);
this.buf[lmtwt3] |= (ushort)(cmsk >> 32);
}
}
//uses a fast pop count Look Up Table to return the total number of primes...
public long Count {
get {
long cnt = this.cnt;
for (int i = 0; i < this.buf.Length; ++i) cnt += cntLUT[this.buf[i]];
return cnt;
}
}
//returns the number of cull operations used to sieve the prime bit array...
public long Ops {
get {
return this.opcnt;
}
}
//generate the enumeration of primes...
public IEnumerator<ulong> GetEnumerator() {
yield return 2; yield return 3; yield return 5; yield return 7;
yield return 11; yield return 13; yield return 17; yield return 19;
ulong pd = 0;
for (uint i = 0, w = 0, wi = 0, pn = 0, msk = 1; w < this.buf.Length; ++i) {
if ((this.buf[w] & msk) == 0) //found a prime bit...
yield return pd + modPRMS[pn];
++pn;
if (msk >= 0x8000) { msk = 1; ++w; ++wi; if (wi == 3) { wi = 0; pn = 0; pd += 210; } }
else msk <<= 1;
}
}
//required for the above enumeration...
IEnumerator IEnumerable.GetEnumerator() {
return this.GetEnumerator();
}
}
class Program {
static void Main(string[] args) {
Console.WriteLine("This program calculates primes by a simple maximually wheel factorized version of the Sieve of Eratosthenes.\r\n");
const ulong n = 1000000000;
var elpsd = -DateTime.Now.Ticks;
var gen = new SoE(n);
elpsd += DateTime.Now.Ticks;
Console.WriteLine("{0} primes found to {1} using {2} operations in {3} milliseconds.", gen.Count, n, gen.Ops, elpsd / 10000);
// Console.WriteLine();
// foreach (var p in gen) {
// Console.Write(p + " ");
// }
// Console.WriteLine();
// Console.WriteLine("\r\nThere are {0} primes with the last one {1} and the sum {2}.",gen.Count(),gen.Last(),gen.Sum(x => (long)x));
Console.Write("\r\nPress any key to exit:");
Console.ReadKey(true);
Console.WriteLine();
}
}
}
Este código realmente ejecuta un pequeño tanto por ciento más rápido que la SOA anteriores como debería, ya que son un poco menos de operaciones y el cuello de botella principal de esta gran tamaño de la matriz para un rango de un mil millones es el tiempo de acceso a memoria de algo así como 40 a más de 100 ciclos de reloj de la CPU en función de las especificaciones de la CPU y de memoria; esto significa que optimizaciones de código (que no sean la reducción del número total de operaciones) son ineficaces ya que la mayoría de las veces es pasar la espera de acceso a la memoria. En cualquier caso, mediante un gran búfer de memoria no es la forma más eficiente para tamizar grandes intervalos, con un factor de hasta aproximadamente ocho veces mejora para la página utilizando segmentación SoE con el mismo factorización máximo de la rueda (que también allana el camino para multi-procesamiento).
Es en la implementación de la página de segmentación y multi-procesamiento que el SOA es muy deficiente para rangos muy por encima de cuatro mil millones en comparación con el estado del medio ambiente como cualquier ganancia debido a la complejidad asintótica reducida de la SOA rápidamente comidos por página sobrecarga de procesamiento factores relacionados con el primer procesamiento sin cuadrados y calculando el número mucho mayor de direcciones de página de inicio; alternativamente, se supera esto almacenando marcadores en la memoria RAM en un enorme costo en consumo de memoria y otras ineficiencias para acceder a estas estructuras almacenar marcador. END_EDIT_ADD2
En resumen, la SOA no es realmente un tamiz práctica en comparación con la de la rueda totalmente SoE factorizada ya que al igual que el aumento de la complejidad asintótica comienza a traerlo cerca de actuación para el estado del medio ambiente totalmente optimizado, que empieza a perder eficacia debido a los detalles de aplicación práctica en cuanto al tiempo de acceso a memoria relativa y complejidades página de segmentación, así como en general, siendo más complejo y difícil de escribir. En mi opinión se trata más de un concepto intelectual interesante y ejercicio mental de un tamiz práctica en comparación con el estado del medio ambiente.
Algún día voy a adaptar estas técnicas a una página multi-hilo segmentado criba de Eratóstenes a ser casi tan rápido en C # como Atkin y de Bernstein aplicación "PrimeGen" de la SOA en 'C' y soplará hacia fuera del agua para grandes rangos por encima de unos cuatro mil millones de incluso un solo hilo, con un impulso adicional en la velocidad de hasta aproximadamente cuatro años cuando multi-threading en mi i7 (ocho núcleos incluyendo Hyper threading).
Aquí es otra aplicación. Utiliza BitArray para ahorrar memoria. El Parallel.For necesita .NET Framework 4.
static List<int> FindPrimesBySieveOfAtkins(int max)
{
// var isPrime = new BitArray((int)max+1, false);
// Can't use BitArray because of threading issues.
var isPrime = new bool[max + 1];
var sqrt = (int)Math.Sqrt(max);
Parallel.For(1, sqrt, x =>
{
var xx = x * x;
for (int y = 1; y <= sqrt; y++)
{
var yy = y * y;
var n = 4 * xx + yy;
if (n <= max && (n % 12 == 1 || n % 12 == 5))
isPrime[n] ^= true;
n = 3 * xx + yy;
if (n <= max && n % 12 == 7)
isPrime[n] ^= true;
n = 3 * xx - yy;
if (x > y && n <= max && n % 12 == 11)
isPrime[n] ^= true;
}
});
var primes = new List<int>() { 2, 3 };
for (int n = 5; n <= sqrt; n++)
{
if (isPrime[n])
{
primes.Add(n);
int nn = n * n;
for (int k = nn; k <= max; k += nn)
isPrime[k] = false;
}
}
for (int n = sqrt + 1; n <= max; n++)
if (isPrime[n])
primes.Add(n);
return primes;
}
Esta es una implementación más rápida de la criba de Atkin, robé el algoritmo de este script Python aquí (me da ningún crédito por el algoritmo):
http://programmingpraxis.com/2010/02/ 19 / tamiz-de-atkin-mejorada /
using System;
using System.Collections;
using System.Collections.Generic;
namespace PrimeGenerator
{
// The block element type for the bit array,
// use any unsigned value. WARNING: UInt64 is
// slower even on x64 architectures.
using BitArrayType = System.UInt32;
// This should never be any bigger than 256 bits - leave as is.
using BitsPerBlockType = System.Byte;
// The prime data type, this can be any unsigned value, the limit
// of this type determines the limit of Prime value that can be
// found. WARNING: UInt64 is slower even on x64 architectures.
using PrimeType = System.Int32;
/// <summary>
/// Calculates prime number using the Sieve of Eratosthenes method.
/// </summary>
/// <example>
/// <code>
/// var lpPrimes = new Eratosthenes(1e7);
/// foreach (UInt32 luiPrime in lpPrimes)
/// Console.WriteLine(luiPrime);
/// </example>
public class Atkin : IEnumerable<PrimeType>
{
#region Constants
/// <summary>
/// Constant for number of bits per block, calculated based on size of BitArrayType.
/// </summary>
const BitsPerBlockType cbBitsPerBlock = sizeof(BitArrayType) * 8;
#endregion
#region Protected Locals
/// <summary>
/// The limit for the maximum prime value to find.
/// </summary>
protected readonly PrimeType mpLimit;
/// <summary>
/// The number of primes calculated or null if not calculated yet.
/// </summary>
protected PrimeType? mpCount = null;
/// <summary>
/// The current bit array where a set bit means
/// the odd value at that location has been determined
/// to not be prime.
/// </summary>
protected BitArrayType[] mbaOddPrime;
#endregion
#region Initialisation
/// <summary>
/// Create Sieve of Atkin generator.
/// </summary>
/// <param name="limit">The limit for the maximum prime value to find.</param>
public Atkin(PrimeType limit)
{
// Check limit range
if (limit > PrimeType.MaxValue - (PrimeType)Math.Sqrt(PrimeType.MaxValue))
throw new ArgumentOutOfRangeException();
mpLimit = limit;
FindPrimes();
}
#endregion
#region Private Methods
/// <summary>
/// Finds the prime number within range.
/// </summary>
private unsafe void FindPrimes()
{
// Allocate bit array.
mbaOddPrime = new BitArrayType[(((mpLimit >> 1) + 1) / cbBitsPerBlock) + 1];
PrimeType lpYLimit, lpN, lpXX3, lpXX4, lpDXX, lpDN, lpDXX4, lpXX, lpX, lpYY, lpMinY, lpS, lpK;
fixed (BitArrayType* lpbOddPrime = &mbaOddPrime[0])
{
// n = 3x^2 + y^2 section
lpXX3 = 3;
for (lpDXX = 0; lpDXX < 12 * SQRT((mpLimit - 1) / 3); lpDXX += 24)
{
lpXX3 += lpDXX;
lpYLimit = (12 * SQRT(mpLimit - lpXX3)) - 36;
lpN = lpXX3 + 16;
for (lpDN = -12; lpDN < lpYLimit + 1; lpDN += 72)
{
lpN += lpDN;
lpbOddPrime[(lpN >> 1) / cbBitsPerBlock] ^=
(BitArrayType)((BitArrayType)1 << (int)((lpN >> 1) % cbBitsPerBlock));
}
lpN = lpXX3 + 4;
for (lpDN = 12; lpDN < lpYLimit + 1; lpDN += 72)
{
lpN += lpDN;
lpbOddPrime[(lpN >> 1) / cbBitsPerBlock] ^=
(BitArrayType)((BitArrayType)1 << (int)((lpN >> 1) % cbBitsPerBlock));
}
}
// # n = 4x^2 + y^2 section
lpXX4 = 0;
for (lpDXX4 = 4; lpDXX4 < 8 * SQRT((mpLimit - 1) / 4) + 4; lpDXX4 += 8)
{
lpXX4 += lpDXX4;
lpN = lpXX4 + 1;
if ((lpXX4 % 3) != 0)
{
for (lpDN = 0; lpDN < (4 * SQRT(mpLimit - lpXX4)) - 3; lpDN += 8)
{
lpN += lpDN;
lpbOddPrime[(lpN >> 1) / cbBitsPerBlock] ^=
(BitArrayType)((BitArrayType)1 << (int)((lpN >> 1) % cbBitsPerBlock));
}
}
else
{
lpYLimit = (12 * SQRT(mpLimit - lpXX4)) - 36;
lpN = lpXX4 + 25;
for (lpDN = -24; lpDN < lpYLimit + 1; lpDN += 72)
{
lpN += lpDN;
lpbOddPrime[(lpN >> 1) / cbBitsPerBlock] ^=
(BitArrayType)((BitArrayType)1 << (int)((lpN >> 1) % cbBitsPerBlock));
}
lpN = lpXX4 + 1;
for (lpDN = 24; lpDN < lpYLimit + 1; lpDN += 72)
{
lpN += lpDN;
lpbOddPrime[(lpN >> 1) / cbBitsPerBlock] ^=
(BitArrayType)((BitArrayType)1 << (int)((lpN >> 1) % cbBitsPerBlock));
}
}
}
// # n = 3x^2 - y^2 section
lpXX = 1;
for (lpX = 3; lpX < SQRT(mpLimit / 2) + 1; lpX += 2)
{
lpXX += 4 * lpX - 4;
lpN = 3 * lpXX;
if (lpN > mpLimit)
{
lpMinY = ((SQRT(lpN - mpLimit) >> 2) << 2);
lpYY = lpMinY * lpMinY;
lpN -= lpYY;
lpS = 4 * lpMinY + 4;
}
else
lpS = 4;
for (lpDN = lpS; lpDN < 4 * lpX; lpDN += 8)
{
lpN -= lpDN;
if (lpN <= mpLimit && lpN % 12 == 11)
lpbOddPrime[(lpN >> 1) / cbBitsPerBlock] ^=
(BitArrayType)((BitArrayType)1 << (int)((lpN >> 1) % cbBitsPerBlock));
}
}
// xx = 0
lpXX = 0;
for (lpX = 2; lpX < SQRT(mpLimit / 2) + 1; lpX += 2)
{
lpXX += 4*lpX - 4;
lpN = 3*lpXX;
if (lpN > mpLimit)
{
lpMinY = ((SQRT(lpN - mpLimit) >> 2) << 2) - 1;
lpYY = lpMinY * lpMinY;
lpN -= lpYY;
lpS = 4*lpMinY + 4;
}
else
{
lpN -= 1;
lpS = 0;
}
for (lpDN = lpS; lpDN < 4 * lpX; lpDN += 8)
{
lpN -= lpDN;
if (lpN <= mpLimit && lpN % 12 == 11)
lpbOddPrime[(lpN>>1) / cbBitsPerBlock] ^=
(BitArrayType)((BitArrayType)1 << (int)((lpN>>1) % cbBitsPerBlock));
}
}
// # eliminate squares
for (lpN = 5; lpN < SQRT(mpLimit) + 1; lpN += 2)
if ((lpbOddPrime[(lpN >> 1) / cbBitsPerBlock] & ((BitArrayType)1 << (int)((lpN >> 1) % cbBitsPerBlock))) != 0)
for (lpK = lpN * lpN; lpK < mpLimit; lpK += lpN * lpN)
if ((lpK & 1) == 1)
lpbOddPrime[(lpK >> 1) / cbBitsPerBlock] &=
(BitArrayType)~((BitArrayType)1 << (int)((lpK >> 1) % cbBitsPerBlock));
}
}
/// <summary>
/// Calculates the truncated square root for a number.
/// </summary>
/// <param name="value">The value to get the square root for.</param>
/// <returns>The truncated sqrt of the value.</returns>
private unsafe PrimeType SQRT(PrimeType value)
{
return (PrimeType)Math.Sqrt(value);
}
/// <summary>
/// Gets a bit value by index.
/// </summary>
/// <param name="bits">The blocks containing the bits.</param>
/// <param name="index">The index of the bit.</param>
/// <returns>True if bit is set, false if cleared.</returns>
private bool GetBitSafe(BitArrayType[] bits, PrimeType index)
{
if ((index & 1) == 1)
return (bits[(index >> 1) / cbBitsPerBlock] & ((BitArrayType)1 << (int)((index >> 1) % cbBitsPerBlock))) != 0;
else
return false;
}
#endregion
#region Public Properties
/// <summary>
/// Get the limit for the maximum prime value to find.
/// </summary>
public PrimeType Limit
{
get
{
return mpLimit;
}
}
/// <summary>
/// Returns the number of primes found in the range.
/// </summary>
public PrimeType Count
{
get
{
if (!mpCount.HasValue)
{
PrimeType lpCount = 0;
foreach (PrimeType liPrime in this) lpCount++;
mpCount = lpCount;
}
return mpCount.Value;
}
}
/// <summary>
/// Determines if a value in range is prime or not.
/// </summary>
/// <param name="test">The value to test for primality.</param>
/// <returns>True if the value is prime, false otherwise.</returns>
public bool this[PrimeType test]
{
get
{
if (test > mpLimit) throw new ArgumentOutOfRangeException();
if (test <= 1) return false;
if (test == 2) return true;
if ((test & 1) == 0) return false;
return !GetBitSafe(mbaOddPrime, test >> 1);
}
}
#endregion
#region Public Methods
/// <summary>
/// Gets the enumerator for the primes.
/// </summary>
/// <returns>The enumerator of the primes.</returns>
public IEnumerator<PrimeType> GetEnumerator()
{
// return [2,3] + filter(primes.__getitem__, xrange(5,limit,2))
// Two & Three always prime.
yield return 2;
yield return 3;
// Start at first block, third MSB (5).
int liBlock = 0;
byte lbBit = 2;
BitArrayType lbaCurrent = mbaOddPrime[0] >> lbBit;
// For each value in range stepping in incrments of two for odd values.
for (PrimeType lpN = 5; lpN <= mpLimit; lpN += 2)
{
// If current bit not set then value is prime.
if ((lbaCurrent & 1) == 1)
yield return lpN;
// Move to NSB.
lbaCurrent >>= 1;
// Increment bit value.
lbBit++;
// If block is finished.
if (lbBit == cbBitsPerBlock)
{
lbBit = 0;
lbaCurrent = mbaOddPrime[++liBlock];
//// Move to first bit of next block skipping full blocks.
while (lbaCurrent == 0)
{
lpN += ((PrimeType)cbBitsPerBlock) << 1;
if (lpN <= mpLimit)
lbaCurrent = mbaOddPrime[++liBlock];
else
break;
}
}
}
}
#endregion
#region IEnumerable<PrimeType> Implementation
/// <summary>
/// Gets the enumerator for the primes.
/// </summary>
/// <returns></returns>
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
#endregion
}
}
Su estrecha en la velocidad de mi versión más optimizada de la criba de Eratóstenes, pero aún es más lenta en aproximadamente un 20%, se puede encontrar aquí:
Aquí está el mío, que utiliza una clase llamada CompartmentalisedParallel que le permite realizar en paralelo para los bucles, sino controlar el número de hilos de manera que los índices se agrupan para arriba. Sin embargo, debido a los problemas de threads que necesita ya sea bloquear la BitArray cada vez que se altera o crear una BitArray separado para cada hilo y luego XOR juntos al final, la primera opción era bastante lento debido a la cantidad de bloqueos, el segundo opción parecía más rápido para mí!
using System;
using System.Collections;
using System.Collections.Generic;
using System.Threading.Tasks;
namespace PrimeGenerator
{
public class Atkin : Primes
{
protected BitArray mbaPrimes;
protected bool mbThreaded = true;
public Atkin(int limit)
: this(limit, true)
{
}
public Atkin(int limit, bool threaded)
: base(limit)
{
mbThreaded = threaded;
if (mbaPrimes == null) FindPrimes();
}
public bool Threaded
{
get
{
return mbThreaded;
}
}
public override IEnumerator<int> GetEnumerator()
{
yield return 2;
yield return 3;
for (int lsN = 5; lsN <= msLimit; lsN += 2)
if (mbaPrimes[lsN]) yield return lsN;
}
private void FindPrimes()
{
mbaPrimes = new BitArray(msLimit + 1, false);
int lsSQRT = (int)Math.Sqrt(msLimit);
int[] lsSquares = new int[lsSQRT + 1];
for (int lsN = 0; lsN <= lsSQRT; lsN++)
lsSquares[lsN] = lsN * lsN;
if (Threaded)
{
CompartmentalisedParallel.For<BitArray>(
1, lsSQRT + 1, new ParallelOptions(),
(start, finish) => { return new BitArray(msLimit + 1, false); },
(lsX, lsState, lbaLocal) =>
{
int lsX2 = lsSquares[lsX];
for (int lsY = 1; lsY <= lsSQRT; lsY++)
{
int lsY2 = lsSquares[lsY];
int lsN = 4 * lsX2 + lsY2;
if (lsN <= msLimit && (lsN % 12 == 1 || lsN % 12 == 5))
lbaLocal[lsN] ^= true;
lsN -= lsX2;
if (lsN <= msLimit && lsN % 12 == 7)
lbaLocal[lsN] ^= true;
if (lsX > lsY)
{
lsN -= lsY2 * 2;
if (lsN <= msLimit && lsN % 12 == 11)
lbaLocal[lsN] ^= true;
}
}
return lbaLocal;
},
(lbaResult, start, finish) =>
{
lock (mbaPrimes)
mbaPrimes.Xor(lbaResult);
},
-1
);
}
else
{
for (int lsX = 1; lsX <= lsSQRT; lsX++)
{
int lsX2 = lsSquares[lsX];
for (int lsY = 1; lsY <= lsSQRT; lsY++)
{
int lsY2 = lsSquares[lsY];
int lsN = 4 * lsX2 + lsY2;
if (lsN <= msLimit && (lsN % 12 == 1 || lsN % 12 == 5))
mbaPrimes[lsN] ^= true;
lsN -= lsX2;
if (lsN <= msLimit && lsN % 12 == 7)
mbaPrimes[lsN] ^= true;
if (lsX > lsY)
{
lsN -= lsY2 * 2;
if (lsN <= msLimit && lsN % 12 == 11)
mbaPrimes[lsN] ^= true;
}
}
}
}
for (int lsN = 5; lsN < lsSQRT; lsN += 2)
if (mbaPrimes[lsN])
{
var lsS = lsSquares[lsN];
for (int lsK = lsS; lsK <= msLimit; lsK += lsS)
mbaPrimes[lsK] = false;
}
}
}
}
Y la clase CompartmentalisedParallel:
using System;
using System.Threading.Tasks;
namespace PrimeGenerator
{
public static class CompartmentalisedParallel
{
#region Int
private static int[] CalculateCompartments(int startInclusive, int endExclusive, ref int threads)
{
if (threads == 0) threads = 1;
if (threads == -1) threads = Environment.ProcessorCount;
if (threads > endExclusive - startInclusive) threads = endExclusive - startInclusive;
int[] liThreadIndexes = new int[threads + 1];
liThreadIndexes[threads] = endExclusive - 1;
int liIndexesPerThread = (endExclusive - startInclusive) / threads;
for (int liCount = 0; liCount < threads; liCount++)
liThreadIndexes[liCount] = liCount * liIndexesPerThread;
return liThreadIndexes;
}
public static void For<TLocal>(
int startInclusive, int endExclusive,
ParallelOptions parallelOptions,
Func<int, int, TLocal> localInit,
Func<int, ParallelLoopState, TLocal, TLocal> body,
Action<TLocal, int, int> localFinally,
int threads)
{
int[] liThreadIndexes = CalculateCompartments(startInclusive, endExclusive, ref threads);
if (threads > 1)
Parallel.For(
0, threads, parallelOptions,
(liThread, lsState) =>
{
TLocal llLocal = localInit(liThreadIndexes[liThread], liThreadIndexes[liThread + 1]);
for (int liCounter = liThreadIndexes[liThread]; liCounter < liThreadIndexes[liThread + 1]; liCounter++)
body(liCounter, lsState, llLocal);
localFinally(llLocal, liThreadIndexes[liThread], liThreadIndexes[liThread + 1]);
}
);
else
{
TLocal llLocal = localInit(startInclusive, endExclusive);
for (int liCounter = startInclusive; liCounter < endExclusive; liCounter++)
body(liCounter, null, llLocal);
localFinally(llLocal, startInclusive, endExclusive);
}
}
public static void For(
int startInclusive, int endExclusive,
ParallelOptions parallelOptions,
Action<int, ParallelLoopState> body,
int threads)
{
int[] liThreadIndexes = CalculateCompartments(startInclusive, endExclusive, ref threads);
if (threads > 1)
Parallel.For(
0, threads, parallelOptions,
(liThread, lsState) =>
{
for (int liCounter = liThreadIndexes[liThread]; liCounter < liThreadIndexes[liThread + 1]; liCounter++)
body(liCounter, lsState);
}
);
else
for (int liCounter = startInclusive; liCounter < endExclusive; liCounter++)
body(liCounter, null);
}
public static void For(
int startInclusive, int endExclusive,
ParallelOptions parallelOptions,
Action<int> body,
int threads)
{
int[] liThreadIndexes = CalculateCompartments(startInclusive, endExclusive, ref threads);
if (threads > 1)
Parallel.For(
0, threads, parallelOptions,
(liThread) =>
{
for (int liCounter = liThreadIndexes[liThread]; liCounter < liThreadIndexes[liThread + 1]; liCounter++)
body(liCounter);
}
);
else
for (int liCounter = startInclusive; liCounter < endExclusive; liCounter++)
body(liCounter);
}
public static void For(
int startInclusive, int endExclusive,
Action<int, ParallelLoopState> body,
int threads)
{
For(startInclusive, endExclusive, new ParallelOptions(), body, threads);
}
public static void For(
int startInclusive, int endExclusive,
Action<int> body,
int threads)
{
For(startInclusive, endExclusive, new ParallelOptions(), body, threads);
}
public static void For<TLocal>(
int startInclusive, int endExclusive,
Func<int, int, TLocal> localInit,
Func<int, ParallelLoopState, TLocal, TLocal> body,
Action<TLocal, int, int> localFinally,
int threads)
{
For<TLocal>(startInclusive, endExclusive, new ParallelOptions(), localInit, body, localFinally, threads);
}
#endregion
#region Long
private static long[] CalculateCompartments(long startInclusive, long endExclusive, ref long threads)
{
if (threads == 0) threads = 1;
if (threads == -1) threads = Environment.ProcessorCount;
if (threads > endExclusive - startInclusive) threads = endExclusive - startInclusive;
long[] liThreadIndexes = new long[threads + 1];
liThreadIndexes[threads] = endExclusive - 1;
long liIndexesPerThread = (endExclusive - startInclusive) / threads;
for (long liCount = 0; liCount < threads; liCount++)
liThreadIndexes[liCount] = liCount * liIndexesPerThread;
return liThreadIndexes;
}
public static void For<TLocal>(
long startInclusive, long endExclusive,
ParallelOptions parallelOptions,
Func<long, long, TLocal> localInit,
Func<long, ParallelLoopState, TLocal, TLocal> body,
Action<TLocal, long, long> localFinally,
long threads)
{
long[] liThreadIndexes = CalculateCompartments(startInclusive, endExclusive, ref threads);
if (threads > 1)
Parallel.For(
0, threads, parallelOptions,
(liThread, lsState) =>
{
TLocal llLocal = localInit(liThreadIndexes[liThread], liThreadIndexes[liThread + 1]);
for (long liCounter = liThreadIndexes[liThread]; liCounter < liThreadIndexes[liThread + 1]; liCounter++)
body(liCounter, lsState, llLocal);
localFinally(llLocal, liThreadIndexes[liThread], liThreadIndexes[liThread + 1]);
}
);
else
{
TLocal llLocal = localInit(startInclusive, endExclusive);
for (long liCounter = startInclusive; liCounter < endExclusive; liCounter++)
body(liCounter, null, llLocal);
localFinally(llLocal, startInclusive, endExclusive);
}
}
public static void For(
long startInclusive, long endExclusive,
ParallelOptions parallelOptions,
Action<long, ParallelLoopState> body,
long threads)
{
long[] liThreadIndexes = CalculateCompartments(startInclusive, endExclusive, ref threads);
if (threads > 1)
Parallel.For(
0, threads, parallelOptions,
(liThread, lsState) =>
{
for (long liCounter = liThreadIndexes[liThread]; liCounter < liThreadIndexes[liThread + 1]; liCounter++)
body(liCounter, lsState);
}
);
else
for (long liCounter = startInclusive; liCounter < endExclusive; liCounter++)
body(liCounter, null);
}
public static void For(
long startInclusive, long endExclusive,
ParallelOptions parallelOptions,
Action<long> body,
long threads)
{
long[] liThreadIndexes = CalculateCompartments(startInclusive, endExclusive, ref threads);
if (threads > 1)
Parallel.For(
0, threads, parallelOptions,
(liThread) =>
{
for (long liCounter = liThreadIndexes[liThread]; liCounter < liThreadIndexes[liThread + 1]; liCounter++)
body(liCounter);
}
);
else
for (long liCounter = startInclusive; liCounter < endExclusive; liCounter++)
body(liCounter);
}
public static void For(
long startInclusive, long endExclusive,
Action<long, ParallelLoopState> body,
long threads)
{
For(startInclusive, endExclusive, new ParallelOptions(), body, threads);
}
public static void For(
long startInclusive, long endExclusive,
Action<long> body,
long threads)
{
For(startInclusive, endExclusive, new ParallelOptions(), body, threads);
}
public static void For<TLocal>(
long startInclusive, long endExclusive,
Func<long, long, TLocal> localInit,
Func<long, ParallelLoopState, TLocal, TLocal> body,
Action<TLocal, long, long> localFinally,
long threads)
{
For<TLocal>(startInclusive, endExclusive, new ParallelOptions(), localInit, body, localFinally, threads);
}
#endregion
}
}
clase base Primes:
using System.Collections;
using System.Collections.Generic;
namespace PrimeGenerator
{
public abstract class Primes : IEnumerable<int>
{
protected readonly int msLimit;
public Primes(int limit)
{
msLimit = limit;
}
public int Limit
{
get
{
return msLimit;
}
}
public int Count
{
get
{
int liCount = 0;
foreach (int liPrime in this)
liCount++;
return liCount;
}
}
public abstract IEnumerator<int> GetEnumerator();
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}
}
Se usa de la siguiente manera:
var lpPrimes = new Atkin(count, true);
Console.WriteLine(lpPrimes.Count);
Console.WriteLine(s.ElapsedMilliseconds);
Sin embargo, he encontrado el Eratóstenes a ser más rápido en todos los casos, incluso con una CPU de cuatro núcleo funcionando en el modo de multiproceso para el Atkin:
using System;
using System.Collections;
using System.Collections.Generic;
namespace PrimeGenerator
{
public class Eratosthenes : Primes
{
protected BitArray mbaOddEliminated;
public Eratosthenes(int limit)
: base(limit)
{
if (mbaOddEliminated == null) FindPrimes();
}
public override IEnumerator<int> GetEnumerator()
{
yield return 2;
for (int lsN = 3; lsN <= msLimit; lsN+=2)
if (!mbaOddEliminated[lsN>>1]) yield return lsN;
}
private void FindPrimes()
{
mbaOddEliminated = new BitArray((msLimit>>1) + 1);
int lsSQRT = (int)Math.Sqrt(msLimit);
for (int lsN = 3; lsN < lsSQRT + 1; lsN += 2)
if (!mbaOddEliminated[lsN>>1])
for (int lsM = lsN*lsN; lsM <= msLimit; lsM += lsN<<1)
mbaOddEliminated[lsM>>1] = true;
}
}
}
Si tienes la Atkin a correr más rápido, por favor hágamelo saber!
Aquí está una mejora de la criba de Eratóstenes usando FixBitArrays personalizados y código no seguro para los resultados de velocidad, esto es alrededor de 225% más rápido que mi algoritmo de Eratóstenes anterior, y la clase es independiente (esto no es multiproceso - Eratóstenes no es compatible con múltiples threading), en un procesador AMD Phenom II X4 965 puedo calcular números primos a mil millones límite en 9.261 ms:
using System;
using System.Collections;
using System.Collections.Generic;
namespace PrimeGenerator
{
// The block element type for the bit array,
// use any unsigned value. WARNING: UInt64 is
// slower even on x64 architectures.
using BitArrayType = System.UInt32;
// This should never be any bigger than 256 bits - leave as is.
using BitsPerBlockType = System.Byte;
// The prime data type, this can be any unsigned value, the limit
// of this type determines the limit of Prime value that can be
// found. WARNING: UInt64 is slower even on x64 architectures.
using PrimeType = System.UInt32;
/// <summary>
/// Calculates prime number using the Sieve of Eratosthenes method.
/// </summary>
/// <example>
/// <code>
/// var lpPrimes = new Eratosthenes(1e7);
/// foreach (UInt32 luiPrime in lpPrimes)
/// Console.WriteLine(luiPrime);
/// </example>
public class Eratosthenes : IEnumerable<PrimeType>
{
#region Constants
/// <summary>
/// Constant for number of bits per block, calculated based on size of BitArrayType.
/// </summary>
const BitsPerBlockType cbBitsPerBlock = sizeof(BitArrayType) * 8;
#endregion
#region Protected Locals
/// <summary>
/// The limit for the maximum prime value to find.
/// </summary>
protected readonly PrimeType mpLimit;
/// <summary>
/// The current bit array where a set bit means
/// the odd value at that location has been determined
/// to not be prime.
/// </summary>
protected BitArrayType[] mbaOddNotPrime;
#endregion
#region Initialisation
/// <summary>
/// Create Sieve of Eratosthenes generator.
/// </summary>
/// <param name="limit">The limit for the maximum prime value to find.</param>
public Eratosthenes(PrimeType limit)
{
// Check limit range
if (limit > PrimeType.MaxValue - (PrimeType)Math.Sqrt(PrimeType.MaxValue))
throw new ArgumentOutOfRangeException();
mpLimit = limit;
FindPrimes();
}
#endregion
#region Private Methods
/// <summary>
/// Finds the prime number within range.
/// </summary>
private unsafe void FindPrimes()
{
// Allocate bit array.
mbaOddNotPrime = new BitArrayType[(((mpLimit >> 1) + 1) / cbBitsPerBlock) + 1];
// Cache Sqrt of limit.
PrimeType lpSQRT = (PrimeType)Math.Sqrt(mpLimit);
// Fix the bit array for pointer access
fixed (BitArrayType* lpbOddNotPrime = &mbaOddNotPrime[0])
// Scan primes up to lpSQRT
for (PrimeType lpN = 3; lpN <= lpSQRT; lpN += 2)
// If the current bit value for index lpN is cleared (prime)
if (
(
lpbOddNotPrime[(lpN >> 1) / cbBitsPerBlock] &
((BitArrayType)1 << (BitsPerBlockType)((lpN >> 1) % cbBitsPerBlock))
) == 0
)
// Leave it cleared (prime) and mark all multiples of lpN*2 from lpN*lpN as not prime
for (PrimeType lpM = lpN * lpN; lpM <= mpLimit; lpM += lpN << 1)
// Set as not prime
lpbOddNotPrime[(lpM >> 1) / cbBitsPerBlock] |=
(BitArrayType)((BitArrayType)1 << (BitsPerBlockType)((lpM >> 1) % cbBitsPerBlock));
}
/// <summary>
/// Gets a bit value by index.
/// </summary>
/// <param name="bits">The blocks containing the bits.</param>
/// <param name="index">The index of the bit.</param>
/// <returns>True if bit is set, false if cleared.</returns>
private bool GetBitSafe(BitArrayType[] bits, PrimeType index)
{
return (bits[index / cbBitsPerBlock] & ((BitArrayType)1 << (BitsPerBlockType)(index % cbBitsPerBlock))) != 0;
}
#endregion
#region Public Properties
/// <summary>
/// Get the limit for the maximum prime value to find.
/// </summary>
public PrimeType Limit
{
get
{
return mpLimit;
}
}
/// <summary>
/// Returns the number of primes found in the range.
/// </summary>
public PrimeType Count
{
get
{
PrimeType lptCount = 0;
foreach (PrimeType liPrime in this)
lptCount++;
return lptCount;
}
}
/// <summary>
/// Determines if a value in range is prime or not.
/// </summary>
/// <param name="test">The value to test for primality.</param>
/// <returns>True if the value is prime, false otherwise.</returns>
public bool this[PrimeType test]
{
get
{
if (test > mpLimit) throw new ArgumentOutOfRangeException();
if (test <= 1) return false;
if (test == 2) return true;
if ((test & 1) == 0) return false;
return !GetBitSafe(mbaOddNotPrime, test >> 1);
}
}
#endregion
#region Public Methods
/// <summary>
/// Gets the enumerator for the primes.
/// </summary>
/// <returns>The enumerator of the primes.</returns>
public IEnumerator<PrimeType> GetEnumerator()
{
// Two always prime.
yield return 2;
// Start at first block, second MSB.
int liBlock = 0;
byte lbBit = 1;
BitArrayType lbaCurrent = mbaOddNotPrime[0] >> 1;
// For each value in range stepping in incrments of two for odd values.
for (PrimeType lpN = 3; lpN <= mpLimit; lpN += 2)
{
// If current bit not set then value is prime.
if ((lbaCurrent & 1) == 0)
yield return lpN;
// Move to NSB.
lbaCurrent >>= 1;
// Increment bit value.
lbBit++;
// If block is finished.
if (lbBit == cbBitsPerBlock)
{
// Move to first bit of next block.
lbBit = 0;
liBlock++;
lbaCurrent = mbaOddNotPrime[liBlock];
}
}
}
#endregion
#region IEnumerable<PrimeType> Implementation
/// <summary>
/// Gets the enumerator for the primes.
/// </summary>
/// <returns>The enumerator for the prime numbers.</returns>
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
#endregion
}
}
Las primas que se encuentran en 1000000000: 50847534 en 9.261 ms
