Sieve of Eratosthenes in PL/SQL

Yesterday I posted an Oracle SQL query that would produce primes, but it wasn't an implementation of the Sieve of Eratosthenes. Here for your viewing pleasure discomfort is a version in Oracle PL/SQL.

create or replace package josh.sieve as
   type prime_numbers is table of number;
   function calculate ( the_end number ) return prime_numbers pipelined;

create or replace package body josh.sieve as
   function calculate ( the_end number ) return prime_numbers pipelined is
      type bitbucket is table of boolean index by binary_integer;
      primes bitbucket;
      max_sqrt number :=floor(sqrt(the_end));
      i number:=3;
      j number:=1;
        pipe row(2);

        for i IN 1 .. the_end loop
          primes(i) := true;
        end loop;

        while i <= the_end loop
          if primes(i) then
            if(i<=max_sqrt) then
              while j<=the_end loop
              end loop;
            end if;

            pipe row(i);
          end if;

        end loop;

This is the ugliest one so far. It really burns my eyes!

What I liked
I was kind of pleased to see the pipe row(foo); functionality. This is very similar to yield in c# where I can just lazily return numbers as they are found instead of building up the whole list table in advance.

What I hated
There's a bunch here. First off, I tried to write this with a for loop, but there is no way to define the step value. I had to resort to using a while loop with an external counter variable. It also sucks that I have to define a custom type which is just a table of numbers. Finally, I didn't see a clean way to initialize a table with a size and default value.

Why it burns my eyes
I'm not digging that assignments have to have a colon-equal "foo := 42" operator. To the same tune as basic, I hate that blocks end with an end keyword. This is an especially big WTF when you consider that lines are terminated with semi-colons. The end result is a bunch of colon-ish punctuation littered with end keywords.

Regardless, I was pleased with the performance. Running a query like select count(1) from table(josh.sieve.calculate(1000000)); runs in about 600 milliseconds on our db machine. Not too shabby...

Prime Numbers as a SQL Query

This isn't a Sieve of Eratosthenes algorithm, but it's too good not to share it.

