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 toInteger.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)
arithmetic-shift
andbitwise-and
) are basically quicker ways to divide by 8 or 16 (and get the remainder). I could perhaps replace those withtruncate/
(orquotient/remainder
in Racket). I didn't actually write the code for "ease of understanding" per se, though I suppose I should make a greater effort to do so. e.g.,m
(innext-marked-from
) could have been namedmask
, since it masks out the bits we don't care about when callingfirst-set-bit
. \$\endgroup\$divide-by-16
is a useful abstraction, particularly if the reason I'm looking at the code is because I am not up to speed on a bit-shifting sieve or the various related functions. For what it's worth, looking at the Racket code base, there appears to be a lot of code where comments were an unrealized afterthought. \$\endgroup\$