22 September 2016

Variant A

Algorithmically, this is most closely related to the APL implementation.

On the 64KB Kaypro 10, it stops to do a garbage collection every couple of results. This seems like an obvious area for improvement.

DEFINE (((PRIMES (LAMBDA (N)
        (PROG (COUNT PRIMES)
            (SETQ COUNT 3)
            (SETQ PRIMES (LIST 2))
       NEXT (COND ((LESSP (LENGTH PRIMES) N)
                  (COND ((MEMBER 0 (MAPCAR PRIMES '(LAMBDA (X) (REMAINDER COUNT X)))) NIL)
                        (T (NCONC PRIMES (LIST COUNT)))))
            (T (RETURN PRIMES)))
        (SETQ COUNT (PLUS COUNT 1))
        (GO NEXT))))))

In fact, performance was so poor I thought I'd try a version that was more closely related to the algorithm in the BASIC implementations.

Variant B

DEFINE ((
  (DIVP (LAMBDA (N LIST)
        (PROG NIL (MAPCAR LIST '(LAMBDA (P)
                                  (COND ((ZEROP (REMAINDER N P)) (RETURN T)))))
                  (RETURN NIL))))

  (PRIMES (LAMBDA (N)
        (PROG (COUNT PRIMES)
            (SETQ COUNT 3)
            (SETQ PRIMES (LIST 2))
       NEXT (COND ((LESSP (LENGTH PRIMES) N)
                  (COND ((DIVP COUNT PRIMES) NIL)
                        (T (NCONC PRIMES (LIST COUNT)))))
            (T (RETURN PRIMES)))
        (SETQ COUNT (PLUS COUNT 1))
        (GO NEXT))))
))

Predictably, this variant is about three times faster, and causes a quarter of the number of garbage collections the APL-like variant makes.