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
Integer.numberOfTrailingZerosin 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)