Esto es aburrido, lo sé, pero necesito un poco de ayuda para entender una implementación de Sieve of Eratosthenes. Es la solución al this Programming Praxis problem.Ayuda para entender la aplicación Sieve of Eratosthenes
(define (primes n)
(let* ((max-index (quotient (- n 3) 2))
(v (make-vector (+ 1 max-index) #t)))
(let loop ((i 0) (ps '(2)))
(let ((p (+ i i 3)) (startj (+ (* 2 i i) (* 6 i) 3)))
(cond ((>= (* p p) n)
(let loop ((j i) (ps ps))
(cond ((> j max-index) (reverse ps))
((vector-ref v j)
(loop (+ j 1) (cons (+ j j 3) ps)))
(else (loop (+ j 1) ps)))))
((vector-ref v i)
(let loop ((j startj))
(if (<= j max-index)
(begin (vector-set! v j #f)
(loop (+ j p)))))
(loop (+ 1 i) (cons p ps)))
(else (loop (+ 1 i) ps)))))))
La parte estoy teniendo problemas con es startj
. Ahora, puedo ver que p
va a pedalear entre números impares comenzando en 3, definido como (+ i i 3)
. Pero no entiendo la relación entre p
y startj
, que es (+ (* 2 i i) (* 6 i) 3)
.
Editar: Entiendo que la idea es saltarse los números previamente tamizados. La definición del rompecabezas establece que al tamizar un número x
, el tamizado debe comenzar en el cuadrado de x
. Por lo tanto, al cribar 3, comienza eliminando 9, etc.
Sin embargo, lo que no entiendo es cómo se le ocurrió al autor esa expresión para startj
(algebraicamente hablando).
De los comentarios del rompecabezas:
En general, cuando tamizado por n, tamizar comienza en n-cuadrado porque todos los múltiplos de n anteriores ya han sido tamizada.
El resto de la expresión tiene que ver con la referencia cruzada entre los números y los índices de tamizado. Hay un 2 en la expresión porque eliminamos todos los números pares antes de comenzar. Hay un 3 en la expresión porque los vectores de Esquema están basados en cero, y los números 0, 1 y 2 no son parte del tamiz. Creo que el 6 es en realidad una combinación de 2 y 3, pero ha pasado un tiempo desde que miré el código, así que te dejaré que lo descubras.
Si alguien me podría ayudar con esto, eso sería genial. ¡Gracias!
Bueno, expresada algebraicamente tenemos 'p = 2i + 3' y' startj = 2i^2 + 6i + 3', así que obviamente ... er ... obviamente ... hm. Esa no es la implementación más clara de Sieve que he leído alguna vez. –
De hecho :) Algunos comentarios hubieran sido agradables. – harto
'startj = (i + 1) * p + i' Se está saltando algunos números que ya se hubieran filtrado por pasos anteriores, creo. – ephemient