Prime number generation with the Sieve of Eratosthenes

 

Recently I have been getting back into Project Euler problems. One of the most common things I found I needed in my PE tool bag was a method to generate primes quickly, and to determine primality quickly. During a discussion with Darrell Hawley he told me about the Sieve of Eratosthenes. The method I was taking initially to determine primality was the AKS Primality Test, the algorithm, while efficient, was a bit more in depth than I was looking for, however the Sieve of Eratosthenes was simple and quick and deterministic all important factors.

The Sieve
The sieve itself is rather simple and makes sense when you get right down to it. The sieve is based on eliminating prime factors. So, to find the primes below a number ‘n’ we’ll take the following steps in the algorithm:

1.       To start, create a list of bools of size n+1)
a.       this differs from the Wikipedia definition, it is so we can tell if a number ‘x’ is prime by accessing array[x]
b.      We need to initialize this list to be all true, start by making indices 0 and 1 false (not prime)

2.       Start at the first prime, p = 2, and that is true in the array (for prime)

3.       Repeat the following while  p^2 < n
a.       Set all multiples of p to false (since p divides hem they are not prime)
b.      Find the index of the next true value in the array, set p to this number

4.       The list you are left with is a simple prime number test now as well.
a.       If array[i] == true, i is prime, else composite

Now that we have a list of size n+1 that has been sifted for prime numbers we can determine an number of things:

  •   We know all the primes below n
  •  We know if n is prime
  •  We can quickly determine if x is prime if array[x] is true

 

On my machine (Intel C2D 2.26Ghz running Win7 32bit) I can calculate all the primes under 1,000,000,00 in only 1m15s and I use this method quite frequently in my Project Euler solutions.

 

My C# code is available as Eratosthenes.cs

 

Retrieving All Blog Posts from Kentico CMS's API

Kentico CMS is a powerful web content solution, highly customizable though a web interface. My personal favorite feature is its open API allowing you to create your own .Net based controls, modules and event handlers. The one flaw I find in the API is its poor documentation. I wanted to get all blog posts from all blogs on my test site. I quickly found the Method CMS.Blogs.BlogHelper.GetAllPosts(), however that is about all the CMS was good for, it provided no examples or more explicit details on usage other than what params the function accepted. I was left on my own to find out what each param did and what it should be.

Site Name was easy enough, what the site I created is named in the CMS Site Manager, in my case, "SRT".

The AliasPath through me off though, I had no clue what this should be, all I knew is I wanted it to return all posts. I found out that the alias path is the URL path to your blog. So http://localhost/KenticoCMS/Blogs/Blog-1.aspx has the alias of '/Blogs/Blog-1'. You can however use the wildcard '%' to return posts from all blogs, as I have.

The culture code would be useful if you are hosting a community site and would like to serve up only certain cultured items, In my test example I only have en-US cultured documents so I set this to "en-US" I also set combineWithDefaultCulture to true, this wont effect my results of retrieving my posts since the default culture on my site is "en-US"

Where and OrderBy threw me  a bit, I tried using standard SQL like "NodeID = 14" but everything seems to be throwing errors here. I will just handle any sorting/filtering I wish to do with LINQ once I have the dataset. After the error was thrown I was able to see the SQL statement created by this function, which I think I will manipulate and use on my own instead of the function in the future.  Query: SELECT * FROM View_CONTENT_Blog_Joined WHERE ((((SiteName = N'SRT') AND (Published = 1)) AND ((DocumentCulture = N'') OR (DocumentCulture = N'en-US'))) AND (NodeID = 14)) ORDER BY 1. So all of this content is coming from the View_CONTENT_Blog_Joined view.

 And finally I only wanted to aggregate published posts so I set Published = true.

 

I ended up with this: BlogHelper.GetBlogPosts("SRT", "%", "", true, "", "", true); This will return only one table named 'cms.blogpost'.

 

 A small SQL script I wrote that will give me only the informaion I need and the username/Full Name of the post creator is as follows:

