Nota: Se envió una entrada de desafío de @David_Burnham antes de la fecha límite, pero mi sistema de correo electrónico la puso en cuarentena. La descubrí después de la publicación original del blog. Estoy actualizando los resultados para reflejar los cambios según la nueva entrada.
Gracias a todos los que enviaron código para el Desafío 2. La puntuación fue un desafío, ya que algunos códigos funcionaron mejor con valores pequeños y otros con valores grandes. La siguiente tabla muestra los resultados de cada parte del desafío. Hubo tres ejecuciones para esPrime , 1000 números impares aleatorios de 5 dígitos no divisibles por 5, números impares de 8 y 9 dígitos no divisibles por 5 y números impares de 12 a 15 dígitos no divisibles por 5. Los resultados se basaron en las dos últimas condiciones. Los puntos se dividieron entre los desafíos: 1,5 puntos para el 1.º , 1 para el 2.º y 0,5 para el 3.º . También se dan los tiempos de los envíos más rápidos (en segundos).
El tiempo de isPrime(Small) de @leelaim fue el más rápido de cualquier miembro del equipo de JMP (+3 puntos). El script isPrime(Big) de @landon usa la función Parallel Assign para mejorar la velocidad. Dos de las entradas almacenaron en caché sus resultados para obtenerPrimos usando Espacio de nombres . Este enfoque es útil cuando es necesario acceder a los resultados más de una vez (sin embargo, los tiempos de ejecución se basan en resultados no almacenados en caché). Las cuatro entradas se incluyen a continuación.
Aquí está la clasificación después de dos desafíos:
El desafío 3 se publicará el miércoles 1 de junio.
El desafío 2 pedía encontrar primos de dos maneras posibles. Dado un valor entero positivo n , tenías que encontrar: 1) n primos o 2) todos los primos menores de n . Empecemos con 2), ya que es algo más fácil de implementar. El método más simple para encontrar primos es la división de prueba. Empezando con 2 como candidato y un conjunto vacío de primos, comprueba si algo del conjunto actual de primos divide al número candidato de forma exacta. Si no, añádelo al conjunto de primos y continúa con el siguiente candidato. Como no hay nada en el conjunto de primos para comenzar, se suma 2. Verificando 3, no divide nada en {2} y se suma al conjunto de primos. Sin embargo, el número 4 divide algo en {2,3} y no se suma. A continuación se muestra un ejemplo de implementación.
getPrimes2 = Function( {n}, {primeSet,i,j},
primeSet = [];
For(i=2,i<=n,i++,
For(j=2,j<=N Row(primeSet),j++,
If(Mod(i,j)==0, Break());
);
If(j>N Row(primeSet),primeSet = primeSet |/ i);
);
primeSet;
);
Este enfoque tiene algunas ventajas: es fácil de entender, el código es conciso y se adapta fácilmente a ambos desafíos de búsqueda de primos. Desafortunadamente, es extremadamente lento. Encontrar los primos menores de 100 000 me llevó 19,43 segundos .
Un enfoque ligeramente más complejo consiste en usar una criba. En lugar de comprobar la primalidad de un número, las cribas permiten comprobar la primalidad de los números. La más antigua y conocida es la Criba de Eratóstenes . Se parte de la premisa de que todos los números son primos. Empezando con 2 como primer primo, se encuentran todos los números que lo dividen exactamente y se eliminan del conjunto de primos. Se continúa con el siguiente número que aún esté en el conjunto de primos. A continuación se muestra una versión no optimizada.
getPrimes2 = Function( {n}, {primeSet,i,j},
primeSet = J( n, 1, 1 );
primeSet[1] = 0;
For( i = 2, i <= n, i++,
For( j = i, j <= n / i, j++,
primeSet[j * i] = 0
)
);
Loc( primeSet );
);
La ventaja más obvia es la velocidad. Mi tiempo para encontrar todos los primos menores de 100 000 fue de 0,2811 s, aproximadamente 70 veces más rápido, y de 3,4025 s para 1 000 000. El código sigue siendo conciso y fácil de entender. Una pequeña desventaja es que se necesita crear un vector para rastrear los números no primos (es decir, no se puede aumentar la lista por concatenación, lo cual, como veremos más adelante, no es necesariamente una ventaja). Esto dificulta la búsqueda de n primos, ya que no se sabe exactamente qué tan grande será el vector necesario.
A continuación se presentan dos versiones optimizadas. La primera comienza eliminando todos los múltiplos de dos y, a continuación, recorre solo los números impares a partir del 3. Sqrt( n ) se utiliza para el límite superior del bucle externo, ya que todos los números no primos menores que ese número ya se habrán filtrado. Por ejemplo, para encontrar todos los primos menores de 100, solo se necesita filtrar hasta 10. Los números filtrados para cualquier primo mayor que 10 serán el producto de ese primo por un número menor que 10, que se habrá eliminado con algún otro número primo (por ejemplo, 11*5 se elimina con el filtro para 5, 11*9 con el filtro para 3, etc.). Estas mejoras reducen el tiempo de ejecución a más de la mitad, a 1,3545. El segundo muestra la ventaja de utilizar las operaciones matriciales de JSL para el bucle interno, con tiempos de 0,01625 para 1.000.000 y 2,6694 para 100.000.000, ¡una mejora de casi 100 veces!
getPrimes2 = Function( {n}, {primeSet,i,j},
primeSet = J( n, 1, 1 );
primeSet[4::n::2] = 0;
primeSet[1] = 0;
For( i = 3, i <= Sqrt( n ), i+=2,
For( j = i, j <= n / i, j++,
primeSet[j * i] = 0
)
);
Loc( primeSet );
);
getPrimes2 = Function( {n}, {primeSet,i,j,upper},
primeSet = J( n, 1, 1 );
primeSet[4::n::2] = 0;
primeSet[1] = 0;
i = 3;
upper = Sqrt(n);
For(i=3,i<=upper,i+=2,
If(primeSet[i] == 1,
primeSet[(i*2)::n::i] = 0;
);
);
Loc( primeSet );
);
¿Se puede mejorar? La Criba de Atkin es teóricamente más eficiente y se implementó en los ejemplos Primes Atkins.JSL y Primes Atkins (optimizado).JSL . El primero ofrece una implementación no optimizada y más fácil de entender (2,236 s para 1 000 000). Mejor que la versión no optimizada de Eratóstenes. Sin embargo, la versión optimizada no superó a Eratóstenes optimizado (4,914 s para 100 000 000). Además, es mucho más larga y compleja, tanto programática como teóricamente.
¿Qué tal leer una tabla de números? Aunque esto no se ajusta a la idea de escribir un algoritmo, no dije que no se pudiera. @Craige_Hales ofreció una solución con este enfoque. Dada la especificación del problema de que n no debe exceder 1e8, el tamaño del script para contener los valores comprimidos requirió más de 4 millones de caracteres de código, 4,6 MB de espacio en disco y aproximadamente 5,5 segundos para cargarse, independientemente del tamaño de n . Más lento que las otras soluciones. Aunque no es ni el más rápido ni el más corto, he incluido el script de Craige por su enfoque único del problema, el uso de la compresión y Asignación paralela .
Encontrar n primos es un problema más desafiante. Suponiendo que usas un tamiz, necesitarás crear un vector de valores hasta el n º primo. Para hacer esto, se necesita estimar un límite superior para ese valor. Se debe evitar la subestimación ya que puede requerir volver a ejecutar parte o todo el algoritmo para encontrar valores no tamizados. Estimar el valor del n-ésimo primo.jmp muestra 6 estimaciones diferentes. Est1 da un caso donde los valores se subestiman para n pequeños. Muchas estimaciones solo se aplican a n mayores que un valor específico y se debe tener cuidado para proporcionar estimaciones alternativas en estos casos. Est2 es bueno para n ≥ 13 y Este3 mejora eso para valores más grandes. Desafortunadamente, los buenos límites rara vez son simples. Est4 se usó en Envío rápido de Primes.jsl . Si bien no hace un trabajo tan bueno y subestima para valores muy grandes de n , es simple y fácil de recordar. Son 5 se derivó usando Nonlinear con los valores reales. Est6 mejora Son 5 alterando ligeramente los valores para que ninguno de la tabla esté subestimado. No se garantiza que no existan subestimaciones entre 100 y 1e8. Las demás columnas de la tabla indican las subestimaciones/sobreestimaciones para cada técnica.
La determinación de la primalidad podría seguir un proceso similar al de la generación de primos. Dado un número x , se podría considerar i = 2. Si Mod( n , i ) = 0 , detenerse; de lo contrario, incrementar i . Continuar hasta que Mod( n , i ) = 0 o i = n . El código a continuación se beneficia de verificar solo el impar i después de la prueba inicial en i = 2 y detenerse cuando i > = Ceiling(Sqrt( n )) .
isPrime = Function({inVals},{i,j,outVec,nextVal,uBound},
outVec = J(N Row(inVals),1,-1);
For(i=1,i<=N Row(inVals),i++,
nextVal = inVals[i];
If(Mod(nextVal,2) == 0,
outVec[i] == 0;
,//ELSE
j = 3;
uBound = Ceiling(Sqrt(nextVal));
While(j < uBound & Mod(nextVal,j) != 0, j+=2);
If(j >= uBound, outVec[i] = 1,outVec[i] = 0);
)
);
outVec;
);
El script anterior tarda aproximadamente 1,4 segundos en comprobar los 1.000 números de ocho y nueve dígitos de la tabla Tabla de números grandes.jmp ( Pequeño ).
Para mejorar esto aún más, puedes generar un vector de números primos (hasta Ceiling(Sqrt( n )) ) e iterarlos.
getPrimes = Function( {n}, {primeSet,i,j,upper},
primeSet = J( n, 1, 1 );
primeSet[4::n::2] = 0;
primeSet[1] = 0;
i = 3;
upper = Sqrt(n);
For(i=3,i<=upper,i+=2,
If(primeSet[i] == 1,
primeSet[(i*2)::n::i] = 0;
);
);
Loc( primeSet );
);
isPrime = Function({inVals},{i,j,outVec,primeVec,nextVal},
outVec = J(N Row(inVals),1,-1);
primeVec = getPrimes(Ceiling(Sqrt(Max(inVals))));
For(i=1,i<=N Row(inVals),i++,
nextVal = inVals[i];
j=1;
While(j < N Row(primeVec) & Mod(nextVal,primeVec[j]) != 0, j++);
If(j >= N Row(primeVec), outVec[i]=1,outVec[i]=0);
);
outVec;
);
Esto reduce el tiempo a más de la mitad, a menos de 0,6 segundos.
Dos notas generales para mejorar la velocidad: En situaciones donde un valor de matriz debe usarse más de una vez, es más rápido asignar el valor a una variable, usando la variable en lugar de la matriz indexada. Si bien esto puede alargar el código, ahorrará tiempo. Pruebe esto reemplazando "nextVal" en el código anterior con su valor de matriz indexada ( inVals[i] ). En segundo lugar, la concatenación de matrices y Lugar se ralentiza a medida que aumenta el tamaño de la matriz. Si puede trabajar con una matriz ordenada, Loc ordenado realiza una búsqueda binaria y es mucho más rápido. Consulte Speed testing matrix operations.jsl para obtener más ejemplos sobre referenciación y concatenación de matrices.
Intentar encontrar primos en la columna de números grandes ( Grande ) es más problemático. Encontrar los primeros 10 toma alrededor de 1,9 segundos. En este punto, debe confiar en un algoritmo especializado para realizar mejoras. Miller-Rabin (MR) es una técnica de uso común y de implementación relativamente fácil para probar la primalidad. Se proporciona una versión determinista en millerRabin1.jsl . MR se basa en la exponenciación modular y se debe tener cuidado para evitar incurrir en errores de desbordamiento. Por sí solo, MR tarda 5,28 segundos en procesar los 1000 números Grande . Puede sorprenderle que MR sea más lento que el primer algoritmo isPrime anterior (2,34 segundos) al procesar los números Pequeño . Esto probablemente se deba a que se vuelve más eficiente computacionalmente a medida que los números aumentan de tamaño, lo que sugiere una mejora: pruebe hasta un cierto tamaño primo utilizando el punto 2) anterior. Si el número es primo, deténgase. De lo contrario, cambie a MR. Este enfoque se puede encontrar en millerRabin2.jsl . Se realizó un ajuste para encontrar el número ideal de primos para la verificación. Esto redujo el tiempo a la mitad, a 2,33 segundos.
