Thanks Gary (and Neil and Robby)
Very enlightening. I didn't know about "when". Of course what you said
about "set!" and "cond" makes perfect sense. Minor mods to your code
(using your set! elimination idea twice and caching (integer-sqrt x)) gives
the code below.
I noticed that I can also remove the define for candidate if I'm willing to
call (first candidate-primes) twice. Comments?
Thanks again!
-Joe
; function to create a list of prime factors of a number
; invoke as (factor n)
(define (factor n)
(let loop-factors ([facts '()] [x n] [start 2] [end 1000]
[candidate-primes (primes-from-to 2 1000)])
(define isqrtx (integer-sqrt x))
(cond [(and (empty? candidate-primes) (>= end isqrtx))
(if (= 1 x) facts (append facts (list x)))]
[else (cond [(empty? candidate-primes)
; attempt to pull in more primes in an efficient
manner
(set! start end)
(set! end (* 2 end))
(when (> (* 1.5 end) isqrtx)
(set! end isqrtx))
(loop-factors facts x start end (primes-from-to
start end))]
[else (define candidate (first candidate-primes))
(cond [(zero? (remainder x candidate))
(loop-factors (append facts (list
candidate)) (quotient x candidate) start end candidate-primes)]
[else
(loop-factors facts x start end (rest
candidate-primes))])])])))
On Sun, Feb 19, 2012 at 12:50 PM, Gary Baumgartner <g...@cs.toronto.edu>wrote:
> Applying a lot of what Neil said:
>
> ; function to create a list of prime factors of a number
> ; invoke as (factor n)
> (define (factor n)
> (let loop-factors ([facts '()] [x n] [start 2] [end 1000]
> [candidate-primes (primes-from-to 2 1000)])
> (cond [(and (empty? candidate-primes) (>= end (integer-sqrt x)))
> (if (= 1 x) facts (append facts (list x)))]
> [else (cond [(empty? candidate-primes)
> ; attempt to pull in more primes in an efficient
> manner
> (set! start end)
> (set! end (* 2 end))
> (when (> (* 1.25 end) (integer-sqrt x))
> (set! end (integer-sqrt x)))
> (set! candidate-primes (primes-from-to start end))
> (loop-factors facts x start end candidate-primes)]
> [else (define candidate (first candidate-primes))
> (cond [(zero? (remainder x candidate))
> (set! facts (append facts (list
> candidate)))
> (loop-factors facts (quotient x
> candidate) start end
> candidate-primes)]
> [else
> (loop-factors facts x start end (rest
> candidate-primes))])])])))
>
> When you're using a lot of 'begin's in 'if's, consider 'cond' which has
> imlicit 'begin'.
> And for single-branch 'if's [which must be for side-effect], 'when' or
> 'unless'.
>
> As for the 'set!'ing: notice, e.g., that
> (set! facts (append facts (list
> candidate)))
> (loop-factors facts (quotient x
> candidate) start end
> candidate-primes)
> is just
> (loop-factors (append facts (list
> candidate))
> (quotient x candidate)
> start end
> candidate-primes)
> ____________________
> Racket Users list:
> http://lists.racket-lang.org/users
>
____________________
Racket Users list:
http://lists.racket-lang.org/users