SELECT FullName,UserID,UserName,NodeAliasPath,DocumentName,DocumentCreatedWhen,BlogPostBody,BlogPostSummary from KenticoCMS.dbo.CMS_User as U INNER JOIN KenticoCMS.dbo.View_CONTENT_BlogPost_Joined as BlogPost on BlogPost.DocumentCreatedByUserID = U.UserID;

You can add sort and where clauses as you see fit to filter through the mess, but I wanted everything in the database.

My New Blog Theme Released!

 

Ive finally finished my blog theme, it has some quirks, but those will be worked out.

So you probably want to get to customizing the theme for yourself right away, to make it your own. First, open your current blog while you are signed in and click on 'My Blog Dashboard'. This will take you to...your blog dashboard. From here you want to click on 'Configure' on the main tab bar.

 Once you are in the theme tab. Open the drop down menu and select Granite. You will get an alert of 'Are you sure you want to configure a different theme? Any unsaved changes made to this theme's configurable options will be lost.'. Just letting you know you cant go back to your old settings. So if you want to save your configuration of your old theme, click export on the bottom of the theme tab before you change your theme. If you chose to export your current theme config you can always go back to the way your blog used to look by selecting that theme again and importing that XML file.

Now you should be in the configurations options for the Granite theme. You should see 6 tabs, General, Header, Sidebar, Body, Custom Styles, Preview.

 

General

Changes made here will be represented all over the blog.

General Content: Changes made to these options will change the way regular (not otherwise modified) text is displayed throughout the blog.

Links: These will change the way links are colored throughout the blog. To modify links further you will have to modify the 'a' style in Custom Styles, but that will be covered later.

Background: Pretty self explanatory, the background color of the blog.


Header

These options only effect the header portion of the blog.

Header Color: This is the color of the header's background, the 'swoosh'

Text Color/Font/Font Size: All of these modify the font of the title of your blog (not the description/tagline)


Body

I think you can tell what part of the blog this will change.

The difference between Post * and List *:
 Any List option will be reflected in each blog post listed on the homepage of your blog.
 Any Post option will be reflected in each blog post in its own page.

m/.* Title/: These options will change the font of the title of the blog post.

m/.* Body/: These options will change the background of the blog post.

The text in the body of the posts is the default font specified by "General -> General Content"


Sidebar

At this point I think you can tell what is what and what it will change in the sidebar.

The one thing I do want to touch on are Sidebar Widgets. To get to them "Sidebar -> Sidebar Content -> Sidebar Widgets".

Here you can greatly customize the way your sidebar looks. I have stuck with the default, added my Xbox360 Gamer Card via an HTML IMG link using a "generic content" widget. I also added my latest twitter feed via an "RSS Reader" widget. You can use widgets to add a picture, a list (from your blog lists), RSS feeds, even videos. You can embed Widgetbox.com widgets, you can even add your own custom widgets. I suggest you play around and find a way to make the sidebar on your blog exactly how you want it. You can also style all of the individual widgets.


Custom Styles

 This section allows you to customize any CSS tags not editable with the dynamic theme UI.

For example, The 'a' tag is listed in the CSS (located at ~/Themes/Blog/Granite/Style/style.css) as :   a { text-decoration:none;  }
Say you're not happy with this, you want all of your links to be overlined and italic. Simply add this to your "Custom Style" page and it will be reflected in your blog:
a
{
    font-style:italic;
    text-decoration:overline;
}

Once you are comfortable with the way your blog looks, just click 'Save'.

If you have any issues, getting ahold of me on twitter, or via message here would be the ideal way.

 

Feel free to download and use my theme on your Community Server 2008 Blog: Granite.zip
Just unzip and place in your ~/Themes/Blogs folder

 

Multithreading in C#

