Fermat factorization method limit

Posted by Fakrudeen on Stack Overflow See other posts from Stack Overflow or by Fakrudeen
Published on 2010-03-15T07:43:45Z Indexed on 2010/03/15 7:49 UTC
Read the original article Hit count: 259

Filed under:
|

I am trying to implement Fermat's factorization [Algorithm C in Art of computer programming Vol. 2]. Unfortunately in my edition [ISBN 81-7758-335-2], this algorithm is printed incorrectly. what should be the condition on factor-inner loop below? I am running the loop till y <= n [passed in as limit].

(if (< limit y) 0 (factor-inner x (+ y 2) (- r y) limit))

Is there anyway to avoid this condition altogether, as it will double the speed of loop?

(define (factor n) 
    (let ( ( square-root (inexact->exact (floor (sqrt n))) ) ) 
     (factor-inner (+ (* 2 square-root) 1) 1 (- (* square-root square-root) n) n)
    )
)
(define (factor-inner x y r limit)
(if (= r 0)
    (/ (- x y) 2)

    (begin 
        (display x)(display " ")(display y)(display " ")(display r)(newline)
        ;(sleep-current-thread 1)
        (if (< r 0)
            (factor-inner   (+ x 2) y (+  r x) limit)
            (if (< limit y) 0 (factor-inner x (+ y 2) (- r y) limit))
        )
    )
)
)

© Stack Overflow or respective owner

Related posts about algorithm

Related posts about Scheme