primos - El algoritmo del tamiz de Eratóstenes en JavaScript se ejecuta sin fin para un gran número
numeros primos python while (5)
Como llego un poco tarde a la fiesta. Me gustaría agregar mi contribución simple y un poco hacky que encuentra todos los números primos hasta 100:
<!DOCTYPE html>
<html>
<title>Primes</title>
<head>
<script>
function findPrimes() {
var primes = []
var search = []
var maxNumber = 100
for(var i=2; i<maxNumber; i++){
if(search[i]==undefined){
primes.push(i);
for(var j=i+i; j<maxNumber; j+=i){
search[j] = 0;
}
}
}
document.write(primes);
}
findPrimes();
</script>
</head>
<body>
</body>
</html>
He estado tratando de escribir el algoritmo de Tamiz de Eratóstenes en JavaScript. Básicamente simplemente seguí los pasos a continuación:
- Cree una lista de enteros consecutivos de 2 a (n-1)
- Sea el primer número primo p igual a 2
- Comenzando desde p, cuenta en incrementos de p y elimina cada uno de estos números (p y múltiplos de p)
- Ir al siguiente número en la lista y repetir 2,3,4
- Agregar números primos eliminados involuntariamente a la lista
Y esto es lo que he encontrado:
function eratosthenes(n){
var array = [];
var tmpArray = []; // for containing unintentionally deleted elements like 2,3,5,7,...
var maxPrimeFactor = 0;
var upperLimit = Math.sqrt(n);
var output = [];
// Eratosthenes algorithm to find all primes under n
// Make an array from 2 to (n - 1)
//used as a base array to delete composite number from
for(var i = 2; i < n; i++){
array.push(i);
}
// Remove multiples of primes starting from 2, 3, 5,...
for(var i = array[0]; i < upperLimit; i = array[0]){
removeMultiples:
for(var j = i, k = i; j < n; j += i){
var index = array.indexOf(j);
if(index === -1)
continue removeMultiples;
else
array.splice(index,1);
}
tmpArray.push(k);
}
array.unshift(tmpArray);
return array;
}
Funciona para números pequeños pero no para números mayores a un millón. Utilicé Node.js para probar y el proceso parece interminable y no se muestra ningún error de memoria. He leído una solución here (también en javascript) pero todavía no puedo comprenderla completamente.
Pregunta: ¿Cómo hacer que esto funcione para números suficientemente grandes, como un millón o más?
Está haciendo el Tamiz de Eratóstenes mucho más lento haciendo uso de funciones de manipulación de matrices, como Array#indexOf y Array#splice que se ejecuta en tiempo lineal. Cuando puede tener O (1) para ambas operaciones involucradas.
A continuación se muestra el Tamiz de Eratóstenes siguiendo las prácticas de programación convencionales:
var eratosthenes = function(n) {
// Eratosthenes algorithm to find all primes under n
var array = [], upperLimit = Math.sqrt(n), output = [];
// Make an array from 2 to (n - 1)
for (var i = 0; i < n; i++) {
array.push(true);
}
// Remove multiples of primes starting from 2, 3, 5,...
for (var i = 2; i <= upperLimit; i++) {
if (array[i]) {
for (var j = i * i; j < n; j += i) {
array[j] = false;
}
}
}
// All array[i] set to true are primes
for (var i = 2; i < n; i++) {
if(array[i]) {
output.push(i);
}
}
return output;
};
Esta pregunta es un poco mezquina en la definición de lo que es un "gran número" y acepta que comienza en solo un millón, para lo cual funciona la respuesta actual ; sin embargo, usa bastante memoria como en un número de 8 bytes (un doble real de 64 bits) para cada elemento que se tamizará y otro número de 8 bytes para cada primo encontrado. Esa respuesta no funcionaría para "grandes cantidades" de aproximadamente 250 millones o más, ya que excedería la cantidad de memoria disponible para la máquina de ejecución de JavaScript.
El siguiente código JavaScript que implementa la página "infinita" (sin límites) del Tamiz Segmentado de Eratóstenes supera ese problema, ya que solo utiliza un búfer de tamizado segmentado de 16 Kilobytes de páginas con un bit de bits (un bit representa un número primo potencial) y solo usa el almacenamiento para primos base hasta la raíz cuadrada del número más alto actual en el segmento de la página actual, con los números primos encontrados reales enumerados en orden sin necesidad de almacenamiento; también ahorrando tiempo al solo tamizar los compuestos impares, ya que el único primo par es 2:
var SoEPgClass = (function () {
function SoEPgClass() {
this.bi = -1; // constructor resets the enumeration to start...
}
SoEPgClass.prototype.next = function () {
if (this.bi < 1) {
if (this.bi < 0) {
this.bi++;
this.lowi = 0; // other initialization done here...
this.bpa = [];
return 2;
} else { // bi must be zero:
var nxt = 3 + 2 * this.lowi + 262144; //just beyond the current page
this.buf = [];
for (var i = 0; i < 2048; i++) this.buf.push(0); // faster initialization 16 KByte''s:
if (this.lowi <= 0) { // special culling for first page as no base primes yet:
for (var i = 0, p = 3, sqr = 9; sqr < nxt; i++, p += 2, sqr = p * p)
if ((this.buf[i >> 5] & (1 << (i & 31))) === 0)
for (var j = (sqr - 3) >> 1; j < 131072; j += p)
this.buf[j >> 5] |= 1 << (j & 31);
} else { // other than the first "zeroth" page:
if (!this.bpa.length) { // if this is the first page after the zero one:
this.bps = new SoEPgClass(); // initialize separate base primes stream:
this.bps.next(); // advance past the only even prime of 2
this.bpa.push(this.bps.next()); // keep the next prime (3 in this case)
}
// get enough base primes for the page range...
for (var p = this.bpa[this.bpa.length - 1], sqr = p * p; sqr < nxt;
p = this.bps.next(), this.bpa.push(p), sqr = p * p);
for (var i = 0; i < this.bpa.length; i++) { //for each base prime in the array
var p = this.bpa[i];
var s = (p * p - 3) >> 1; //compute the start index of the prime squared
if (s >= this.lowi) // adjust start index based on page lower limit...
s -= this.lowi;
else { //for the case where this isn''t the first prime squared instance
var r = (this.lowi - s) % p;
s = (r != 0) ? p - r : 0;
}
//inner tight composite culling loop for given prime number across page
for (var j = s; j < 131072; j += p) this.buf[j >> 5] |= 1 << (j & 31);
}
}
}
}
//find next marker still with prime status
while (this.bi < 131072 && this.buf[this.bi >> 5] & (1 << (this.bi & 31))) this.bi++;
if (this.bi < 131072) // within buffer: output computed prime
return 3 + ((this.lowi + this.bi++) * 2);
else { // beyond buffer range: advance buffer
this.bi = 0;
this.lowi += 131072;
return this.next(); // and recursively loop just once to make a new page buffer
}
};
return SoEPgClass;
})();
El código anterior se puede utilizar para contar los números primos hasta el límite dado por el siguiente código de JavaScript:
window.onload = function () {
var elpsd = -new Date().getTime();
var top_num = 1000000000;
var cnt = 0;
var gen = new SoEPgClass();
while (gen.next() <= top_num) cnt++;
elpsd += (new Date()).getTime();
document.getElementById(''content'')
.innerText = ''Found '' + cnt + '' primes up to '' + top_num + '' in '' + elpsd + '' milliseconds.'';
};
Si las dos piezas de código JavaScript anteriores se colocan en un archivo llamado app.js en la misma carpeta que el siguiente código HTML llamado whatever.html, podrá ejecutar el código en su navegador abriendo el archivo HTML en él:
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8" />
<title>Page Segmented Sieve of Eratosthenes in JavaScript</title>
<script src="app.js"></script>
</head>
<body>
<h1>Page Segmented Sieve of Eratosthenes in JavaScript.</h1>
<div id="content"></div>
</body>
</html>
Este código que se puede filtrar hasta el rango de los mil millones es de unos pocos segundos cuando se ejecuta en un motor de ejecución de JavaScript que utiliza la compilación Just-In-Time (JIT), como el motor V8 de Google Chrome. Se pueden lograr más ganancias utilizando la factorización extrema de la rueda y la eliminación previa de los buffers de página de los primos base más bajos, en cuyo caso la cantidad de trabajo realizado puede reducirse en un factor adicional de cuatro, lo que significa que se puede contar el número de primos. hasta mil millones en unos pocos segundos (el conteo no requiere enumeración como se usa aquí, sino que puede usar técnicas de conteo de bits directamente en los buffers del segmento de la página), aunque a costa de una mayor complejidad de código.
EDIT_ADD:
La velocidad de ejecución puede acelerarse en un factor de tres o más utilizando TypedArray y las optimizaciones de asm.js de ECMAScript 2015 (ahora se admite en todos los navegadores comunes) con las modificaciones de código de la siguiente manera:
"use strict";
var SoEPgClass = (function () {
function SoEPgClass() {
this.bi = -1; // constructor resets the enumeration to start...
this.buf = new Uint8Array(16384);
}
SoEPgClass.prototype.next = function () {
if (this.bi < 1) {
if (this.bi < 0) {
this.bi++;
this.lowi = 0; // other initialization done here...
this.bpa = [];
return 2;
} else { // bi must be zero:
var nxt = 3 + 2 * this.lowi + 262144; // just beyond the current page
for (var i = 0; i < 16384; ++i) this.buf[i] = 0 >>> 0; // zero buffer
if (this.lowi <= 0) { // special culling for first page as no base primes yet:
for (var i = 0, p = 3, sqr = 9; sqr < nxt; ++i, p += 2, sqr = p * p)
if ((this.buf[i >> 3] & (1 << (i & 7))) === 0)
for (var j = (sqr - 3) >> 1; j < 131072; j += p)
this.buf[j >> 3] |= 1 << (j & 7);
} else { // other than the first "zeroth" page:
if (!this.bpa.length) { // if this is the first page after the zero one:
this.bps = new SoEPgClass(); // initialize separate base primes stream:
this.bps.next(); // advance past the only even prime of 2
this.bpa.push(this.bps.next()); // keep the next prime (3 in this case)
}
// get enough base primes for the page range...
for (var p = this.bpa[this.bpa.length - 1], sqr = p * p; sqr < nxt;
p = this.bps.next(), this.bpa.push(p), sqr = p * p);
for (var i = 0; i < this.bpa.length; ++i) { // for each base prime in the array
var p = this.bpa[i] >>> 0;
var s = (p * p - 3) >>> 1; // compute the start index of the prime squared
if (s >= this.lowi) // adjust start index based on page lower limit...
s -= this.lowi;
else { // for the case where this isn''t the first prime squared instance
var r = (this.lowi - s) % p;
s = (r != 0) ? p - r : 0;
}
if (p <= 8192) {
var slmt = Math.min(131072, s + (p << 3));
for (; s < slmt; s += p) {
var msk = (1 >>> 0) << (s & 7);
for (var j = s >>> 3; j < 16384; j += p) this.buf[j] |= msk;
}
}
else
// inner tight composite culling loop for given prime number across page
for (var j = s; j < 131072; j += p) this.buf[j >> 3] |= (1 >>> 0) << (j & 7);
}
}
}
}
//find next marker still with prime status
while (this.bi < 131072 && this.buf[this.bi >> 3] & ((1 >>> 0) << (this.bi & 7)))
this.bi++;
if (this.bi < 131072) // within buffer: output computed prime
return 3 + ((this.lowi + this.bi++) << 1);
else { // beyond buffer range: advance buffer
this.bi = 0;
this.lowi += 131072;
return this.next(); // and recursively loop just once to make a new page buffer
}
};
return SoEPgClass;
})();
La aceleración funciona porque utiliza las matrices primitivas ECMAScript previamente escritas para evitar sobrecargas mediante el uso directo de enteros en las matrices (también evitando el desperdicio de espacio mediante el uso de representaciones flotantes) y también utiliza las sugerencias de tipo disponibles utilizando asm.js para provocar manipulaciones de bits. usar enteros / bytes sin signo Además, para ahorrar tiempo para las asignaciones de matriz, ahora asigna la matriz de cribado una vez y solo la pone en cero para cada nuevo segmento de página. Ahora se filtra a mil millones en aproximadamente 16 segundos con una CPU de 1.92 Gigahertz en lugar de aproximadamente 50 segundos. Además, el algoritmo se modifica para simplificar la representación del número compuesto interno (en bits empaquetados en bits) para obtener una velocidad adicional para primos más pequeños, que es la mayoría de las operaciones de eliminación.
Tenga en cuenta que ahora, aproximadamente el 60% del tiempo gastado ahora se gasta simplemente en la enumeración de los números primos encontrados. Esto podría reducirse en gran medida para el uso habitual de un tamiz de este tipo para simplemente contar los números primos encontrados sumando el número de bits cero en la matriz para cada página de segmento. Si se hizo esto, el tiempo de tamizar a mil millones sería algo cercano a 7 segundos en esta CPU de bajo rendimiento y puede haber otras optimizaciones posibles (todo el tiempo utilizando el motor de JavaScript de Google Chrome versión 72 V8 que se mejora constantemente y versiones posteriores pueden correr más rápido).
TBH, personalmente no me gusta JavaScript con todas sus extensiones y complejidades que han sido necesarias para convertirlo en un lenguaje "moderno" y, en particular, no me gusta la escritura dinámica, por lo que adopté el TypeScript de Microsoft cuando apareció hace algunos años. El código anterior es en realidad una modificación del código como resultado de TypeScript junto con su énfasis en la Programación Orientada a Objetos (OOP) tipificada estáticamente. Se me ocurrió que la llamada del "siguiente" método de instancia a través de la forma estándar de agregar métodos al "prototipo" puede ser mucho más lenta que solo llamar a una función, así que la probé y descubrí que ese es exactamente el caso, con este ejecutable enlace que enumera los números primos encontrados aproximadamente dos veces y media más rápido con solo cambiar la enumeración a una función de cierre de salida simple.
Ahora, podemos eliminar la enumeración de los primos solo contando el número de primos encontrados como se muestra en este otro enlace ejecutable con código modificado , lo que demuestra que incluso con la mejora anterior, la enumeración de los primos encontrados todavía cuesta casi tanto tiempo como en realidad el tamizado con este algoritmo con uno capaz de determinar el tiempo de enumeración como la diferencia entre el tiempo de ejecución para los dos enlaces anteriores al código ejecutable.
Tenga en cuenta que los tiempos de ejecución de los enlaces serán diferentes (y probablemente más cortos) que los que menciono aquí, ya que la mayoría de las CPU actuales serán más rápidas y más potentes que la tableta de Windows que estoy utilizando actualmente (Intel x5-Z3850 a 1.92 Gigahertz y El JavaScript se ejecuta en la máquina en la que está viendo el enlace.
Esto hace que JavaScript sea solo un poco más lento que el mismo algoritmo implementado en JVM o DotNet, que por supuesto es mucho más lento que el código nativo altamente optimizado compilado de lenguajes como C / C ++, Rust, Nim, Haskell, Swift, FreePascal, Julia, etc., que pueden ejecutar este algoritmo en aproximadamente dos segundos en esta CPU de gama baja. WebAssembly puede ejecutar este algoritmo hasta aproximadamente dos o tres veces más rápido que el JavaScript aquí, dependiendo de la implementación del navegador; también, cuando la especificación de WebAssembly esté completamente completa e implementada, tendremos soporte de subprocesos múltiples para obtener más ganancias por el factor de la cantidad de núcleos efectivos utilizados.
END_EDIT_ADD
EDIT_ADD_MORE:
Una vez que se realicen las modificaciones anteriores bastante pequeñas para simplemente contar los números primos encontrados de manera eficiente en lugar de enumerarlos, lo que hace que el tiempo de conteo sea un pequeño gasto general en comparación con el tamizado, valdría la pena hacer los cambios más extensos para usar la factorización máxima de la rueda ( por no solo 2 para "solo probabilidades", sino también 3, 5 y 7 para una rueda que cubre un tramo de 210 primos potenciales) y también antes de seleccionar la inicialización de las pequeñas matrices de cribado para que no sea necesario se eliminan los siguientes números primos de 11, 13, 17 y 19. Esto reduce el número de operaciones de selección de números compuestos cuando se utiliza el tamiz segmentado de páginas en un factor de aproximadamente cuatro a un rango de mil millones y se puede escribir para que se ejecute aproximadamente cuatro veces más rápido debido a las operaciones reducidas con cada operación de eliminación casi la misma velocidad que para el código anterior.
La forma de realizar la factorización de la rueda de 210 vástagos de manera eficiente es seguir este método de cribado "solo con posibilidades": el algoritmo actual anterior se puede considerar como cribar un plano lleno de bits de dos donde el otro plano puede eliminarse ya que contiene solo los números pares sobre dos; para el intervalo de 210 podemos definir 48 arreglos de bits de este tamaño que representan posibles números primos de 11 y superiores, donde todos los otros 162 planos contienen números que son factores de dos, tres, cinco o siete y por lo tanto no es necesario ser considerado. De esta manera, es igual de eficiente tamizar con menos requisitos de memoria (en más de la mitad en comparación con "solo probabilidades" y tanta eficiencia como aquí, donde una "página" de 48 planos representa 16 Kilobytes = 131072 bits por plano 210 veces, que es un rango de 27,525,120 números por segmento de página de tamiz, por lo tanto solo 40 segmentos de página por tamizar a mil millones (en lugar de casi 4 mil como antes), y por lo tanto menos sobrecarga en el cálculo de la dirección de inicio por primo base por segmento de página para un Mayor ganancia en eficiencia.
Aunque el código extendido descrito anteriormente es de unos pocos cientos de líneas y mucho más para publicar aquí, puede contar el número de números primos a mil millones en menos de dos segundos en mi CPU Intel G92 de 1.92 Gigaherz de gama baja usando el motor de Google V8 JavaScript, que es aproximadamente cuatro a cinco veces más lento que el mismo algoritmo ejecutado en código nativo. Esto se trata del límite de lo que podemos hacer en JavaScript, con más técnicas avanzadas de "desenrollado de bucle" y (por supuesto) no está disponible el multiprocesamiento. Sin embargo, es suficiente para que coincida con la implementación C de referencia optimizada a mano del Tamiz de Atkin en esta CPU de gama baja, que se ejecuta a aproximadamente 1,4 segundos.
Aunque el código anterior es bastante eficiente hasta un rango de aproximadamente 16 mil millones, otras mejoras pueden ayudar a mantener la eficiencia a rangos aún mayores de varias decenas de miles de millones de dólares, de modo que se podría contar el número de primos hasta aproximadamente 1e14 en unos pocos días usando JavaScript en una CPU más rápida. Esto es interesante ya que el número de números primos de este rango no se conoció hasta 1985 y luego se determinó mediante una técnica de análisis numérico, ya que las computadoras de ese día no eran lo suficientemente potentes para ejecutar el Tamiz de Eratóstenes lo suficientemente rápido para ese rango en una tiempo razonable.
Con mi actual "anti-JavaScript" y el sesgo de estilo de codificación funcional pro, escribiría este código usando Fable, que es una implementación de F # (lenguaje "funcional" ML tipificado estáticamente que también es compatible con OOP, si se desea) que se transmite a JavaScript muy de manera eficiente, por lo que es probable que el código generado sea tan rápido como si estuviera escrito directamente en JavaScript.
Para mostrar que el código puede ejecutarse casi tan rápido en el motor de Chrome V8 JavaScript usando Fable (con la interfaz Elmish React), al escribir JavaScript puro, como en el último enlace anterior , hay un enlace a un IDE en línea de Fable que contiene el algoritmo anterior . Se ejecuta un poco más lento que el JavaScript puro, y la vista de "Código" de la salida de JavaScript muestra por qué: el código generado para Tail Call Optimizations (TCO) no es un bucle tan simple como el de JavaScript. código solo para los apretados bucles internos de selección para obtener la misma velocidad. El código está escrito en un estilo funcional, excepto por la mutación del contenido de la matriz y según sea necesario para las funciones del generador de secuencias, que están en la misma forma que el JavaScript para una fácil comprensión; Funcionaría tan rápido si esta parte del código del generador de transmisión se escribiera para usar secuencias F #, sin mutación visible.
Dado que el código Fable anterior es F # puro, también podría ejecutarse con la biblioteca Fabulous como un generador de JavaScript de DotNet Core, o podría ejecutarse en múltiples plataformas y un poco más rápido ejecutándolo directamente bajo DotNet Core.
END_EDIT_ADD_MORE
En resumen, hay todo tipo de algoritmos que pueden encontrar los números primos a unos pocos millones en el orden de un segundo, pero se necesita un algoritmo de Tamiz de Eratóstenes basado en matriz segmentada por página para determinar los números primos a miles de millones en ese orden de tiempo de ejecución .
Pondría esto como un comentario para Alexander, pero no tengo la reputación de hacerlo. Su respuesta es asombrosa, y esto solo lo modifica para hacerlo más rápido. Me puse a prueba mediante la prueba n = 100,000,000.
En lugar de usar verdadero y falso en ''array'', obtengo un gran aumento de velocidad al usar 1 y 0. Esto redujo mi tiempo en Chrome de 5000 ms a 4250 ms. Firefox no se vio afectado (5600 ms en cualquier caso).
Entonces podemos tener en cuenta que los números pares nunca serán primos. Ponga 2 en ''salida'' fuera del bate y puede hacer i = 3; i + = 2, y j + = i * 2 durante el tamiz (podemos omitir los múltiplos pares ya que cualquier número multiplicado por un número par es par), siempre que también i + = 2 mientras presionamos para ''salir'' en fin. Esto redujo mi tiempo en Chrome de 4250 ms a 3350 ms. Firefox se benefició un poco menos, pasando de 5600 ms a 4800 ms.
De todos modos, la combinación de esos dos ajustes me dio un aumento de velocidad del 33% en Chrome y un aumento del 14% en Firefox. Aquí está la versión mejorada del código de Alexander.
var eratosthenes = function(n) {
// Eratosthenes algorithm to find all primes under n
var array = [], upperLimit = Math.sqrt(n), output = [2];
// Make an array from 2 to (n - 1)
for (var i = 0; i < n; i++)
array.push(1);
// Remove multiples of primes starting from 2, 3, 5,...
for (var i = 3; i <= upperLimit; i += 2) {
if (array[i]) {
for (var j = i * i; j < n; j += i*2)
array[j] = 0;
}
}
// All array[i] set to 1 (true) are primes
for (var i = 3; i < n; i += 2) {
if(array[i]) {
output.push(i);
}
}
return output;
};
Solo por diversión, implementé el algoritmo de tamiz Erastoten (ejecutado con Node) siguiendo estrictamente las reglas de TDD. Esta versión debería ser suficiente para las entrevistas, como ejercicio escolar o como lo fui yo, para jugar un poco.
Permítanme decirles que definitivamente creo que la respuesta aceptada debe ser la proporcionada por GordonBGood.
module.exports.compute = function( size )
{
if ( !utils.isPositiveInteger( size ) )
{
throw new TypeError( "Input must be a positive integer" );
}
console.time(''optimal'');
console.log();
console.log( "Starting for optimal computation where size = " + size );
let sieve = utils.generateArraySeq( 2, size );
let prime = 2;
while ( prime )
{
// mark multiples
for ( let i = 0; i < sieve.length; i += prime )
{
if ( sieve[i] !== prime )
{
sieve[i] = -1;
}
}
let old_prime = prime;
// find next prime number
for ( let i = 0; i < sieve.length; i++ )
{
if ( ( sieve[i] !== -1 ) && ( sieve[i] > prime ) )
{
prime = sieve[i];
break;
}
}
if ( old_prime === prime )
{
break;
}
}
console.timeEnd(''optimal'');
// remove marked elements from the array
return sieve.filter(
function( element )
{
return element !== -1;
} );
} // compute
Apreciaré cualquier crítica sensata.
El repositorio completo se puede encontrar en mi cuenta github.