secretos - Cálculo de números primos en Scala: ¿cómo funciona este código?

numeros primos seguridad

Question

Así que he pasado horas tratando de averiguar exactamente cómo este código produce números primos.

lazy val ps: Stream[Int] = 2 #:: Stream.from(3).filter(i =>
ps.takeWhile{j => j * j <= i}.forall{ k => i % k > 0});

He usado una cantidad de impresiones, etc., pero nada que lo haga más claro.

Esto es lo que creo que hace el código:

/**
* [2,3]
*
* takeWhile 2*2 <= 3
* takeWhile 2*2 <= 4 found match
* (4 % [2,3] > 1) return false.
* takeWhile 2*2 <= 5 found match
* (5 % [2,3] > 1) return true
* Add 5 to the list
* takeWhile 2*2 <= 6 found match
* (6 % [2,3,5] > 1) return false
* takeWhile 2*2 <= 7
* (7 % [2,3,5] > 1) return true
* Add 7 to the list
*/

Pero si cambio j*j en la lista para que sea 2 * 2, lo que suponía que funcionaría exactamente igual, causa un error de stackoverflow.

Obviamente me falta algo fundamental aquí, y realmente podría usar a alguien que me explique esto como si tuviera cinco años.

Cualquier ayuda sería muy apreciada.

Answer 1

Tus explicaciones son en su mayoría correctas, solo cometiste dos errores:

takeWhile no incluye el último elemento marcado:

scala> List(1,2,3).takeWhile(_<2)
res1: List[Int] = List(1)

Usted asume que ps siempre contiene solo dos y tres, pero debido a que Stream es flojo, es posible agregarle nuevos elementos. De hecho, cada vez que se encuentra un nuevo primo se agrega a ps y en el siguiente paso takeWhile considerará este nuevo elemento añadido. Aquí, es importante recordar que la cola de un Stream se calcula solo cuando es necesaria, por lo tanto, takeWhile no puede verlo antes de que todo se evalúe como verdadero.

Ten estas dos cosas en mente y deberías llegar a esto:

ps = [2]
i = 3
takeWhile
2*2 <= 3 -> false
forall on []
-> true
ps = [2,3]
i = 4
takeWhile
2*2 <= 4 -> true
3*3 <= 4 -> false
forall on [2]
4%2 > 0 -> false
ps = [2,3]
i = 5
takeWhile
2*2 <= 5 -> true
3*3 <= 5 -> false
forall on [2]
5%2 > 0 -> true
ps = [2,3,5]
i = 6
...

Si bien estos pasos describen el comportamiento del código, no es del todo correcto, ya que no solo agregar elementos al Stream es vago, sino que cada operación en él. Esto significa que cuando llama a xs.takeWhile(f) no todos los valores hasta que el punto cuando f es falso se computan de una vez; se computan cuando todo el mundo quiere verlos (porque es la única función que necesita ver en todos los elementos antes de que definitivamente puedan dar como resultado verdadero, porque falso puede abortar antes). Aquí el orden de cálculo cuando la pereza se considera en todas partes (ejemplo solo mirando 9):

ps = [2,3,5,7]
i = 9
takeWhile on 2
2*2 <= 9 -> true
forall on 2
9%2 > 0 -> true
takeWhile on 3
3*3 <= 9 -> true
forall on 3
9%3 > 0 -> false
ps = [2,3,5,7]
i = 10
...

Como forall se cancela cuando se evalúa como falso, takeWhile no calcula los restantes elementos posibles.

Answer 2

No estoy seguro de que buscar una explicación procedimental / imperativa sea la mejor manera de obtener comprensión aquí. Los flujos provienen de la programación funcional y se entienden mejor desde esa perspectiva. Los aspectos clave de la definición que ha dado son:

1. Es flojo . Aparte del primer elemento en la secuencia, nada se computa hasta que lo solicite. Si nunca pides el 5to primo, nunca será computado.

2. Es recursivo La lista de números primos se define en términos de sí misma.

3. Es infinito Los flujos tienen la propiedad interesante (porque son flojos) de que pueden representar una secuencia con un número infinito de elementos. Stream.from(3) es un ejemplo de esto: representa la lista [3, 4, 5, ...].

Veamos si podemos entender por qué tu definición calcula la secuencia de números primos.

La definición comienza con 2 #:: ... Esto solo dice que el primer número en la secuencia es 2, lo suficientemente simple hasta el momento.

La siguiente parte define el resto de los números primos. Podemos comenzar con todos los números de conteo comenzando en 3 ( Stream.from(3) ), pero obviamente necesitamos filtrar un montón de estos números (es decir, todos los compuestos). Así que consideremos cada número i . Si no soy un múltiplo de un número primo menor, entonces soy primo. Es decir, i es primo si, para todos los primos k menor que i , i % k > 0 . En Scala, podríamos expresar esto como

nums.filter(i => ps.takeWhile(k => k < i).forall(k => i % k > 0))

Sin embargo, no es realmente necesario verificar todos los números primos menores; solo necesitamos verificar los números primos cuyo cuadrado es menor que o igual a i (esto es un hecho de la teoría de números * ). Entonces, podríamos escribir

nums.filter(i => ps.takeWhile(k => k * k <= i).forall(k => i % k > 0))

Así que derivamos su definición.

