Hi Rodolfo,<div><br></div><div>Thanks for the suggestions. Your re-factoring (no pun intended) of the conds really cleaned things up. Much appreciated.</div><div><br></div><div>About the unnecessary loops, good point, I simply changed to starting with end set to 10 instead of 1000 and I think that helps a lot. I know that there are other gross inefficiencies as well (for example, if primes-from-to gets called to just add a few primes to the list it is very slow as it goes through the whole list. A better implementation would "know" that the values on storedlst are already checked and skip checking them.</div>
<div><br></div><div>About the formatting: I really like to keep the code short on the screen, so I'm not fond of your use of newlines, I find that it is easier to read and debug code if you don't have to scroll down to see it.</div>
<div><br></div><div>Thanks again. Latest code below (I found and fixed a howler of a bug in primes-from-to).</div><div>-Joe</div><div><br></div><div><div>; function that returns a list of all integers between the two arguments inclusive</div>
<div>(define (interval-list m n)</div><div> (if (> m n) '() (cons m (interval-list (+ 1 m) n))))</div><div><br></div><div>; sieve of erostosthenes </div><div>(define (sieve lst)</div><div> (define (remove-multiples n lst)</div>
<div> (if (null? lst) '()</div><div> (if (= (modulo (car lst) n) 0)</div><div> (remove-multiples n (cdr lst))</div><div> (cons (car lst)</div><div> (remove-multiples n (cdr lst))))))</div>
<div> (if (null? lst) '() (cons (car lst) (sieve (remove-multiples (car lst) (cdr lst))))))</div><div><br></div><div>; wrapper function for sieve, saves a list of primes for future calls</div><div>(define primes-from-to</div>
<div> (let ([lastend 5] [storedlst '(2 3 5)])</div><div> (lambda (start end)</div><div> (cond [(<= lastend start) (set! storedlst (sieve (append storedlst (interval-list lastend end))))]</div><div> [(< lastend end) (primes-from-to lastend end)])</div>
<div> </div><div> ; storedlst now has all the primes needed</div><div> (when (< lastend end) (set! lastend end))</div><div> (filter (lambda (v) (and (<= start v) (<= v end))) storedlst))))</div>
<div><br></div><div>; function to create a list of prime factors of a number</div><div>; invoke as (factor n)</div><div>(define (factor n)</div><div> (let loop-factors ([facts '()] [x n] [start 2] [end 10] [candidate-primes (primes-from-to 2 10)])</div>
<div> (define isqrtx (integer-sqrt x))</div><div> (cond</div><div> [(and (empty? candidate-primes) (>= end isqrtx))</div><div> (if (= 1 x) facts (append facts (list x)))]</div><div> [(empty? candidate-primes)</div>
<div> ; attempt to pull in more primes in an efficient manner</div><div> (set! start end)</div><div> (set! end (* 2 end))</div><div> (when (> (* 1.5 end) isqrtx) (set! end isqrtx))</div><div> (loop-factors facts x start end (primes-from-to start end))]</div>
<div> [(zero? (remainder x (first candidate-primes)))</div><div> (loop-factors (append facts (list (first candidate-primes))) (quotient x (first candidate-primes)) start end candidate-primes)]</div><div> [else</div>
<div> (loop-factors facts x start end (rest candidate-primes))])))</div></div><div><br></div><div><br></div><div><br><div class="gmail_quote">On Sun, Feb 19, 2012 at 5:33 PM, Rodolfo Carvalho <span dir="ltr"><<a href="mailto:rhcarvalho@gmail.com">rhcarvalho@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hello Joe,<br><br>I'd like to make a few suggestions also.<br><br>~ 1 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~<div class="im">
<br><br>I repeat what Neil V. said:<br><br><blockquote style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote">
Formatting-wise, you might consider generally putting newlines between
each of the three parts of an "if" form. It's easier to distinguish the
parts at a glance, especially if the parts contain parens, and you can
also sometimes better see symmetries/asymmetries between the branches.</blockquote><br></div>And a similar rule would apply to let-, cond-, etc-clauses (i.e. the ones around square brackets []).<br><br>So instead of<br><br>
(let ([a 1] [b 2] [c 3])<br>
...)<br><br>I'd write for clarity:<br><br>(let ([a 1]<br> [b 2]<br> [c 3])<br> ...)<br><br><br><br>~ 2 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~<br><br>The three `cond' uses are like `if's. They only have 1 test and an else clause. So considering the cond's and if's, the code branches like this:<br>
<br>cond --- if ---- [1]<br> \ \---- [2]<br> \<br> \----- cond --- [3]<br> \<br> \------- cond ------ [4]<br> \----------- [5]<br><br><br>It is possible to replace a pattern like this:<br>
<br>(cond<br> [..a..]<br> [else (cond<br> [..b..]<br> ...)])<br><br>With this simpler:<br><br>(cond<br>
[..a..]<br>
[..b..]<br>
...)<br><br>That's one of the things that makes cond's different than if's...<br><br>After applying the above, the branching structure becomes:<br><br>cond --- if ---- [1]<br>
| \---- [2]<br>
|------ [3]<br>
|------ [4]<br>
|------ [5]<br><br><br><br>~ 3 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~<br><br>Using DrRacket's Debugger, I noticed that to compute (factor 4) the code was iterating many unnecessary times in the loop, until the candidate-primes list was exhausted.<br>
<br>Looking back at the code, we see that there's only one way to stop the recursion, which is when (and (empty? candidate-primes) (>= end isqrtx)) holds true.<br>So even when we want to factorize small numbers we have to go through the entire list of computed primes.<br>
This suggests rethinking about the conditions...<br><br><br>Here's the code with my changes:<div class="im"><br><br><br>; function to create a list of prime factors of a number<br>; invoke as (factor n)<br>(define (factor n)<br>
(let loop-factors ([facts '()]<br>
[x n]<br> [start 2]<br> [end 1000]<br> [candidate-primes (primes-from-to 2 1000)])<br> (define isqrtx (integer-sqrt x))<br> (cond<br>
[(and (empty? candidate-primes)<br>
(>= end isqrtx))<br> (if (= 1 x)<br> facts<br> (append facts (list x)))]<br></div><div class="im"> [(empty? candidate-primes)<br> ; attempt to pull in more primes in an efficient manner<br>
(set! start end)<br>
(set! end (* 2 end))<br> (when (> (* 1.5 end) isqrtx)<br> (set! end isqrtx))<br> (loop-factors facts<br> x<br> start<br> end<br> (primes-from-to start end))]<br>
</div>
[(zero? (remainder x (first candidate-primes)))<br> (loop-factors (append facts (list (first candidate-primes)))<br> (quotient x (first candidate-primes))<div class="im"><br> start<br>
end<br>
candidate-primes)]<br> [else<br> (loop-factors facts<br> x<br> start<br> end<br></div> (rest candidate-primes))])))<br>
<br><br><br>[]'s<span class="HOEnZb"><font color="#888888"><br><br clear="all">Rodolfo Carvalho<br>
</font></span></blockquote></div><br></div>