digitalBush

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)

	vals.Add(2)

	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
		    Next
		End If
		vals.Add(i)
	    End If
	Next

	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.

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);                        

    vals.Add(2);

    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;
	    }
	    vals.Add(i);
	}
    }
    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 VB.net 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.

Conclusion
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!

For the past 5 years I've been head down in C# and I really enjoy the language.  While I consider myself a C# developer primarily, there are plenty of other languages I use on a day to day basis.

• C# - Server side code for ASP.NET websites, internal windows forms applications, and utility applications which load and export data.
• SQL - Database querying for CRUD operations (not so much anymore, NHibernate rocks my world) and for ad-hoc reporting.
• PL/SQL - Triggers and a few user defined functions in the database.
• Javascript - Client side code to make things move and to retrieve data asynchronously.
• HTML - Web page markup.
• CSS - Web page styling and positioning.
• Regular Expressions - Pattern matching in strings.
• XSLT - Transforming XML documents into other outputs.
• XPath - Querying XML documents.
• Batch Files/Scripts - Command line programming to automate tasks, move around the file system, and do stuff to files.

There may be a few more that I'm not thinking about.  The point is that I'm not really "just a C# developer." I'm sure if you sit down and think about it, you use quite a few languages yourself. So, while I'm most comfortable in C#, I feel confident that I could bang out code in just about any language.  I'm only more comfortable with C# because it's what I've been using the most frequently as of late.

This is a personal challenge to myself.  I want to explore a few languages and see what I can learn.  The .NET (C#, VB.NET, F#) languages should be easy just because they all share the same base libraries.  Beyond that, who knows what I'll discover.

(Queue cheesy TV announcer voice)

Are you a javascript developer?

Do you graciously host demos of your stuff on your own website?

Have you been wondering where your bandwidth has gone?

Do your web logs show people hotlinking to your scripts?

If you answered yes to these questions, then boy do I have a product for you. It's hotlinkr; the revolutionary javascript hotlink countermeasure that's sure to make the web a better place!

hotlinkr is targeted towards hard working open source javascript developers who provide demos of their work only to have them hotlinked from people on other sites.  You could just pull the script and have the offending site lose the functionality your script was providing. What's the fun in that? Teach them a lesson about executing code which you don't have control over.  Replace the script with hotlinkr!

hotlinkr will deface the website in one of many ways.  What you choose to do to the offending site is entirely up to you  You could be polite and just pop up a tiny alert.  You can be sneaky and overlay a div which makes nothing on the website clickable.  You could be funny and rick roll the site. Or just let the script choose at random!  The possibilities are endless! (That is, if you consider 18 possibilities endless.)

Special thanks to:

• Jared Barboza for contributing the fail, move, spaz and vroomvroom functions as well as several IE fixes.
• Mike Alsup for contributing the rickroll function as well as being the first to try this out on a large scale.
• Cornify for supplying us with an unlimited number of unicorns and rainbows to distribute to the offending hotlinkers.

What are you waiting for?  Go check your logs and see who is hotlinking your javascript files right now!  Download now so you can take advantage of the special introductory price of free! That's right FREE! But wait there's more. If you download now within the next 5 minutes, we'll double the offer. That's right ladies and gentlemen, download within the next 5 minutes for free and you'll be able to download a 2nd copy for the same price as the first, FREE!

(Some restriction apply, see site for details.  Offer may apply to certain areas.  Authors are not responsible for the rage from website owners that you will inevitably piss off.  No animals were harmed in the making of this script.)

Unless you've been under a rock, you should know that Massachusetts elected a Republican senator to replace the late Ted Kennedy. Hopefully you also realize that the state has been democratic since the 80's. This election has disrupted the democratic majority in the senate and has essentially killed the healthcare reform bill in it's current state. The people have spoken; very few people in this country are comfortable with the current healthcare reform bill. The bill is huge; it's doubtful that any of the people voting on the bill have actually read it; and no one is sure if the country can even afford it.

courtesy of brykmantra

So, now what?
I'm personally not a fan of universal healthcare. With that said, I still feel like the healthcare system needs some reform. Actually, given that I work in the healthcare industry, I KNOW how messed up our healthcare system is. Now it's back to the drawing board.  It's definitely not time to give up on fixing healthcare.

Quit Whining!
Lawmakers, you should be thankful that this out-of-band election took place.  Now you can see just how far you've strayed from the path of real America.  We elected you to represent us, so now you had better start.  The Massachusetts election is your warning: Stop working for the special interest groups and start working for us or we'll find someone else who will.

Let's Start Small
In order to regain support for healthcare reform, the country as a whole needs to understand what's actually being done. My challenge to you is to go back and not try to reform healthcare in one failed swoop.  Write smaller bills which focus on a particular area.  Keep it small and simple so that those of us who want to know what the bill represents can actually sit down and read it in an hour or two.  My water cooler conversations should be able to talk about the "Healthcare Tort Reform" or the "Children's Healthcare Coverage" bills.  You see the difference there?  I can talk about the bill in a simple statement and know the general idea of what we're trying to do.  "Healthcare Reform" is such a broad term that you could be doing anything in that bill; it's just too hard to understand what you're doing.

What are you waiting for?  Go back to the beginning and figure out what needs fixing and fix it already.  Lawmakers, this is your job.  To everyone else, please make sure that you vote for people who you think will make a difference and will more closely represent your values.  It's time to stop voting based on party lines and start looking at the people and what they stand for.