Ayuda para entender la aplicación Sieve of Eratosthenes

Question

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.

(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!

Answer 1

Creo que lo he descubierto, con la ayuda de programmingpraxis 'comments on their website. Para actualizar el problema, startj se define en el listado como (+ (* 2 i i) (* 6 i) 3), es decir, 2i^2 + 6i + 3.

No entendía inicialmente cómo esta expresión relacionada con p - ya que 'tamizar' para un número p debe comenzar en p^2, pensé que startj debería ser algo relacionado con 4i^2 + 12i + 9.

Sin embargo, startj es un índice en el vector v, que contiene los números impares a partir de 3. Por lo tanto, el índice de p^2 es en realidad (p^2 - 3)/2.

Expandiendo la ecuación: (p^2 - 3)/2 = ([4i^2 + 12i + 9] - 3)/2 = 2i^2 + 6i + 3 - que es el valor de startj.

me siento que podría haber sido más claro para definir startj como (quotient (- (* p p) 3) 2), pero de todos modos - Creo que lo resuelve :)

Answer 2

David Seiler: quizás no sea el más claro, pero además de implementar el tamiz básico, también tiene que implementar las tres optimizaciones descritas en el ejercicio.

Harto: ese fue mi segundo ejercicio. Todavía estaba experimentando con mi estilo de escritura.

Ephemient: correcto.

Vea una explicación más completa en mi comentario en Programming Praxis.

EDIT: He agregado un comentario adicional en Programming Praxis. Y cuando realmente miré el código, estaba equivocado sobre la derivación del número 6 en la fórmula; lo siento, te confundo.