Multithreading is something that seems to keep popping up on me when I am coding. My applications either need to do some crazy calculation (and not return 42) or a function will be waiting for a while before returning anything. Both of these leave my GUI locked up to the point where in Vista I get a straight black screen and the wait O, and in XP if I click on the GUI I get yelled at for touching an application that is not responding. I soon learned you can't just call all your code out of the GUI, there are these sweet abstractions like…Business Logic Layer, and Data Access layer. But that's not what this post is about. If I get my code away from the GUI but it is still called by say, a button click, the process will still not respond and the user will be unable to interact with the GUI or get any feedback about execution.

The answer to this problem is fairly simple Multithreading! There are a few different ways to go about it. The two I've used the most are what I will talk about, BackgroundWorkers and Threads.

System. ComponentModel.BackgroundWorker

BackgroundWorkers were the easiest way for me to get into multithreading an application, and they are the first way I did. BackgroundWorkers take care of all the busy work behind the scenes for you, you don't even have to know what a thread pool is, or Mutex, or Semaphore, or even apartment states. There are some setbacks though. You can't build a Ferrari with legos.

To get your BackgroundWorker going first create a BackgroundWorker object, this takes no arguments. There are a few events you will need to handle as well. DoWork is called when the BackgroundWorker is started from RunWorkerAsync; DoWork is where the meat of your processing intense code will go. If you need to pass an argument to your thread you can use RunWorkerAsync(object), the drawback is you can only send one object to the worker so you may need to write your own container class. ProgressChanged is called when ReportProgress(int) is called, one drawback of this is you can only represent completion on a 1-100 basis (progress bar) which for some applications makes sense but there is no built in method of text feedback on progress. And lastly you will need to handle RunWorkerCompleted which is called whenever the worker ends. This could be because of an error in the thread, the thread dying naturally or by calling CancelAsync.

BackgroundWorker bw = new BackgroundWorker();
bw.DoWork += new DoWorkEventHandler(bw_DoWork);
bw.ProgressChanged += new ProgressChangedEventHandler(bw_ProgressChanged);
bw.RunWorkerCompleted += new RunWorkerCompletedEventHandler(bw_RunWorkerCompleted);

In bw_DoWork any arguments passed to the worker are in DoWorkEventArgs.Argument but this example takes no arguments.

void bw_DoWork(object sender, DoWorkEventArgs e)
{
 e.Result = doMassiveWorkOMG();
 return
;

}

ProgreessChanged is simple enough. If I have some metric to determine what point in finishing I am at I can update a progress bar to show the user that progress. Inside the doMassiveWorkOMG function:

while(stillDoingEpicWork)
{
 bw.ReportProgress(percentComplete);
}

 

Simple enough right? So now when doMassiveWorkOMG is done with its work bw_RunWorkerCompleted will be called. Inside bw_RunWorkerCompleted we need to handle and errors that may have occurred (if we care) and handle what happens at the end of worker execution.

 

void bw_RunWorkerCompleted(object sender, RunWorkerCompletedEventArgs e)
{
 if
(e.Cancelled)
  throw
new OMGWhyDidYouCancelMeException();
 else
if (e.Error != null)
  throw
e;
 else

 {
  sendResultToSomeplaceAwesome(e.Result);
  giveChildrenOfTheWorldCandy();
 }
}

That's all there is to BackgroundWorkers, fairly simple and gets the job done. Now lets do the same thing in a Thread.

System.Threading.Thread

Threads have a bit more going on, and as such are a little more dificult to use but provides more. Creating threads is a little more dificult than a BackgroundWorker; a Thread takes a ThreadStart object or a ParameterizedThreadStart delegate that links to a void(void) or void(object) function respectivly. So to recreate our previous example we would create our thread like this

Thread myThread = new Thread(ThreadStart(doMassiveWorkOMG));
myThread.Name = "MassiveWorkThread";

I should mention, calling "new Thread()" is discouragedthe favored use is calling ThreadPool.QueueWorkItem.

The name only helps us while in the debugger we can see where the thread is running in the Thread Window. There are plenty of other properties to set for the thread such as Priority which sets the priority of the thread, IsBackground which sets wheather the thread runs as a background process or not, and ApartmentState which lets you set if the ApartmentState of the thread is STA or MTA.

