[plt-scheme] Re: Unreasonably slow
This is a bit late, but the solution to "What is the smallest number
that is evenly divisible by all of the numbers from 1 to 20"
is much simpler:
(require (planet "math.ss" ("soegaard" "math.plt" 1 3)))
(apply lcm (interval 1 20))
On Oct 29, 3:38 pm, Jens Axel Soegaard <jensa... at soegaard.net> wrote:
> Alex Rozenshteyn wrote:
> > I wrote this code for project euler problem 7:
>
> Project Euler is great fun. Obviously part of the fun is to write
> your own number theoretic functions, but since there are quite
> a few exercises at Project Euler that use the same concepts,
> it is convenient to use a library. For example:
>
> http://planet.plt-scheme.org/package-source/soegaard/math.plt/1/3/doc...
>
> > (require (planet "math.ss" ("soegaard" "math.plt" 1 3)))
> > (nth-prime 10000)
>
> With respect to the stream code, I suspect the problem is that the algorithm
> you use are quadratic. I tried replacing the two uses of stream-append with
> stream-cons, but the code was still slow.
>
> > (require r5rs)
> > (require srfi/41)
>
> > (define stream-primes
> > (let ((numbers (stream-cons 2 (stream-from 3 2)))
> > (filter-stream
> > (stream-lambda
> > (divisor strm)
> > (let ((not-div
> > (lambda (dividend)
> > (not (zero? (modulo dividend divisor))))))
> > (stream-filter not-div strm)))))
> > (stream-let
> > loop
> > ((strm numbers)
> > (primes stream-null))
> > (define prime (stream-car strm))
> > (stream-append
> > (stream prime)
> > (loop (filter-stream prime (stream-cdr strm))
> > (stream-append primes (stream prime)))))))
>
> > and I ran (stream-ref stream-primes 10000)
>
> > It took unreasonably long to run. Much longer than it took my python
> > code (which uses python's generators, to which srfi/41's lazy
> > comprehensions are as close as I can find in scheme). I'm curious as
> > to whether this is an artifact of lazy comprehensions in scheme being
> > slow or just my code being wrong.
>
> There are alternatives to streams though. Two options come to
> mind, namely srfi 42 and the for construct. As an example
> of the use of srfi 42 here is a solution to an earlier Euler exercise
> that you probably already have solved:
>
> What is the smallest number that is evenly divisible by
> all of the numbers from 1 to 20?
>
> > (require srfi/42 (planet "math.ss" ("soegaard" "math.plt" 1 3)))
>
> ; The largest prime factor of any n in 1..20 is 19.
> ; The primes below 20 is given by: (prev-primes 20 20)
>
> > (list-ec (:list p (prev-primes 20 20))
> (list p (max-ec (: n 1 21) ; n runs from 0 to 20
> (max-dividing-power p n))))
> ({19 1} {17 1} {13 1} {11 1} {7 1} {5 1} {3 2} {2 4})
>
> And given the prime number factorization it is easy to get
> the number:
>
> > (apply * (map (lambda (l) (apply expt l))
> '({19 1} {17 1} {13 1} {11 1} {7 1} {5 1} {3 2} {2 4})))
>
> --
> Jens Axel Søgaard
>
> _________________________________________________
> For list-related administrative tasks:
> http://list.cs.brown.edu/mailman/listinfo/plt-scheme