Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 

There's a Lot to Learn From Even Simple Puzzles

By Phil Factor,

"There's a lot to learn from even simple puzzles"

SQLServerCentral has long had a reputation for lively, egalitarian debate but there are occasions, when it's working at its very best, that are worth singling out for special mention. A short while ago, Joe Celko suggested to me that we run a competition on SQL Server Central and Simple-Talk to write the simplest, most elegant code to find all the primes below 1000. I was a bit dubious.

"What would you ever want prime numbers for?" I asked.

"Don't you just like to read them? Am I the only guy who stays awake for leap-second every year, looking at his NIST radio controlled d clock jump forward or hang back?" Joe replied

Yes, Joe, you probably are. I was rather missing the point.

"There are some check digit schemes that use primes for weights, and some numbering schemes that use prime factors so that you need (k) of (n) numbers to crack the key." he added, kindly.

His point was that here was a tricky programming problem for which there was no established SQL solution. Database developers love that sort of challenge. We duly set the Summer SQL Stumpers challenge on July 27, having no idea that, ultimately, a team of SSC members would develop algorithms that would find not only the first 1000 primes, but also the first million primes, and with routines that ran in less than 5 seconds!

This was SSC at its finest. Twenty-four pages of discussion, argument and needling fired up several programmers to come up with a solution. Pleitch was early into the race, soon to be joined by Mike Ross, Mike Dougherty, Steve Munson and Paul Ramster. Some contestants submitted multiple solutions, whereas others were content to chip in with suggested improvements to submitted contributions. It soon became apparent that the contestants felt that the challenge of finding all primes below 10000 wasn't hard enough, and went for a million instead. Tim Shay led the way with a very clever algorithm that took 11 seconds, which was later corrected by Pleitch. Tim noted,

"I spend a good part of the day working and reworking queries looking for the 'sweet spots' in performance. Looking at the results of the variations I tried, and the others posted, there's a lot to learn from even 'simple' puzzles."

Then Peso produced a 'Sieve of Atkins' solution that ran in 7 seconds. Jeff Moden's effort was stunning for the excellent level of its documentation, but others such as andriy.zabavskyy were taking up the challenge with code that was hitting similar times. Joe and I were really impressed with the entries that were able to make the Sieve of Atkins and Aristophanes solutions work quickly. They were portable too. At various points, every one of the major contestants looked be in pole position. Peso's continuous refinements brought the time down to the 5 second mark but Barry Young's final entry was awe-inspiring, and finally tipped the balance in his favor.

After executing, and timing, countless versions of code from a large number of contestants over the two weekends, we were somewhat cross-eyed, but never overwhelmed. We learned something about SQL from judging the contest. It was great work by all the 'contestants' and the 24 pages of the forum provide a fascinating insight into how a group of people can work together to solve a problem.

Total article views: 377 | Views in the last 30 days: 2
 
Related Articles
ARTICLE

Finding Primes

While it's not likely that many of you need to find prime numbers using T-SQL, it is an interesting ...

BLOG

MSSQLTips.com Kindle Contest

I'm always wary of contests to win free stuff, but the folks running MSSQLTips.com are legitimate (I...

FORUM

Performance challenge

Select prime numbers

FORUM

Creating Stored Procedure in SQL server 2000 for Printing Prime Numbers

"Trying to create a sp that prints Prime numbers upto 500"

BLOG

September Performance Contest

This month SafePeak is sponsoring a contest centered around improving performance in SQL Server. Th...

Tags
editorial    
puzzle    
sqlservercentral    
 
Contribute

Join the most active online SQL Server Community

SQL knowledge, delivered daily, free:

Email address:  

You make SSC a better place

As a member of SQLServerCentral, you get free access to loads of fresh content: thousands of articles and SQL scripts, a library of free eBooks, a weekly database news roundup, a great Q & A platform… And it’s our huge, buzzing community of SQL Server Professionals that makes it such a success.

Join us!

Steve Jones
Editor, SQLServerCentral.com

Already a member? Jump in:

Email address:   Password:   Remember me: Forgotten your password?
Steve Jones