[racket] static variables question

Hi Rodolfo,

Thanks for the suggestions.  Your re-factoring (no pun intended) of the
conds really cleaned things up.  Much appreciated.

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.

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.

Thanks again.  Latest code below (I found and fixed a howler of a bug in
primes-from-to).
-Joe

; function that returns a list of all integers between the two arguments
inclusive
(define  (interval-list m n)
  (if (> m n) '() (cons m (interval-list (+ 1 m) n))))

; sieve of erostosthenes
(define (sieve lst)
  (define (remove-multiples n lst)
    (if (null? lst) '()
        (if  (= (modulo (car lst) n) 0)
             (remove-multiples n (cdr lst))
             (cons (car lst)
                   (remove-multiples n (cdr lst))))))
  (if (null? lst) '() (cons (car lst) (sieve (remove-multiples (car lst)
(cdr lst))))))

; wrapper function for sieve, saves a list of primes for future calls
(define primes-from-to
  (let ([lastend 5] [storedlst '(2 3 5)])
    (lambda (start end)
      (cond [(<= lastend start) (set! storedlst (sieve (append storedlst
(interval-list lastend end))))]
            [(< lastend end) (primes-from-to lastend end)])

      ; storedlst now has all the primes needed
      (when (< lastend end) (set! lastend end))
      (filter (lambda (v) (and (<= start v) (<= v end))) storedlst))))

; 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 10] [candidate-primes
(primes-from-to 2 10)])
    (define isqrtx (integer-sqrt x))
    (cond
      [(and (empty? candidate-primes) (>= end isqrtx))
       (if (= 1 x) facts (append facts (list x)))]
      [(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))]
      [(zero? (remainder x (first candidate-primes)))
       (loop-factors (append facts (list (first candidate-primes)))
(quotient x (first candidate-primes)) start end candidate-primes)]
      [else
       (loop-factors facts x start end (rest candidate-primes))])))



On Sun, Feb 19, 2012 at 5:33 PM, Rodolfo Carvalho <rhcarvalho at gmail.com>wrote:

> Hello Joe,
>
> I'd like to make a few suggestions also.
>
> ~ 1 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>
>
> I repeat what Neil V. said:
>
> 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.
>
>
> And a similar rule would apply to let-, cond-, etc-clauses (i.e. the ones
> around square brackets []).
>
> So instead of
>
> (let ([a 1] [b 2] [c 3])
>    ...)
>
> I'd write for clarity:
>
> (let ([a 1]
>       [b 2]
>       [c 3])
>   ...)
>
>
>
> ~ 2 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>
> 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:
>
> cond --- if ---- [1]
>   \          \---- [2]
>    \
>     \----- cond --- [3]
>             \
>              \------- cond ------ [4]
>                         \----------- [5]
>
>
> It is possible to replace a pattern like this:
>
> (cond
>    [..a..]
>    [else (cond
>                [..b..]
>                ...)])
>
> With this simpler:
>
> (cond
>    [..a..]
>    [..b..]
>     ...)
>
> That's one of the things that makes cond's different than if's...
>
> After applying the above, the branching structure becomes:
>
> cond --- if ---- [1]
>   |          \---- [2]
>   |------ [3]
>   |------ [4]
>   |------ [5]
>
>
>
> ~ 3 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>
> 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.
>
> 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.
> So even when we want to factorize small numbers we have to go through the
> entire list of computed primes.
> This suggests rethinking about the conditions...
>
>
> Here's the code with my changes:
>
>
>
> ; 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)))]
>       [(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))]
>       [(zero? (remainder x (first candidate-primes)))
>        (loop-factors (append facts (list (first candidate-primes)))
>                      (quotient x (first candidate-primes))
>
>                      start
>                      end
>                      candidate-primes)]
>       [else
>        (loop-factors facts
>                      x
>                      start
>                      end
>                      (rest candidate-primes))])))
>
>
>
> []'s
>
> Rodolfo Carvalho
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20120219/0a31d613/attachment-0001.html>