select r 
from (
  select rownum+1 r from dual connect by rownum < 10000
  or 0 not in(
    select mod(r,rownum+1) from dual
    connect by rownum<sqrt(r)

This is an Oracle query that will generate all of the primes up to 10,000. The query is not even close to fast, but I think it's kind of funny. It's just your typical everyday brute force method of calculating prime numbers.

Sieve of Eratosthenes in F#

Here is the third(hopefully of many) implementations of the Sieve of Eratosthenes. F# has been making a lot of noise lately, so let's see what's up.

let findPrimes max=
    seq {         
        yield 2 
        let maxSquareRoot:int = int (sqrt (float max))
        let primes = Array.create (max+1) true
        for n in 3 .. 2 .. max do             
            if primes.[n] then
                if n<=maxSquareRoot  then
                    for i in n*n..2*n..max do primes.[i] <- false
                yield n

I struggled a bit with F#. Functional languages have a different look and feel for sure. The hardest part of this was that I had several ways to implement this. I'm still not sure I chose the most optimal way since this is the slowest one so far. My first stab used lists like so:

let getPrimes max =
    let maxSquareRoot:int = int (sqrt (float max))
    let primes = Array.create (max+1) true    
    2::[3 .. 2 .. max]
    |>List.filter(fun n->
        if primes.[n] && n<=maxSquareRoot  then
            for i in n*n..2*n..max do primes.[i] <- false

This version was slower than what I ultimately wrote up top using sequences, but I really like the pipe syntax. I think both versions are very compact and easy to follow. I'm a little bummed that both versions are slower than my C# version. If anyone can help me write a better(faster) version, I'd love the help. I feel like I'm not seeing the full potential of the language and I'm missing something huge.

Sieve of Eratosthenes in VB

Here is the second (hopefully of many) implementations of the Sieve of Eratosthenes. For this one I wanted to step outside of my comfort zone and do a language which I really don't care that much for.

Function FindPrimes(ByVal max As Integer) As IList(Of Integer)
	Dim vals = New List(Of Integer)(max / (Math.Log(max) - 1.08366))
	Dim maxSquareRoot = Math.Sqrt(max)
	Dim eliminated As New BitArray(max + 1)


	For i = 3 To max Step 2
	    If (Not eliminated(i)) Then
		If (i < maxSquareRoot) Then
		    For j = i * i To max Step 2 * i
			eliminated(j) = True
		End If
	    End If

	Return vals
End Function

I won't bother explaining the algorithm or my optimizations again. What I want to talk about is the language.

This one was easy for me; after all, it's the same .NET base libraries that I'm comfortable with. At first I wrote the code with a bunch of "As Integer" garbage everywhere. Once I realized I didn't need it, I went back and scrapped a bunch of the unnecessary code to create what you see above. It looks okay to me, but I still don't like some of the noise that VB requires.

  • End Foo - This has to be my number on gripe about VB syntax. I REALLY hate the wordiness that is required to end a block of code. To my eye it destroys the balance of whitespace in the code and makes it harder to see code depth at a glance.
  • Proper Case Keywords - This is a minor thing, but I really dislike the proper cased keywords. I'm used to seeing words start with a capital letter only if it's a class or public member. For me it's still a whitespace thing and these capital letters everywhere encroach on it big time.

It's not all hate from me though. I actually enjoyed the loop syntax (minus the "Next" statement at the end). The only reason I needed the Step statement was because I was skipping numbers. The syntax just felt natural.

In the end, it's not my favorite language, but it's not my least favorite.  I would squarely place this in the "meh" category. I would write code in VB if I needed to work in a legacy environment, but for new .NET code I would still turn to C#.

As always, if you see something stupid that I did then please let me know and I'll update as necessary.

Sieve of Eratosthenes in C#

In my personal quest to find out if the programming language really matters, I present to you my first piece of code.  This is my reference implementation of Sieve of Eratosthenes in my preferred language, C#.  For this and all future language implementations, I'll put the code at the top (without comments) and then narrate my experience below.  Now, to the code!

IList<int> findPrimes(int max) {
    var vals = new List<int>((int)(max/(Math.Log(max)-1.08366)));
    var maxSquareRoot = Math.Sqrt(max);
    var eliminated = new System.Collections.BitArray(max + 1);                        


    for (int i = 3; i <= max; i+=2) {
	if (!eliminated[i]) {
	    if (i < maxSquareRoot) {
		for (int j = i * i; j <= max; j+=2*i)
		    eliminated[j] = true;
    return vals;

I started by following the wikipedia definition and then optimized from there.

Algorithm Optimizations
I cut my work in half by treating the special case of '2'. We know that 2 is prime and all even numbers thereafter are not. So, we'll add two immediately and then start looping at 3 only checking odd numbers from there forward.

After we've found a prime, we only need to eliminate numbers from it's square and forward. Let's say we want to find all prime numbers up to 100 and we've just identified 7 as a prime. Per the algorithm, I'll need to eliminate 2*7, 3*7 ,4*7, 5*7, 6*7, 7*7 ,8*7 ,9*7, 10*7 ,11*7, 12*7 ,13*7 and 14*7. None of the even multiples matter (even times an odd is always even) and none of the multiples up to the square of the prime matter since we've already done those multiples in previous loops. So really we only have to eliminate 7*7, 9*7, 11*7 and 13*7. That's a 9 fewer iterations and those savings become more fruitful the deeper you go!

The last optimization is the square root calculation and check. We know from above that we only need to start eliminating beginning at the square of the current prime. Therefore it also makes sense that we can stop even trying once we get past the to square root of the max. This saves a bunch more iterations.

Language Optimizations
Originally I had started by returning an IEnumerable<int>. I wasn't using the list you see above and instead I was using yield return i. I really like that syntax, but once I got to the version (Coming Soon!), I didn't have a direct translation for the yield keyword. I took the lazy route in the VB version and just stuffed it all into a list and returned that. To my surprise it was faster! I went back and changed the C# version above and it performed better. I'm not sure why, but I'm going with it.

What do you think that you get when do a sizeof(bool) in C#? I was surprised to find out that my trusty booleans actually take up a whole byte instead of a single bit. I speculate that there is a performance benefit that all of your types fit into a byte level offset in memory. I was thrilled to find out that we have a BitArray class that is useful for situations above when you need to store a lot of booleans and you need them to only take up a bit in memory. I'm not sure it helped anything, but I feel better knowing I'm using the least amount of memory possible. :)

Despite the fact that I know C# really well, I'm very thrilled that I was able to learn a few things about the language. Also, I'm really happy with the performance of this reference implementation. On my machine (2.66 GHz Core2 Duo and 2 GB of RAM) I can find all of the primes under 1,000,000 in 19ms. I think I've squeezed all I can out of this version. Please let me know if you see something I missed or did wrong and I'll make adjustments.

EDIT: I just added one more optimization that's worth noting. Instead of constructing my list with an empty constructor, I can save a several milliseconds off the larger sets by specifying a start size of the internal array structure behind the list. If I set this size at or slightly above the end count of prime numbers, then I avoid a lot of costly array copying as the array bounds keep getting hit. It turns out that there is quite a bit of math involved in accurately predicting the number of primes underneath a given number. I chose to cheat and just use Legendre's constant with the Prime Number Theorem which is close enough for my purposes. I can now calculate all primes under 1,000,000 in 10ms on my machine. Neat!