« July 2006 | Main | October 2006 »
September 17, 2006
I GOT IT!!!
2005 Triumph Daytona 650 with 1,066 miles
Posted by gravits at 11:56 AM | Comments (5) | TrackBack
September 15, 2006
Hacker's Delight
EA is having a series of internal programming contests which were open to all programmers within their company (worldwide). Because of the heavy ties with EA, the FIEA students were allowed to submit a solution to the 6th challenge of this contest. We had about a week (aside from our normal busy course-load) to work on this. Of course, with more time, I feel that we would have all been able to improve our times.
The challenge was this:
Write the fastest function possible to enumerate all possible combinations of 4 bits in a 64-bit word.
There are 635,376 possible combinations ( { 64 choose 4 } or factorial(64) / (factorial(4) * factorial(64 - 4)) )
The task is to enumerate each of these unique combinations (such as above) exactly once until all 635,376 have been written into an array. Although order does not matter, no value can be duplicated.
The naïve approach is to iterate from 0 to 0xffffffffffffffff and check each value to see if it has exactly four bits. This would take around 2,300 years on our standard dev machines. We will consider this approach to be "sub-optimal". This is one of those problems where the right approach makes all the difference...
There was no prize involved as this was just for fun (and for the students, getting noticed). So a few of us took the challenge and submitted a solution.
The results were really cool and I learned a good bit by doing this.
I ended up placing 11th in the contest, leading the FIEA submissions with 28.2336 cycles per element for a time of 4.9830ms
The Director of Technology Development has posted the results on this website below. Which includes a better description with code samples.
http://www.hejl.com/hd/6/results.html
Posted by gravits at 11:40 AM | Comments (1) | TrackBack