Fermat factorization method limit
- by Fakrudeen
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))
)
)
)
)
