Archie Maskill
A software development blog

Multiple Filtered, Infinite, Lazy Streams (and the Sieve of Eratosthenes)

While playing about with some of the problems on Project Euler, I came across this one:

Calculate the 10,001st prime number.

While I find the maths interesting, the real reason I’m working through these problems is to flex some of my Lisp muscles. This particular problem reminded me of a very cool algorithm I saw a while back in “The Structure and Interpretation of Computer Programs” that used a combination of the Sieve of Eratosthenes and infinite, lazy streams.

The principle of the Sieve is as follows:

Every natural number is regarded as a candidate for being a prime number:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 ….

We know that 2 is a prime number (we make a note of that). Any multiple of 2 is NOT a prime number, so we remove these from the list:

3 5 7 9 11 13 15 17 19 21 23 25 27 …

3 must be prime (we make a note of that). Any multiple of 3 is NOT a prime number, so we remove these from the list:

5 7 11 13 17 19 23 25 …

5 must be prime (we make a note of that). Any multiple of 5 is NOT a prime number, so we remove these from the list:

7 11 13 17 19 23 …

… and so on.

Implementations of this algorithm are not renowned for their speed; however, I wanted to implement this algorithm to not ony demonstrate the Sieve as a set of multiple filtered infinite lazy streams, but to show how easy it is to implement streams themselves within Scheme (specifically PLT Scheme), if someone has not been kind enough to do this for you already.

A stream is like a list. While a list contains all of its evaluated data, a stream contains only two things: the first item of data, and a promise to generate more of this data should it be asked for.

In Scheme, it’s very easy to implement both a promise to do something, and a means for forcing that promise to be fulfilled:

(define-syntax-rule (make-promise form)
  (lambda () form))
(define-syntax-rule (force-promise promise)
  (promise))

Thus:

(force-promise (make-promise (+ 1 2 3)))  ; => 6

Now, a stream contains a data item, and the promise of further data items. Here is an example of the syntax we’d like to use, inspired by the syntax of list manipulation:

(stream-car (cons-stream 5 7))   ; => 5
(stream-cdr (cons-stream 5 7))   ; => 7
(empty-stream? the-empty-stream) ; => #t

We can implement this as follows:

(define-syntax-rule (cons-stream x y)
  (cons x (make-promise y)))
(define (stream-car s) (car s))
(define (stream-cdr s) (force-promise (cdr s)))
(define the-empty-stream null)
(define (empty-stream? s) (null? s))

The Sieve of Eratosthenes works by repeated filtering on the set of all natural numbers. As no computer has enough memory to contain this entire set of numbers, this makes the method ideal for implementation using streams.

Here, we define a filtering mechanism:

(define (stream-filter pred s)
  (cond ((stream-null? s) the-empty-stream)
        ((pred (stream-car s)) (cons-stream (stream-car s)
                                            (stream-filter pred (stream-cdr s))))
        (else (stream-filter pred (stream-cdr s)))))

… and something to generate an infinite stream of natural numbers…

(define (integers-starting-from n)
  (cons-stream n
               (integers-starting-from (+ n 1))))

… and, hey presto, we now have enough working parts to building the Sieve!

(define (nth-prime N)
  (let iter ([count 1]
             [stream (integers-starting-from 2)])
    (if (= count N)
        (stream-car stream)
        (let ((prime-number (stream-car stream)))
          (iter (+ count 1)
                (stream-filter (lambda (x)
                                 (> (mod x prime-number) 0))
                               stream))))))

(nth-prime 10001)  ; => 104743

This particular implementation finds the 10,001st prime number.
As I said, it’s not an efficient implementation, but I found it to be an incredibly scenic route.

Advertisements

No Responses to “Multiple Filtered, Infinite, Lazy Streams (and the Sieve of Eratosthenes)”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: