Sieve of Eratosthenes [SOLVED]

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

science4sail
Posts: 3
Joined: Fri Sep 26, 2008 12:23 am UTC

Sieve of Eratosthenes [SOLVED]

Postby science4sail » Fri Sep 26, 2008 1:00 am UTC

I'm trying to implement a simple sieve number sieve in (PLT) Scheme

Code: Select all

;max is currently set at 50 in the REPL
(define (sieve nums)
    (if (pair? nums)
   (let ((head (car nums)))
     (if (< (* head head)
       max)
         (cons head
          (sieve (filter (lambda (x)
                 (not (= 0 (modulo x head))))
               (cdr nums))))
         nums))

(define (filter pred xs)
  (if (pair? xs)
      (let ((head (car xs))
       (tail (cdr xs))
       (if (pred (head))
      (cons (head)
            (filter pred tail))
      (filter pred tail))
       '()))))
   '()))

however, when I test it on a list of numbers, nothing seems to happen. At least "filter" seems to work correctly

Code: Select all

> (+ 1 1)
2
> (filter (lambda (x) (not (= 0 (modulo x 2)))) '(2 3 4 5 6 7 8 9))
(3 5 7 9)
> (sieve '(2 3 4 5 6 7 8 9))
>


any suggestions?

(also, general comments would be appreciated. I'm new to this language)
Last edited by science4sail on Fri Sep 26, 2008 2:30 am UTC, edited 1 time in total.

User avatar
jemthealmighty
Posts: 145
Joined: Fri May 23, 2008 6:55 am UTC
Location: Dubbo, NSW, Australia
Contact:

Re: Sieve of Eratosthenes

Postby jemthealmighty » Fri Sep 26, 2008 1:13 am UTC

Hello science4sail,
First off, welcome to the forums.
I don't know the language you are using so if you go through line by line and write out what it is meant to do in something like pseudo code either you'll find the bug, or I'll be able to do some prototypes in python or something and see where the problem is.

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Sieve of Eratosthenes

Postby Xanthir » Fri Sep 26, 2008 2:11 am UTC

This your exact code? 'Cause your parens aren't matched properly. When I pretty-print your code, it comes out like this:

Code: Select all

(define (sieve nums)
 (if (pair? nums)
     (let ((head (car nums)))
       (if (< (* head head) max)
           (cons head
                 (sieve
                  (filter (lambda (x) (not (= 0 (modulo x head))))
                   (cdr nums))))
           nums))
     (define (filter pred xs)
      (if (pair? xs)
          (let ((head (car xs))
                (tail (cdr xs))
                (if (pred (head)) (cons (head) (filter pred tail))
                 (filter pred tail))
                (quote nil)))))
     'nil))

So there's your issue. Filter is defined properly, but Sieve is broken. When you pass it a list of length > 2, it fails the opening (if) and drops down to just return '() ( 'nil in Lisp, which I pretty-printed this in). I'm not familiar with PLTScheme's printing philosophy, but I guess it just doesn't print anything when a function returns the empty list?

Does your REPL match parens for you? If not, drop it and get a better one.

(I'd also recommend picking up Common Lisp over Scheme, but that's really just personal preference.)
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

science4sail
Posts: 3
Joined: Fri Sep 26, 2008 12:23 am UTC

Re: Sieve of Eratosthenes

Postby science4sail » Fri Sep 26, 2008 2:30 am UTC

I changed the opening "if" to check for emptiness (or the lack thereof), and it works!
Thanks! :)

PS. Scheme is because I happened to come across the Wizard Book. PLT...I'm not sure how I ended up there.

rabuf
Posts: 15
Joined: Thu Mar 20, 2008 2:30 pm UTC

Re: Sieve of Eratosthenes

Postby rabuf » Fri Sep 26, 2008 2:32 am UTC

As Xanthir said, the parens don't match. However, that's not the only problem. Filter is also not defined properly, and required some alterations to run correctly on it's own. Something to keep in mind about Scheme: (symbol) is evaluated as a function call. Your code contains several function calls where you don't want them. Some of your code reminds me of the typos I used to make when I first started using Lisp after using Java/C/C++ for most of a decade. You need to break yourself of the habit of placing parens around parameter lists.

@Xanthir:
Xanthir wrote:So there's your issue. Filter is defined properly, but Sieve is broken. When you pass it a list of length > 2, it fails the opening (if) and drops down to just return '() ( 'nil in Lisp, which I pretty-printed this in).

pair? in Scheme is equivalent to consp in Common Lisp. It's not failing when the list's length > 2, but rather, when you have an atom.

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Sieve of Eratosthenes [SOLVED]

Postby Xanthir » Fri Sep 26, 2008 2:43 am UTC

Ah, that makes more sense rabuf. Thanks.

@Science4sail:
Your code only works because you are very, very lucky. Your parens are still mismatched, and as rabuf said, you have several function calls when you don't intend them. I didn't even look at the code itself once I saw the mismatched parens. ^_^

Edit: All right, now I *know* your code doesn't work as written. I just rewrote it in Lisp, and it definitely does not do what it is supposed to do. See where you test if the square of head is less than 50? There's no alternate clause! This means that once head goes above 7, sieve just returns an empty list. It only *appears* to work given the very small number of inputs you're feeding it.

Here's corrected code in Lisp:

Code: Select all

(defun sieve (nums)
  (if nums
      (let ((head (first nums)))
        (if (< head 8)
            (cons head
                  (sieve
                   (remove-if (curry 'dividesp head)
                              (rest nums))))
                nums))))
(defun dividesp (x num)
    (zerop (mod num x)))
(defun curry (func &rest args)
    (lambda (&rest more-args)
        (apply func (append args more-args))))


In Scheme, it'd probably looks something like this (I really don't know the particular ways in which Scheme's basic functions differ from Lisp):

Code: Select all

(define (sieve nums)
  (if (not (empty? nums))
      (let ((head (first nums)))
        (if (< head 8)
            (cons head
                  (sieve
                   (remove-if (curry 'dividesp head)
                              (rest nums))))
                nums))))

Translate dividesp and curry appropriately as well, and assume an appropriate implementation of remove-if (this function is built into Lisp, but is equivalent to the opposite of your filter function).
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

science4sail
Posts: 3
Joined: Fri Sep 26, 2008 12:23 am UTC

Re: Sieve of Eratosthenes [SOLVED]

Postby science4sail » Fri Sep 26, 2008 5:06 am UTC

I've modified it and removed all the parens that seemed unnecessary

"filter" then disappeared completely, as I found an existing function to do the same...named "filter"

the (aligned) code again with the rest of its horrific block:

Code: Select all

;the code generates primes up to "m" (and one above)
(define (primes m)
  (define (sieve nums)
    (if (not (null? nums))
        (let ((head (car nums)))
          (if (< (* head head)
                    m)
              (cons head
                    (sieve (filter (lambda (x)
                                     (not (zero? (modulo x head))))
                                   (cdr nums))))
               nums))
        '()))
  (define (wheel curr n)
    (cons curr
          (if (< curr m)
              (wheel (+ curr 3 n)
                     (- n))
              '())))
  (append '(2 3)
          (sieve (wheel 5 (- 1)))))

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Sieve of Eratosthenes [SOLVED]

Postby Xanthir » Fri Sep 26, 2008 1:56 pm UTC

All right, looks good. It works now. I'd modify (wheel) a bit to move the (cons) call into the then-clause of the (if) - right now it can generate numbers above the limit you set. This code won't do that:

Code: Select all

(define (wheel curr n)
   (if (< curr m) (cons curr (wheel (+ curr 3 n) (- n))) nil))

One note, though - while your generator is relatively fast, it's definitely not tail-recursive, and so (sieve) can overflow the stack with large numbers. For me it happens somewhere between 100k and 1M.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))


Return to “Coding”

Who is online

Users browsing this forum: Steeler [Crawler] and 6 guests