Ahora, si probabas la primera definición (con k < i ), habrías encontrado que no funcionaba. Por qué no? Tiene que ver con el hecho de que esta es una definición recursiva.

Supongamos que estamos tratando de decidir qué viene después de 2 en la secuencia. La definición nos dice que primero determinemos si 3 pertenece. Para hacerlo, consideramos que la lista de primos hasta el primero es mayor o igual a 3 ( takeWhile(k => k < i) ). El primer primo es 2, que es menos de 3 - hasta ahora todo bien. Pero aún no conocemos el segundo mejor momento, así que tenemos que calcularlo. Bien, entonces primero tenemos que ver si 3 pertenecen ... ¡BOOM!

* Es bastante fácil ver que si un número n es compuesto, entonces el cuadrado de uno de sus factores debe ser menor que o igual a n . Si n es compuesto, entonces por definición n == a * b , donde 1 < a <= b < n (podemos garantizar que a <= b simplemente etiquetando los dos factores de manera apropiada). De a <= b se sigue que a^2 <= a * b , por lo que se sigue que a^2 <= n .

Answer 3

Ese código es más fácil (para mí, al menos) leer con algunas variables renombradas sugestivamente , como

lazy val ps: Stream[Int] = 2 #:: Stream.from(3).filter(i =>
ps.takeWhile{p => p * p <= i}.forall{ p => i % p > 0});

Esto se lee de izquierda a derecha con toda naturalidad, como

los primos son 2 , y los números i de 3 arriba, que todos los primos p cuyo cuadrado no exceda el i , no se dividen en partes iguales (es decir, sin algún resto distinto de cero).

En una verdadera forma recursiva, para entender esta definición como la definición de la corriente cada vez mayor de primos, asumimos que es así, y desde esa suposición vemos que no surge contradicción, es decir, la verdad de la definición se mantiene.

El único problema potencial después de eso es el momento de acceder a la secuencia de ps cuando se está definiendo . Como primer paso, imagina que tenemos otra corriente de primos que se nos proporciona desde algún lugar, mágicamente. Luego, después de ver la verdad de la definición, verifique que el tiempo de acceso sea correcto, es decir, nunca intentemos acceder a las áreas de ps antes de que se definan; eso haría que la definición quedara estancada, improductiva .

Recuerdo leer en algún lado (no recuerdo dónde) algo así como lo siguiente: una conversación entre un estudiante y un asistente,

• estudiante: ¿ qué números son primos?
• mago: bueno, ¿sabes qué número es el primer primo?
• s: sí, son 2 .
• w: está bien (escribe rápidamente 2 en una hoja de papel). ¿Y el próximo?
• s: bueno, el próximo candidato es 3 . necesitamos verificar si está dividido por cualquier primo cuyo cuadrado no lo exceda, ¡pero aún no sé cuáles son los primos!
• w: no te preocupes, te las daré. Es una magia que conozco; Soy un mago después de todo.
• s: está bien, entonces, ¿cuál es el primer número primo?
• w: (mira por encima del pedazo de papel) 2 .
• s: genial, entonces su cuadrado ya es mayor que 3 ... HEY, ¡has engañado! .....

Aquí hay una traducción de pseudocódigo ¹ de su código, leída parcialmente de derecha a izquierda , con algunas variables retituladas para mayor claridad (usando p para "primo"):

ps = 2 : filter (/i-> all (/p->rem i p > 0) (takeWhile (/p->p^2 <= i) ps)) [3..]

cual es también

ps = 2 : [i | i <- [3..], and [rem i p > 0 | p <- takeWhile (/p->p^2 <= i) ps]]

que es un poco más visualmente evidente, usando listas de comprensión . and comprueba que todas las entradas en una lista de Booleanos son True (leer | como "para", <- como "extraídas de", "como" que "y (/p-> ...) como" lambda de p " )

Así que ya ves , ps es una lista perezosa de 2, y luego de los números que saqué de una secuencia [3,4,5,...] modo que para todos los p extraídos de ps modo que p^2 <= i , se es cierto que i % p > 0 . Que es en realidad un algoritmo de división de prueba óptimo . :)

Aquí hay una sutileza, por supuesto: la lista ps es abierta. Lo usamos porque está siendo "desarrollado" (eso por supuesto, porque es flojo). Cuando se toman p s de ps , podría ser un caso en el que se ejecute más allá de su final, en cuyo caso tendríamos un cálculo sin terminación en nuestras manos (un " agujero negro "). Simplemente sucede :) (y necesita / puede ser probado matemáticamente) que esto es imposible con la definición anterior. Entonces 2 se pone en ps incondicionalmente, entonces hay algo para empezar.

Pero si tratamos de "simplificar",

bad = 2 : [i | i <- [3..], and [rem i p > 0 | p <- takeWhile (/p->p < i) bad]]

deja de funcionar después de producir solo un número, 2: cuando se considera 3 como el candidato, takeWhile (/p->p < 3) bad exige el siguiente número en bad después de 2, pero todavía no hay más números allí. "Salta por delante de sí mismo".

Esto es "arreglado" con

bad = 2 : [i | i <- [3..], and [rem i p > 0 | p <- [2..(i-1)] ]]

pero ese es un algoritmo de división de prueba mucho más lento, muy lejos del óptimo .

-

¹ ( Haskell en realidad, es más fácil para mí de esa manera :))