Un enfoque de Kobayashi Maru para encontrar números primos

Se ha dicho que «La gran ingeniería logra un equilibrio entre objetivos contrapuestos». Creo que esto es cierto, tanto en ingeniería mecánica como de software. En este último, los objetivos en competencia suelen ser la claridad, el tamaño y la velocidad.

Así que pensé que era una gran oportunidad para aplicar este principio cuando un informático de América del Sur me retó a escribir un programa en lenguaje sencillo, basado en la criba de Eratóstenes, que pudiera contar el número de números primos inferiores a 250 000 en menos de un segundo (en una computadora de última generación de Walmart).

Ahora bien, el inglés sencillo no es el idioma más rápido del mundo, porque la claridad triunfa sobre la velocidad cuando el objetivo principal de un idioma es ser natural . Pero el inglés sencillo es un lenguaje razonablemente rápido, y al equilibrar objetivos contrapuestos, generalmente podemos encontrar una solución aceptable para cualquier problema que se nos presente.

En este caso, primero necesitábamos dejar claro el famoso Tamiz de Eratóstenes; fácil de entender. Así que comenzamos con la descripción de Wikipedia del algoritmo…

Para encontrar todos los números primos menores o iguales a un entero dado n por el método de Eratóstenes:
1. Crea una lista de enteros consecutivos del 2 al n: (2, 3, 4, …, n).
2. Inicialmente, sea p igual a 2, el número primo más pequeño.
3. Enumere los múltiplos de p contando hasta n desde 2p en incrementos de p, y márquelos en la lista (serán 2p, 3p, 4p,…; la p en sí no debe marcarse).
4. Encuentra el primer número mayor que p en la lista que no está marcado. Si no hay tal número, deténgase. De lo contrario, haga que p ahora sea igual a este nuevo número (que es el próximo primo) y repita desde el paso 3.

…que en lenguaje sencillo se lee así:

To make a list of prime numbers less than or equal to a number:
Create the list of consecutive integers from 2 to the number. \ wiki's #1
Get an entry from the list. \ wiki's #2
Loop. Mark higher multiples of the entry. \ wiki's #3
Get the entry for the next lowest possible prime. If the entry is not nil, repeat. \ wiki's #4

Eso se encarga del objetivo de claridad . Si se lo pregunta, las definiciones de tipo y las rutinas de soporte que hacen que eso realmente funcione son igualmente claras:

An entry is a thing with a number and a non-prime flag.
A list is some entries.

To create a list of consecutive integers from a number to another number:
Privatize the number.
Loop.
If the number is greater than the other number, exit.
Create an entry for the number.
Append the entry to the list.
Add 1 to the number.
Repeat.

To create an entry for a number:
Allocate memory for the entry.
Put the number into the entry's number.
Clear the entry's non-prime flag.

To mark higher multiples of an entry:
Privatize the entry.
Loop.
Put the entry's next into the entry.
If the entry is nil, exit.
If the entry's number is evenly divisible by the original entry's number, 
  set the entry's non-prime flag.
Repeat.

To get an entry for the next lowest possible prime:
Put the entry's next into the entry.
If the entry is nil, exit. 
If the entry's non-prime flag is set, repeat.

Así que claridad, bien. Tamaño, bueno (el ejecutable es de solo 150k). Pero ¿qué pasa con la velocidad? Un poco más de 4 minutos para hacer la lista completa de números entre 1 y 250 000. No es bueno. Hmm… ¿Qué haría el Capitán Kirk? ¿Y si sacrificamos un poco de tamaño por la velocidad? ¿Por qué, después de todo, seguimos calculando números primos una y otra vez cuando nunca cambian? Así que volví a ejecutar el programa, esta vez con una rutina adicional como esta…

To make a prime string from a list:
Put "N" into the prime string.
Loop.
Get an entry from the list.
If the entry is nil, exit.
If the entry's non-prime flag is set, append "N" to the prime string; repeat.
Append "Y" to the prime string.
Repeat.

…para hacer una string con todos los números primos marcados. Luego guardé la string en un archivo de texto y la pegué en una biblioteca que llamé «Comprobador de números primos súper rápido para números entre 1 y 250, 000». Así es como se ve esa biblioteca:

The prime string is a string equal to "NYYNYNYNNNYNYNNNYNYNNNYNNNNNYNYNNNNN...

To decide if a number is prime (fast check):
If the number is less than 1, say no.
If the number is greater than the prime string's length, say no.
Put the prime string's first into a byte pointer.
Add the number to the byte pointer.
Subtract 1 from the byte pointer.
If the byte pointer's target is the big-Y byte, say yes.
Say no.

La string principal en la fuente es, por supuesto, mucho más larga que la que se muestra arriba. Y podría ser 8 veces más corto si usáramos bits en lugar de «Y» para marcar los números primos. Pero me duele la cabeza tener que pensar tanto. En cualquier caso, este programa…

To run:
  Start up.
  Write "Working..." on the console.
  Start a timer.
  Get a count of prime numbers less than or equal to 250000.
  Stop the timer.
  Write the count then " prime numbers." on the console.
  Write the timer's string then " milliseconds." on the console.
  Wait for the escape key.
  Shut down.

To get a count of prime numbers less than or equal to a number:
  Privatize the number.
  Clear the count.
  Loop.
  If the number is prime (fast check), add 1 to the count.
  Subtract 1 from the number.
  If the number is less than 2, break.
  Repeat.

…que es muy claro y razonablemente pequeño (alrededor de 400k), también es notablemente rápido . puede contar los 22 044 números primos menores o iguales a 250 000 en 16 milisegundos o menos. Y dado que está (indirectamente) basado en el tamiz de Eratóstenes, ¡cumple con los requisitos de la especificación original!

Creo que el capitán Kirk lo aprobaría.