Starting the thread is as simple as BackgroundWorker in that we simply need to call myThread.Start() which calls the function we put in our ThreadStart delegate, In this case doMassiveWorkOMG. Keeping track of progress isnt as simple as a BackgroundWorker but in much the same way we increment a progress bar we can update a status label.

public void updateWorkPercentage(int progress)
{//update the progress bar to a new value
 theBestProgressBar.Dispatcher.Invoke(DispatcherPriority.Normal, new System.Windows.Forms.MethodInvoker(delegate()
 {
  theBestProgressBar.Value = progress;
 }));
}

public void updateApplicationStatus(string message)
{//update a status label with a new message
 amazingLabel.Dispatcher.Invoke(DispatcherPriority.Normal, new System.Windows.Forms.MethodInvoker(delegate()
 {
  amazingLabel.Content = message;
 }));
}

It is worthwhile to say this method can be used in a BackgroundWorker as well. Take note that I didn't just call label.content or progressBar.value. Since this will be called on a thread that isnt the GUI thread you will end up with a sweet "The calling thread cannot access this object because a different thread owns it." error if you try to call it dirrectly. For an explination of exactly why it must be done this way look here.

Since we don't have a RunWorkerCompleted function or even the ReportProgress function in threads we have to modify the function we call (doMassiveWorkOMG) to handle updating its status, reporting its results (to the GUI/another function/etc)

void doMassiveWorkOMG()
{
 while
(stillDoingEpicWork)
 {
  updateWorkPercentage(percentComplete);
  updateApplicationStatus(currentStatusMessage);
  epicWorkResult = doMoreEpicWork();
 }
 reportWorkResult(epicWorkResult);
}

There are plenty of ways to get values back from the thread which are easily googleable and Im going to leave out here to keep the post under 90 pages.

 

When should I use what!?

Well, I cant tell you that, you know the scope of your application better than I do. But I tend to use BackgroundWorkers when I just need a simple function running in a thread. If I need the ability to pause/resume, access COM objects like the clipboard I use a Thread with an STA Apartment State (BackgroundWorkers cant do COM Interop that I have found).

In the end you can make a BackgroundWorker do almost anything you can make a Thread do with a little work. But I would rather just use the BackgroundWorker as it is and move to Threads if I need anything more.

Why I’m not buying a 3G iPhone

Since the iPhone 3G was announced at WWDC'08 it seems like it's the new phone everyone has to have. So many features have been added and hardware upgrades as well. I have a 2.5G iPhone and many people have asked me "are you going to get the new iPhone?" and being a geek, the latest and greatest toys are always the best. With the 2.5G iPhone I let my brain take back seat to my credit card, BUT Im letting my brain take over on this one and stop me from spending $299 on a white 16G iPhone 3G. There are plenty more reasons than the financial.

 

Shared features, improved localization

The 3G iPhone is getting tons of improvements. The App Store, 3G (benched at 2x current iPhones EDGE speed @ WWDC), A-GPS, Exchange support, email attachments, search contacts just to name a few.

So we've got all these great features coming to us, awesome. But all 2.5G iPhones get the firmware 2.0 upgrade free. So we all get…App Store, Exchange support, email attachments, searching contacts. That only leaves us with A-GPS and 3G for another $300! So, we have Google maps triangulation, its not that good but it gets you close, plus no turn by turn directions. However the new iPhone with its GPS wont get that either. So what exactly is the point of knowing where in a 100ft circle you are, I've always been able to get from where I am to where I am going with "current location". So I'm counting that out of the pros.

 

3G

