[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