Hi Neil, thanks for the input. My responses inline below:<br><br><div class="gmail_quote">On Sun, Feb 19, 2012 at 2:02 AM, Neil Van Dyke <span dir="ltr"><<a href="mailto:neil@neilvandyke.org">neil@neilvandyke.org</a>></span> wrote:<br> <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Some random feedback, from a quick glance at the code (I didn't work through the algorithm)...<br> <br> Do you mean to do "[candidate-primes (primes-from-to 2 1000)]" each time that "factor" is called?<br></blockquote><div><br></div><div>Yes, basically I'm trying to avoid generating all the primes up to (sqrt n) if possible. </div> <div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> <br> 2 and 1000 are magic numbers, and should at least be given names, for documentation purposes and so that the constants appear in only one place.<br></blockquote><div><br></div><div>Yes, they are "start" and "end", but when I tried this:</div> <div><br></div><div>(let* loop-factors ([facts '()] [x n] [start 2] [end 1000] [candidate-primes (primes-from-to start end)])</div><div><br></div><div>The compiler said: let*: bad syntax (not a sequence of identifier--expression bindings) in: loop-factors </div> <div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> <br> Also consider whether these magic numbers are arbitrary limits that are unnecessary, and then whether they should be arguments or irrelevant to the algorithm.<br></blockquote><div><br></div><div>Good point, but (factor 923472398 2 1000) seemed ugly to me. I suppose I could put them in a helper function?</div> <div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> <br> For more idiomatic Racket, try to get rid of the "set!" forms, such as by passing those values as part of a named-"let".<br> <br></blockquote><div><br></div><div>OK, but I'd need to see an example.</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> If "end" is always non-negative, is "(or (> end (integer-sqrt x)) (> (* 1.25 end) (integer-sqrt x)))" redundant?<br></blockquote><div><br></div><div>This is where I'm trying to be "smart" about how many primes are using during the factorization.</div> <div><br></div><div>Let's say you are at a point in the algorithm where start is 16000, end is 32000 and (integer-sqrt x) is 65000. Further let's say that primes have only been generated (by primes-from-to) up to 32000.</div> <div><br></div><div>It may be possible that one of the primes in [start end] will divide x and you will be done at 32000, but if not, you will need to get more primes with (primes-from-to start end). Normally you'd get [32000 64000], but if x is prime the you will then have to come back for [64000 65000] before being done. It is much more efficient to make one call (primes-from-to 32000 65000) than to make two calls.</div> <div><br></div><div>Anyway that was my thinking </div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> <br> You are doing "(integer-sqrt x)" a few times, when "x" can't change in between. You might want to have the code look like "(integer-sqrt x)" is computed only once in the block of code in which "x" can't change. Just good practice, IMHO; I don't promise that it makes a performance difference.<br> <br></blockquote><div><br></div><div>Hmmm, yes, I left that as an exercise for the compiler! More seriously, will the Racket compiler optimizes those calls?</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> You have some tests in nested "if" forms that look redundant. Perhaps those can be adjusted so that redundant tests don't happen, such as by getting rid of the "and" and shuffling around the "if" forms and their clauses. (Sometimes this can be done easily; other times, it requires creating little helper procedures, and gets messy.)<br> </blockquote><div><br></div><div>Yes, I've obviously got some learning to do. thanks.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> <br> 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.<br> <br> Lots of people use "append" casually, but if you get to the point of fine-tuning this code or some other code, I usually try to build up lists with the code pattern "(cons NEW-ELEMENT EXISTING-LIST)". Sometimes this means doing a "reverse" after the list is complete. However, assuming that the rest of the algorithm is essentially the same, whether avoiding "append" is actually faster can come down to characteristics of the garbage collector (and both the sizes and the lifetimes of the lists can be relevant), so I think you'd have to evaluate performance empirically.<br> </blockquote><div><br></div><div>Interesting! Is there a Racket profiler available?</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> <br> You can use "(zero? X)" instead of "(= 0 X)". This is a minor point of personal style: I have a bit of folk wisdom that, if you're testing numeric equality with a constant in an algorithm, such as a number that changes in a loop, most often that constant should be 0, and using "zero?" acknowledges that.<br> </blockquote><div><br></div><div>I like it. thanks again.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> <br> Joe Gilray wrote at 02/19/2012 04:05 AM:<div class="HOEnZb"><div class="h5"><br> <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> Here's a slight reworking of the factor function. I think it is prettier and my in the spirit of Racket/Scheme.<br> </blockquote> <br> <br></div></div><span class="HOEnZb"><font color="#888888"> -- <br> <a href="http://www.neilvandyke.org/" target="_blank">http://www.neilvandyke.org/</a><br> </font></span></blockquote></div><br>