But the iPhone 3G gets its name from ATTs 3G wireless data network, faster internet, awesome! For almost everyone, this is a huge improvement. For me, not so much, 9 months out of the year I am attending school at MTU in Houghton, Mi. We barely get coverage up there let alone are we CLOSE to 3G coverage, and until ATT bought Dobson (cellular one) we could only get Alltel or Cell One phones, any other phones would be quickly de-contracted for being out of your 'home' usage area. So 3/4ths of my year, I'm going to be in an EDGE only zone anyway. Well, Ill be in a mostly Wi-Fi zone, at home and school I have Wi-Fi and I rarely need the data network elsewhere. So why should I pay $10 more per month for the same data and losing my 200 free texts? If the U.P. of Michigan gets 3G (or good cell phone coverage period) it would be more worth it, but for email away from Wi-Fi, streaming my music from home EDGE isn't that bad. YouTube is the only app I would like to see improvement on, but I use that…once a month.

 

2.5G still kickin' strong

Those being the big reasons, there are plenty of other reasons I am, and others will stick to the iPhone 2.5G. I bought my iPhone pretty soon after it was released and got an 8Gig phone. I have about 32Gigs of music so my Zune was keeping me happy until I broke that 30Gig mark, and my iPhone doesn't even get close to holding all my music for me. There is of course the argument that I'm not going to listen to days worth of music before I have the ability to re-sync my iPhone. This is very true, but what if I sync something, and I'm in the mood for a different style, 8Gigs doesn't give me much flexibility. To solve this and not care about the size of my phone all together I use Orb on my home server. I won't get into a big post about orb, but basically it lets me stream my Movies/Recorded TV shows/Music and best yet, live TV shows from my computer to my phone (or Xbox 360, or another computer, or WM phone, or…you get the idea). Since orb automatically sets the bit rate to something that my connection can handle it allows me to stream decent quality music to my iPhone while I drive anywhere, my iPhone now has access to 2TB worth of data. Video when I'm on Wi-Fi and audio anywhere.

The only REAL reason I would get the iPhone 3G over my EDGE version is the flush headphone jack. But Im working out the details of a mod right now so hopefully I can wipe that off the pros board. Even with that, there is not enough new and amazing to make the iPhone 3G worth it.

Posted 30 June 2008 10:59 AM by cmsears | no comments
Filed under: , , , , ,
Charlie who?

I did it, I started a blog. And I’ve gotta say, these first blog posts are pretty hard. There is the tried and true “about me” blog post, and there is the tactic of just writing a blog post like it’s a second post. But the fact of the matter is, this isn’t a second blog post. There may be people reading this that have no clue who I am or why they should care. So I’m gonna have to follow the trend.

 

Who the heck is Charlie Sears?

Short answer: I am, and I’m awesome. Long answer: I’m the guy in the picture on the right. I’m a 20 year old Software Engineering major at Michigan Tech and interning at SRT Solutions. At school the majority of my code is Java/C++ and at work I do a lot of .Net development with ASP.NET and C#. When I’m just working on personal projects I use C# (and love LINQ, life without is overrated). I’m also VERY interested in learning F# (saw Dustin Campbell give a talk at CodeMash and was fascinated) and will be starting some research into that soon. I’m a pretty big video game player too, TF2, CS:S, AoC, WoW are all my addictions right now. I’ve been into computers since I was very little, though the first piece of electronics that fascinated me was the garage door opener. I’ve been coding since I was 11, C was my first language.

 

Ok, I know who you are now. Why the heck should I care?

Short answer: I’m awesome, I’ve said it before. Long answer: Get my name out there, and I’m sure there are people who care about the same things I do. Plus I have great hair, I promise not to blog TOO much about that. I’ve got my opinions, everyone does, and I think there are at least…4-5 people out there (that’s a scientific number, I promise) who care about what I have to say. I’m still in school and learning a ton so I don’t know if a lot of what I have to say will be amazing news to anyone. But I like to stay on the front of my learning and will be posting about things I find interesting. I won’t always post about software development.

 

Ok, you still have me, but I’m a bit confused about what you will talk about.

I won’t tell you I’m awesome here, you know that by now. But I’m going to talk about things that interest me and involve computers. New language features I find out about, new hardware, video games, life as an intern/student. For the most part Ill focus on things that plug in and how we make them do what we want, and how they don’t do what we want. I use computers in every part of my life to store media, for fun, for

 

More posts to come soon. Let me know what you think.