Sieve of Eratosthenes in Scheme (R7RS)

Question

I've seen many implementations of Sieve of Eratosthenes in Scheme, but I thought I'd try to write one that is both space- and time-efficient:

• Space-efficient: I use R7RS bytevectors as a bitset, which encodes odd numbers starting with 3 (so bit 0 = 3, bit 1 = 5, bit 2 = 7, etc.).
• Time-efficient: Many implementations scan the table looking for the next viable prime. I instead use first-set-bit (analogous to Integer.numberOfTrailingZeros in Java) to avoid scanning each bit individually.

This code generates prime numbers up to at least n, and usually a handful more. It depends on SRFI 60 for the bitwise operations.

(define (primes-up-to-about n)
  (define table
    (make-bytevector (+ (arithmetic-shift n -4) 1) 255))
  (define len (bytevector-length table))
  (define bitlen (arithmetic-shift len 3))

  (define (clear! i)
    (define q (arithmetic-shift i -3))
    (bytevector-u8-set! table q
                        (copy-bit (bitwise-and i 7) (bytevector-u8-ref table q) #f)))
  (define (next-marked-from i)
    (let loop ((q (arithmetic-shift i -3))
               (m (arithmetic-shift -1 (bitwise-and i 7))))
      (and (< q len)
           (let ((v (bitwise-and (bytevector-u8-ref table q) m)))
             (cond ((zero? v) (loop (+ q 1) -1))
                   (else (+ (arithmetic-shift q 3) (first-set-bit v))))))))
  (define (index->value i)
    (+ i i 3))

  (let loop ((rv '(2)) (i 0))
    (define next (next-marked-from i))
    (if (not next)
        (reverse rv)
        (let ((nextval (index->value next)))
          (do ((j next (+ j nextval)))
              ((>= j bitlen))
            (clear! j))
          (loop (cons nextval rv) next)))))

I'm looking for ways to make the code more compact and/or elegant without sacrificing the space or time efficiency.

In particular, if you can make a SRFI 42 :bitset generator that actually does the equivalent of my next-marked-from, I can just turn the whole function into a list-ec comprehension. What's not to like? :-)

---

For people who want to test this program in Racket (since there aren't very many R7RS implementations currently around), add the following lines before the function definition:

(require srfi/60)
(define bytevector-length bytes-length)
(define bytevector-u8-ref bytes-ref)
(define bytevector-u8-set! bytes-set!)
(define make-bytevector make-bytes)

Answer 1

To be honest, if it weren't for the hint in the first line (define (primes-up-to-about n)), I'd have no idea that this was an implementation of the Sieve of Eratosthenes.

The main problem, I think, is that names like table, clear!, and next-marked-from are all too low-level, not much better than the bytevector primitives, and devoid of contextual meaning.

To start, I think you should be able to rearrange the definitions.

  (define bytelen (+ (arithmetic-shift n -4) 1))
  (define primes-table (make-bytevector bytelen 255))
  (define bitlen (arithmetic-shift len 3))

Instead of clear!, try a more meaningful name like mark-as-composite!.

To complete the abstraction of the bytevector as a sieve, you would also need a helper function (define (next-prime-above n) …) that combines your next-marked-from and index->value.

(reverse rv) seems suspiciously expensive. I think you should be able to build the list of primes in ascending order using smarter recursion.