[plt-scheme] Unreasonably slow

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

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