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 <rhcarva...@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
>
____________________
Racket Users list:
http://lists.racket-lang.org/users
