[racket] static variables question

From: Joe Gilray (jgilray at gmail.com)
Date: Sun Feb 19 12:52:21 EST 2012

Hi Neil, thanks for the input.  My responses inline below:

On Sun, Feb 19, 2012 at 2:02 AM, Neil Van Dyke <neil at neilvandyke.org> wrote:

> Some random feedback, from a quick glance at the code (I didn't work
> through the algorithm)...
> Do you mean to do "[candidate-primes (primes-from-to 2 1000)]" each time
> that "factor" is called?

Yes, basically I'm trying to avoid generating all the primes up to (sqrt n)
if possible.

> 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.

Yes, they are "start" and "end", but when I tried this:

(let* loop-factors ([facts '()] [x n] [start 2] [end 1000]
[candidate-primes (primes-from-to start end)])

The compiler said: let*: bad syntax (not a sequence of
identifier--expression bindings) in: loop-factors

> Also consider whether these magic numbers are arbitrary limits that are
> unnecessary, and then whether they should be arguments or irrelevant to the
> algorithm.

Good point, but (factor 923472398 2 1000) seemed ugly to me.  I suppose I
could put them in a helper function?

> For more idiomatic Racket, try to get rid of the "set!" forms, such as by
> passing those values as part of a named-"let".
OK, but I'd need to see an example.

If "end" is always non-negative, is "(or (> end (integer-sqrt x)) (> (*
> 1.25 end) (integer-sqrt x)))" redundant?

This is where I'm trying to be "smart" about how many primes are using
during the factorization.

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.

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.

Anyway that was my thinking

> 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.
Hmmm, yes, I left that as an exercise for the compiler!  More seriously,
will the Racket compiler optimizes those calls?

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.)

Yes, I've obviously got some learning to do.  thanks.

> 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.
> 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.

Interesting!  Is there a Racket profiler available?

> 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.

I like it.  thanks again.

> Joe Gilray wrote at 02/19/2012 04:05 AM:
>  Here's a slight reworking of the factor function.  I think it is prettier
>> and my in the spirit of Racket/Scheme.
> --
> http://www.neilvandyke.org/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20120219/022f5463/attachment.html>

Posted on the users mailing list.