Sieve of Eratosthenes: Ruby and Python

Here's a bit more math history and coding nonsense, this time involving prime numbers...

Eratosthenes was a Greek mathematician and one of the greatest scholars of Alexandria (273-192 B.C). He derived an algorithm for sifting out the composite numbers in the natural series, leaving only prime numbers remaining. The algorithm works like this:

1. Start with a list of all the odd numbers in order, starting from 3.
2. Cancel the successive multiples for each element, one after another.
3. Continue iterating through the list until you reach the end.

As usual, just for fun, I coded up the Sieve of Eratosthenes in Ruby and Python. Here, we start with a list of natural numbers in order, beginning with the first prime number, 2. The sieve logic then examines each element of the list, and if the value of the list element in question is less than the square root of the maximum value in the list, then we proceed to remove all multiples of this list element, starting from the square of this element and working upwards through the end of the list. Such an approach increases efficiency a bit so that we do not have to check all elements up through to the end of the list when searching for multiples to sift out.


In Ruby

def execute(limit=100)
  # set up
  primes = (2..limit).to_a

  # sieve logic
  sieve_end = Math.sqrt(limit).floor
  for i in 0...primes.size
    break if primes[i] > sieve_end
    primes.delete_if { |n| n >= primes[i]**2 && n%primes[i]==0 }
  end

  primes
end

In Python

def sublime(m):
   return lambda x: x==m or (x>m and x%m!=0)

def execute(limit=100):
   # set-up
   primes = range(2,limit+1)

   # sieve logic
   sieve_end = int(sqrt(limit))

   for i in range(0, len(primes)):
       if primes[i] > sieve_end: break
       primes[i:] = filter(sublime(primes[i]), primes)

   return primes

While the code above may offend pure Rubyists and Pythonistas, it nevertheless appeals to me for still being rather clean. I tried to use more a more functional programming approach, with a nice Ruby block and a Python lambda function for sifting out the non-primes.

I haven't been coding any Java seriously for the past few months, and I don't seem to miss Java much. I must admit that functional programming seems quite fresh and interesting, and both Ruby and Python have features that allow for a functional approach mapping, reducing, and filtering lists.

Wonder if I should try this in CLisp tonight?

Starting Up Google Code Project

I am starting up a Google Code project at http://code.google.com/p/brooke-fujita/. It should be a good way to store/share any code I write, in an effective and easily-accessible manner. I have opted for the Apache style licensing, just for kicks. よろしく！

Rant on Ruby On Rails

I have just about wrapped up my spike using Ruby on Rails. It was only for a very small RESTful web service, but this experience has left a somewhat bitter aftertaste. Here's a short list of things I hate about Ruby on Rails:

1. No documentation.
This one floored me, but it is true. Just have a look here. Do you see any useful specifications? User manuals? Nope. Just some dry API documentation, a handful of tutorials, and a link to a book for sale. Sorry, but does anyone find this acceptable?

2. Questionable release management
The latest Rails release broke what little library support was available for composite keys for database tables. I don't even know if this has been fixed yet. But that's not all.

The latest Rails release also apparently broke the API for setting up functional tests. Again, I don't even know if this has been addressed, not even in edge Rails.

3. Rails API for send_file and send_data leaks memory
This is not a mongrel problem. I've seen this happen with webrick, and I bet this would happen with whatever else you happen to use with Rails, but if you try to stream data or a file with the aforementioned APIs, Rails will not release the memory it uses. The current best practice is to use the HTTP header X-Sendfile if you've got to send a static file, but you are hosed if you need to do something dynamic. Oh, and I think this issue has been around since 2006.

Now, this is just a short, 3-bullet list. I get this sneaking suspicion that if I were working on a larger project, one with more enterprise-level requirements such as Service Level Agreements on performance or speed, I suppose I would find more drawbacks to using Ruby on Rails.

Which is a disappointing, for the expressiveness of Ruby and Rail's basic approach to being a fast-track framework for web apps that babysit databases actually makes for a very highly productive environment. Don't get me wrong: I would consider Ruby on Rails for future projects, but only after carefully considering the functional requirements versus what Rails can/cannot/will not do. There's way too much hype surrounding Rails right now, and that clouds better judgment.